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 : static 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 5930 : BigPtrArray::BigPtrArray()
49 : {
50 5930 : nBlock = nCur = 0;
51 5930 : nSize = 0;
52 5930 : nMaxBlock = nBlockGrowSize;
53 5930 : ppInf = new BlockInfo* [ nMaxBlock ];
54 5930 : }
55 :
56 5912 : BigPtrArray::~BigPtrArray()
57 : {
58 5912 : if( nBlock )
59 : {
60 5906 : BlockInfo** pp = ppInf;
61 11812 : for( sal_uInt16 n = 0; n < nBlock; ++n, ++pp )
62 : {
63 5906 : delete[] (*pp)->pData;
64 5906 : delete *pp;
65 : }
66 : }
67 5912 : delete[] ppInf;
68 5912 : }
69 :
70 : // Also moving is done simply here. Optimization is useless because of the
71 : // division of this field into multiple parts.
72 75 : void BigPtrArray::Move( sal_uLong from, sal_uLong to )
73 : {
74 75 : if (from != to)
75 : {
76 65 : sal_uInt16 cur = Index2Block( from );
77 65 : BlockInfo* p = ppInf[ cur ];
78 65 : ElementPtr pElem = p->pData[ from - p->nStart ];
79 65 : Insert( pElem, to ); // insert first, then delete!
80 65 : Remove( ( to < from ) ? ( from + 1 ) : from );
81 : }
82 75 : }
83 :
84 3948168 : ElementPtr BigPtrArray::operator[]( sal_uLong idx ) const
85 : {
86 : assert(idx < nSize); // operator[]: Index out of bounds
87 3948168 : nCur = Index2Block( idx );
88 3948168 : BlockInfo* p = ppInf[ nCur ];
89 3948168 : return p->pData[ idx - p->nStart ];
90 : }
91 :
92 : /** Search a block at a given position */
93 4291504 : sal_uInt16 BigPtrArray::Index2Block( sal_uLong pos ) const
94 : {
95 : // last used block?
96 4291504 : BlockInfo* p = ppInf[ nCur ];
97 4291504 : if( p->nStart <= pos && p->nEnd >= pos )
98 4227375 : return nCur;
99 : // Index = 0?
100 64129 : if( !pos )
101 31747 : return 0;
102 :
103 : // following one?
104 32382 : if( nCur < ( nBlock - 1 ) )
105 : {
106 32122 : p = ppInf[ nCur+1 ];
107 32122 : if( p->nStart <= pos && p->nEnd >= pos )
108 9922 : return nCur+1;
109 : }
110 : // previous one?
111 260 : else if( pos < p->nStart && nCur > 0 )
112 : {
113 260 : p = ppInf[ nCur-1 ];
114 260 : if( p->nStart <= pos && p->nEnd >= pos )
115 238 : return nCur-1;
116 : }
117 :
118 : // binary search: always successful
119 22222 : sal_uInt16 lower = 0, upper = nBlock - 1;
120 22222 : sal_uInt16 cur = 0;
121 : for(;;)
122 : {
123 74263 : sal_uInt16 n = lower + ( upper - lower ) / 2;
124 74263 : cur = ( n == cur ) ? n+1 : n;
125 74263 : p = ppInf[ cur ];
126 74263 : if( p->nStart <= pos && p->nEnd >= pos )
127 22222 : return cur;
128 :
129 52041 : if( p->nStart > pos )
130 84 : upper = cur;
131 : else
132 51957 : lower = cur;
133 52041 : }
134 : }
135 :
136 : /** Update all index areas
137 :
138 : @param pos last correct block (starting point)
139 : */
140 19894 : void BigPtrArray::UpdIndex( sal_uInt16 pos )
141 : {
142 19894 : BlockInfo** pp = ppInf + pos;
143 19894 : sal_uLong idx = (*pp)->nEnd + 1;
144 40996 : while( ++pos < nBlock )
145 : {
146 1208 : BlockInfo* p = *++pp;
147 1208 : p->nStart = idx;
148 1208 : idx += p->nElem;
149 1208 : p->nEnd = idx - 1;
150 : }
151 19894 : }
152 :
153 : /** Create and insert new block
154 :
155 : Existing blocks will be moved rearward.
156 :
157 : @param pos Position at which the new block should be created.
158 : */
159 5942 : BlockInfo* BigPtrArray::InsBlock( sal_uInt16 pos )
160 : {
161 5942 : if( nBlock == nMaxBlock )
162 : {
163 : // than extend the array first
164 0 : BlockInfo** ppNew = new BlockInfo* [ nMaxBlock + nBlockGrowSize ];
165 0 : memcpy( ppNew, ppInf, nMaxBlock * sizeof( BlockInfo* ));
166 0 : delete[] ppInf;
167 0 : nMaxBlock += nBlockGrowSize;
168 0 : ppInf = ppNew;
169 : }
170 5942 : if( pos != nBlock )
171 : {
172 2 : memmove( ppInf + pos+1, ppInf + pos,
173 3 : ( nBlock - pos ) * sizeof( BlockInfo* ));
174 : }
175 5942 : ++nBlock;
176 5942 : BlockInfo* p = new BlockInfo;
177 5942 : ppInf[ pos ] = p;
178 :
179 5942 : if( pos )
180 13 : p->nStart = p->nEnd = ppInf[ pos-1 ]->nEnd + 1;
181 : else
182 5929 : p->nStart = p->nEnd = 0;
183 :
184 5942 : p->nEnd--; // no elements
185 5942 : p->nElem = 0;
186 5942 : p->pData = new ElementPtr [ MAXENTRY ];
187 5942 : p->pBigArr = this;
188 5942 : return p;
189 : }
190 :
191 13 : void BigPtrArray::BlockDel( sal_uInt16 nDel )
192 : {
193 13 : nBlock = nBlock - nDel;
194 13 : if( nMaxBlock - nBlock > nBlockGrowSize )
195 : {
196 : // than shrink array
197 0 : nDel = (( nBlock / nBlockGrowSize ) + 1 ) * nBlockGrowSize;
198 0 : BlockInfo** ppNew = new BlockInfo* [ nDel ];
199 0 : memcpy( ppNew, ppInf, nBlock * sizeof( BlockInfo* ));
200 0 : delete[] ppInf;
201 0 : ppInf = ppNew;
202 0 : nMaxBlock = nDel;
203 : }
204 13 : }
205 :
206 160068 : void BigPtrArray::Insert( const ElementPtr& rElem, sal_uLong pos )
207 : {
208 : CHECKIDX( ppInf, nBlock, nSize, nCur );
209 :
210 : BlockInfo* p;
211 : sal_uInt16 cur;
212 160068 : if( !nSize )
213 : {
214 : // special case: insert first element
215 5929 : p = InsBlock( cur = 0 );
216 : }
217 154139 : else if( pos == nSize )
218 : {
219 : // special case: insert at end
220 53354 : cur = nBlock - 1;
221 53354 : p = ppInf[ cur ];
222 53354 : if( p->nElem == MAXENTRY )
223 : // the last block is full, create a new one
224 0 : p = InsBlock( ++cur );
225 : }
226 : else
227 : {
228 : // standard case:
229 100785 : cur = Index2Block( pos );
230 100785 : p = ppInf[ cur ];
231 : }
232 :
233 160068 : if( p->nElem == MAXENTRY )
234 : {
235 : // does the last entry fit into the next block?
236 : BlockInfo* q;
237 739 : if( cur < ( nBlock - 1 ) && ppInf[ cur+1 ]->nElem < MAXENTRY )
238 : {
239 726 : q = ppInf[ cur+1 ];
240 726 : if( q->nElem )
241 : {
242 726 : int nCount = q->nElem;
243 726 : ElementPtr *pFrom = q->pData + nCount,
244 726 : *pTo = pFrom+1;
245 114034 : while( nCount-- )
246 112582 : ++( *--pTo = *--pFrom )->nOffset;
247 : }
248 726 : q->nStart--;
249 726 : q->nEnd--;
250 : }
251 : else
252 : {
253 : // If it does not fit, then insert a new block. But if there is more
254 : // than 50% space in the array then compress first.
255 13 : if( /*nBlock == nMaxBlock &&*/
256 13 : nBlock > ( nSize / ( MAXENTRY / 2 ) ) &&
257 0 : cur >= Compress() )
258 : {
259 : // Something was moved before the current position and all
260 : // pointer might be invalid. Thus restart Insert.
261 0 : Insert( rElem, pos );
262 160068 : return ;
263 : }
264 :
265 13 : q = InsBlock( cur+1 );
266 : }
267 :
268 : // entry does not fit anymore - clear space
269 739 : ElementPtr pLast = p->pData[ MAXENTRY-1 ];
270 739 : pLast->nOffset = 0;
271 739 : pLast->pBlock = q;
272 :
273 739 : q->pData[ 0 ] = pLast;
274 739 : q->nElem++;
275 739 : q->nEnd++;
276 :
277 739 : p->nEnd--;
278 739 : p->nElem--;
279 : }
280 : // now we have free space - insert
281 160068 : pos -= p->nStart;
282 : assert(pos < MAXENTRY);
283 160068 : if( pos != p->nElem )
284 : {
285 100773 : int nCount = p->nElem - sal_uInt16(pos);
286 100773 : ElementPtr *pFrom = p->pData + p->nElem;
287 100773 : ElementPtr *pTo = pFrom + 1;
288 3338556 : while( nCount-- )
289 3137010 : ++( *--pTo = *--pFrom )->nOffset;
290 : }
291 : // insert element and update indices
292 160068 : rElem->nOffset = sal_uInt16(pos);
293 160068 : rElem->pBlock = p;
294 160068 : p->pData[ pos ] = rElem;
295 160068 : p->nEnd++;
296 160068 : p->nElem++;
297 160068 : nSize++;
298 160068 : if( cur != ( nBlock - 1 ) ) UpdIndex( cur );
299 160068 : nCur = cur;
300 :
301 : CHECKIDX( ppInf, nBlock, nSize, nCur );
302 : }
303 :
304 19793 : void BigPtrArray::Remove( sal_uLong pos, sal_uLong n )
305 : {
306 : CHECKIDX( ppInf, nBlock, nSize, nCur );
307 :
308 19793 : sal_uInt16 nBlkdel = 0; // deleted blocks
309 19793 : sal_uInt16 cur = Index2Block( pos ); // current block number
310 19793 : sal_uInt16 nBlk1 = cur; // 1st treated block
311 19793 : sal_uInt16 nBlk1del = USHRT_MAX; // 1st deleted block
312 19793 : BlockInfo* p = ppInf[ cur ];
313 19793 : pos -= p->nStart;
314 :
315 19793 : sal_uLong nElem = n;
316 39599 : while( nElem )
317 : {
318 19806 : sal_uInt16 nel = p->nElem - sal_uInt16(pos);
319 19806 : if( sal_uLong(nel) > nElem )
320 19776 : nel = sal_uInt16(nElem);
321 : // move elements if needed
322 19806 : if( ( pos + nel ) < sal_uLong(p->nElem) )
323 : {
324 19776 : ElementPtr *pTo = p->pData + pos;
325 19776 : ElementPtr *pFrom = pTo + nel;
326 19776 : int nCount = p->nElem - nel - sal_uInt16(pos);
327 431488 : while( nCount-- )
328 : {
329 391936 : *pTo = *pFrom++;
330 391936 : (*pTo)->nOffset = (*pTo)->nOffset - nel;
331 391936 : ++pTo;
332 : }
333 : }
334 19806 : p->nEnd -= nel;
335 19806 : p->nElem = p->nElem - nel;
336 : // possibly delete block completely
337 19806 : if( !p->nElem )
338 : {
339 11 : delete[] p->pData;
340 11 : nBlkdel++;
341 11 : if( USHRT_MAX == nBlk1del )
342 6 : nBlk1del = cur;
343 : }
344 19806 : nElem -= nel;
345 19806 : if( !nElem )
346 19793 : break;
347 13 : p = ppInf[ ++cur ];
348 13 : pos = 0;
349 : }
350 :
351 : // update table if blocks were removed
352 19793 : if( nBlkdel )
353 : {
354 17 : for( sal_uInt16 i = nBlk1del; i < ( nBlk1del + nBlkdel ); i++ )
355 11 : delete ppInf[ i ];
356 :
357 6 : if( ( nBlk1del + nBlkdel ) < nBlock )
358 : {
359 2 : memmove( ppInf + nBlk1del, ppInf + nBlk1del + nBlkdel,
360 3 : ( nBlock - nBlkdel - nBlk1del ) * sizeof( BlockInfo* ) );
361 :
362 : // UpdateIdx updates the successor thus start before first elem
363 1 : if( !nBlk1 )
364 : {
365 1 : p = ppInf[ 0 ];
366 1 : p->nStart = 0;
367 1 : p->nEnd = p->nElem-1;
368 : }
369 : else
370 : {
371 0 : --nBlk1;
372 : }
373 : }
374 6 : BlockDel( nBlkdel ); // blocks were deleted
375 : }
376 :
377 19793 : nSize -= n;
378 19793 : if( nBlk1 != ( nBlock - 1 ) && nSize )
379 76 : UpdIndex( nBlk1 );
380 19793 : nCur = nBlk1;
381 :
382 : // call Compress() if there is more than 50% space in the array
383 19793 : if( nBlock > ( nSize / ( MAXENTRY / 2 ) ) )
384 18916 : Compress();
385 :
386 : CHECKIDX( ppInf, nBlock, nSize, nCur );
387 19793 : }
388 :
389 99405 : void BigPtrArray::Replace( sal_uLong idx, const ElementPtr& rElem)
390 : {
391 : assert(idx < nSize); // Index out of bounds
392 99405 : nCur = Index2Block( idx );
393 99405 : BlockInfo* p = ppInf[ nCur ];
394 99405 : rElem->nOffset = sal_uInt16(idx - p->nStart);
395 99405 : rElem->pBlock = p;
396 99405 : p->pData[ idx - p->nStart ] = rElem;
397 99405 : }
398 :
399 : /** Compress the array */
400 18916 : sal_uInt16 BigPtrArray::Compress( short nMax )
401 : {
402 : CHECKIDX( ppInf, nBlock, nSize, nCur );
403 :
404 : // Iterate over InfoBlock array from beginning to end. If there is a deleted
405 : // block in between so move all following ones accordingly. The pointer <pp>
406 : // represents the "old" and <qq> the "new" array.
407 18916 : BlockInfo** pp = ppInf, **qq = pp;
408 : BlockInfo* p;
409 18916 : BlockInfo* pLast(0); // last empty block
410 18916 : sal_uInt16 nLast = 0; // missing elements
411 18916 : sal_uInt16 nBlkdel = 0; // number of deleted blocks
412 18916 : sal_uInt16 nFirstChgPos = USHRT_MAX; // at which position was the 1st change?
413 :
414 : // convert fill percentage into number of remaining elements
415 18916 : nMax = MAXENTRY - (long) MAXENTRY * nMax / 100;
416 :
417 37839 : for( sal_uInt16 cur = 0; cur < nBlock; ++cur )
418 : {
419 18923 : p = *pp++;
420 18923 : sal_uInt16 n = p->nElem;
421 : // Check if a not completely full block will be ignored. This happens if
422 : // the current block would have to be split but the filling of the
423 : // inspected block is already over its threshold value. In this case we
424 : // do not fill more (it's expensive because of a double memmove() call)
425 18923 : if( nLast && ( n > nLast ) && ( nLast < nMax ) )
426 0 : nLast = 0;
427 18923 : if( nLast )
428 : {
429 7 : if( USHRT_MAX == nFirstChgPos )
430 7 : nFirstChgPos = cur;
431 :
432 : // Not full yet? Than fill up.
433 7 : if( n > nLast )
434 0 : n = nLast;
435 :
436 : // move elements from current to last block
437 7 : ElementPtr* pElem = pLast->pData + pLast->nElem;
438 7 : ElementPtr* pFrom = p->pData;
439 14 : for( sal_uInt16 nCount = n, nOff = pLast->nElem;
440 : nCount; --nCount, ++pElem )
441 : {
442 : *pElem = *pFrom++,
443 : (*pElem)->pBlock = pLast,
444 7 : (*pElem)->nOffset = nOff++;
445 : }
446 :
447 : // adjustment
448 7 : pLast->nElem = pLast->nElem + n;
449 7 : nLast = nLast - n;
450 7 : p->nElem = p->nElem - n;
451 :
452 : // Is the current block now empty as a result?
453 7 : if( !p->nElem )
454 : {
455 : // than remove
456 7 : delete[] p->pData;
457 7 : delete p, p = 0;
458 7 : ++nBlkdel;
459 : }
460 : else
461 : {
462 0 : pElem = p->pData, pFrom = pElem + n;
463 0 : int nCount = p->nElem;
464 0 : while( nCount-- )
465 : {
466 0 : *pElem = *pFrom++;
467 0 : (*pElem)->nOffset = (*pElem)->nOffset - n;
468 0 : ++pElem;
469 : }
470 : }
471 : }
472 :
473 18923 : if( p ) // BlockInfo was not deleted
474 : {
475 18916 : *qq++ = p; // adjust to correct position
476 :
477 : // keep the potentially existing last half-full block
478 18916 : if( !nLast && p->nElem < MAXENTRY )
479 : {
480 18916 : pLast = p;
481 18916 : nLast = MAXENTRY - p->nElem;
482 : }
483 : }
484 : }
485 :
486 : // if blocks were deleted shrink BlockInfo array if needed
487 18916 : if( nBlkdel )
488 7 : BlockDel( nBlkdel );
489 :
490 : // and re-index
491 18916 : p = ppInf[ 0 ];
492 18916 : p->nEnd = p->nElem - 1;
493 18916 : UpdIndex( 0 );
494 :
495 18916 : if( nCur >= nFirstChgPos )
496 0 : nCur = 0;
497 :
498 : CHECKIDX( ppInf, nBlock, nSize, nCur );
499 :
500 18916 : return nFirstChgPos;
501 : }
502 :
503 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
