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