xref: /aoo4110/main/sw/source/core/bastyp/bparr.cxx (revision b1cdbd2c)
1 /**************************************************************
2  *
3  * Licensed to the Apache Software Foundation (ASF) under one
4  * or more contributor license agreements.  See the NOTICE file
5  * distributed with this work for additional information
6  * regarding copyright ownership.  The ASF licenses this file
7  * to you under the Apache License, Version 2.0 (the
8  * "License"); you may not use this file except in compliance
9  * with the License.  You may obtain a copy of the License at
10  *
11  *   http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing,
14  * software distributed under the License is distributed on an
15  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16  * KIND, either express or implied.  See the License for the
17  * specific language governing permissions and limitations
18  * under the License.
19  *
20  *************************************************************/
21 
22 
23 
24 // MARKER(update_precomp.py): autogen include statement, do not remove
25 #include "precompiled_sw.hxx"
26 
27 
28 
29 #include <string.h>
30 #include <limits.h>
31 #include "bparr.hxx"
32 
33 // die Blockverwaltung waechst/schrumpft immer um 20 Bloecke, das sind dann
34 // immer ~ 20 * MAXENTRY == 20000 Eintraege
35 const sal_uInt16 nBlockGrowSize = 20;
36 
37 #ifndef DBG_UTIL
38 
39 #define CHECKIDX( p, n, i, c )
40 
41 #else
42 
43 #define CHECKIDX( p, n, i, c ) CheckIdx( p, n, i, c );
44 
CheckIdx(BlockInfo ** ppInf,sal_uInt16 nBlock,sal_uLong nSize,sal_uInt16 nCur)45 void CheckIdx( BlockInfo** ppInf, sal_uInt16 nBlock, sal_uLong nSize, sal_uInt16 nCur )
46 {
47 	DBG_ASSERT( !nSize || nCur < nBlock, "BigPtrArray: CurIndex steht falsch" );
48 
49 	sal_uLong nIdx = 0;
50 	for( sal_uInt16 nCnt = 0; nCnt < nBlock; ++nCnt, ++ppInf )
51 	{
52 		nIdx += (*ppInf)->nElem;
53 		// Array mit Luecken darf es nicht geben
54 		DBG_ASSERT( !nCnt || (*(ppInf-1))->nEnd + 1 == (*ppInf)->nStart,
55 					"BigPtrArray: Luecke in der Verwaltung!" );
56 	}
57 
58 	DBG_ASSERT( nIdx == nSize, "BigPtrArray: Anzahl ungueltig" );
59 }
60 
61 #endif
62 
63 
BigPtrArray()64 BigPtrArray::BigPtrArray()
65 {
66 	nBlock = nCur = 0;
67 	nSize = 0;
68 	nMaxBlock = nBlockGrowSize;		// == 20 * 1000 Eintraege
69 	ppInf = new BlockInfo* [ nMaxBlock ];
70 }
71 
72 
73 
~BigPtrArray()74 BigPtrArray::~BigPtrArray()
75 {
76 	if( nBlock )
77 	{
78 		BlockInfo** pp = ppInf;
79 		for( sal_uInt16 n = 0; n < nBlock; ++n, ++pp )
80 		{
81 			delete[] (*pp)->pData;
82 			delete    *pp;
83 		}
84 	}
85 	delete[] ppInf;
86 }
87 
88 // Auch der Move ist schlicht. Optimieren ist hier wg. der
89 // Stueckelung des Feldes zwecklos!
90 
Move(sal_uLong from,sal_uLong to)91 void BigPtrArray::Move( sal_uLong from, sal_uLong to )
92 {
93 	sal_uInt16 cur = Index2Block( from );
94 	BlockInfo* p = ppInf[ cur ];
95 	ElementPtr pElem = p->pData[ from - p->nStart ];
96 	Insert( pElem, to );			// erst einfuegen, dann loeschen !!!!
97 	Remove( ( to < from ) ? ( from + 1 ) : from );
98 }
99 
100 // das Ende ist EXCLUSIV
101 
102 
ForEach(sal_uLong nStart,sal_uLong nEnd,FnForEach fn,void * pArgs)103 void BigPtrArray::ForEach( sal_uLong nStart, sal_uLong nEnd,
104 							FnForEach fn, void* pArgs )
105 {
106 	if( nEnd > nSize )
107 		nEnd = nSize;
108 
109 	if( nStart < nEnd )
110 	{
111 		sal_uInt16 cur = Index2Block( nStart );
112 		BlockInfo** pp = ppInf + cur;
113 		BlockInfo* p = *pp;
114 		sal_uInt16 nElem = sal_uInt16( nStart - p->nStart );
115 		ElementPtr* pElem = p->pData + nElem;
116 		nElem = p->nElem - nElem;
117 		for(;;)
118 		{
119 			if( !(*fn)( *pElem++, pArgs ) || ++nStart >= nEnd )
120 				break;
121 
122 			// naechstes Element
123 			if( !--nElem )
124 			{
125 				// neuer Block
126 				p = *++pp;
127 				pElem = p->pData;
128 				nElem = p->nElem;
129 			}
130 		}
131 	}
132 }
133 
134 
operator [](sal_uLong idx) const135 ElementPtr BigPtrArray::operator[]( sal_uLong idx ) const
136 {
137 	// weil die Funktion eben doch nicht const ist:
138 	DBG_ASSERT( idx < nSize, "operator[]: Index aussserhalb" );
139 	BigPtrArray* pThis = (BigPtrArray*) this;
140 	sal_uInt16 cur = Index2Block( idx );
141 	BlockInfo* p = ppInf[ cur ];
142 	pThis->nCur = cur;
143 	return p->pData[ idx - p->nStart ];
144 }
145 
146 ///////////////////////////////////////////////////////////////////////////
147 
148 // private Methoden
149 
150 // Suchen des Blocks einer bestimmten Position
151 // Algorithmus:
152 // 1. Test, ob der letzte Block der gesuchte Block ist
153 // 2. Sonderfall: Index = 0?
154 // 3. Test der Nachbarbloecke
155 
156 // 4. Binaere Suche
157 
158 
159 
Index2Block(sal_uLong pos) const160 sal_uInt16 BigPtrArray::Index2Block( sal_uLong pos ) const
161 {
162 	// zuletzt verwendeter Block?
163 	BlockInfo* p = ppInf[ nCur ];
164 	if( p->nStart <= pos && p->nEnd >= pos )
165 		return nCur;
166 	// Index = 0?
167 	if( !pos )
168 		return 0;
169 	// Folgeblock?
170 	if( nCur < ( nBlock - 1 ) )
171 	{
172 		p = ppInf[ nCur+1 ];
173 		if( p->nStart <= pos && p->nEnd >= pos )
174 			return nCur+1;
175 	}
176 	// vorangehender Block?
177 	else if( pos < p->nStart && nCur > 0 )
178 	{
179 		p = ppInf[ nCur-1 ];
180 		if( p->nStart <= pos && p->nEnd >= pos )
181 			return nCur-1;
182 	}
183 	// Binaere Suche:
184 	// Diese fuehrt immer zum Erfolg
185 	sal_uInt16 lower = 0, upper = nBlock - 1;
186 	sal_uInt16 cur = 0;
187 	for(;;)
188 	{
189 		sal_uInt16 n = lower + ( upper - lower ) / 2;
190 		cur = ( n == cur ) ? n+1 : n;
191 		p = ppInf[ cur ];
192 		if( p->nStart <= pos && p->nEnd >= pos )
193 			return cur;
194 		if( p->nStart > pos )
195 			upper = cur;
196 		else
197 			lower = cur;
198 	}
199 }
200 
201 
202 // Update aller Indexbereiche ab einer bestimmten Position
203 
204 // pos bezeichnet den letzten korrekten Block
205 
UpdIndex(sal_uInt16 pos)206 void BigPtrArray::UpdIndex( sal_uInt16 pos )
207 {
208 	BlockInfo** pp = ppInf + pos;
209 	sal_uLong idx = (*pp)->nEnd + 1;
210 	BlockInfo* p;
211 	while( ++pos < nBlock )
212 	{
213 		p = *++pp;
214 		p->nStart = idx;
215 		idx       += p->nElem;
216 		p->nEnd   = idx - 1;
217 	}
218 }
219 
220 // Einrichten eines neuen Blocks an einer bestimmten Position
221 
222 // Vorhandene Blocks werden nach hinten verschoben
223 
224 
225 
InsBlock(sal_uInt16 pos)226 BlockInfo* BigPtrArray::InsBlock( sal_uInt16 pos )
227 {
228 	if( nBlock == nMaxBlock )
229 	{
230 		// dann sollte wir mal das Array erweitern
231 		BlockInfo** ppNew = new BlockInfo* [ nMaxBlock + nBlockGrowSize ];
232 		memcpy( ppNew, ppInf, nMaxBlock * sizeof( BlockInfo* ));
233 		delete[] ppInf;
234 		nMaxBlock += nBlockGrowSize;
235 		ppInf = ppNew;
236 	}
237 	if( pos != nBlock )
238 		memmove( ppInf + pos+1, ppInf + pos ,
239 				 ( nBlock - pos ) * sizeof (BlockInfo*) );
240 	++nBlock;
241 	BlockInfo* p = new BlockInfo;
242 	ppInf[ pos ] = p;
243 
244 	if( pos )
245 		p->nStart = p->nEnd = ppInf[ pos-1 ]->nEnd + 1;
246 	else
247 		p->nStart = p->nEnd = 0;
248 	p->nEnd--;	// keine Elemente
249 	p->nElem = 0;
250 	p->pData = new ElementPtr [ MAXENTRY ];
251 	p->pBigArr = this;
252 	return p;
253 }
254 
BlockDel(sal_uInt16 nDel)255 void BigPtrArray::BlockDel( sal_uInt16 nDel )
256 {
257 	nBlock = nBlock - nDel;
258 	if( nMaxBlock - nBlock > nBlockGrowSize )
259 	{
260 		// dann koennen wir wieder schrumpfen
261 		nDel = (( nBlock / nBlockGrowSize ) + 1 ) * nBlockGrowSize;
262 		BlockInfo** ppNew = new BlockInfo* [ nDel ];
263 		memcpy( ppNew, ppInf, nBlock * sizeof( BlockInfo* ));
264 		delete[] ppInf;
265 		ppInf = ppNew;
266 		nMaxBlock = nDel;
267 	}
268 }
269 
270 
Insert(const ElementPtr & rElem,sal_uLong pos)271 void BigPtrArray::Insert( const ElementPtr& rElem, sal_uLong pos )
272 {
273 	CHECKIDX( ppInf, nBlock, nSize, nCur );
274 
275 	BlockInfo* p;
276 	sal_uInt16 cur;
277 	if( !nSize )
278 		// Sonderfall: erstes Element einfuegen
279 		p = InsBlock( cur = 0 );
280 	else if( pos == nSize )
281 	{
282 		// Sonderfall: Einfuegen am Ende
283 		cur = nBlock - 1;
284 		p = ppInf[ cur ];
285 		if( p->nElem == MAXENTRY )
286 			// Der letzte Block ist voll, neuen anlegen
287 			p = InsBlock( ++cur );
288 	}
289 	else
290 	{
291 		// Standardfall:
292 		cur = Index2Block( pos );
293 		p = ppInf[ cur ];
294 	}
295 	if( p->nElem == MAXENTRY )
296 	{
297 		// passt der letzte Eintrag in den naechsten Block?
298 		BlockInfo* q;
299 		if( cur < ( nBlock - 1 ) && ppInf[ cur+1 ]->nElem < MAXENTRY )
300 		{
301 			q = ppInf[ cur+1 ];
302 			if( q->nElem )
303 			{
304 				int nCount = q->nElem;
305 				ElementPtr *pFrom = q->pData + nCount,
306 									*pTo = pFrom+1;
307 				while( nCount-- )
308 					++( *--pTo = *--pFrom )->nOffset;
309 			}
310 			q->nStart--;
311 			q->nEnd--;
312 		}
313 		else
314 		{
315 			// Wenn er auch nicht in den Folgeblock passt, muss ein
316 			// neuer Block eingefuegt werden
317 			// erst mal bei Bedarf komprimieren
318 
319 			// wenn mehr als 50% "Luft" im Array ist, dann sollte man mal das
320 			// Compress aufrufen
321 			if( /*nBlock == nMaxBlock &&*/
322 				nBlock > ( nSize / ( MAXENTRY / 2 ) ) &&
323 				cur >= Compress() )
324 			{
325 				// es wurde vor der akt. Pos etwas verschoben und alle
326 				// Pointer koennen ungueltig sein. Also das Insert
327 				// nochmals aufsetzen
328 				Insert( rElem, pos );
329 				return ;
330 			}
331 
332 			q = InsBlock( cur+1 );
333 		}
334 
335 		// Eintrag passt nicht mehr. Dann muss Platz gemacht werden
336 		ElementPtr pLast = p->pData[ MAXENTRY-1 ];
337 		pLast->nOffset = 0;
338 		pLast->pBlock = q;
339 
340 		q->pData[ 0 ] = pLast;
341 		q->nElem++;
342 		q->nEnd++;
343 
344 		p->nEnd--;
345 		p->nElem--;
346 	}
347 	// Nun haben wir einen freien Block am Wickel: eintragen
348 	pos -= p->nStart;
349 	DBG_ASSERT( pos < MAXENTRY, "falsche Pos" );
350 	if( pos != p->nElem )
351 	{
352 		int nCount = p->nElem - sal_uInt16(pos);
353 		ElementPtr *pFrom = p->pData + p->nElem,
354 							*pTo = pFrom + 1;
355 		while( nCount-- )
356 			++( *--pTo = *--pFrom )->nOffset;
357 	}
358 	// Element eintragen und Indexe updaten
359 	((ElementPtr&)rElem)->nOffset = sal_uInt16(pos);
360 	((ElementPtr&)rElem)->pBlock = p;
361 	p->pData[ pos ] = rElem;
362 	p->nEnd++;
363 	p->nElem++;
364 	nSize++;
365 	if( cur != ( nBlock - 1 ) ) UpdIndex( cur );
366 	nCur = cur;
367 
368 	CHECKIDX( ppInf, nBlock, nSize, nCur );
369 }
370 
Remove(sal_uLong pos,sal_uLong n)371 void BigPtrArray::Remove( sal_uLong pos, sal_uLong n )
372 {
373 	CHECKIDX( ppInf, nBlock, nSize, nCur );
374 
375 	sal_uInt16 nBlkdel = 0;					// entfernte Bloecke
376 	sal_uInt16 cur = Index2Block( pos );	// aktuelle Blocknr
377 	sal_uInt16 nBlk1 = cur;                 // 1. behandelter Block
378 	sal_uInt16 nBlk1del = USHRT_MAX;		// 1. entfernter Block
379 	BlockInfo* p = ppInf[ cur ];
380 	pos -= p->nStart;
381 	sal_uLong nElem = n;
382 	while( nElem )
383 	{
384 		sal_uInt16 nel = p->nElem - sal_uInt16(pos);
385 		if( sal_uLong(nel) > nElem )
386 			nel = sal_uInt16(nElem);
387 		// Eventuell Elemente verschieben
388 		if( ( pos + nel ) < sal_uLong(p->nElem) )
389 		{
390 			ElementPtr *pTo = p->pData + pos,
391 								*pFrom = pTo + nel;
392 			int nCount = p->nElem - nel - sal_uInt16(pos);
393 			while( nCount-- )
394 			{
395                 *pTo = *pFrom++;
396                 (*pTo)->nOffset = (*pTo)->nOffset - nel;
397                 ++pTo;
398 			}
399 		}
400 		p->nEnd -= nel;
401 		p->nElem = p->nElem - nel;
402 		if( !p->nElem )
403 		{
404 			// eventuell Block ganz entfernen
405 			delete[] p->pData;
406 			nBlkdel++;
407 			if( USHRT_MAX == nBlk1del )
408 				nBlk1del = cur;
409 		}
410 		nElem -= nel;
411 		if( !nElem )
412 			break;
413 		p = ppInf[ ++cur ];
414 		pos = 0;
415 	}
416 	// Am Ende die Tabelle updaten, falls Bloecke geloescht waren
417 	if( nBlkdel )
418 	{
419 		// loeschen sollte man immer !!
420 		for( sal_uInt16 i = nBlk1del; i < ( nBlk1del + nBlkdel ); i++ )
421 			delete ppInf[ i ];
422 
423 		if( ( nBlk1del + nBlkdel ) < nBlock )
424 		{
425 			memmove( ppInf + nBlk1del, ppInf + nBlk1del + nBlkdel,
426 					 ( nBlock - nBlkdel - nBlk1del ) * sizeof( BlockInfo* ) );
427 
428 			// JP 19.07.95: nicht den ersten behandelten, sondern den davor!!
429 			//				UpdateIdx updatet nur alle Nachfolgende!!
430 			if( !nBlk1 )
431 			{
432 				p = ppInf[ 0 ];
433 				p->nStart = 0;
434 				p->nEnd = p->nElem-1;
435 			}
436 			else
437 				--nBlk1;
438 		}
439 		BlockDel( nBlkdel );			// es wurden Bloecke geloescht
440 	}
441 
442 	nSize -= n;
443 	if( nBlk1 != ( nBlock - 1 ) && nSize )
444 		UpdIndex( nBlk1 );
445 	nCur = nBlk1;
446 
447 	// wenn mehr als 50% "Luft" im Array ist, dann sollte man mal das
448 	// Compress aufrufen
449 	if( nBlock > ( nSize / ( MAXENTRY / 2 ) ) )
450 		Compress();
451 
452 	CHECKIDX( ppInf, nBlock, nSize, nCur );
453 }
454 
455 
Replace(sal_uLong idx,const ElementPtr & rElem)456 void BigPtrArray::Replace( sal_uLong idx, const ElementPtr& rElem)
457 {
458 	// weil die Funktion eben doch nicht const ist:
459 	DBG_ASSERT( idx < nSize, "Set: Index aussserhalb" );
460 	BigPtrArray* pThis = (BigPtrArray*) this;
461 	sal_uInt16 cur = Index2Block( idx );
462 	BlockInfo* p = ppInf[ cur ];
463 	pThis->nCur = cur;
464 	((ElementPtr&)rElem)->nOffset = sal_uInt16(idx - p->nStart);
465 	((ElementPtr&)rElem)->pBlock = p;
466 	p->pData[ idx - p->nStart ] = rElem;
467 }
468 
469 
470 // Array komprimieren
471 
Compress(short nMax)472 sal_uInt16 BigPtrArray::Compress( short nMax )
473 {
474 	CHECKIDX( ppInf, nBlock, nSize, nCur );
475 
476 	// Es wird von vorne nach hinten ueber das InfoBlock Array iteriert.
477 	// Wenn zwischen durch Block gel�scht werden, dann mussen alle
478 	// nachfolgenden verschoben werden. Dazu werden die Pointer pp und qq
479 	// benutzt; wobei pp das "alte" Array, qq das "neue" Array ist.
480 	BlockInfo** pp = ppInf, **qq = pp;
481 	BlockInfo* p;
482 	BlockInfo* pLast(0);				// letzter nicht voller Block
483 	sal_uInt16 nLast = 0;					// fehlende Elemente
484 	sal_uInt16 nBlkdel = 0;					// Anzahl der geloeschte Bloecke
485 	sal_uInt16 nFirstChgPos = USHRT_MAX;	// ab welcher Pos gab es die 1. Aenderung?
486 
487 	// von Fuell-Prozenten auf uebrige Eintrage umrechnen
488 	nMax = MAXENTRY - (long) MAXENTRY * nMax / 100;
489 
490 	for( sal_uInt16 cur = 0; cur < nBlock; ++cur )
491 	{
492 		p = *pp++;
493 		sal_uInt16 n = p->nElem;
494 		// Testen, ob der noch nicht volle Block so gelassen wird
495 		// dies ist der Fall, wenn der aktuelle Block gesplittet
496 		// werden muesste, der noch nicht volle Block aber bereits
497 		// ueber dem uebergebenen Break-Wert voll ist. In diesem
498 		// Fall wird von einer weiteren Fuellung (die ja wegen dem
499 		// zweifachen memmove() zeitaufwendig ist) abgesehen.
500 		if( nLast && ( n > nLast ) && ( nLast < nMax ) )
501 			nLast = 0;
502 		if( nLast )
503 		{
504 			if( USHRT_MAX == nFirstChgPos )
505 				nFirstChgPos = cur;
506 
507 			// ein nicht voller Block vorhanden: auffuellen
508 			if( n > nLast )
509 				n = nLast;
510 
511 			// Elemente uebertragen, vom akt. in den letzten
512 			ElementPtr* pElem = pLast->pData + pLast->nElem;
513 			ElementPtr* pFrom = p->pData;
514 			for( sal_uInt16 nCount = n, nOff = pLast->nElem;
515 							nCount; --nCount, ++pElem )
516 				*pElem = *pFrom++,
517 					(*pElem)->pBlock = pLast,
518 					(*pElem)->nOffset = nOff++;
519 
520 			// korrigieren
521 			pLast->nElem = pLast->nElem + n;
522 			nLast = nLast - n;
523 			p->nElem = p->nElem - n;
524 
525 			// Ist der aktuelle Block dadurch leer geworden?
526 			if( !p->nElem )
527 			{
528 				// dann kann der entfernt werden
529 				delete[] p->pData;
530 				delete   p, p = 0;
531 				++nBlkdel;
532 			}
533 			else
534 			{
535 				pElem = p->pData, pFrom = pElem + n;
536 				int nCount = p->nElem;
537 				while( nCount-- )
538 				{
539 					*pElem = *pFrom++;
540 					(*pElem)->nOffset = (*pElem)->nOffset - n;
541 					++pElem;
542 				}
543 			}
544 		}
545 
546 		if( p )		// die Blockinfo wurde nicht geloescht
547 		{
548 			*qq++ = p;		// dann setze sie an die richtige neue Position
549 
550 			// eventuell den letzten halbvollen Block festhalten
551 			if( !nLast && p->nElem < MAXENTRY )
552 			{
553 				pLast = p;
554 				nLast = MAXENTRY - p->nElem;
555 			}
556 		}
557 	}
558 
559 	// Bloecke geloescht wurden, ggfs. das BlockInfo Array verkuerzen
560 	if( nBlkdel )
561 		BlockDel( nBlkdel );
562 
563 	// Und neu durchindizieren
564 	p = ppInf[ 0 ];
565 	p->nEnd = p->nElem - 1;
566 	UpdIndex( 0 );
567 
568 	if( nCur >= nFirstChgPos )
569 		nCur = 0;
570 
571 	CHECKIDX( ppInf, nBlock, nSize, nCur );
572 
573 	return nFirstChgPos;
574 }
575 
576 
577