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