Stop leaking all ScPostIt instances.
[LibreOffice.git] / sc / source / core / data / compressedarray.cxx
blob8d3288418d1c00d58fe5db523646b58a30cca1c5
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3 * This file is part of the LibreOffice project.
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/.
9 * This file incorporates work covered by the following license notice:
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 .
21 #include "compressedarray.hxx"
22 #include "address.hxx"
24 #include <algorithm>
26 template< typename A, typename D >
27 ScCompressedArray<A,D>::ScCompressedArray( A nMaxAccessP, const D& rValue,
28 size_t nDeltaP )
29 : nCount(1)
30 , nLimit(1)
31 , nDelta( nDeltaP > 0 ? nDeltaP : 1)
32 , pData( new DataEntry[1])
33 , nMaxAccess( nMaxAccessP)
35 pData[0].aValue = rValue;
36 pData[0].nEnd = nMaxAccess;
40 template< typename A, typename D >
41 ScCompressedArray<A,D>::ScCompressedArray( A nMaxAccessP, const D* pDataArray,
42 size_t nDataCount )
43 : nCount(0)
44 , nLimit( nDataCount)
45 , nDelta( nScCompressedArrayDelta)
46 , pData( new DataEntry[nDataCount])
47 , nMaxAccess( nMaxAccessP)
49 D aValue = pDataArray[0];
50 for (size_t j=0; j<nDataCount; ++j)
52 if (!(aValue == pDataArray[j]))
54 pData[nCount].aValue = aValue;
55 pData[nCount].nEnd = j-1;
56 ++nCount;
57 aValue = pDataArray[j];
60 pData[nCount].aValue = aValue;
61 pData[nCount].nEnd = nMaxAccess;
62 ++nCount;
63 Resize( nCount);
67 template< typename A, typename D >
68 ScCompressedArray<A,D>::~ScCompressedArray()
70 delete[] pData;
74 template< typename A, typename D >
75 void ScCompressedArray<A,D>::Resize( size_t nNewLimit)
77 if ((nCount <= nNewLimit && nNewLimit < nLimit) || nLimit < nNewLimit)
79 nLimit = nNewLimit;
80 DataEntry* pNewData = new DataEntry[nLimit];
81 memcpy( pNewData, pData, nCount*sizeof(DataEntry));
82 delete[] pData;
83 pData = pNewData;
88 template< typename A, typename D >
89 size_t ScCompressedArray<A,D>::Search( A nAccess ) const
91 if (nAccess == 0)
92 return 0;
94 long nLo = 0;
95 long nHi = static_cast<long>(nCount) - 1;
96 long nStart = 0;
97 long nEnd = 0;
98 long i = 0;
99 bool bFound = (nCount == 1);
100 while (!bFound && nLo <= nHi)
102 i = (nLo + nHi) / 2;
103 if (i > 0)
104 nStart = (long) pData[i - 1].nEnd;
105 else
106 nStart = -1;
107 nEnd = (long) pData[i].nEnd;
108 if (nEnd < (long) nAccess)
109 nLo = ++i;
110 else
111 if (nStart >= (long) nAccess)
112 nHi = --i;
113 else
114 bFound = true;
116 return (bFound ? static_cast<size_t>(i) : (nAccess < 0 ? 0 : nCount-1));
120 template< typename A, typename D >
121 void ScCompressedArray<A,D>::SetValue( A nStart, A nEnd, const D& rValue )
123 if (0 <= nStart && nStart <= nMaxAccess && 0 <= nEnd && nEnd <= nMaxAccess
124 && nStart <= nEnd)
126 if ((nStart == 0) && (nEnd == nMaxAccess))
127 Reset( rValue);
128 else
130 // Create a temporary copy in case we got a reference passed that
131 // points to a part of the array to be reallocated.
132 D aNewVal( rValue);
133 size_t nNeeded = nCount + 2;
134 if (nLimit < nNeeded)
136 nLimit += nDelta;
137 if (nLimit < nNeeded)
138 nLimit = nNeeded;
139 DataEntry* pNewData = new DataEntry[nLimit];
140 memcpy( pNewData, pData, nCount*sizeof(DataEntry));
141 delete[] pData;
142 pData = pNewData;
145 size_t ni; // number of leading entries
146 size_t nInsert; // insert position (nMaxAccess+1 := no insert)
147 bool bCombined = false;
148 bool bSplit = false;
149 if (nStart > 0)
151 // skip leading
152 ni = this->Search( nStart);
154 nInsert = nMaxAccess+1;
155 if (!(pData[ni].aValue == aNewVal))
157 if (ni == 0 || (pData[ni-1].nEnd < nStart - 1))
158 { // may be a split or a simple insert or just a shrink,
159 // row adjustment is done further down
160 if (pData[ni].nEnd > nEnd)
161 bSplit = true;
162 ni++;
163 nInsert = ni;
165 else if (ni > 0 && pData[ni-1].nEnd == nStart - 1)
166 nInsert = ni;
168 if (ni > 0 && pData[ni-1].aValue == aNewVal)
169 { // combine
170 pData[ni-1].nEnd = nEnd;
171 nInsert = nMaxAccess+1;
172 bCombined = true;
175 else
177 nInsert = 0;
178 ni = 0;
181 size_t nj = ni; // stop position of range to replace
182 while (nj < nCount && pData[nj].nEnd <= nEnd)
183 nj++;
184 if (!bSplit)
186 if (nj < nCount && pData[nj].aValue == aNewVal)
187 { // combine
188 if (ni > 0)
190 if (pData[ni-1].aValue == aNewVal)
191 { // adjacent entries
192 pData[ni-1].nEnd = pData[nj].nEnd;
193 nj++;
195 else if (ni == nInsert)
196 pData[ni-1].nEnd = nStart - 1; // shrink
198 nInsert = nMaxAccess+1;
199 bCombined = true;
201 else if (ni > 0 && ni == nInsert)
202 pData[ni-1].nEnd = nStart - 1; // shrink
204 if (ni < nj)
205 { // remove middle entries
206 if (!bCombined)
207 { // replace one entry
208 pData[ni].nEnd = nEnd;
209 pData[ni].aValue = aNewVal;
210 ni++;
211 nInsert = nMaxAccess+1;
213 if (ni < nj)
214 { // remove entries
215 memmove( pData + ni, pData + nj,
216 (nCount - nj) * sizeof(DataEntry));
217 nCount -= nj - ni;
221 if (nInsert < static_cast<size_t>(nMaxAccess+1))
222 { // insert or append new entry
223 if (nInsert <= nCount)
225 if (!bSplit)
226 memmove( pData + nInsert + 1, pData + nInsert,
227 (nCount - nInsert) * sizeof(DataEntry));
228 else
230 memmove( pData + nInsert + 2, pData + nInsert,
231 (nCount - nInsert) * sizeof(DataEntry));
232 pData[nInsert+1] = pData[nInsert-1];
233 nCount++;
236 if (nInsert)
237 pData[nInsert-1].nEnd = nStart - 1;
238 pData[nInsert].nEnd = nEnd;
239 pData[nInsert].aValue = aNewVal;
240 nCount++;
247 template< typename A, typename D >
248 void ScCompressedArray<A,D>::CopyFrom( const ScCompressedArray<A,D>& rArray, A nStart,
249 A nEnd, long nSourceDy )
251 size_t nIndex;
252 A nRegionEnd;
253 for (A j=nStart; j<=nEnd; ++j)
255 const D& rValue = (j==nStart ?
256 rArray.GetValue( j+nSourceDy, nIndex, nRegionEnd) :
257 rArray.GetNextValue( nIndex, nRegionEnd));
258 nRegionEnd -= nSourceDy;
259 if (nRegionEnd > nEnd)
260 nRegionEnd = nEnd;
261 this->SetValue( j, nRegionEnd, rValue);
262 j = nRegionEnd;
267 template< typename A, typename D >
268 const D& ScCompressedArray<A,D>::Insert( A nStart, size_t nAccessCount )
270 size_t nIndex = this->Search( nStart);
271 // No real insertion is needed, simply extend the one entry and adapt all
272 // following. In case nStart points to the start row of an entry, extend
273 // the previous entry (inserting before nStart).
274 if (nIndex > 0 && pData[nIndex-1].nEnd+1 == nStart)
275 --nIndex;
276 const D& rValue = pData[nIndex].aValue; // the value "copied"
279 pData[nIndex].nEnd += nAccessCount;
280 if (pData[nIndex].nEnd >= nMaxAccess)
282 pData[nIndex].nEnd = nMaxAccess;
283 nCount = nIndex + 1; // discard trailing entries
285 } while (++nIndex < nCount);
286 return rValue;
290 template< typename A, typename D >
291 void ScCompressedArray<A,D>::Remove( A nStart, size_t nAccessCount )
293 A nEnd = nStart + nAccessCount - 1;
294 size_t nIndex = this->Search( nStart);
295 // equalize/combine/remove all entries in between
296 if (nEnd > pData[nIndex].nEnd)
297 this->SetValue( nStart, nEnd, pData[nIndex].aValue);
298 // remove an exactly matching entry by shifting up all following by one
299 if ((nStart == 0 || (nIndex > 0 && nStart == pData[nIndex-1].nEnd+1)) &&
300 pData[nIndex].nEnd == nEnd && nIndex < nCount-1)
302 // In case removing an entry results in two adjacent entries with
303 // identical data, combine them into one. This is also necessary to
304 // make the algorithm used in SetValue() work correctly, it relies on
305 // the fact that consecutive values actually differ.
306 size_t nRemove;
307 if (nIndex > 0 && pData[nIndex-1].aValue == pData[nIndex+1].aValue)
309 nRemove = 2;
310 --nIndex;
312 else
313 nRemove = 1;
314 memmove( pData + nIndex, pData + nIndex + nRemove, (nCount - (nIndex +
315 nRemove)) * sizeof(DataEntry));
316 nCount -= nRemove;
318 // adjust end rows, nIndex still being valid
321 pData[nIndex].nEnd -= nAccessCount;
322 } while (++nIndex < nCount);
323 pData[nCount-1].nEnd = nMaxAccess;
327 // === ScBitMaskCompressedArray ==============================================
329 template< typename A, typename D >
330 void ScBitMaskCompressedArray<A,D>::AndValue( A nStart, A nEnd,
331 const D& rValueToAnd )
333 if (nStart > nEnd)
334 return;
336 size_t nIndex = this->Search( nStart);
339 if ((this->pData[nIndex].aValue & rValueToAnd) != this->pData[nIndex].aValue)
341 A nS = ::std::max( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
342 A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
343 this->SetValue( nS, nE, this->pData[nIndex].aValue & rValueToAnd);
344 if (nE >= nEnd)
345 break; // while
346 nIndex = this->Search( nE + 1);
348 else if (this->pData[nIndex].nEnd >= nEnd)
349 break; // while
350 else
351 ++nIndex;
352 } while (nIndex < this->nCount);
356 template< typename A, typename D >
357 void ScBitMaskCompressedArray<A,D>::OrValue( A nStart, A nEnd,
358 const D& rValueToOr )
360 if (nStart > nEnd)
361 return;
363 size_t nIndex = this->Search( nStart);
366 if ((this->pData[nIndex].aValue | rValueToOr) != this->pData[nIndex].aValue)
368 A nS = ::std::max( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
369 A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
370 this->SetValue( nS, nE, this->pData[nIndex].aValue | rValueToOr);
371 if (nE >= nEnd)
372 break; // while
373 nIndex = this->Search( nE + 1);
375 else if (this->pData[nIndex].nEnd >= nEnd)
376 break; // while
377 else
378 ++nIndex;
379 } while (nIndex < this->nCount);
383 template< typename A, typename D >
384 void ScBitMaskCompressedArray<A,D>::CopyFromAnded(
385 const ScBitMaskCompressedArray<A,D>& rArray, A nStart, A nEnd,
386 const D& rValueToAnd, long nSourceDy )
388 size_t nIndex;
389 A nRegionEnd;
390 for (A j=nStart; j<=nEnd; ++j)
392 const D& rValue = (j==nStart ?
393 rArray.GetValue( j+nSourceDy, nIndex, nRegionEnd) :
394 rArray.GetNextValue( nIndex, nRegionEnd));
395 nRegionEnd -= nSourceDy;
396 if (nRegionEnd > nEnd)
397 nRegionEnd = nEnd;
398 this->SetValue( j, nRegionEnd, rValue & rValueToAnd);
399 j = nRegionEnd;
403 template< typename A, typename D >
404 A ScBitMaskCompressedArray<A,D>::GetFirstForCondition( A nStart, A nEnd,
405 const D& rBitMask, const D& rMaskedCompare ) const
407 size_t nIndex = this->Search( nStart);
410 if ((this->pData[nIndex].aValue & rBitMask) == rMaskedCompare)
412 A nFound = nIndex > 0 ? this->pData[nIndex-1].nEnd + 1 : 0;
413 return ::std::max( nFound, nStart);
415 if (this->pData[nIndex].nEnd >= nEnd)
416 break; // while
417 ++nIndex;
418 } while (nIndex < this->nCount);
419 return ::std::numeric_limits<A>::max();
422 template< typename A, typename D >
423 A ScBitMaskCompressedArray<A,D>::GetLastAnyBitAccess( A nStart,
424 const D& rBitMask ) const
426 A nEnd = ::std::numeric_limits<A>::max();
427 size_t nIndex = this->nCount-1;
428 while (1)
430 if ((this->pData[nIndex].aValue & rBitMask) != 0)
432 nEnd = this->pData[nIndex].nEnd;
433 break; // while
435 else
437 if (nIndex > 0)
439 --nIndex;
440 if (this->pData[nIndex].nEnd < nStart)
441 break; // while
443 else
444 break; // while
447 return nEnd;
450 // === Force instantiation of specializations ================================
452 template class ScCompressedArray< SCROW, sal_uInt8>; // flags, base class
453 template class ScBitMaskCompressedArray< SCROW, sal_uInt8>; // flags
455 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */