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 
22 #include <limits.h>
23 #include <string.h>
24 
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 
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.
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 
83 {
84  assert(idx < m_nSize); // operator[]: Index out of bounds
85  m_nCur = Index2Block( idx );
86  BlockInfo* p = m_ppInf[ m_nCur ];
87  return p->mvData[ idx - p->nStart ];
88 }
89 
91 sal_uInt16 BigPtrArray::Index2Block( sal_uLong pos ) const
92 {
93  // last used block?
94  BlockInfo* p = m_ppInf[ m_nCur ];
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 
138 void BigPtrArray::UpdIndex( sal_uInt16 pos )
139 {
140  BlockInfo** pp = m_ppInf.get() + pos;
141  sal_uLong 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 
187 void 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 
202 {
203  CHECKIDX( m_ppInf.get(), m_nBlock, m_nSize, m_nCur );
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 
303  CHECKIDX( m_ppInf.get(), m_nBlock, m_nSize, m_nCur );
304 }
305 
307 {
308  CHECKIDX( m_ppInf.get(), m_nBlock, m_nSize, m_nCur );
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_uLong nElem = n;
318  while( nElem )
319  {
320  sal_uInt16 nel = p->nElem - sal_uInt16(pos);
321  if( sal_uLong(nel) > nElem )
322  nel = sal_uInt16(nElem);
323  // move elements if needed
324  if( ( pos + nel ) < sal_uLong(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 
387  CHECKIDX( m_ppInf.get(), m_nBlock, m_nSize, m_nCur );
388 }
389 
391 {
392  assert(idx < m_nSize); // Index out of bounds
393  m_nCur = Index2Block( idx );
394  BlockInfo* p = m_ppInf[ m_nCur ];
395  pElem->m_nOffset = sal_uInt16(idx - p->nStart);
396  pElem->m_pBlock = p;
397  p->mvData[ idx - p->nStart ] = pElem;
398 }
399 
402 {
403  CHECKIDX( m_ppInf.get(), m_nBlock, m_nSize, m_nCur );
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 - 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 
500  CHECKIDX( m_ppInf.get(), m_nBlock, m_nSize, m_nCur );
501 
502  return nFirstChgPos;
503 }
504 
505 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
sal_uInt16 m_nCur
last used block
Definition: bparr.hxx:73
BlockInfo * m_pBlock
Definition: bparr.hxx:36
#define CHECKIDX(p, n, i, c)
Definition: bparr.cxx:45
sal_uIntPtr sal_uLong
BigPtrArray * pBigArr
in this array the block is located
Definition: bparr.hxx:57
#define COMPRESSLVL
Definition: bparr.hxx:53
sal_uInt16 m_nOffset
Definition: bparr.hxx:37
sal_uInt16 nElem
number of elements
Definition: bparr.hxx:61
sal_uInt16 m_nBlock
number of blocks
Definition: bparr.hxx:71
sal_uLong m_nSize
number of elements
Definition: bparr.hxx:69
sal_uInt16 Index2Block(sal_uLong) const
block search
Definition: bparr.cxx:91
void Move(sal_uLong from, sal_uLong to)
Definition: bparr.cxx:70
void Replace(sal_uLong pos, BigPtrEntry *p)
Definition: bparr.cxx:390
BigPtrArray()
Definition: bparr.cxx:48
void BlockDel(sal_uInt16)
some blocks were deleted
Definition: bparr.cxx:187
sal_uLong nStart
Definition: bparr.hxx:60
std::unique_ptr< BlockInfo *[]> m_ppInf
block info
Definition: bparr.hxx:68
static const sal_uInt16 nBlockGrowSize
Resize block management by this constant.
Definition: bparr.cxx:27
void Insert(BigPtrEntry *p, sal_uLong pos)
Definition: bparr.cxx:201
sal_uInt16 m_nMaxBlock
current max. number of blocks
Definition: bparr.hxx:70
int i
sal_uInt16 Compress()
Compress the array.
Definition: bparr.cxx:401
std::array< BigPtrEntry *, MAXENTRY > mvData
data block
Definition: bparr.hxx:59
BlockInfo * InsBlock(sal_uInt16)
insert block
Definition: bparr.cxx:157
#define MAXENTRY
Definition: bparr.hxx:47
void UpdIndex(sal_uInt16)
recalculate indices
Definition: bparr.cxx:138
BigPtrEntry * operator[](sal_uLong) const
Definition: bparr.cxx:82
~BigPtrArray()
Definition: bparr.cxx:56
sal_uLong nEnd
start- and end index
Definition: bparr.hxx:60
const o3tl::enumarray< SvxAdjust, unsigned short > aSvxToUnoAdjust USHRT_MAX
Definition: unosett.cxx:261
void Remove(sal_uLong pos, sal_uLong n=1)
Definition: bparr.cxx:306