diff options
Diffstat (limited to 'sc/source/core/data/compressedarray.cxx')
| -rw-r--r-- | sc/source/core/data/compressedarray.cxx | 418 |
1 files changed, 418 insertions, 0 deletions
diff --git a/sc/source/core/data/compressedarray.cxx b/sc/source/core/data/compressedarray.cxx new file mode 100644 index 000000000..793b43b43 --- /dev/null +++ b/sc/source/core/data/compressedarray.cxx @@ -0,0 +1,418 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +#include <compressedarray.hxx> +#include <global.hxx> + +template< typename A, typename D > +ScCompressedArray<A,D>::ScCompressedArray( A nMaxAccessP, const D& rValue ) + : nCount(1) + , nLimit(1) + , pData( new DataEntry[1]) + , nMaxAccess( nMaxAccessP) +{ + pData[0].aValue = rValue; + pData[0].nEnd = nMaxAccess; +} + +template< typename A, typename D > +size_t ScCompressedArray<A,D>::Search( A nAccess ) const +{ + if (nAccess == 0) + return 0; + + tools::Long nLo = 0; + tools::Long nHi = static_cast<tools::Long>(nCount) - 1; + tools::Long nStart = 0; + tools::Long i = 0; + bool bFound = (nCount == 1); + while (!bFound && nLo <= nHi) + { + i = (nLo + nHi) / 2; + if (i > 0) + nStart = static_cast<tools::Long>(pData[i - 1].nEnd); + else + nStart = -1; + tools::Long nEnd = static_cast<tools::Long>(pData[i].nEnd); + if (nEnd < static_cast<tools::Long>(nAccess)) + nLo = ++i; + else + if (nStart >= static_cast<tools::Long>(nAccess)) + nHi = --i; + else + bFound = true; + } + return (bFound ? static_cast<size_t>(i) : (nAccess < 0 ? 0 : nCount-1)); +} + +template< typename A, typename D > +void ScCompressedArray<A,D>::SetValue( A nStart, A nEnd, const D& rValue ) +{ + if (!(0 <= nStart && nStart <= nMaxAccess && 0 <= nEnd && nEnd <= nMaxAccess + && nStart <= nEnd)) + return; + + if ((nStart == 0) && (nEnd == nMaxAccess)) + Reset( rValue); + else + { + // Create a temporary copy in case we got a reference passed that + // points to a part of the array to be reallocated. + D aNewVal( rValue); + size_t nNeeded = nCount + 2; + if (nLimit < nNeeded) + { + nLimit *= 1.5; + if (nLimit < nNeeded) + nLimit = nNeeded; + std::unique_ptr<DataEntry[]> pNewData(new DataEntry[nLimit]); + memcpy( pNewData.get(), pData.get(), nCount*sizeof(DataEntry)); + pData = std::move(pNewData); + } + + size_t ni; // number of leading entries + size_t nInsert; // insert position (nMaxAccess+1 := no insert) + bool bCombined = false; + bool bSplit = false; + if (nStart > 0) + { + // skip leading + ni = this->Search( nStart); + + nInsert = nMaxAccess+1; + if (!(pData[ni].aValue == aNewVal)) + { + if (ni == 0 || (pData[ni-1].nEnd < nStart - 1)) + { // may be a split or a simple insert or just a shrink, + // row adjustment is done further down + if (pData[ni].nEnd > nEnd) + bSplit = true; + ni++; + nInsert = ni; + } + else if (ni > 0 && pData[ni-1].nEnd == nStart - 1) + nInsert = ni; + } + if (ni > 0 && pData[ni-1].aValue == aNewVal) + { // combine + pData[ni-1].nEnd = nEnd; + nInsert = nMaxAccess+1; + bCombined = true; + } + } + else + { + nInsert = 0; + ni = 0; + } + + size_t nj = ni; // stop position of range to replace + while (nj < nCount && pData[nj].nEnd <= nEnd) + nj++; + if (!bSplit) + { + if (nj < nCount && pData[nj].aValue == aNewVal) + { // combine + if (ni > 0) + { + if (pData[ni-1].aValue == aNewVal) + { // adjacent entries + pData[ni-1].nEnd = pData[nj].nEnd; + nj++; + } + else if (ni == nInsert) + pData[ni-1].nEnd = nStart - 1; // shrink + } + nInsert = nMaxAccess+1; + bCombined = true; + } + else if (ni > 0 && ni == nInsert) + pData[ni-1].nEnd = nStart - 1; // shrink + } + if (ni < nj) + { // remove middle entries + if (!bCombined) + { // replace one entry + pData[ni].nEnd = nEnd; + pData[ni].aValue = aNewVal; + ni++; + nInsert = nMaxAccess+1; + } + if (ni < nj) + { // remove entries + memmove( pData.get() + ni, pData.get() + nj, + (nCount - nj) * sizeof(DataEntry)); + nCount -= nj - ni; + } + } + + if (nInsert < static_cast<size_t>(nMaxAccess+1)) + { // insert or append new entry + if (nInsert <= nCount) + { + if (!bSplit) + memmove( pData.get() + nInsert + 1, pData.get() + nInsert, + (nCount - nInsert) * sizeof(DataEntry)); + else + { + memmove( pData.get() + nInsert + 2, pData.get() + nInsert, + (nCount - nInsert) * sizeof(DataEntry)); + pData[nInsert+1] = pData[nInsert-1]; + nCount++; + } + } + if (nInsert) + pData[nInsert-1].nEnd = nStart - 1; + pData[nInsert].nEnd = nEnd; + pData[nInsert].aValue = aNewVal; + nCount++; + } + } +} + +template< typename A, typename D > +void ScCompressedArray<A,D>::CopyFrom( const ScCompressedArray<A,D>& rArray, A nDestStart, + A nDestEnd, A nSrcStart ) +{ + assert( this != &rArray && "cannot copy self->self" ); + size_t nIndex = 0; + A nRegionEnd; + for (A j=nDestStart; j<=nDestEnd; ++j) + { + const D& rValue = (j==nDestStart ? + rArray.GetValue( j - nDestStart + nSrcStart, nIndex, nRegionEnd) : + rArray.GetNextValue( nIndex, nRegionEnd)); + nRegionEnd = nRegionEnd - nSrcStart + nDestStart; + if (nRegionEnd > nDestEnd) + nRegionEnd = nDestEnd; + this->SetValue( j, nRegionEnd, rValue); + j = nRegionEnd; + } +} + +template< typename A, typename D > +const D& ScCompressedArray<A,D>::Insert( A nStart, size_t nAccessCount ) +{ + size_t nIndex = this->Search( nStart); + // No real insertion is needed, simply extend the one entry and adapt all + // following. In case nStart points to the start row of an entry, extend + // the previous entry (inserting before nStart). + if (nIndex > 0 && pData[nIndex-1].nEnd+1 == nStart) + --nIndex; + const D& rValue = pData[nIndex].aValue; // the value "copied" + do + { + pData[nIndex].nEnd += nAccessCount; + if (pData[nIndex].nEnd >= nMaxAccess) + { + pData[nIndex].nEnd = nMaxAccess; + nCount = nIndex + 1; // discard trailing entries + } + } while (++nIndex < nCount); + return rValue; +} + +template< typename A, typename D > +void ScCompressedArray<A,D>::InsertPreservingSize( A nStart, size_t nAccessCount, const D& rFillValue ) +{ + const A nPrevLastPos = GetLastPos(); + + Insert(nStart, nAccessCount); + for (A i = nStart; i < A(nStart + nAccessCount); ++i) + SetValue(i, rFillValue); + + const A nNewLastPos = GetLastPos(); + Remove(nPrevLastPos, nNewLastPos - nPrevLastPos); +} + +template< typename A, typename D > +void ScCompressedArray<A,D>::Remove( A nStart, size_t nAccessCount ) +{ + A nEnd = nStart + nAccessCount - 1; + size_t nIndex = this->Search( nStart); + // equalize/combine/remove all entries in between + if (nEnd > pData[nIndex].nEnd) + this->SetValue( nStart, nEnd, pData[nIndex].aValue); + // remove an exactly matching entry by shifting up all following by one + if ((nStart == 0 || (nIndex > 0 && nStart == pData[nIndex-1].nEnd+1)) && + pData[nIndex].nEnd == nEnd && nIndex < nCount-1) + { + // In case removing an entry results in two adjacent entries with + // identical data, combine them into one. This is also necessary to + // make the algorithm used in SetValue() work correctly, it relies on + // the fact that consecutive values actually differ. + size_t nRemove; + if (nIndex > 0 && pData[nIndex-1].aValue == pData[nIndex+1].aValue) + { + nRemove = 2; + --nIndex; + } + else + nRemove = 1; + memmove( pData.get() + nIndex, pData.get() + nIndex + nRemove, (nCount - (nIndex + + nRemove)) * sizeof(DataEntry)); + nCount -= nRemove; + } + // adjust end rows, nIndex still being valid + do + { + pData[nIndex].nEnd -= nAccessCount; + } while (++nIndex < nCount); + pData[nCount-1].nEnd = nMaxAccess; +} + +template< typename A, typename D > +void ScCompressedArray<A,D>::RemovePreservingSize( A nStart, size_t nAccessCount, const D& rFillValue ) +{ + const A nPrevLastPos = GetLastPos(); + + Remove(nStart, nAccessCount); + + const A nNewLastPos = GetLastPos(); + InsertPreservingSize(nNewLastPos, nNewLastPos - nPrevLastPos, rFillValue); +} + +template< typename A, typename D > +void ScCompressedArray<A,D>::Iterator::operator++() +{ + ++mnRegion; + if (mnRegion > mrArray.pData[mnIndex].nEnd) + ++mnIndex; +} + +template< typename A, typename D > +typename ScCompressedArray<A,D>::Iterator ScCompressedArray<A,D>::Iterator::operator+(size_t nAccessCount) const +{ + A nRegion = mnRegion + nAccessCount; + auto nIndex = mnIndex; + while (nRegion > mrArray.pData[nIndex].nEnd) + ++nIndex; + return Iterator(mrArray, nIndex, nRegion); +} + +// === ScBitMaskCompressedArray ============================================== + +template< typename A, typename D > +void ScBitMaskCompressedArray<A,D>::AndValue( A nStart, A nEnd, + const D& rValueToAnd ) +{ + if (nStart > nEnd) + return; + + size_t nIndex = this->Search( nStart); + do + { + if ((this->pData[nIndex].aValue & rValueToAnd) != this->pData[nIndex].aValue) + { + A nS = ::std::max<A>( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart); + A nE = ::std::min( this->pData[nIndex].nEnd, nEnd); + this->SetValue( nS, nE, this->pData[nIndex].aValue & rValueToAnd); + if (nE >= nEnd) + break; // while + nIndex = this->Search( nE + 1); + } + else if (this->pData[nIndex].nEnd >= nEnd) + break; // while + else + ++nIndex; + } while (nIndex < this->nCount); +} + +template< typename A, typename D > +void ScBitMaskCompressedArray<A,D>::OrValue( A nStart, A nEnd, + const D& rValueToOr ) +{ + if (nStart > nEnd) + return; + + size_t nIndex = this->Search( nStart); + do + { + if ((this->pData[nIndex].aValue | rValueToOr) != this->pData[nIndex].aValue) + { + A nS = ::std::max<A>( (nIndex>0 ? this->pData[nIndex-1].nEnd+1 : 0), nStart); + A nE = ::std::min( this->pData[nIndex].nEnd, nEnd); + this->SetValue( nS, nE, this->pData[nIndex].aValue | rValueToOr); + if (nE >= nEnd) + break; // while + nIndex = this->Search( nE + 1); + } + else if (this->pData[nIndex].nEnd >= nEnd) + break; // while + else + ++nIndex; + } while (nIndex < this->nCount); +} + +template< typename A, typename D > +void ScBitMaskCompressedArray<A,D>::CopyFromAnded( + const ScBitMaskCompressedArray<A,D>& rArray, A nStart, A nEnd, + const D& rValueToAnd ) +{ + size_t nIndex = 0; + A nRegionEnd; + for (A j=nStart; j<=nEnd; ++j) + { + const D& rValue = (j==nStart ? + rArray.GetValue( j, nIndex, nRegionEnd) : + rArray.GetNextValue( nIndex, nRegionEnd)); + if (nRegionEnd > nEnd) + nRegionEnd = nEnd; + this->SetValue( j, nRegionEnd, rValue & rValueToAnd); + j = nRegionEnd; + } +} + +template< typename A, typename D > +A ScBitMaskCompressedArray<A,D>::GetLastAnyBitAccess( const D& rBitMask ) const +{ + A nEnd = ::std::numeric_limits<A>::max(); + size_t nIndex = this->nCount-1; + while (true) + { + if (this->pData[nIndex].aValue & rBitMask) + { + nEnd = this->pData[nIndex].nEnd; + break; // while + } + else + { + if (nIndex > 0) + { + --nIndex; + if (this->pData[nIndex].nEnd < 0) + break; // while + } + else + break; // while + } + } + return nEnd; +} + +// === Force instantiation of specializations ================================ + +template class ScCompressedArray< SCROW, CRFlags>; // flags, base class +template class ScBitMaskCompressedArray< SCROW, CRFlags>; // flags +template class ScCompressedArray< SCCOL, sal_uInt16>; +template class ScCompressedArray< SCCOL, CRFlags>; +template class ScCompressedArray< SCROW, sal_uInt16>; +template class ScBitMaskCompressedArray< SCCOL, CRFlags>; + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ |