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