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 0 : 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 0 : , nMaxAccess( nMaxAccessP)
34 : {
35 0 : pData[0].aValue = rValue;
36 0 : pData[0].nEnd = nMaxAccess;
37 0 : }
38 :
39 :
40 : template< typename A, typename D >
41 0 : 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 0 : , nMaxAccess( nMaxAccessP)
48 : {
49 0 : D aValue = pDataArray[0];
50 0 : for (size_t j=0; j<nDataCount; ++j)
51 : {
52 0 : 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 0 : pData[nCount].aValue = aValue;
61 0 : pData[nCount].nEnd = nMaxAccess;
62 0 : ++nCount;
63 0 : Resize( nCount);
64 0 : }
65 :
66 :
67 : template< typename A, typename D >
68 0 : ScCompressedArray<A,D>::~ScCompressedArray()
69 : {
70 0 : delete[] pData;
71 0 : }
72 :
73 :
74 : template< typename A, typename D >
75 0 : void ScCompressedArray<A,D>::Resize( size_t nNewLimit)
76 : {
77 0 : if ((nCount <= nNewLimit && nNewLimit < nLimit) || nLimit < nNewLimit)
78 : {
79 0 : nLimit = nNewLimit;
80 0 : DataEntry* pNewData = new DataEntry[nLimit];
81 0 : memcpy( pNewData, pData, nCount*sizeof(DataEntry));
82 0 : delete[] pData;
83 0 : pData = pNewData;
84 : }
85 0 : }
86 :
87 :
88 : template< typename A, typename D >
89 0 : size_t ScCompressedArray<A,D>::Search( A nAccess ) const
90 : {
91 0 : if (nAccess == 0)
92 0 : return 0;
93 :
94 0 : long nLo = 0;
95 0 : long nHi = static_cast<long>(nCount) - 1;
96 0 : long nStart = 0;
97 0 : long nEnd = 0;
98 0 : long i = 0;
99 0 : bool bFound = (nCount == 1);
100 0 : while (!bFound && nLo <= nHi)
101 : {
102 0 : i = (nLo + nHi) / 2;
103 0 : if (i > 0)
104 0 : nStart = (long) pData[i - 1].nEnd;
105 : else
106 0 : nStart = -1;
107 0 : nEnd = (long) pData[i].nEnd;
108 0 : if (nEnd < (long) nAccess)
109 0 : nLo = ++i;
110 : else
111 0 : if (nStart >= (long) nAccess)
112 0 : nHi = --i;
113 : else
114 0 : bFound = true;
115 : }
116 0 : return (bFound ? static_cast<size_t>(i) : (nAccess < 0 ? 0 : nCount-1));
117 : }
118 :
119 :
120 : template< typename A, typename D >
121 0 : void ScCompressedArray<A,D>::SetValue( A nStart, A nEnd, const D& rValue )
122 : {
123 0 : if (0 <= nStart && nStart <= nMaxAccess && 0 <= nEnd && nEnd <= nMaxAccess
124 : && nStart <= nEnd)
125 : {
126 0 : if ((nStart == 0) && (nEnd == nMaxAccess))
127 0 : 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 0 : D aNewVal( rValue);
133 0 : size_t nNeeded = nCount + 2;
134 0 : if (nLimit < nNeeded)
135 : {
136 0 : nLimit += nDelta;
137 0 : if (nLimit < nNeeded)
138 0 : nLimit = nNeeded;
139 0 : DataEntry* pNewData = new DataEntry[nLimit];
140 0 : memcpy( pNewData, pData, nCount*sizeof(DataEntry));
141 0 : delete[] pData;
142 0 : pData = pNewData;
143 : }
144 :
145 : size_t ni; // number of leading entries
146 : size_t nInsert; // insert position (nMaxAccess+1 := no insert)
147 0 : bool bCombined = false;
148 0 : bool bSplit = false;
149 0 : if (nStart > 0)
150 : {
151 : // skip leading
152 0 : ni = this->Search( nStart);
153 :
154 0 : nInsert = nMaxAccess+1;
155 0 : if (!(pData[ni].aValue == aNewVal))
156 : {
157 0 : 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 0 : if (pData[ni].nEnd > nEnd)
161 0 : bSplit = true;
162 0 : ni++;
163 0 : nInsert = ni;
164 : }
165 0 : else if (ni > 0 && pData[ni-1].nEnd == nStart - 1)
166 0 : nInsert = ni;
167 : }
168 0 : if (ni > 0 && pData[ni-1].aValue == aNewVal)
169 : { // combine
170 0 : pData[ni-1].nEnd = nEnd;
171 0 : nInsert = nMaxAccess+1;
172 0 : bCombined = true;
173 : }
174 : }
175 : else
176 : {
177 0 : nInsert = 0;
178 0 : ni = 0;
179 : }
180 :
181 0 : size_t nj = ni; // stop position of range to replace
182 0 : while (nj < nCount && pData[nj].nEnd <= nEnd)
183 0 : nj++;
184 0 : if (!bSplit)
185 : {
186 0 : if (nj < nCount && pData[nj].aValue == aNewVal)
187 : { // combine
188 0 : if (ni > 0)
189 : {
190 0 : if (pData[ni-1].aValue == aNewVal)
191 : { // adjacent entries
192 0 : pData[ni-1].nEnd = pData[nj].nEnd;
193 0 : nj++;
194 : }
195 0 : else if (ni == nInsert)
196 0 : pData[ni-1].nEnd = nStart - 1; // shrink
197 : }
198 0 : nInsert = nMaxAccess+1;
199 0 : bCombined = true;
200 : }
201 0 : else if (ni > 0 && ni == nInsert)
202 0 : pData[ni-1].nEnd = nStart - 1; // shrink
203 : }
204 0 : if (ni < nj)
205 : { // remove middle entries
206 0 : if (!bCombined)
207 : { // replace one entry
208 0 : pData[ni].nEnd = nEnd;
209 0 : pData[ni].aValue = aNewVal;
210 0 : ni++;
211 0 : nInsert = nMaxAccess+1;
212 : }
213 0 : if (ni < nj)
214 : { // remove entries
215 0 : memmove( pData + ni, pData + nj,
216 0 : (nCount - nj) * sizeof(DataEntry));
217 0 : nCount -= nj - ni;
218 : }
219 : }
220 :
221 0 : if (nInsert < static_cast<size_t>(nMaxAccess+1))
222 : { // insert or append new entry
223 0 : if (nInsert <= nCount)
224 : {
225 0 : if (!bSplit)
226 0 : memmove( pData + nInsert + 1, pData + nInsert,
227 0 : (nCount - nInsert) * sizeof(DataEntry));
228 : else
229 : {
230 0 : memmove( pData + nInsert + 2, pData + nInsert,
231 0 : (nCount - nInsert) * sizeof(DataEntry));
232 0 : pData[nInsert+1] = pData[nInsert-1];
233 0 : nCount++;
234 : }
235 : }
236 0 : if (nInsert)
237 0 : pData[nInsert-1].nEnd = nStart - 1;
238 0 : pData[nInsert].nEnd = nEnd;
239 0 : pData[nInsert].aValue = aNewVal;
240 0 : nCount++;
241 : }
242 : }
243 : }
244 0 : }
245 :
246 :
247 : template< typename A, typename D >
248 0 : 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 0 : for (A j=nStart; j<=nEnd; ++j)
254 : {
255 0 : const D& rValue = (j==nStart ?
256 : rArray.GetValue( j+nSourceDy, nIndex, nRegionEnd) :
257 0 : rArray.GetNextValue( nIndex, nRegionEnd));
258 0 : nRegionEnd -= nSourceDy;
259 0 : if (nRegionEnd > nEnd)
260 0 : nRegionEnd = nEnd;
261 0 : this->SetValue( j, nRegionEnd, rValue);
262 0 : j = nRegionEnd;
263 : }
264 0 : }
265 :
266 :
267 : template< typename A, typename D >
268 0 : const D& ScCompressedArray<A,D>::Insert( A nStart, size_t nAccessCount )
269 : {
270 0 : 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 0 : if (nIndex > 0 && pData[nIndex-1].nEnd+1 == nStart)
275 0 : --nIndex;
276 0 : const D& rValue = pData[nIndex].aValue; // the value "copied"
277 0 : do
278 : {
279 0 : pData[nIndex].nEnd += nAccessCount;
280 0 : if (pData[nIndex].nEnd >= nMaxAccess)
281 : {
282 0 : pData[nIndex].nEnd = nMaxAccess;
283 0 : nCount = nIndex + 1; // discard trailing entries
284 : }
285 : } while (++nIndex < nCount);
286 0 : return rValue;
287 : }
288 :
289 :
290 : template< typename A, typename D >
291 0 : void ScCompressedArray<A,D>::Remove( A nStart, size_t nAccessCount )
292 : {
293 0 : A nEnd = nStart + nAccessCount - 1;
294 0 : size_t nIndex = this->Search( nStart);
295 : // equalize/combine/remove all entries in between
296 0 : 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 0 : if ((nStart == 0 || (nIndex > 0 && nStart == pData[nIndex-1].nEnd+1)) &&
300 0 : 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 0 : do
320 : {
321 0 : pData[nIndex].nEnd -= nAccessCount;
322 : } while (++nIndex < nCount);
323 0 : pData[nCount-1].nEnd = nMaxAccess;
324 0 : }
325 :
326 :
327 : // === ScBitMaskCompressedArray ==============================================
328 :
329 : template< typename A, typename D >
330 0 : void ScBitMaskCompressedArray<A,D>::AndValue( A nStart, A nEnd,
331 : const D& rValueToAnd )
332 : {
333 0 : if (nStart > nEnd)
334 0 : return;
335 :
336 0 : size_t nIndex = this->Search( nStart);
337 0 : do
338 : {
339 0 : 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 0 : else if (this->pData[nIndex].nEnd >= nEnd)
349 0 : break; // while
350 : else
351 0 : ++nIndex;
352 : } while (nIndex < this->nCount);
353 : }
354 :
355 :
356 : template< typename A, typename D >
357 0 : void ScBitMaskCompressedArray<A,D>::OrValue( A nStart, A nEnd,
358 : const D& rValueToOr )
359 : {
360 0 : if (nStart > nEnd)
361 0 : return;
362 :
363 0 : size_t nIndex = this->Search( nStart);
364 0 : do
365 : {
366 0 : if ((this->pData[nIndex].aValue | rValueToOr) != this->pData[nIndex].aValue)
367 : {
368 0 : A nS = ::std::max( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
369 0 : A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
370 0 : this->SetValue( nS, nE, this->pData[nIndex].aValue | rValueToOr);
371 0 : if (nE >= nEnd)
372 0 : break; // while
373 0 : nIndex = this->Search( nE + 1);
374 : }
375 0 : else if (this->pData[nIndex].nEnd >= nEnd)
376 0 : break; // while
377 : else
378 0 : ++nIndex;
379 : } while (nIndex < this->nCount);
380 : }
381 :
382 :
383 : template< typename A, typename D >
384 0 : 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 0 : for (A j=nStart; j<=nEnd; ++j)
391 : {
392 0 : const D& rValue = (j==nStart ?
393 : rArray.GetValue( j+nSourceDy, nIndex, nRegionEnd) :
394 0 : rArray.GetNextValue( nIndex, nRegionEnd));
395 0 : nRegionEnd -= nSourceDy;
396 0 : if (nRegionEnd > nEnd)
397 0 : nRegionEnd = nEnd;
398 0 : this->SetValue( j, nRegionEnd, rValue & rValueToAnd);
399 0 : j = nRegionEnd;
400 : }
401 0 : }
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 0 : A ScBitMaskCompressedArray<A,D>::GetLastAnyBitAccess( A nStart,
424 : const D& rBitMask ) const
425 : {
426 0 : A nEnd = ::std::numeric_limits<A>::max();
427 0 : size_t nIndex = this->nCount-1;
428 : while (true)
429 : {
430 0 : if ((this->pData[nIndex].aValue & rBitMask) != 0)
431 : {
432 0 : nEnd = this->pData[nIndex].nEnd;
433 0 : break; // while
434 : }
435 : else
436 : {
437 0 : if (nIndex > 0)
438 : {
439 0 : --nIndex;
440 0 : if (this->pData[nIndex].nEnd < nStart)
441 0 : break; // while
442 : }
443 : else
444 0 : break; // while
445 : }
446 : }
447 0 : 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: */
|
