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 :
21 : #include "compressedarray.hxx"
22 : #include "address.hxx"
23 :
24 : #include <algorithm>
25 :
26 : template< typename A, typename D >
27 1051 : 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 1051 : , nMaxAccess( nMaxAccessP)
34 : {
35 1051 : pData[0].aValue = rValue;
36 1051 : pData[0].nEnd = nMaxAccess;
37 1051 : }
38 :
39 :
40 : template< typename A, typename D >
41 20 : 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 20 : , nMaxAccess( nMaxAccessP)
48 : {
49 20 : D aValue = pDataArray[0];
50 20500 : for (size_t j=0; j<nDataCount; ++j)
51 : {
52 20480 : if (!(aValue == pDataArray[j]))
53 : {
54 0 : pData[nCount].aValue = aValue;
55 0 : pData[nCount].nEnd = j-1;
56 0 : ++nCount;
57 0 : aValue = pDataArray[j];
58 : }
59 : }
60 20 : pData[nCount].aValue = aValue;
61 20 : pData[nCount].nEnd = nMaxAccess;
62 20 : ++nCount;
63 20 : Resize( nCount);
64 20 : }
65 :
66 :
67 : template< typename A, typename D >
68 920 : ScCompressedArray<A,D>::~ScCompressedArray()
69 : {
70 920 : delete[] pData;
71 1840 : }
72 :
73 :
74 : template< typename A, typename D >
75 20 : void ScCompressedArray<A,D>::Resize( size_t nNewLimit)
76 : {
77 20 : if ((nCount <= nNewLimit && nNewLimit < nLimit) || nLimit < nNewLimit)
78 : {
79 20 : nLimit = nNewLimit;
80 20 : DataEntry* pNewData = new DataEntry[nLimit];
81 20 : memcpy( pNewData, pData, nCount*sizeof(DataEntry));
82 20 : delete[] pData;
83 20 : pData = pNewData;
84 : }
85 20 : }
86 :
87 :
88 : template< typename A, typename D >
89 4167 : size_t ScCompressedArray<A,D>::Search( A nAccess ) const
90 : {
91 4167 : if (nAccess == 0)
92 1875 : return 0;
93 :
94 2292 : long nLo = 0;
95 2292 : long nHi = static_cast<long>(nCount) - 1;
96 2292 : long nStart = 0;
97 2292 : long nEnd = 0;
98 2292 : long i = 0;
99 2292 : bool bFound = (nCount == 1);
100 5856 : while (!bFound && nLo <= nHi)
101 : {
102 1272 : i = (nLo + nHi) / 2;
103 1272 : if (i > 0)
104 1102 : nStart = (long) pData[i - 1].nEnd;
105 : else
106 170 : nStart = -1;
107 1272 : nEnd = (long) pData[i].nEnd;
108 1272 : if (nEnd < (long) nAccess)
109 393 : nLo = ++i;
110 : else
111 879 : if (nStart >= (long) nAccess)
112 75 : nHi = --i;
113 : else
114 804 : bFound = true;
115 : }
116 2292 : return (bFound ? static_cast<size_t>(i) : (nAccess < 0 ? 0 : nCount-1));
117 : }
118 :
119 :
120 : template< typename A, typename D >
121 327 : void ScCompressedArray<A,D>::SetValue( A nStart, A nEnd, const D& rValue )
122 : {
123 327 : if (0 <= nStart && nStart <= nMaxAccess && 0 <= nEnd && nEnd <= nMaxAccess
124 : && nStart <= nEnd)
125 : {
126 327 : if ((nStart == 0) && (nEnd == nMaxAccess))
127 49 : Reset( rValue);
128 : else
129 : {
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 278 : D aNewVal( rValue);
133 278 : size_t nNeeded = nCount + 2;
134 278 : if (nLimit < nNeeded)
135 : {
136 160 : nLimit += nDelta;
137 160 : if (nLimit < nNeeded)
138 0 : nLimit = nNeeded;
139 160 : DataEntry* pNewData = new DataEntry[nLimit];
140 160 : memcpy( pNewData, pData, nCount*sizeof(DataEntry));
141 160 : delete[] pData;
142 160 : pData = pNewData;
143 : }
144 :
145 : size_t ni; // number of leading entries
146 : size_t nInsert; // insert position (nMaxAccess+1 := no insert)
147 278 : bool bCombined = false;
148 278 : bool bSplit = false;
149 278 : if (nStart > 0)
150 : {
151 : // skip leading
152 163 : ni = this->Search( nStart);
153 :
154 163 : nInsert = nMaxAccess+1;
155 163 : if (!(pData[ni].aValue == aNewVal))
156 : {
157 116 : 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 69 : if (pData[ni].nEnd > nEnd)
161 68 : bSplit = true;
162 69 : ni++;
163 69 : nInsert = ni;
164 : }
165 47 : else if (ni > 0 && pData[ni-1].nEnd == nStart - 1)
166 47 : nInsert = ni;
167 : }
168 163 : if (ni > 0 && pData[ni-1].aValue == aNewVal)
169 : { // combine
170 47 : pData[ni-1].nEnd = nEnd;
171 47 : nInsert = nMaxAccess+1;
172 47 : bCombined = true;
173 : }
174 : }
175 : else
176 : {
177 115 : nInsert = 0;
178 115 : ni = 0;
179 : }
180 :
181 278 : size_t nj = ni; // stop position of range to replace
182 566 : while (nj < nCount && pData[nj].nEnd <= nEnd)
183 10 : nj++;
184 278 : if (!bSplit)
185 : {
186 210 : if (nj < nCount && pData[nj].aValue == aNewVal)
187 : { // combine
188 120 : if (ni > 0)
189 : {
190 16 : if (pData[ni-1].aValue == aNewVal)
191 : { // adjacent entries
192 0 : pData[ni-1].nEnd = pData[nj].nEnd;
193 0 : nj++;
194 : }
195 16 : else if (ni == nInsert)
196 1 : pData[ni-1].nEnd = nStart - 1; // shrink
197 : }
198 120 : nInsert = nMaxAccess+1;
199 120 : bCombined = true;
200 : }
201 90 : else if (ni > 0 && ni == nInsert)
202 0 : pData[ni-1].nEnd = nStart - 1; // shrink
203 : }
204 278 : if (ni < nj)
205 : { // remove middle entries
206 10 : if (!bCombined)
207 : { // replace one entry
208 4 : pData[ni].nEnd = nEnd;
209 4 : pData[ni].aValue = aNewVal;
210 4 : ni++;
211 4 : nInsert = nMaxAccess+1;
212 : }
213 10 : if (ni < nj)
214 : { // remove entries
215 6 : memmove( pData + ni, pData + nj,
216 6 : (nCount - nj) * sizeof(DataEntry));
217 6 : nCount -= nj - ni;
218 : }
219 : }
220 :
221 278 : if (nInsert < static_cast<size_t>(nMaxAccess+1))
222 : { // insert or append new entry
223 107 : if (nInsert <= nCount)
224 : {
225 107 : if (!bSplit)
226 39 : memmove( pData + nInsert + 1, pData + nInsert,
227 39 : (nCount - nInsert) * sizeof(DataEntry));
228 : else
229 : {
230 68 : memmove( pData + nInsert + 2, pData + nInsert,
231 68 : (nCount - nInsert) * sizeof(DataEntry));
232 68 : pData[nInsert+1] = pData[nInsert-1];
233 68 : nCount++;
234 : }
235 : }
236 107 : if (nInsert)
237 68 : pData[nInsert-1].nEnd = nStart - 1;
238 107 : pData[nInsert].nEnd = nEnd;
239 107 : pData[nInsert].aValue = aNewVal;
240 107 : nCount++;
241 : }
242 : }
243 : }
244 327 : }
245 :
246 :
247 : template< typename A, typename D >
248 114 : void ScCompressedArray<A,D>::CopyFrom( const ScCompressedArray<A,D>& rArray, A nStart,
249 : A nEnd, long nSourceDy )
250 : {
251 : size_t nIndex;
252 : A nRegionEnd;
253 239 : for (A j=nStart; j<=nEnd; ++j)
254 : {
255 114 : const D& rValue = (j==nStart ?
256 : rArray.GetValue( j+nSourceDy, nIndex, nRegionEnd) :
257 239 : rArray.GetNextValue( nIndex, nRegionEnd));
258 125 : nRegionEnd -= nSourceDy;
259 125 : if (nRegionEnd > nEnd)
260 69 : nRegionEnd = nEnd;
261 125 : this->SetValue( j, nRegionEnd, rValue);
262 125 : j = nRegionEnd;
263 : }
264 114 : }
265 :
266 :
267 : template< typename A, typename D >
268 28 : const D& ScCompressedArray<A,D>::Insert( A nStart, size_t nAccessCount )
269 : {
270 28 : 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 28 : if (nIndex > 0 && pData[nIndex-1].nEnd+1 == nStart)
275 0 : --nIndex;
276 28 : const D& rValue = pData[nIndex].aValue; // the value "copied"
277 28 : do
278 : {
279 28 : pData[nIndex].nEnd += nAccessCount;
280 28 : if (pData[nIndex].nEnd >= nMaxAccess)
281 : {
282 28 : pData[nIndex].nEnd = nMaxAccess;
283 28 : nCount = nIndex + 1; // discard trailing entries
284 : }
285 : } while (++nIndex < nCount);
286 28 : return rValue;
287 : }
288 :
289 :
290 : template< typename A, typename D >
291 27 : void ScCompressedArray<A,D>::Remove( A nStart, size_t nAccessCount )
292 : {
293 27 : A nEnd = nStart + nAccessCount - 1;
294 27 : size_t nIndex = this->Search( nStart);
295 : // equalize/combine/remove all entries in between
296 27 : if (nEnd > pData[nIndex].nEnd)
297 0 : this->SetValue( nStart, nEnd, pData[nIndex].aValue);
298 : // remove an exactly matching entry by shifting up all following by one
299 36 : if ((nStart == 0 || (nIndex > 0 && nStart == pData[nIndex-1].nEnd+1)) &&
300 9 : pData[nIndex].nEnd == nEnd && nIndex < nCount-1)
301 : {
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 0 : if (nIndex > 0 && pData[nIndex-1].aValue == pData[nIndex+1].aValue)
308 : {
309 0 : nRemove = 2;
310 0 : --nIndex;
311 : }
312 : else
313 0 : nRemove = 1;
314 0 : memmove( pData + nIndex, pData + nIndex + nRemove, (nCount - (nIndex +
315 0 : nRemove)) * sizeof(DataEntry));
316 0 : nCount -= nRemove;
317 : }
318 : // adjust end rows, nIndex still being valid
319 27 : do
320 : {
321 27 : pData[nIndex].nEnd -= nAccessCount;
322 : } while (++nIndex < nCount);
323 27 : pData[nCount-1].nEnd = nMaxAccess;
324 27 : }
325 :
326 :
327 : // === ScBitMaskCompressedArray ==============================================
328 :
329 : template< typename A, typename D >
330 96 : void ScBitMaskCompressedArray<A,D>::AndValue( A nStart, A nEnd,
331 : const D& rValueToAnd )
332 : {
333 96 : if (nStart > nEnd)
334 96 : return;
335 :
336 96 : size_t nIndex = this->Search( nStart);
337 0 : do
338 : {
339 96 : if ((this->pData[nIndex].aValue & rValueToAnd) != this->pData[nIndex].aValue)
340 : {
341 0 : A nS = ::std::max( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
342 0 : A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
343 0 : this->SetValue( nS, nE, this->pData[nIndex].aValue & rValueToAnd);
344 0 : if (nE >= nEnd)
345 0 : break; // while
346 0 : nIndex = this->Search( nE + 1);
347 : }
348 96 : else if (this->pData[nIndex].nEnd >= nEnd)
349 96 : break; // while
350 : else
351 0 : ++nIndex;
352 : } while (nIndex < this->nCount);
353 : }
354 :
355 :
356 : template< typename A, typename D >
357 141 : void ScBitMaskCompressedArray<A,D>::OrValue( A nStart, A nEnd,
358 : const D& rValueToOr )
359 : {
360 141 : if (nStart > nEnd)
361 141 : return;
362 :
363 141 : size_t nIndex = this->Search( nStart);
364 0 : do
365 : {
366 141 : if ((this->pData[nIndex].aValue | rValueToOr) != this->pData[nIndex].aValue)
367 : {
368 126 : A nS = ::std::max( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
369 126 : A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
370 126 : this->SetValue( nS, nE, this->pData[nIndex].aValue | rValueToOr);
371 126 : if (nE >= nEnd)
372 126 : break; // while
373 0 : nIndex = this->Search( nE + 1);
374 : }
375 15 : else if (this->pData[nIndex].nEnd >= nEnd)
376 15 : break; // while
377 : else
378 0 : ++nIndex;
379 : } while (nIndex < this->nCount);
380 : }
381 :
382 :
383 : template< typename A, typename D >
384 39 : void ScBitMaskCompressedArray<A,D>::CopyFromAnded(
385 : const ScBitMaskCompressedArray<A,D>& rArray, A nStart, A nEnd,
386 : const D& rValueToAnd, long nSourceDy )
387 : {
388 : size_t nIndex;
389 : A nRegionEnd;
390 103 : for (A j=nStart; j<=nEnd; ++j)
391 : {
392 64 : const D& rValue = (j==nStart ?
393 : rArray.GetValue( j+nSourceDy, nIndex, nRegionEnd) :
394 128 : rArray.GetNextValue( nIndex, nRegionEnd));
395 64 : nRegionEnd -= nSourceDy;
396 64 : if (nRegionEnd > nEnd)
397 39 : nRegionEnd = nEnd;
398 64 : this->SetValue( j, nRegionEnd, rValue & rValueToAnd);
399 64 : j = nRegionEnd;
400 : }
401 39 : }
402 :
403 : template< typename A, typename D >
404 0 : A ScBitMaskCompressedArray<A,D>::GetFirstForCondition( A nStart, A nEnd,
405 : const D& rBitMask, const D& rMaskedCompare ) const
406 : {
407 0 : size_t nIndex = this->Search( nStart);
408 0 : do
409 : {
410 0 : if ((this->pData[nIndex].aValue & rBitMask) == rMaskedCompare)
411 : {
412 0 : A nFound = nIndex > 0 ? this->pData[nIndex-1].nEnd + 1 : 0;
413 0 : return ::std::max( nFound, nStart);
414 : }
415 0 : if (this->pData[nIndex].nEnd >= nEnd)
416 0 : break; // while
417 0 : ++nIndex;
418 : } while (nIndex < this->nCount);
419 0 : return ::std::numeric_limits<A>::max();
420 : }
421 :
422 : template< typename A, typename D >
423 66 : A ScBitMaskCompressedArray<A,D>::GetLastAnyBitAccess( A nStart,
424 : const D& rBitMask ) const
425 : {
426 66 : A nEnd = ::std::numeric_limits<A>::max();
427 66 : size_t nIndex = this->nCount-1;
428 : while (true)
429 : {
430 71 : if ((this->pData[nIndex].aValue & rBitMask) != 0)
431 : {
432 8 : nEnd = this->pData[nIndex].nEnd;
433 8 : break; // while
434 : }
435 : else
436 : {
437 63 : if (nIndex > 0)
438 : {
439 5 : --nIndex;
440 5 : if (this->pData[nIndex].nEnd < nStart)
441 0 : break; // while
442 : }
443 : else
444 58 : break; // while
445 : }
446 : }
447 5 : return nEnd;
448 : }
449 :
450 : // === Force instantiation of specializations ================================
451 :
452 : template class ScCompressedArray< SCROW, sal_uInt8>; // flags, base class
453 : template class ScBitMaskCompressedArray< SCROW, sal_uInt8>; // flags
454 :
455 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
