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 1513 : 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 1513 : , nMaxAccess( nMaxAccessP)
33 : {
34 1513 : pData[0].aValue = rValue;
35 1513 : pData[0].nEnd = nMaxAccess;
36 1513 : }
37 :
38 : template< typename A, typename D >
39 20 : 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 20 : , nMaxAccess( nMaxAccessP)
46 : {
47 20 : D aValue = pDataArray[0];
48 20500 : for (size_t j=0; j<nDataCount; ++j)
49 : {
50 20480 : 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 20 : pData[nCount].aValue = aValue;
59 20 : pData[nCount].nEnd = nMaxAccess;
60 20 : ++nCount;
61 20 : Resize( nCount);
62 20 : }
63 :
64 : template< typename A, typename D >
65 1512 : ScCompressedArray<A,D>::~ScCompressedArray()
66 : {
67 1512 : delete[] pData;
68 3024 : }
69 :
70 : template< typename A, typename D >
71 20 : void ScCompressedArray<A,D>::Resize( size_t nNewLimit)
72 : {
73 20 : if ((nCount <= nNewLimit && nNewLimit < nLimit) || nLimit < nNewLimit)
74 : {
75 20 : nLimit = nNewLimit;
76 20 : DataEntry* pNewData = new DataEntry[nLimit];
77 20 : memcpy( pNewData, pData, nCount*sizeof(DataEntry));
78 20 : delete[] pData;
79 20 : pData = pNewData;
80 : }
81 20 : }
82 :
83 : template< typename A, typename D >
84 4650 : size_t ScCompressedArray<A,D>::Search( A nAccess ) const
85 : {
86 4650 : if (nAccess == 0)
87 1305 : return 0;
88 :
89 3345 : long nLo = 0;
90 3345 : long nHi = static_cast<long>(nCount) - 1;
91 3345 : long nStart = 0;
92 3345 : long nEnd = 0;
93 3345 : long i = 0;
94 3345 : bool bFound = (nCount == 1);
95 8916 : while (!bFound && nLo <= nHi)
96 : {
97 2226 : i = (nLo + nHi) / 2;
98 2226 : if (i > 0)
99 1583 : nStart = static_cast<long>(pData[i - 1].nEnd);
100 : else
101 643 : nStart = -1;
102 2226 : nEnd = static_cast<long>(pData[i].nEnd);
103 2226 : if (nEnd < static_cast<long>(nAccess))
104 870 : nLo = ++i;
105 : else
106 1356 : if (nStart >= static_cast<long>(nAccess))
107 75 : nHi = --i;
108 : else
109 1281 : bFound = true;
110 : }
111 3345 : return (bFound ? static_cast<size_t>(i) : (nAccess < 0 ? 0 : nCount-1));
112 : }
113 :
114 : template< typename A, typename D >
115 630 : void ScCompressedArray<A,D>::SetValue( A nStart, A nEnd, const D& rValue )
116 : {
117 630 : if (0 <= nStart && nStart <= nMaxAccess && 0 <= nEnd && nEnd <= nMaxAccess
118 : && nStart <= nEnd)
119 : {
120 630 : if ((nStart == 0) && (nEnd == nMaxAccess))
121 54 : 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 576 : D aNewVal( rValue);
127 576 : size_t nNeeded = nCount + 2;
128 576 : if (nLimit < nNeeded)
129 : {
130 215 : nLimit += nDelta;
131 215 : if (nLimit < nNeeded)
132 0 : nLimit = nNeeded;
133 215 : DataEntry* pNewData = new DataEntry[nLimit];
134 215 : memcpy( pNewData, pData, nCount*sizeof(DataEntry));
135 215 : delete[] pData;
136 215 : pData = pNewData;
137 : }
138 :
139 : size_t ni; // number of leading entries
140 : size_t nInsert; // insert position (nMaxAccess+1 := no insert)
141 576 : bool bCombined = false;
142 576 : bool bSplit = false;
143 576 : if (nStart > 0)
144 : {
145 : // skip leading
146 411 : ni = this->Search( nStart);
147 :
148 411 : nInsert = nMaxAccess+1;
149 411 : if (!(pData[ni].aValue == aNewVal))
150 : {
151 353 : 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 74 : if (pData[ni].nEnd > nEnd)
155 73 : bSplit = true;
156 74 : ni++;
157 74 : nInsert = ni;
158 : }
159 279 : else if (ni > 0 && pData[ni-1].nEnd == nStart - 1)
160 279 : nInsert = ni;
161 : }
162 411 : if (ni > 0 && pData[ni-1].aValue == aNewVal)
163 : { // combine
164 279 : pData[ni-1].nEnd = nEnd;
165 279 : nInsert = nMaxAccess+1;
166 279 : bCombined = true;
167 : }
168 : }
169 : else
170 : {
171 165 : nInsert = 0;
172 165 : ni = 0;
173 : }
174 :
175 576 : size_t nj = ni; // stop position of range to replace
176 1171 : while (nj < nCount && pData[nj].nEnd <= nEnd)
177 19 : nj++;
178 576 : if (!bSplit)
179 : {
180 503 : if (nj < nCount && pData[nj].aValue == aNewVal)
181 : { // combine
182 136 : if (ni > 0)
183 : {
184 16 : if (pData[ni-1].aValue == aNewVal)
185 : { // adjacent entries
186 0 : pData[ni-1].nEnd = pData[nj].nEnd;
187 0 : nj++;
188 : }
189 16 : else if (ni == nInsert)
190 1 : pData[ni-1].nEnd = nStart - 1; // shrink
191 : }
192 136 : nInsert = nMaxAccess+1;
193 136 : bCombined = true;
194 : }
195 367 : else if (ni > 0 && ni == nInsert)
196 0 : pData[ni-1].nEnd = nStart - 1; // shrink
197 : }
198 576 : if (ni < nj)
199 : { // remove middle entries
200 19 : if (!bCombined)
201 : { // replace one entry
202 13 : pData[ni].nEnd = nEnd;
203 13 : pData[ni].aValue = aNewVal;
204 13 : ni++;
205 13 : nInsert = nMaxAccess+1;
206 : }
207 19 : if (ni < nj)
208 : { // remove entries
209 6 : memmove( pData + ni, pData + nj,
210 6 : (nCount - nj) * sizeof(DataEntry));
211 6 : nCount -= nj - ni;
212 : }
213 : }
214 :
215 576 : if (nInsert < static_cast<size_t>(nMaxAccess+1))
216 : { // insert or append new entry
217 148 : if (nInsert <= nCount)
218 : {
219 148 : if (!bSplit)
220 75 : memmove( pData + nInsert + 1, pData + nInsert,
221 75 : (nCount - nInsert) * sizeof(DataEntry));
222 : else
223 : {
224 73 : memmove( pData + nInsert + 2, pData + nInsert,
225 73 : (nCount - nInsert) * sizeof(DataEntry));
226 73 : pData[nInsert+1] = pData[nInsert-1];
227 73 : nCount++;
228 : }
229 : }
230 148 : if (nInsert)
231 73 : pData[nInsert-1].nEnd = nStart - 1;
232 148 : pData[nInsert].nEnd = nEnd;
233 148 : pData[nInsert].aValue = aNewVal;
234 148 : nCount++;
235 : }
236 : }
237 : }
238 630 : }
239 :
240 : template< typename A, typename D >
241 127 : void ScCompressedArray<A,D>::CopyFrom( const ScCompressedArray<A,D>& rArray, A nStart,
242 : A nEnd, long nSourceDy )
243 : {
244 127 : size_t nIndex = 0;
245 : A nRegionEnd;
246 274 : for (A j=nStart; j<=nEnd; ++j)
247 : {
248 127 : const D& rValue = (j==nStart ?
249 : rArray.GetValue( j+nSourceDy, nIndex, nRegionEnd) :
250 274 : rArray.GetNextValue( nIndex, nRegionEnd));
251 147 : nRegionEnd -= nSourceDy;
252 147 : if (nRegionEnd > nEnd)
253 68 : nRegionEnd = nEnd;
254 147 : this->SetValue( j, nRegionEnd, rValue);
255 147 : j = nRegionEnd;
256 : }
257 127 : }
258 :
259 : template< typename A, typename D >
260 45 : const D& ScCompressedArray<A,D>::Insert( A nStart, size_t nAccessCount )
261 : {
262 45 : 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 45 : if (nIndex > 0 && pData[nIndex-1].nEnd+1 == nStart)
267 0 : --nIndex;
268 45 : const D& rValue = pData[nIndex].aValue; // the value "copied"
269 45 : do
270 : {
271 45 : pData[nIndex].nEnd += nAccessCount;
272 45 : if (pData[nIndex].nEnd >= nMaxAccess)
273 : {
274 45 : pData[nIndex].nEnd = nMaxAccess;
275 45 : nCount = nIndex + 1; // discard trailing entries
276 : }
277 : } while (++nIndex < nCount);
278 45 : return rValue;
279 : }
280 :
281 : template< typename A, typename D >
282 40 : void ScCompressedArray<A,D>::Remove( A nStart, size_t nAccessCount )
283 : {
284 40 : A nEnd = nStart + nAccessCount - 1;
285 40 : size_t nIndex = this->Search( nStart);
286 : // equalize/combine/remove all entries in between
287 40 : 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 50 : if ((nStart == 0 || (nIndex > 0 && nStart == pData[nIndex-1].nEnd+1)) &&
291 10 : 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 40 : do
311 : {
312 40 : pData[nIndex].nEnd -= nAccessCount;
313 : } while (++nIndex < nCount);
314 40 : pData[nCount-1].nEnd = nMaxAccess;
315 40 : }
316 :
317 : // === ScBitMaskCompressedArray ==============================================
318 :
319 : template< typename A, typename D >
320 129 : void ScBitMaskCompressedArray<A,D>::AndValue( A nStart, A nEnd,
321 : const D& rValueToAnd )
322 : {
323 129 : if (nStart > nEnd)
324 129 : return;
325 :
326 129 : size_t nIndex = this->Search( nStart);
327 0 : do
328 : {
329 129 : 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 129 : else if (this->pData[nIndex].nEnd >= nEnd)
339 129 : break; // while
340 : else
341 0 : ++nIndex;
342 : } while (nIndex < this->nCount);
343 : }
344 :
345 : template< typename A, typename D >
346 405 : void ScBitMaskCompressedArray<A,D>::OrValue( A nStart, A nEnd,
347 : const D& rValueToOr )
348 : {
349 405 : if (nStart > nEnd)
350 405 : return;
351 :
352 405 : size_t nIndex = this->Search( nStart);
353 0 : do
354 : {
355 405 : if ((this->pData[nIndex].aValue | rValueToOr) != this->pData[nIndex].aValue)
356 : {
357 390 : A nS = ::std::max( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
358 390 : A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
359 390 : this->SetValue( nS, nE, this->pData[nIndex].aValue | rValueToOr);
360 390 : if (nE >= nEnd)
361 390 : break; // while
362 0 : nIndex = this->Search( nE + 1);
363 : }
364 15 : else if (this->pData[nIndex].nEnd >= nEnd)
365 15 : break; // while
366 : else
367 0 : ++nIndex;
368 : } while (nIndex < this->nCount);
369 : }
370 :
371 : template< typename A, typename D >
372 56 : void ScBitMaskCompressedArray<A,D>::CopyFromAnded(
373 : const ScBitMaskCompressedArray<A,D>& rArray, A nStart, A nEnd,
374 : const D& rValueToAnd, long nSourceDy )
375 : {
376 56 : size_t nIndex = 0;
377 : A nRegionEnd;
378 137 : for (A j=nStart; j<=nEnd; ++j)
379 : {
380 81 : const D& rValue = (j==nStart ?
381 : rArray.GetValue( j+nSourceDy, nIndex, nRegionEnd) :
382 162 : rArray.GetNextValue( nIndex, nRegionEnd));
383 81 : nRegionEnd -= nSourceDy;
384 81 : if (nRegionEnd > nEnd)
385 56 : nRegionEnd = nEnd;
386 81 : this->SetValue( j, nRegionEnd, rValue & rValueToAnd);
387 81 : j = nRegionEnd;
388 : }
389 56 : }
390 :
391 : template< typename A, typename D >
392 162 : A ScBitMaskCompressedArray<A,D>::GetLastAnyBitAccess( A nStart,
393 : const D& rBitMask ) const
394 : {
395 162 : A nEnd = ::std::numeric_limits<A>::max();
396 162 : size_t nIndex = this->nCount-1;
397 : while (true)
398 : {
399 167 : if ((this->pData[nIndex].aValue & rBitMask) != 0)
400 : {
401 8 : nEnd = this->pData[nIndex].nEnd;
402 8 : break; // while
403 : }
404 : else
405 : {
406 159 : if (nIndex > 0)
407 : {
408 5 : --nIndex;
409 5 : if (this->pData[nIndex].nEnd < nStart)
410 0 : break; // while
411 : }
412 : else
413 154 : break; // while
414 : }
415 : }
416 5 : 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: */
|
