sc/source/core/data/compressedarray.cxx

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