Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : /*
3 : * This file is part of the LibreOffice project.
4 : *
5 : * This Source Code Form is subject to the terms of the Mozilla Public
6 : * License, v. 2.0. If a copy of the MPL was not distributed with this
7 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 : *
9 : * This file incorporates work covered by the following license notice:
10 : *
11 : * Licensed to the Apache Software Foundation (ASF) under one or more
12 : * contributor license agreements. See the NOTICE file distributed
13 : * with this work for additional information regarding copyright
14 : * ownership. The ASF licenses this file to you under the Apache
15 : * License, Version 2.0 (the "License"); you may not use this file
16 : * except in compliance with the License. You may obtain a copy of
17 : * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 : */
19 :
20 : #include "bparr.hxx"
21 :
22 : #include <limits.h>
23 : #include <string.h>
24 :
25 : /** Resize block management by this constant.
26 : As a result there are approx. 20 * MAXENTRY == 20000 entries available */
27 : const sal_uInt16 nBlockGrowSize = 20;
28 :
29 : #if OSL_DEBUG_LEVEL > 2
30 : #define CHECKIDX( p, n, i, c ) CheckIdx( p, n, i, c );
31 : void CheckIdx( BlockInfo** ppInf, sal_uInt16 nBlock, sal_uLong nSize, sal_uInt16 nCur )
32 : {
33 : assert( !nSize || nCur < nBlock ); // BigPtrArray: CurIndex invalid
34 :
35 : sal_uLong nIdx = 0;
36 : for( sal_uInt16 nCnt = 0; nCnt < nBlock; ++nCnt, ++ppInf )
37 : {
38 : nIdx += (*ppInf)->nElem;
39 : // Array with holes is not allowed
40 : assert( !nCnt || (*(ppInf-1))->nEnd + 1 == (*ppInf)->nStart );
41 : }
42 : assert(nIdx == nSize); // invalid count in nSize
43 : }
44 : #else
45 : #define CHECKIDX( p, n, i, c )
46 : #endif
47 :
48 3721 : BigPtrArray::BigPtrArray()
49 : {
50 3721 : nBlock = nCur = 0;
51 3721 : nSize = 0;
52 3721 : nMaxBlock = nBlockGrowSize;
53 3721 : ppInf = new BlockInfo* [ nMaxBlock ];
54 3721 : }
55 :
56 3713 : BigPtrArray::~BigPtrArray()
57 : {
58 3713 : if( nBlock )
59 : {
60 3707 : BlockInfo** pp = ppInf;
61 7414 : for( sal_uInt16 n = 0; n < nBlock; ++n, ++pp )
62 : {
63 3707 : delete[] (*pp)->pData;
64 3707 : delete *pp;
65 : }
66 : }
67 3713 : delete[] ppInf;
68 3713 : }
69 :
70 : // Also moving is done simply here. Optimization is useless because of the
71 : // division of this field into multiple parts.
72 80 : void BigPtrArray::Move( sal_uLong from, sal_uLong to )
73 : {
74 80 : sal_uInt16 cur = Index2Block( from );
75 80 : BlockInfo* p = ppInf[ cur ];
76 80 : ElementPtr pElem = p->pData[ from - p->nStart ];
77 80 : Insert( pElem, to ); // insert first, then delete!
78 80 : Remove( ( to < from ) ? ( from + 1 ) : from );
79 80 : }
80 :
81 : /** Apply function to every element.
82 :
83 : @param nStart First element to start with
84 : @param nEnd Last element (exclusive!)
85 : @param fn Function
86 : @param pArgs Additional arguments for <fn>
87 : */
88 93183 : void BigPtrArray::ForEach( sal_uLong nStart, sal_uLong nEnd,
89 : FnForEach fn, void* pArgs )
90 : {
91 93183 : if( nEnd > nSize )
92 0 : nEnd = nSize;
93 :
94 93183 : if( nStart < nEnd )
95 : {
96 93005 : sal_uInt16 cur = Index2Block( nStart );
97 93005 : BlockInfo** pp = ppInf + cur;
98 93005 : BlockInfo* p = *pp;
99 93005 : sal_uInt16 nElem = sal_uInt16( nStart - p->nStart );
100 93005 : ElementPtr* pElem = p->pData + nElem;
101 93005 : nElem = p->nElem - nElem;
102 : for(;;)
103 : {
104 102545 : if( !(*fn)( *pElem++, pArgs ) || ++nStart >= nEnd )
105 93005 : break;
106 :
107 : // next element
108 9540 : if( !--nElem )
109 : {
110 : // new block
111 6 : p = *++pp;
112 6 : pElem = p->pData;
113 6 : nElem = p->nElem;
114 : }
115 9540 : }
116 : }
117 93183 : }
118 :
119 2577635 : ElementPtr BigPtrArray::operator[]( sal_uLong idx ) const
120 : {
121 : assert(idx < nSize); // operator[]: Index out of bounds
122 2577635 : nCur = Index2Block( idx );
123 2577635 : BlockInfo* p = ppInf[ nCur ];
124 2577635 : return p->pData[ idx - p->nStart ];
125 : }
126 :
127 : /** Search a block at a given position */
128 2817488 : sal_uInt16 BigPtrArray::Index2Block( sal_uLong pos ) const
129 : {
130 : // last used block?
131 2817488 : BlockInfo* p = ppInf[ nCur ];
132 2817488 : if( p->nStart <= pos && p->nEnd >= pos )
133 2750547 : return nCur;
134 : // Index = 0?
135 66941 : if( !pos )
136 33015 : return 0;
137 :
138 : // following one?
139 33926 : if( nCur < ( nBlock - 1 ) )
140 : {
141 33510 : p = ppInf[ nCur+1 ];
142 33510 : if( p->nStart <= pos && p->nEnd >= pos )
143 15302 : return nCur+1;
144 : }
145 : // previous one?
146 416 : else if( pos < p->nStart && nCur > 0 )
147 : {
148 416 : p = ppInf[ nCur-1 ];
149 416 : if( p->nStart <= pos && p->nEnd >= pos )
150 393 : return nCur-1;
151 : }
152 :
153 : // binary search: always successful
154 18231 : sal_uInt16 lower = 0, upper = nBlock - 1;
155 18231 : sal_uInt16 cur = 0;
156 : for(;;)
157 : {
158 61277 : sal_uInt16 n = lower + ( upper - lower ) / 2;
159 61277 : cur = ( n == cur ) ? n+1 : n;
160 61277 : p = ppInf[ cur ];
161 61277 : if( p->nStart <= pos && p->nEnd >= pos )
162 18231 : return cur;
163 :
164 43046 : if( p->nStart > pos )
165 86 : upper = cur;
166 : else
167 42960 : lower = cur;
168 43046 : }
169 : }
170 :
171 : /** Update all index areas
172 :
173 : @param pos last correct block (starting point)
174 : */
175 12219 : void BigPtrArray::UpdIndex( sal_uInt16 pos )
176 : {
177 12219 : BlockInfo** pp = ppInf + pos;
178 12219 : sal_uLong idx = (*pp)->nEnd + 1;
179 : BlockInfo* p;
180 26318 : while( ++pos < nBlock )
181 : {
182 1880 : p = *++pp;
183 1880 : p->nStart = idx;
184 1880 : idx += p->nElem;
185 1880 : p->nEnd = idx - 1;
186 : }
187 12219 : }
188 :
189 : /** Create and insert new block
190 :
191 : Existing blocks will be moved rearward.
192 :
193 : @param pos Position at which the new block should be created.
194 : */
195 3734 : BlockInfo* BigPtrArray::InsBlock( sal_uInt16 pos )
196 : {
197 3734 : if( nBlock == nMaxBlock )
198 : {
199 : // than extend the array first
200 0 : BlockInfo** ppNew = new BlockInfo* [ nMaxBlock + nBlockGrowSize ];
201 0 : memcpy( ppNew, ppInf, nMaxBlock * sizeof( BlockInfo* ));
202 0 : delete[] ppInf;
203 0 : nMaxBlock += nBlockGrowSize;
204 0 : ppInf = ppNew;
205 : }
206 3734 : if( pos != nBlock )
207 : {
208 2 : memmove( ppInf + pos+1, ppInf + pos,
209 3 : ( nBlock - pos ) * sizeof( BlockInfo* ));
210 : }
211 3734 : ++nBlock;
212 3734 : BlockInfo* p = new BlockInfo;
213 3734 : ppInf[ pos ] = p;
214 :
215 3734 : if( pos )
216 14 : p->nStart = p->nEnd = ppInf[ pos-1 ]->nEnd + 1;
217 : else
218 3720 : p->nStart = p->nEnd = 0;
219 :
220 3734 : p->nEnd--; // no elements
221 3734 : p->nElem = 0;
222 3734 : p->pData = new ElementPtr [ MAXENTRY ];
223 3734 : p->pBigArr = this;
224 3734 : return p;
225 : }
226 :
227 14 : void BigPtrArray::BlockDel( sal_uInt16 nDel )
228 : {
229 14 : nBlock = nBlock - nDel;
230 14 : if( nMaxBlock - nBlock > nBlockGrowSize )
231 : {
232 : // than shrink array
233 0 : nDel = (( nBlock / nBlockGrowSize ) + 1 ) * nBlockGrowSize;
234 0 : BlockInfo** ppNew = new BlockInfo* [ nDel ];
235 0 : memcpy( ppNew, ppInf, nBlock * sizeof( BlockInfo* ));
236 0 : delete[] ppInf;
237 0 : ppInf = ppNew;
238 0 : nMaxBlock = nDel;
239 : }
240 14 : }
241 :
242 105363 : void BigPtrArray::Insert( const ElementPtr& rElem, sal_uLong pos )
243 : {
244 : CHECKIDX( ppInf, nBlock, nSize, nCur );
245 :
246 : BlockInfo* p;
247 : sal_uInt16 cur;
248 105363 : if( !nSize )
249 : {
250 : // special case: insert first element
251 3720 : p = InsBlock( cur = 0 );
252 : }
253 101643 : else if( pos == nSize )
254 : {
255 : // special case: insert at end
256 33473 : cur = nBlock - 1;
257 33473 : p = ppInf[ cur ];
258 33473 : if( p->nElem == MAXENTRY )
259 : // the last block is full, create a new one
260 0 : p = InsBlock( ++cur );
261 : }
262 : else
263 : {
264 : // standard case:
265 68170 : cur = Index2Block( pos );
266 68170 : p = ppInf[ cur ];
267 : }
268 :
269 105363 : if( p->nElem == MAXENTRY )
270 : {
271 : // does the last entry fit into the next block?
272 : BlockInfo* q;
273 1134 : if( cur < ( nBlock - 1 ) && ppInf[ cur+1 ]->nElem < MAXENTRY )
274 : {
275 1120 : q = ppInf[ cur+1 ];
276 1120 : if( q->nElem )
277 : {
278 1120 : int nCount = q->nElem;
279 1120 : ElementPtr *pFrom = q->pData + nCount,
280 1120 : *pTo = pFrom+1;
281 279115 : while( nCount-- )
282 276875 : ++( *--pTo = *--pFrom )->nOffset;
283 : }
284 1120 : q->nStart--;
285 1120 : q->nEnd--;
286 : }
287 : else
288 : {
289 : // If it does not fit, then insert a new block. But if there is more
290 : // than 50% space in the array then compress first.
291 14 : if( /*nBlock == nMaxBlock &&*/
292 14 : nBlock > ( nSize / ( MAXENTRY / 2 ) ) &&
293 0 : cur >= Compress() )
294 : {
295 : // Something was moved before the current position and all
296 : // pointer might be invalid. Thus restart Insert.
297 0 : Insert( rElem, pos );
298 105363 : return ;
299 : }
300 :
301 14 : q = InsBlock( cur+1 );
302 : }
303 :
304 : // entry does not fit anymore - clear space
305 1134 : ElementPtr pLast = p->pData[ MAXENTRY-1 ];
306 1134 : pLast->nOffset = 0;
307 1134 : pLast->pBlock = q;
308 :
309 1134 : q->pData[ 0 ] = pLast;
310 1134 : q->nElem++;
311 1134 : q->nEnd++;
312 :
313 1134 : p->nEnd--;
314 1134 : p->nElem--;
315 : }
316 : // now we have free space - insert
317 105363 : pos -= p->nStart;
318 : assert(pos < MAXENTRY);
319 105363 : if( pos != p->nElem )
320 : {
321 68159 : int nCount = p->nElem - sal_uInt16(pos);
322 68159 : ElementPtr *pFrom = p->pData + p->nElem;
323 68159 : ElementPtr *pTo = pFrom + 1;
324 3064555 : while( nCount-- )
325 2928237 : ++( *--pTo = *--pFrom )->nOffset;
326 : }
327 : // insert element and update indices
328 105363 : rElem->nOffset = sal_uInt16(pos);
329 105363 : rElem->pBlock = p;
330 105363 : p->pData[ pos ] = rElem;
331 105363 : p->nEnd++;
332 105363 : p->nElem++;
333 105363 : nSize++;
334 105363 : if( cur != ( nBlock - 1 ) ) UpdIndex( cur );
335 105363 : nCur = cur;
336 :
337 : CHECKIDX( ppInf, nBlock, nSize, nCur );
338 : }
339 :
340 10999 : void BigPtrArray::Remove( sal_uLong pos, sal_uLong n )
341 : {
342 : CHECKIDX( ppInf, nBlock, nSize, nCur );
343 :
344 10999 : sal_uInt16 nBlkdel = 0; // deleted blocks
345 10999 : sal_uInt16 cur = Index2Block( pos ); // current block number
346 10999 : sal_uInt16 nBlk1 = cur; // 1st treated block
347 10999 : sal_uInt16 nBlk1del = USHRT_MAX; // 1st deleted block
348 10999 : BlockInfo* p = ppInf[ cur ];
349 10999 : pos -= p->nStart;
350 :
351 10999 : sal_uLong nElem = n;
352 22012 : while( nElem )
353 : {
354 11013 : sal_uInt16 nel = p->nElem - sal_uInt16(pos);
355 11013 : if( sal_uLong(nel) > nElem )
356 10983 : nel = sal_uInt16(nElem);
357 : // move elements if needed
358 11013 : if( ( pos + nel ) < sal_uLong(p->nElem) )
359 : {
360 10983 : ElementPtr *pTo = p->pData + pos;
361 10983 : ElementPtr *pFrom = pTo + nel;
362 10983 : int nCount = p->nElem - nel - sal_uInt16(pos);
363 287477 : while( nCount-- )
364 : {
365 265511 : *pTo = *pFrom++;
366 265511 : (*pTo)->nOffset = (*pTo)->nOffset - nel;
367 265511 : ++pTo;
368 : }
369 : }
370 11013 : p->nEnd -= nel;
371 11013 : p->nElem = p->nElem - nel;
372 : // possibly delete block completely
373 11013 : if( !p->nElem )
374 : {
375 11 : delete[] p->pData;
376 11 : nBlkdel++;
377 11 : if( USHRT_MAX == nBlk1del )
378 6 : nBlk1del = cur;
379 : }
380 11013 : nElem -= nel;
381 11013 : if( !nElem )
382 10999 : break;
383 14 : p = ppInf[ ++cur ];
384 14 : pos = 0;
385 : }
386 :
387 : // update table if blocks were removed
388 10999 : if( nBlkdel )
389 : {
390 17 : for( sal_uInt16 i = nBlk1del; i < ( nBlk1del + nBlkdel ); i++ )
391 11 : delete ppInf[ i ];
392 :
393 6 : if( ( nBlk1del + nBlkdel ) < nBlock )
394 : {
395 2 : memmove( ppInf + nBlk1del, ppInf + nBlk1del + nBlkdel,
396 3 : ( nBlock - nBlkdel - nBlk1del ) * sizeof( BlockInfo* ) );
397 :
398 : // UpdateIdx updates the successor thus start before first elem
399 1 : if( !nBlk1 )
400 : {
401 1 : p = ppInf[ 0 ];
402 1 : p->nStart = 0;
403 1 : p->nEnd = p->nElem-1;
404 : }
405 : else
406 : {
407 0 : --nBlk1;
408 : }
409 : }
410 6 : BlockDel( nBlkdel ); // blocks were deleted
411 : }
412 :
413 10999 : nSize -= n;
414 10999 : if( nBlk1 != ( nBlock - 1 ) && nSize )
415 120 : UpdIndex( nBlk1 );
416 10999 : nCur = nBlk1;
417 :
418 : // call Compress() if there is more than 50% space in the array
419 10999 : if( nBlock > ( nSize / ( MAXENTRY / 2 ) ) )
420 10569 : Compress();
421 :
422 : CHECKIDX( ppInf, nBlock, nSize, nCur );
423 10999 : }
424 :
425 67599 : void BigPtrArray::Replace( sal_uLong idx, const ElementPtr& rElem)
426 : {
427 : assert(idx < nSize); // Index out of bounds
428 67599 : nCur = Index2Block( idx );
429 67599 : BlockInfo* p = ppInf[ nCur ];
430 67599 : rElem->nOffset = sal_uInt16(idx - p->nStart);
431 67599 : rElem->pBlock = p;
432 67599 : p->pData[ idx - p->nStart ] = rElem;
433 67599 : }
434 :
435 : /** Compress the array */
436 10569 : sal_uInt16 BigPtrArray::Compress( short nMax )
437 : {
438 : CHECKIDX( ppInf, nBlock, nSize, nCur );
439 :
440 : // Iterate over InfoBlock array from beginning to end. If there is a deleted
441 : // block in between so move all following ones accordingly. The pointer <pp>
442 : // represents the "old" and <qq> the "new" array.
443 10569 : BlockInfo** pp = ppInf, **qq = pp;
444 : BlockInfo* p;
445 10569 : BlockInfo* pLast(0); // last empty block
446 10569 : sal_uInt16 nLast = 0; // missing elements
447 10569 : sal_uInt16 nBlkdel = 0; // number of deleted blocks
448 10569 : sal_uInt16 nFirstChgPos = USHRT_MAX; // at which position was the 1st change?
449 :
450 : // convert fill percentage into number of remaining elements
451 10569 : nMax = MAXENTRY - (long) MAXENTRY * nMax / 100;
452 :
453 21146 : for( sal_uInt16 cur = 0; cur < nBlock; ++cur )
454 : {
455 10577 : p = *pp++;
456 10577 : sal_uInt16 n = p->nElem;
457 : // Check if a not completely full block will be ignored. This happens if
458 : // the current block would have to be split but the filling of the
459 : // inspected block is already over its threshold value. In this case we
460 : // do not fill more (it's expensive because of a double memmove() call)
461 10577 : if( nLast && ( n > nLast ) && ( nLast < nMax ) )
462 0 : nLast = 0;
463 10577 : if( nLast )
464 : {
465 8 : if( USHRT_MAX == nFirstChgPos )
466 8 : nFirstChgPos = cur;
467 :
468 : // Not full yet? Than fill up.
469 8 : if( n > nLast )
470 0 : n = nLast;
471 :
472 : // move elements from current to last block
473 8 : ElementPtr* pElem = pLast->pData + pLast->nElem;
474 8 : ElementPtr* pFrom = p->pData;
475 16 : for( sal_uInt16 nCount = n, nOff = pLast->nElem;
476 : nCount; --nCount, ++pElem )
477 : {
478 : *pElem = *pFrom++,
479 : (*pElem)->pBlock = pLast,
480 8 : (*pElem)->nOffset = nOff++;
481 : }
482 :
483 : // adjustment
484 8 : pLast->nElem = pLast->nElem + n;
485 8 : nLast = nLast - n;
486 8 : p->nElem = p->nElem - n;
487 :
488 : // Is the current block now empty as a result?
489 8 : if( !p->nElem )
490 : {
491 : // than remove
492 8 : delete[] p->pData;
493 8 : delete p, p = 0;
494 8 : ++nBlkdel;
495 : }
496 : else
497 : {
498 0 : pElem = p->pData, pFrom = pElem + n;
499 0 : int nCount = p->nElem;
500 0 : while( nCount-- )
501 : {
502 0 : *pElem = *pFrom++;
503 0 : (*pElem)->nOffset = (*pElem)->nOffset - n;
504 0 : ++pElem;
505 : }
506 : }
507 : }
508 :
509 10577 : if( p ) // BlockInfo was not deleted
510 : {
511 10569 : *qq++ = p; // adjust to correct position
512 :
513 : // keep the potentially existing last half-full block
514 10569 : if( !nLast && p->nElem < MAXENTRY )
515 : {
516 10569 : pLast = p;
517 10569 : nLast = MAXENTRY - p->nElem;
518 : }
519 : }
520 : }
521 :
522 : // if blocks were deleted shrink BlockInfo array if needed
523 10569 : if( nBlkdel )
524 8 : BlockDel( nBlkdel );
525 :
526 : // and re-index
527 10569 : p = ppInf[ 0 ];
528 10569 : p->nEnd = p->nElem - 1;
529 10569 : UpdIndex( 0 );
530 :
531 10569 : if( nCur >= nFirstChgPos )
532 0 : nCur = 0;
533 :
534 : CHECKIDX( ppInf, nBlock, nSize, nCur );
535 :
536 10569 : return nFirstChgPos;
537 : }
538 :
539 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
