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 : #include "compressedarray.hxx"
21 : #include "address.hxx"
22 :
23 : #include <algorithm>
24 :
25 : template< typename A, typename D >
26 2544 : ScCompressedArray<A,D>::ScCompressedArray( A nMaxAccessP, const D& rValue,
27 : size_t nDeltaP )
28 : : nCount(1)
29 : , nLimit(1)
30 : , nDelta( nDeltaP > 0 ? nDeltaP : 1)
31 : , pData( new DataEntry[1])
32 2544 : , nMaxAccess( nMaxAccessP)
33 : {
34 2544 : pData[0].aValue = rValue;
35 2544 : pData[0].nEnd = nMaxAccess;
36 2544 : }
37 :
38 : template< typename A, typename D >
39 40 : ScCompressedArray<A,D>::ScCompressedArray( A nMaxAccessP, const D* pDataArray,
40 : size_t nDataCount )
41 : : nCount(0)
42 : , nLimit( nDataCount)
43 : , nDelta( nScCompressedArrayDelta)
44 : , pData( new DataEntry[nDataCount])
45 40 : , nMaxAccess( nMaxAccessP)
46 : {
47 40 : D aValue = pDataArray[0];
48 41000 : for (size_t j=0; j<nDataCount; ++j)
49 : {
50 40960 : if (!(aValue == pDataArray[j]))
51 : {
52 0 : pData[nCount].aValue = aValue;
53 0 : pData[nCount].nEnd = j-1;
54 0 : ++nCount;
55 0 : aValue = pDataArray[j];
56 : }
57 : }
58 40 : pData[nCount].aValue = aValue;
59 40 : pData[nCount].nEnd = nMaxAccess;
60 40 : ++nCount;
61 40 : Resize( nCount);
62 40 : }
63 :
64 : template< typename A, typename D >
65 2580 : ScCompressedArray<A,D>::~ScCompressedArray()
66 : {
67 2580 : delete[] pData;
68 5160 : }
69 :
70 : template< typename A, typename D >
71 40 : void ScCompressedArray<A,D>::Resize( size_t nNewLimit)
72 : {
73 40 : if ((nCount <= nNewLimit && nNewLimit < nLimit) || nLimit < nNewLimit)
74 : {
75 40 : nLimit = nNewLimit;
76 40 : DataEntry* pNewData = new DataEntry[nLimit];
77 40 : memcpy( pNewData, pData, nCount*sizeof(DataEntry));
78 40 : delete[] pData;
79 40 : pData = pNewData;
80 : }
81 40 : }
82 :
83 : template< typename A, typename D >
84 9776 : size_t ScCompressedArray<A,D>::Search( A nAccess ) const
85 : {
86 9776 : if (nAccess == 0)
87 3502 : return 0;
88 :
89 6274 : long nLo = 0;
90 6274 : long nHi = static_cast<long>(nCount) - 1;
91 6274 : long nStart = 0;
92 6274 : long nEnd = 0;
93 6274 : long i = 0;
94 6274 : bool bFound = (nCount == 1);
95 16832 : while (!bFound && nLo <= nHi)
96 : {
97 4284 : i = (nLo + nHi) / 2;
98 4284 : if (i > 0)
99 3082 : nStart = (long) pData[i - 1].nEnd;
100 : else
101 1202 : nStart = -1;
102 4284 : nEnd = (long) pData[i].nEnd;
103 4284 : if (nEnd < (long) nAccess)
104 1656 : nLo = ++i;
105 : else
106 2628 : if (nStart >= (long) nAccess)
107 150 : nHi = --i;
108 : else
109 2478 : bFound = true;
110 : }
111 6274 : return (bFound ? static_cast<size_t>(i) : (nAccess < 0 ? 0 : nCount-1));
112 : }
113 :
114 : template< typename A, typename D >
115 1198 : void ScCompressedArray<A,D>::SetValue( A nStart, A nEnd, const D& rValue )
116 : {
117 1198 : if (0 <= nStart && nStart <= nMaxAccess && 0 <= nEnd && nEnd <= nMaxAccess
118 : && nStart <= nEnd)
119 : {
120 1198 : if ((nStart == 0) && (nEnd == nMaxAccess))
121 106 : Reset( rValue);
122 : else
123 : {
124 : // Create a temporary copy in case we got a reference passed that
125 : // points to a part of the array to be reallocated.
126 1092 : D aNewVal( rValue);
127 1092 : size_t nNeeded = nCount + 2;
128 1092 : if (nLimit < nNeeded)
129 : {
130 412 : nLimit += nDelta;
131 412 : if (nLimit < nNeeded)
132 0 : nLimit = nNeeded;
133 412 : DataEntry* pNewData = new DataEntry[nLimit];
134 412 : memcpy( pNewData, pData, nCount*sizeof(DataEntry));
135 412 : delete[] pData;
136 412 : pData = pNewData;
137 : }
138 :
139 : size_t ni; // number of leading entries
140 : size_t nInsert; // insert position (nMaxAccess+1 := no insert)
141 1092 : bool bCombined = false;
142 1092 : bool bSplit = false;
143 1092 : if (nStart > 0)
144 : {
145 : // skip leading
146 774 : ni = this->Search( nStart);
147 :
148 774 : nInsert = nMaxAccess+1;
149 774 : if (!(pData[ni].aValue == aNewVal))
150 : {
151 662 : if (ni == 0 || (pData[ni-1].nEnd < nStart - 1))
152 : { // may be a split or a simple insert or just a shrink,
153 : // row adjustment is done further down
154 146 : if (pData[ni].nEnd > nEnd)
155 144 : bSplit = true;
156 146 : ni++;
157 146 : nInsert = ni;
158 : }
159 516 : else if (ni > 0 && pData[ni-1].nEnd == nStart - 1)
160 516 : nInsert = ni;
161 : }
162 774 : if (ni > 0 && pData[ni-1].aValue == aNewVal)
163 : { // combine
164 516 : pData[ni-1].nEnd = nEnd;
165 516 : nInsert = nMaxAccess+1;
166 516 : bCombined = true;
167 : }
168 : }
169 : else
170 : {
171 318 : nInsert = 0;
172 318 : ni = 0;
173 : }
174 :
175 1092 : size_t nj = ni; // stop position of range to replace
176 2222 : while (nj < nCount && pData[nj].nEnd <= nEnd)
177 38 : nj++;
178 1092 : if (!bSplit)
179 : {
180 948 : if (nj < nCount && pData[nj].aValue == aNewVal)
181 : { // combine
182 258 : if (ni > 0)
183 : {
184 32 : if (pData[ni-1].aValue == aNewVal)
185 : { // adjacent entries
186 0 : pData[ni-1].nEnd = pData[nj].nEnd;
187 0 : nj++;
188 : }
189 32 : else if (ni == nInsert)
190 2 : pData[ni-1].nEnd = nStart - 1; // shrink
191 : }
192 258 : nInsert = nMaxAccess+1;
193 258 : bCombined = true;
194 : }
195 690 : else if (ni > 0 && ni == nInsert)
196 0 : pData[ni-1].nEnd = nStart - 1; // shrink
197 : }
198 1092 : if (ni < nj)
199 : { // remove middle entries
200 38 : if (!bCombined)
201 : { // replace one entry
202 26 : pData[ni].nEnd = nEnd;
203 26 : pData[ni].aValue = aNewVal;
204 26 : ni++;
205 26 : nInsert = nMaxAccess+1;
206 : }
207 38 : if (ni < nj)
208 : { // remove entries
209 12 : memmove( pData + ni, pData + nj,
210 12 : (nCount - nj) * sizeof(DataEntry));
211 12 : nCount -= nj - ni;
212 : }
213 : }
214 :
215 1092 : if (nInsert < static_cast<size_t>(nMaxAccess+1))
216 : { // insert or append new entry
217 292 : if (nInsert <= nCount)
218 : {
219 292 : if (!bSplit)
220 148 : memmove( pData + nInsert + 1, pData + nInsert,
221 148 : (nCount - nInsert) * sizeof(DataEntry));
222 : else
223 : {
224 144 : memmove( pData + nInsert + 2, pData + nInsert,
225 144 : (nCount - nInsert) * sizeof(DataEntry));
226 144 : pData[nInsert+1] = pData[nInsert-1];
227 144 : nCount++;
228 : }
229 : }
230 292 : if (nInsert)
231 144 : pData[nInsert-1].nEnd = nStart - 1;
232 292 : pData[nInsert].nEnd = nEnd;
233 292 : pData[nInsert].aValue = aNewVal;
234 292 : nCount++;
235 : }
236 : }
237 : }
238 1198 : }
239 :
240 : template< typename A, typename D >
241 246 : void ScCompressedArray<A,D>::CopyFrom( const ScCompressedArray<A,D>& rArray, A nStart,
242 : A nEnd, long nSourceDy )
243 : {
244 246 : size_t nIndex = 0;
245 : A nRegionEnd;
246 532 : for (A j=nStart; j<=nEnd; ++j)
247 : {
248 246 : const D& rValue = (j==nStart ?
249 : rArray.GetValue( j+nSourceDy, nIndex, nRegionEnd) :
250 532 : rArray.GetNextValue( nIndex, nRegionEnd));
251 286 : nRegionEnd -= nSourceDy;
252 286 : if (nRegionEnd > nEnd)
253 130 : nRegionEnd = nEnd;
254 286 : this->SetValue( j, nRegionEnd, rValue);
255 286 : j = nRegionEnd;
256 : }
257 246 : }
258 :
259 : template< typename A, typename D >
260 80 : const D& ScCompressedArray<A,D>::Insert( A nStart, size_t nAccessCount )
261 : {
262 80 : size_t nIndex = this->Search( nStart);
263 : // No real insertion is needed, simply extend the one entry and adapt all
264 : // following. In case nStart points to the start row of an entry, extend
265 : // the previous entry (inserting before nStart).
266 80 : if (nIndex > 0 && pData[nIndex-1].nEnd+1 == nStart)
267 0 : --nIndex;
268 80 : const D& rValue = pData[nIndex].aValue; // the value "copied"
269 80 : do
270 : {
271 80 : pData[nIndex].nEnd += nAccessCount;
272 80 : if (pData[nIndex].nEnd >= nMaxAccess)
273 : {
274 80 : pData[nIndex].nEnd = nMaxAccess;
275 80 : nCount = nIndex + 1; // discard trailing entries
276 : }
277 : } while (++nIndex < nCount);
278 80 : return rValue;
279 : }
280 :
281 : template< typename A, typename D >
282 72 : void ScCompressedArray<A,D>::Remove( A nStart, size_t nAccessCount )
283 : {
284 72 : A nEnd = nStart + nAccessCount - 1;
285 72 : size_t nIndex = this->Search( nStart);
286 : // equalize/combine/remove all entries in between
287 72 : if (nEnd > pData[nIndex].nEnd)
288 0 : this->SetValue( nStart, nEnd, pData[nIndex].aValue);
289 : // remove an exactly matching entry by shifting up all following by one
290 90 : if ((nStart == 0 || (nIndex > 0 && nStart == pData[nIndex-1].nEnd+1)) &&
291 18 : pData[nIndex].nEnd == nEnd && nIndex < nCount-1)
292 : {
293 : // In case removing an entry results in two adjacent entries with
294 : // identical data, combine them into one. This is also necessary to
295 : // make the algorithm used in SetValue() work correctly, it relies on
296 : // the fact that consecutive values actually differ.
297 : size_t nRemove;
298 0 : if (nIndex > 0 && pData[nIndex-1].aValue == pData[nIndex+1].aValue)
299 : {
300 0 : nRemove = 2;
301 0 : --nIndex;
302 : }
303 : else
304 0 : nRemove = 1;
305 0 : memmove( pData + nIndex, pData + nIndex + nRemove, (nCount - (nIndex +
306 0 : nRemove)) * sizeof(DataEntry));
307 0 : nCount -= nRemove;
308 : }
309 : // adjust end rows, nIndex still being valid
310 72 : do
311 : {
312 72 : pData[nIndex].nEnd -= nAccessCount;
313 : } while (++nIndex < nCount);
314 72 : pData[nCount-1].nEnd = nMaxAccess;
315 72 : }
316 :
317 : // === ScBitMaskCompressedArray ==============================================
318 :
319 : template< typename A, typename D >
320 228 : void ScBitMaskCompressedArray<A,D>::AndValue( A nStart, A nEnd,
321 : const D& rValueToAnd )
322 : {
323 228 : if (nStart > nEnd)
324 228 : return;
325 :
326 228 : size_t nIndex = this->Search( nStart);
327 0 : do
328 : {
329 228 : if ((this->pData[nIndex].aValue & rValueToAnd) != this->pData[nIndex].aValue)
330 : {
331 0 : A nS = ::std::max( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
332 0 : A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
333 0 : this->SetValue( nS, nE, this->pData[nIndex].aValue & rValueToAnd);
334 0 : if (nE >= nEnd)
335 0 : break; // while
336 0 : nIndex = this->Search( nE + 1);
337 : }
338 228 : else if (this->pData[nIndex].nEnd >= nEnd)
339 228 : break; // while
340 : else
341 0 : ++nIndex;
342 : } while (nIndex < this->nCount);
343 : }
344 :
345 : template< typename A, typename D >
346 764 : void ScBitMaskCompressedArray<A,D>::OrValue( A nStart, A nEnd,
347 : const D& rValueToOr )
348 : {
349 764 : if (nStart > nEnd)
350 764 : return;
351 :
352 764 : size_t nIndex = this->Search( nStart);
353 0 : do
354 : {
355 764 : if ((this->pData[nIndex].aValue | rValueToOr) != this->pData[nIndex].aValue)
356 : {
357 734 : A nS = ::std::max( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
358 734 : A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
359 734 : this->SetValue( nS, nE, this->pData[nIndex].aValue | rValueToOr);
360 734 : if (nE >= nEnd)
361 734 : break; // while
362 0 : nIndex = this->Search( nE + 1);
363 : }
364 30 : else if (this->pData[nIndex].nEnd >= nEnd)
365 30 : break; // while
366 : else
367 0 : ++nIndex;
368 : } while (nIndex < this->nCount);
369 : }
370 :
371 : template< typename A, typename D >
372 104 : void ScBitMaskCompressedArray<A,D>::CopyFromAnded(
373 : const ScBitMaskCompressedArray<A,D>& rArray, A nStart, A nEnd,
374 : const D& rValueToAnd, long nSourceDy )
375 : {
376 104 : size_t nIndex = 0;
377 : A nRegionEnd;
378 258 : for (A j=nStart; j<=nEnd; ++j)
379 : {
380 154 : const D& rValue = (j==nStart ?
381 : rArray.GetValue( j+nSourceDy, nIndex, nRegionEnd) :
382 308 : rArray.GetNextValue( nIndex, nRegionEnd));
383 154 : nRegionEnd -= nSourceDy;
384 154 : if (nRegionEnd > nEnd)
385 104 : nRegionEnd = nEnd;
386 154 : this->SetValue( j, nRegionEnd, rValue & rValueToAnd);
387 154 : j = nRegionEnd;
388 : }
389 104 : }
390 :
391 : template< typename A, typename D >
392 180 : A ScBitMaskCompressedArray<A,D>::GetLastAnyBitAccess( A nStart,
393 : const D& rBitMask ) const
394 : {
395 180 : A nEnd = ::std::numeric_limits<A>::max();
396 180 : size_t nIndex = this->nCount-1;
397 : while (true)
398 : {
399 190 : if ((this->pData[nIndex].aValue & rBitMask) != 0)
400 : {
401 16 : nEnd = this->pData[nIndex].nEnd;
402 16 : break; // while
403 : }
404 : else
405 : {
406 174 : if (nIndex > 0)
407 : {
408 10 : --nIndex;
409 10 : if (this->pData[nIndex].nEnd < nStart)
410 0 : break; // while
411 : }
412 : else
413 164 : break; // while
414 : }
415 : }
416 10 : return nEnd;
417 : }
418 :
419 : // === Force instantiation of specializations ================================
420 :
421 : template class ScCompressedArray< SCROW, sal_uInt8>; // flags, base class
422 : template class ScBitMaskCompressedArray< SCROW, sal_uInt8>; // flags
423 :
424 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
