Branch data Line data Source code
1 : : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : : /*************************************************************************
3 : : *
4 : : * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 : : *
6 : : * Copyright 2000, 2010 Oracle and/or its affiliates.
7 : : *
8 : : * OpenOffice.org - a multi-platform office productivity suite
9 : : *
10 : : * This file is part of OpenOffice.org.
11 : : *
12 : : * OpenOffice.org is free software: you can redistribute it and/or modify
13 : : * it under the terms of the GNU Lesser General Public License version 3
14 : : * only, as published by the Free Software Foundation.
15 : : *
16 : : * OpenOffice.org is distributed in the hope that it will be useful,
17 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 : : * GNU Lesser General Public License version 3 for more details
20 : : * (a copy is included in the LICENSE file that accompanied this code).
21 : : *
22 : : * You should have received a copy of the GNU Lesser General Public License
23 : : * version 3 along with OpenOffice.org. If not, see
24 : : * <http://www.openoffice.org/license.html>
25 : : * for a copy of the LGPLv3 License.
26 : : *
27 : : ************************************************************************/
28 : :
29 : :
30 : : #include "compressedarray.hxx"
31 : : #include "address.hxx"
32 : :
33 : : #include <algorithm>
34 : :
35 : : template< typename A, typename D >
36 : 1488 : ScCompressedArray<A,D>::ScCompressedArray( A nMaxAccessP, const D& rValue,
37 : : size_t nDeltaP )
38 : : : nCount(1)
39 : : , nLimit(1)
40 : : , nDelta( nDeltaP > 0 ? nDeltaP : 1)
41 : : , pData( new DataEntry[1])
42 [ + - ][ + - ]: 2976 : , nMaxAccess( nMaxAccessP)
[ + + ]
43 : : {
44 : 1488 : pData[0].aValue = rValue;
45 : 1488 : pData[0].nEnd = nMaxAccess;
46 : 1488 : }
47 : :
48 : :
49 : : template< typename A, typename D >
50 : 0 : ScCompressedArray<A,D>::ScCompressedArray( A nMaxAccessP, const D* pDataArray,
51 : : size_t nDataCount )
52 : : : nCount(0)
53 : : , nLimit( nDataCount)
54 : : , nDelta( nScCompressedArrayDelta)
55 : : , pData( new DataEntry[nDataCount])
56 [ # # ][ # # ]: 0 : , nMaxAccess( nMaxAccessP)
57 : : {
58 : 0 : D aValue = pDataArray[0];
59 [ # # ]: 0 : for (size_t j=0; j<nDataCount; ++j)
60 : : {
61 [ # # ]: 0 : if (!(aValue == pDataArray[j]))
62 : : {
63 : 0 : pData[nCount].aValue = aValue;
64 : 0 : pData[nCount].nEnd = j-1;
65 : 0 : ++nCount;
66 : 0 : aValue = pDataArray[j];
67 : : }
68 : : }
69 : 0 : pData[nCount].aValue = aValue;
70 : 0 : pData[nCount].nEnd = nMaxAccess;
71 : 0 : ++nCount;
72 : 0 : Resize( nCount);
73 : 0 : }
74 : :
75 : :
76 : : template< typename A, typename D >
77 : 1206 : ScCompressedArray<A,D>::~ScCompressedArray()
78 : : {
79 [ + - ][ - + ]: 1206 : delete[] pData;
80 : 1206 : }
81 : :
82 : :
83 : : template< typename A, typename D >
84 : 0 : void ScCompressedArray<A,D>::Resize( size_t nNewLimit)
85 : : {
86 [ # # ][ # # ]: 0 : if ((nCount <= nNewLimit && nNewLimit < nLimit) || nLimit < nNewLimit)
[ # # ]
87 : : {
88 : 0 : nLimit = nNewLimit;
89 [ # # ][ # # ]: 0 : DataEntry* pNewData = new DataEntry[nLimit];
90 : 0 : memcpy( pNewData, pData, nCount*sizeof(DataEntry));
91 [ # # ]: 0 : delete[] pData;
92 : 0 : pData = pNewData;
93 : : }
94 : 0 : }
95 : :
96 : :
97 : : template< typename A, typename D >
98 : 5591 : size_t ScCompressedArray<A,D>::Search( A nAccess ) const
99 : : {
100 [ + + ]: 5591 : if (nAccess == 0)
101 : 2546 : return 0;
102 : :
103 : 3045 : long nLo = 0;
104 : 3045 : long nHi = static_cast<long>(nCount) - 1;
105 : 3045 : long nStart = 0;
106 : 3045 : long nEnd = 0;
107 : 3045 : long i = 0;
108 : 3045 : bool bFound = (nCount == 1);
109 [ + + ][ + - ]: 3949 : while (!bFound && nLo <= nHi)
[ + + ]
110 : : {
111 : 904 : i = (nLo + nHi) / 2;
112 [ + + ]: 904 : if (i > 0)
113 : 522 : nStart = (long) pData[i - 1].nEnd;
114 : : else
115 : 382 : nStart = -1;
116 : 904 : nEnd = (long) pData[i].nEnd;
117 [ + + ]: 904 : if (nEnd < (long) nAccess)
118 : 472 : nLo = ++i;
119 : : else
120 [ - + ]: 432 : if (nStart >= (long) nAccess)
121 : 0 : nHi = --i;
122 : : else
123 : 432 : bFound = true;
124 : : }
125 [ + - ][ # # ]: 5591 : return (bFound ? static_cast<size_t>(i) : (nAccess < 0 ? 0 : nCount-1));
126 : : }
127 : :
128 : :
129 : : template< typename A, typename D >
130 : 490 : void ScCompressedArray<A,D>::SetValue( A nStart, A nEnd, const D& rValue )
131 : : {
132 [ + - ][ + - ]: 490 : if (0 <= nStart && nStart <= nMaxAccess && 0 <= nEnd && nEnd <= nMaxAccess
[ + - ][ + - ]
[ + - ]
133 : : && nStart <= nEnd)
134 : : {
135 [ + + ][ + + ]: 490 : if ((nStart == 0) && (nEnd == nMaxAccess))
136 : 95 : Reset( rValue);
137 : : else
138 : : {
139 : : // Create a temporary copy in case we got a reference passed that
140 : : // points to a part of the array to be reallocated.
141 : 395 : D aNewVal( rValue);
142 : 395 : size_t nNeeded = nCount + 2;
143 [ + + ]: 395 : if (nLimit < nNeeded)
144 : : {
145 : 186 : nLimit += nDelta;
146 [ - + ]: 186 : if (nLimit < nNeeded)
147 : 0 : nLimit = nNeeded;
148 [ + - ][ + + ]: 1156 : DataEntry* pNewData = new DataEntry[nLimit];
149 : 186 : memcpy( pNewData, pData, nCount*sizeof(DataEntry));
150 [ + - ]: 186 : delete[] pData;
151 : 186 : pData = pNewData;
152 : : }
153 : :
154 : : size_t ni; // number of leading entries
155 : : size_t nInsert; // insert position (nMaxAccess+1 := no insert)
156 : 395 : bool bCombined = false;
157 : 395 : bool bSplit = false;
158 [ + + ]: 395 : if (nStart > 0)
159 : : {
160 : : // skip leading
161 : 245 : ni = this->Search( nStart);
162 : :
163 : 245 : nInsert = nMaxAccess+1;
164 [ + + ]: 245 : if (!(pData[ni].aValue == aNewVal))
165 : : {
166 [ + + ][ + + ]: 235 : if (ni == 0 || (pData[ni-1].nEnd < nStart - 1))
167 : : { // may be a split or a simple insert or just a shrink,
168 : : // row adjustment is done further down
169 [ + - ]: 60 : if (pData[ni].nEnd > nEnd)
170 : 60 : bSplit = true;
171 : 60 : ni++;
172 : 60 : nInsert = ni;
173 : : }
174 [ + - ][ + - ]: 175 : else if (ni > 0 && pData[ni-1].nEnd == nStart - 1)
175 : 235 : nInsert = ni;
176 : : }
177 [ + + ][ + + ]: 245 : if (ni > 0 && pData[ni-1].aValue == aNewVal)
178 : : { // combine
179 : 175 : pData[ni-1].nEnd = nEnd;
180 : 175 : nInsert = nMaxAccess+1;
181 : 175 : bCombined = true;
182 : : }
183 : : }
184 : : else
185 : : {
186 : 150 : nInsert = 0;
187 : 150 : ni = 0;
188 : : }
189 : :
190 : 395 : size_t nj = ni; // stop position of range to replace
191 [ + + ][ + + ]: 417 : while (nj < nCount && pData[nj].nEnd <= nEnd)
[ + + ]
192 : 22 : nj++;
193 [ + + ]: 395 : if (!bSplit)
194 : : {
195 [ + + ][ + + ]: 335 : if (nj < nCount && pData[nj].aValue == aNewVal)
196 : : { // combine
197 [ - + ]: 39 : if (ni > 0)
198 : : {
199 [ # # ]: 0 : if (pData[ni-1].aValue == aNewVal)
200 : : { // adjacent entries
201 : 0 : pData[ni-1].nEnd = pData[nj].nEnd;
202 : 0 : nj++;
203 : : }
204 [ # # ]: 0 : else if (ni == nInsert)
205 : 0 : pData[ni-1].nEnd = nStart - 1; // shrink
206 : : }
207 : 39 : nInsert = nMaxAccess+1;
208 : 39 : bCombined = true;
209 : : }
210 [ + + ][ - + ]: 296 : else if (ni > 0 && ni == nInsert)
211 : 335 : pData[ni-1].nEnd = nStart - 1; // shrink
212 : : }
213 [ + + ]: 395 : if (ni < nj)
214 : : { // remove middle entries
215 [ + + ]: 22 : if (!bCombined)
216 : : { // replace one entry
217 : 2 : pData[ni].nEnd = nEnd;
218 : 2 : pData[ni].aValue = aNewVal;
219 : 2 : ni++;
220 : 2 : nInsert = nMaxAccess+1;
221 : : }
222 [ + + ]: 22 : if (ni < nj)
223 : : { // remove entries
224 : 20 : memmove( pData + ni, pData + nj,
225 : : (nCount - nj) * sizeof(DataEntry));
226 : 20 : nCount -= nj - ni;
227 : : }
228 : : }
229 : :
230 [ + + ]: 395 : if (nInsert < static_cast<size_t>(nMaxAccess+1))
231 : : { // insert or append new entry
232 [ + - ]: 179 : if (nInsert <= nCount)
233 : : {
234 [ + + ]: 179 : if (!bSplit)
235 : 119 : memmove( pData + nInsert + 1, pData + nInsert,
236 : : (nCount - nInsert) * sizeof(DataEntry));
237 : : else
238 : : {
239 : 60 : memmove( pData + nInsert + 2, pData + nInsert,
240 : : (nCount - nInsert) * sizeof(DataEntry));
241 : 60 : pData[nInsert+1] = pData[nInsert-1];
242 : 60 : nCount++;
243 : : }
244 : : }
245 [ + + ]: 179 : if (nInsert)
246 : 60 : pData[nInsert-1].nEnd = nStart - 1;
247 : 179 : pData[nInsert].nEnd = nEnd;
248 : 179 : pData[nInsert].aValue = aNewVal;
249 : 490 : nCount++;
250 : : }
251 : : }
252 : : }
253 : 490 : }
254 : :
255 : :
256 : : template< typename A, typename D >
257 : 68 : void ScCompressedArray<A,D>::CopyFrom( const ScCompressedArray<A,D>& rArray, A nStart,
258 : : A nEnd, long nSourceDy )
259 : : {
260 : : size_t nIndex;
261 : : A nRegionEnd;
262 [ + + ]: 138 : for (A j=nStart; j<=nEnd; ++j)
263 : : {
264 : : const D& rValue = (j==nStart ?
265 : : rArray.GetValue( j+nSourceDy, nIndex, nRegionEnd) :
266 [ + + ][ + - ]: 70 : rArray.GetNextValue( nIndex, nRegionEnd));
[ + - ]
267 : 70 : nRegionEnd -= nSourceDy;
268 [ + + ]: 70 : if (nRegionEnd > nEnd)
269 : 21 : nRegionEnd = nEnd;
270 [ + - ]: 70 : this->SetValue( j, nRegionEnd, rValue);
271 : 70 : j = nRegionEnd;
272 : : }
273 : 68 : }
274 : :
275 : :
276 : : template< typename A, typename D >
277 : 26 : const D& ScCompressedArray<A,D>::Insert( A nStart, size_t nAccessCount )
278 : : {
279 : 26 : size_t nIndex = this->Search( nStart);
280 : : // No real insertion is needed, simply extend the one entry and adapt all
281 : : // following. In case nStart points to the start row of an entry, extend
282 : : // the previous entry (inserting before nStart).
283 [ # # ][ - + ]: 26 : if (nIndex > 0 && pData[nIndex-1].nEnd+1 == nStart)
284 : 0 : --nIndex;
285 : 26 : const D& rValue = pData[nIndex].aValue; // the value "copied"
286 [ - + ]: 26 : do
287 : : {
288 : 26 : pData[nIndex].nEnd += nAccessCount;
289 [ + - ]: 26 : if (pData[nIndex].nEnd >= nMaxAccess)
290 : : {
291 : 26 : pData[nIndex].nEnd = nMaxAccess;
292 : 26 : nCount = nIndex + 1; // discard trailing entries
293 : : }
294 : : } while (++nIndex < nCount);
295 : 26 : return rValue;
296 : : }
297 : :
298 : :
299 : : template< typename A, typename D >
300 : 14 : void ScCompressedArray<A,D>::Remove( A nStart, size_t nAccessCount )
301 : : {
302 : 14 : A nEnd = nStart + nAccessCount - 1;
303 : 14 : size_t nIndex = this->Search( nStart);
304 : : // equalize/combine/remove all entries in between
305 [ - + ]: 14 : if (nEnd > pData[nIndex].nEnd)
306 : 0 : this->SetValue( nStart, nEnd, pData[nIndex].aValue);
307 : : // remove an exactly matching entry by shifting up all following by one
308 [ + + ][ - + ]: 14 : if ((nStart == 0 || (nIndex > 0 && nStart == pData[nIndex-1].nEnd+1)) &&
[ # # ][ - + ]
[ # # ]
309 : : pData[nIndex].nEnd == nEnd && nIndex < nCount-1)
310 : : {
311 : : // In case removing an entry results in two adjacent entries with
312 : : // identical data, combine them into one. This is also necessary to
313 : : // make the algorithm used in SetValue() work correctly, it relies on
314 : : // the fact that consecutive values actually differ.
315 : : size_t nRemove;
316 [ # # ][ # # ]: 0 : if (nIndex > 0 && pData[nIndex-1].aValue == pData[nIndex+1].aValue)
317 : : {
318 : 0 : nRemove = 2;
319 : 0 : --nIndex;
320 : : }
321 : : else
322 : 0 : nRemove = 1;
323 : 0 : memmove( pData + nIndex, pData + nIndex + nRemove, (nCount - (nIndex +
324 : : nRemove)) * sizeof(DataEntry));
325 : 0 : nCount -= nRemove;
326 : : }
327 : : // adjust end rows, nIndex still being valid
328 [ - + ]: 14 : do
329 : : {
330 : 14 : pData[nIndex].nEnd -= nAccessCount;
331 : : } while (++nIndex < nCount);
332 : 14 : pData[nCount-1].nEnd = nMaxAccess;
333 : 14 : }
334 : :
335 : :
336 : : // === ScBitMaskCompressedArray ==============================================
337 : :
338 : : template< typename A, typename D >
339 : 12 : void ScBitMaskCompressedArray<A,D>::AndValue( A nStart, A nEnd,
340 : : const D& rValueToAnd )
341 : : {
342 [ - + ]: 12 : if (nStart > nEnd)
343 : 12 : return;
344 : :
345 : 12 : size_t nIndex = this->Search( nStart);
346 [ # # ]: 0 : do
347 : : {
348 [ - + ]: 12 : if ((this->pData[nIndex].aValue & rValueToAnd) != this->pData[nIndex].aValue)
349 : : {
350 [ # # ][ # # ]: 0 : A nS = ::std::max( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
351 : 0 : A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
352 [ # # ]: 0 : this->SetValue( nS, nE, this->pData[nIndex].aValue & rValueToAnd);
353 [ # # ]: 0 : if (nE >= nEnd)
354 : 0 : break; // while
355 : 0 : nIndex = this->Search( nE + 1);
356 : : }
357 [ + - ]: 12 : else if (this->pData[nIndex].nEnd >= nEnd)
358 : 12 : break; // while
359 : : else
360 : 0 : ++nIndex;
361 : : } while (nIndex < this->nCount);
362 : : }
363 : :
364 : :
365 : : template< typename A, typename D >
366 : 402 : void ScBitMaskCompressedArray<A,D>::OrValue( A nStart, A nEnd,
367 : : const D& rValueToOr )
368 : : {
369 [ - + ]: 402 : if (nStart > nEnd)
370 : 402 : return;
371 : :
372 : 402 : size_t nIndex = this->Search( nStart);
373 [ # # ]: 0 : do
374 : : {
375 [ + + ]: 402 : if ((this->pData[nIndex].aValue | rValueToOr) != this->pData[nIndex].aValue)
376 : : {
377 [ + + ][ + - ]: 362 : A nS = ::std::max( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart);
378 : 362 : A nE = ::std::min( this->pData[nIndex].nEnd, nEnd);
379 [ + - ]: 362 : this->SetValue( nS, nE, this->pData[nIndex].aValue | rValueToOr);
380 [ + - ]: 362 : if (nE >= nEnd)
381 : 362 : break; // while
382 : 0 : nIndex = this->Search( nE + 1);
383 : : }
384 [ + - ]: 40 : else if (this->pData[nIndex].nEnd >= nEnd)
385 : 40 : break; // while
386 : : else
387 : 0 : ++nIndex;
388 : : } while (nIndex < this->nCount);
389 : : }
390 : :
391 : :
392 : : template< typename A, typename D >
393 : 18 : void ScBitMaskCompressedArray<A,D>::CopyFromAnded(
394 : : const ScBitMaskCompressedArray<A,D>& rArray, A nStart, A nEnd,
395 : : const D& rValueToAnd, long nSourceDy )
396 : : {
397 : : size_t nIndex;
398 : : A nRegionEnd;
399 [ + + ]: 36 : for (A j=nStart; j<=nEnd; ++j)
400 : : {
401 : : const D& rValue = (j==nStart ?
402 : : rArray.GetValue( j+nSourceDy, nIndex, nRegionEnd) :
403 [ + - ][ + - ]: 18 : rArray.GetNextValue( nIndex, nRegionEnd));
[ # # ]
404 : 18 : nRegionEnd -= nSourceDy;
405 [ + - ]: 18 : if (nRegionEnd > nEnd)
406 : 18 : nRegionEnd = nEnd;
407 [ + - ]: 18 : this->SetValue( j, nRegionEnd, rValue & rValueToAnd);
408 : 18 : j = nRegionEnd;
409 : : }
410 : 18 : }
411 : :
412 : : template< typename A, typename D >
413 : 0 : A ScBitMaskCompressedArray<A,D>::GetFirstForCondition( A nStart, A nEnd,
414 : : const D& rBitMask, const D& rMaskedCompare ) const
415 : : {
416 : 0 : size_t nIndex = this->Search( nStart);
417 [ # # ]: 0 : do
418 : : {
419 [ # # ]: 0 : if ((this->pData[nIndex].aValue & rBitMask) == rMaskedCompare)
420 : : {
421 [ # # ]: 0 : A nFound = nIndex > 0 ? this->pData[nIndex-1].nEnd + 1 : 0;
422 [ # # ]: 0 : return ::std::max( nFound, nStart);
423 : : }
424 [ # # ]: 0 : if (this->pData[nIndex].nEnd >= nEnd)
425 : 0 : break; // while
426 : 0 : ++nIndex;
427 : : } while (nIndex < this->nCount);
428 : 0 : return ::std::numeric_limits<A>::max();
429 : : }
430 : :
431 : : template< typename A, typename D >
432 : 4 : A ScBitMaskCompressedArray<A,D>::GetLastAnyBitAccess( A nStart,
433 : : const D& rBitMask ) const
434 : : {
435 : 4 : A nEnd = ::std::numeric_limits<A>::max();
436 : 4 : size_t nIndex = this->nCount-1;
437 : 0 : while (1)
438 : : {
439 [ - + ]: 4 : if ((this->pData[nIndex].aValue & rBitMask) != 0)
440 : : {
441 : 0 : nEnd = this->pData[nIndex].nEnd;
442 : 0 : break; // while
443 : : }
444 : : else
445 : : {
446 [ - + ]: 4 : if (nIndex > 0)
447 : : {
448 : 0 : --nIndex;
449 [ # # ]: 0 : if (this->pData[nIndex].nEnd < nStart)
450 : 0 : break; // while
451 : : }
452 : : else
453 : 4 : break; // while
454 : : }
455 : : }
456 : 4 : return nEnd;
457 : : }
458 : :
459 : : // === Force instantiation of specializations ================================
460 : :
461 : : template class ScCompressedArray< SCROW, sal_uInt8>; // flags, base class
462 : : template class ScBitMaskCompressedArray< SCROW, sal_uInt8>; // flags
463 : :
464 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
