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 569 : BigPtrArray::BigPtrArray()
49 : {
50 569 : nBlock = nCur = 0;
51 569 : nSize = 0;
52 569 : nMaxBlock = nBlockGrowSize;
53 569 : ppInf = new BlockInfo* [ nMaxBlock ];
54 569 : }
55 :
56 221 : BigPtrArray::~BigPtrArray()
57 : {
58 221 : if( nBlock )
59 : {
60 215 : BlockInfo** pp = ppInf;
61 430 : for( sal_uInt16 n = 0; n < nBlock; ++n, ++pp )
62 : {
63 215 : delete[] (*pp)->pData;
64 215 : delete *pp;
65 : }
66 : }
67 221 : delete[] ppInf;
68 221 : }
69 :
70 : // Also moving is done simply here. Optimization is useless because of the
71 : // division of this field into multiple parts.
72 18 : void BigPtrArray::Move( sal_uLong from, sal_uLong to )
73 : {
74 18 : sal_uInt16 cur = Index2Block( from );
75 18 : BlockInfo* p = ppInf[ cur ];
76 18 : ElementPtr pElem = p->pData[ from - p->nStart ];
77 18 : Insert( pElem, to ); // insert first, then delete!
78 18 : Remove( ( to < from ) ? ( from + 1 ) : from );
79 18 : }
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 10331 : void BigPtrArray::ForEach( sal_uLong nStart, sal_uLong nEnd,
89 : FnForEach fn, void* pArgs )
90 : {
91 10331 : if( nEnd > nSize )
92 0 : nEnd = nSize;
93 :
94 10331 : if( nStart < nEnd )
95 : {
96 10312 : sal_uInt16 cur = Index2Block( nStart );
97 10312 : BlockInfo** pp = ppInf + cur;
98 10312 : BlockInfo* p = *pp;
99 10312 : sal_uInt16 nElem = sal_uInt16( nStart - p->nStart );
100 10312 : ElementPtr* pElem = p->pData + nElem;
101 10312 : nElem = p->nElem - nElem;
102 1897 : for(;;)
103 : {
104 12209 : if( !(*fn)( *pElem++, pArgs ) || ++nStart >= nEnd )
105 10312 : break;
106 :
107 : // next element
108 1897 : if( !--nElem )
109 : {
110 : // new block
111 0 : p = *++pp;
112 0 : pElem = p->pData;
113 0 : nElem = p->nElem;
114 : }
115 : }
116 : }
117 10331 : }
118 :
119 328305 : ElementPtr BigPtrArray::operator[]( sal_uLong idx ) const
120 : {
121 : assert(idx < nSize); // operator[]: Index out of bounds
122 328305 : nCur = Index2Block( idx );
123 328305 : BlockInfo* p = ppInf[ nCur ];
124 328305 : return p->pData[ idx - p->nStart ];
125 : }
126 :
127 : /** Search a block at a given position */
128 353147 : sal_uInt16 BigPtrArray::Index2Block( sal_uLong pos ) const
129 : {
130 : // last used block?
131 353147 : BlockInfo* p = ppInf[ nCur ];
132 353147 : if( p->nStart <= pos && p->nEnd >= pos )
133 352341 : return nCur;
134 : // Index = 0?
135 806 : if( !pos )
136 392 : return 0;
137 :
138 : // following one?
139 414 : if( nCur < ( nBlock - 1 ) )
140 : {
141 404 : p = ppInf[ nCur+1 ];
142 404 : if( p->nStart <= pos && p->nEnd >= pos )
143 404 : return nCur+1;
144 : }
145 : // previous one?
146 10 : else if( pos < p->nStart && nCur > 0 )
147 : {
148 10 : p = ppInf[ nCur-1 ];
149 10 : if( p->nStart <= pos && p->nEnd >= pos )
150 10 : return nCur-1;
151 : }
152 :
153 : // binary search: always successful
154 0 : sal_uInt16 lower = 0, upper = nBlock - 1;
155 0 : sal_uInt16 cur = 0;
156 0 : for(;;)
157 : {
158 0 : sal_uInt16 n = lower + ( upper - lower ) / 2;
159 0 : cur = ( n == cur ) ? n+1 : n;
160 0 : p = ppInf[ cur ];
161 0 : if( p->nStart <= pos && p->nEnd >= pos )
162 0 : return cur;
163 :
164 0 : if( p->nStart > pos )
165 0 : upper = cur;
166 : else
167 0 : lower = cur;
168 : }
169 : }
170 :
171 : /** Update all index areas
172 :
173 : @param pos last correct block (starting point)
174 : */
175 1045 : void BigPtrArray::UpdIndex( sal_uInt16 pos )
176 : {
177 1045 : BlockInfo** pp = ppInf + pos;
178 1045 : sal_uLong idx = (*pp)->nEnd + 1;
179 : BlockInfo* p;
180 2142 : while( ++pos < nBlock )
181 : {
182 52 : p = *++pp;
183 52 : p->nStart = idx;
184 52 : idx += p->nElem;
185 52 : p->nEnd = idx - 1;
186 : }
187 1045 : }
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 569 : BlockInfo* BigPtrArray::InsBlock( sal_uInt16 pos )
196 : {
197 569 : 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 569 : if( pos != nBlock )
207 : {
208 0 : memmove( ppInf + pos+1, ppInf + pos,
209 0 : ( nBlock - pos ) * sizeof( BlockInfo* ));
210 : }
211 569 : ++nBlock;
212 569 : BlockInfo* p = new BlockInfo;
213 569 : ppInf[ pos ] = p;
214 :
215 569 : if( pos )
216 1 : p->nStart = p->nEnd = ppInf[ pos-1 ]->nEnd + 1;
217 : else
218 568 : p->nStart = p->nEnd = 0;
219 :
220 569 : p->nEnd--; // no elements
221 569 : p->nElem = 0;
222 569 : p->pData = new ElementPtr [ MAXENTRY ];
223 569 : p->pBigArr = this;
224 569 : return p;
225 : }
226 :
227 6 : void BigPtrArray::BlockDel( sal_uInt16 nDel )
228 : {
229 6 : nBlock = nBlock - nDel;
230 6 : 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 6 : }
241 :
242 13508 : 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 13508 : if( !nSize )
249 : {
250 : // special case: insert first element
251 568 : p = InsBlock( cur = 0 );
252 : }
253 12940 : else if( pos == nSize )
254 : {
255 : // special case: insert at end
256 5105 : cur = nBlock - 1;
257 5105 : p = ppInf[ cur ];
258 5105 : 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 7835 : cur = Index2Block( pos );
266 7835 : p = ppInf[ cur ];
267 : }
268 :
269 13508 : if( p->nElem == MAXENTRY )
270 : {
271 : // does the last entry fit into the next block?
272 : BlockInfo* q;
273 46 : if( cur < ( nBlock - 1 ) && ppInf[ cur+1 ]->nElem < MAXENTRY )
274 : {
275 45 : q = ppInf[ cur+1 ];
276 45 : if( q->nElem )
277 : {
278 45 : int nCount = q->nElem;
279 45 : ElementPtr *pFrom = q->pData + nCount,
280 45 : *pTo = pFrom+1;
281 2802 : while( nCount-- )
282 2712 : ++( *--pTo = *--pFrom )->nOffset;
283 : }
284 45 : q->nStart--;
285 45 : 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 1 : if( /*nBlock == nMaxBlock &&*/
292 : 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 13508 : return ;
299 : }
300 :
301 1 : q = InsBlock( cur+1 );
302 : }
303 :
304 : // entry does not fit anymore - clear space
305 46 : ElementPtr pLast = p->pData[ MAXENTRY-1 ];
306 46 : pLast->nOffset = 0;
307 46 : pLast->pBlock = q;
308 :
309 46 : q->pData[ 0 ] = pLast;
310 46 : q->nElem++;
311 46 : q->nEnd++;
312 :
313 46 : p->nEnd--;
314 46 : p->nElem--;
315 : }
316 : // now we have free space - insert
317 13508 : pos -= p->nStart;
318 : assert(pos < MAXENTRY);
319 13508 : if( pos != p->nElem )
320 : {
321 7834 : int nCount = p->nElem - sal_uInt16(pos);
322 7834 : ElementPtr *pFrom = p->pData + p->nElem;
323 7834 : ElementPtr *pTo = pFrom + 1;
324 113748 : while( nCount-- )
325 98080 : ++( *--pTo = *--pFrom )->nOffset;
326 : }
327 : // insert element and update indices
328 13508 : rElem->nOffset = sal_uInt16(pos);
329 13508 : rElem->pBlock = p;
330 13508 : p->pData[ pos ] = rElem;
331 13508 : p->nEnd++;
332 13508 : p->nElem++;
333 13508 : nSize++;
334 13508 : if( cur != ( nBlock - 1 ) ) UpdIndex( cur );
335 13508 : nCur = cur;
336 :
337 : CHECKIDX( ppInf, nBlock, nSize, nCur );
338 : }
339 :
340 1002 : void BigPtrArray::Remove( sal_uLong pos, sal_uLong n )
341 : {
342 : CHECKIDX( ppInf, nBlock, nSize, nCur );
343 :
344 1002 : sal_uInt16 nBlkdel = 0; // deleted blocks
345 1002 : sal_uInt16 cur = Index2Block( pos ); // current block number
346 1002 : sal_uInt16 nBlk1 = cur; // 1st treated block
347 1002 : sal_uInt16 nBlk1del = USHRT_MAX; // 1st deleted block
348 1002 : BlockInfo* p = ppInf[ cur ];
349 1002 : pos -= p->nStart;
350 :
351 1002 : sal_uLong nElem = n;
352 2005 : while( nElem )
353 : {
354 1003 : sal_uInt16 nel = p->nElem - sal_uInt16(pos);
355 1003 : if( sal_uLong(nel) > nElem )
356 986 : nel = sal_uInt16(nElem);
357 : // move elements if needed
358 1003 : if( ( pos + nel ) < sal_uLong(p->nElem) )
359 : {
360 986 : ElementPtr *pTo = p->pData + pos;
361 986 : ElementPtr *pFrom = pTo + nel;
362 986 : int nCount = p->nElem - nel - sal_uInt16(pos);
363 12025 : while( nCount-- )
364 : {
365 10053 : *pTo = *pFrom++;
366 10053 : (*pTo)->nOffset = (*pTo)->nOffset - nel;
367 10053 : ++pTo;
368 : }
369 : }
370 1003 : p->nEnd -= nel;
371 1003 : p->nElem = p->nElem - nel;
372 : // possibly delete block completely
373 1003 : if( !p->nElem )
374 : {
375 5 : delete[] p->pData;
376 5 : nBlkdel++;
377 5 : if( USHRT_MAX == nBlk1del )
378 5 : nBlk1del = cur;
379 : }
380 1003 : nElem -= nel;
381 1003 : if( !nElem )
382 1002 : break;
383 1 : p = ppInf[ ++cur ];
384 1 : pos = 0;
385 : }
386 :
387 : // update table if blocks were removed
388 1002 : if( nBlkdel )
389 : {
390 10 : for( sal_uInt16 i = nBlk1del; i < ( nBlk1del + nBlkdel ); i++ )
391 5 : delete ppInf[ i ];
392 :
393 5 : if( ( nBlk1del + nBlkdel ) < nBlock )
394 : {
395 0 : memmove( ppInf + nBlk1del, ppInf + nBlk1del + nBlkdel,
396 0 : ( nBlock - nBlkdel - nBlk1del ) * sizeof( BlockInfo* ) );
397 :
398 : // UpdateIdx updates the successor thus start before first elem
399 0 : if( !nBlk1 )
400 : {
401 0 : p = ppInf[ 0 ];
402 0 : p->nStart = 0;
403 0 : p->nEnd = p->nElem-1;
404 : }
405 : else
406 : {
407 0 : --nBlk1;
408 : }
409 : }
410 5 : BlockDel( nBlkdel ); // blocks were deleted
411 : }
412 :
413 1002 : nSize -= n;
414 1002 : if( nBlk1 != ( nBlock - 1 ) && nSize )
415 4 : UpdIndex( nBlk1 );
416 1002 : nCur = nBlk1;
417 :
418 : // call Compress() if there is more than 50% space in the array
419 1002 : if( nBlock > ( nSize / ( MAXENTRY / 2 ) ) )
420 993 : Compress();
421 :
422 : CHECKIDX( ppInf, nBlock, nSize, nCur );
423 1002 : }
424 :
425 5675 : void BigPtrArray::Replace( sal_uLong idx, const ElementPtr& rElem)
426 : {
427 : assert(idx < nSize); // Index out of bounds
428 5675 : nCur = Index2Block( idx );
429 5675 : BlockInfo* p = ppInf[ nCur ];
430 5675 : rElem->nOffset = sal_uInt16(idx - p->nStart);
431 5675 : rElem->pBlock = p;
432 5675 : p->pData[ idx - p->nStart ] = rElem;
433 5675 : }
434 :
435 : /** Compress the array */
436 993 : 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 993 : BlockInfo** pp = ppInf, **qq = pp;
444 : BlockInfo* p;
445 993 : BlockInfo* pLast(0); // last empty block
446 993 : sal_uInt16 nLast = 0; // missing elements
447 993 : sal_uInt16 nBlkdel = 0; // number of deleted blocks
448 993 : sal_uInt16 nFirstChgPos = USHRT_MAX; // at which position was the 1st change?
449 :
450 : // convert fill percentage into number of remaining elements
451 993 : nMax = MAXENTRY - (long) MAXENTRY * nMax / 100;
452 :
453 1987 : for( sal_uInt16 cur = 0; cur < nBlock; ++cur )
454 : {
455 994 : p = *pp++;
456 994 : 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 994 : if( nLast && ( n > nLast ) && ( nLast < nMax ) )
462 0 : nLast = 0;
463 994 : if( nLast )
464 : {
465 1 : if( USHRT_MAX == nFirstChgPos )
466 1 : nFirstChgPos = cur;
467 :
468 : // Not full yet? Than fill up.
469 1 : if( n > nLast )
470 0 : n = nLast;
471 :
472 : // move elements from current to last block
473 1 : ElementPtr* pElem = pLast->pData + pLast->nElem;
474 1 : ElementPtr* pFrom = p->pData;
475 2 : for( sal_uInt16 nCount = n, nOff = pLast->nElem;
476 : nCount; --nCount, ++pElem )
477 : {
478 : *pElem = *pFrom++,
479 : (*pElem)->pBlock = pLast,
480 1 : (*pElem)->nOffset = nOff++;
481 : }
482 :
483 : // adjustment
484 1 : pLast->nElem = pLast->nElem + n;
485 1 : nLast = nLast - n;
486 1 : p->nElem = p->nElem - n;
487 :
488 : // Is the current block now empty as a result?
489 1 : if( !p->nElem )
490 : {
491 : // than remove
492 1 : delete[] p->pData;
493 1 : delete p, p = 0;
494 1 : ++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 994 : if( p ) // BlockInfo was not deleted
510 : {
511 993 : *qq++ = p; // adjust to correct position
512 :
513 : // keep the potentially existing last half-full block
514 993 : if( !nLast && p->nElem < MAXENTRY )
515 : {
516 993 : pLast = p;
517 993 : nLast = MAXENTRY - p->nElem;
518 : }
519 : }
520 : }
521 :
522 : // if blocks were deleted shrink BlockInfo array if needed
523 993 : if( nBlkdel )
524 1 : BlockDel( nBlkdel );
525 :
526 : // and re-index
527 993 : p = ppInf[ 0 ];
528 993 : p->nEnd = p->nElem - 1;
529 993 : UpdIndex( 0 );
530 :
531 993 : if( nCur >= nFirstChgPos )
532 0 : nCur = 0;
533 :
534 : CHECKIDX( ppInf, nBlock, nSize, nCur );
535 :
536 993 : return nFirstChgPos;
537 : }
538 :
539 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
