From 2ecaf778a7a6950082589e74696c3b33753b28ad Mon Sep 17 00:00:00 2001 From: Kohei Yoshida Date: Mon, 17 Sep 2012 21:32:44 -0400 Subject: Use mdds::flat_segment_tree to store row flags. Much less memory footprint & better scalability. Change-Id: Idef9afe5fa6e247e59fb949d4c9955fab4f669dc --- sc/inc/dpcachetable.hxx | 13 +++- sc/source/core/data/dpcachetable.cxx | 142 ++++++++++++++++++++--------------- sc/source/core/data/dpgroup.cxx | 6 +- sc/source/core/data/dptabdat.cxx | 6 +- 4 files changed, 99 insertions(+), 68 deletions(-) (limited to 'sc') diff --git a/sc/inc/dpcachetable.hxx b/sc/inc/dpcachetable.hxx index 5f29711b15ed..c0d06250a6ee 100644 --- a/sc/inc/dpcachetable.hxx +++ b/sc/inc/dpcachetable.hxx @@ -38,7 +38,8 @@ #include #include -class Date; +#include + class ScDPItemData; class ScDPCache; class ScDocument; @@ -132,7 +133,7 @@ public: /** Check whether a specified row is active or not. When a row is active, it is used in calculation of the results data. A row becomes inactive when it is filtered out by page field. */ - bool isRowActive(sal_Int32 nRow) const; + bool isRowActive(sal_Int32 nRow, sal_Int32* pLastRow = NULL) const; /** Set filter on/off flag to each row to control visibility. The caller must ensure that the table is filled before calling this function. */ @@ -175,11 +176,15 @@ private: bool isRowQualified(sal_Int32 nRow, const ::std::vector& rCriteria, const ::boost::unordered_set& rRepeatIfEmptyDims) const; private: + typedef mdds::flat_segment_tree RowFlagType; + /** unique field entires for each field (column). */ ::std::vector< ::std::vector > maFieldEntries; - /** Row flags. The first row below the header row has the index of 0. */ - ::std::vector maRowFlags; + /** Rows visible by standard filter query. */ + RowFlagType maShowByFilter; + /** Rows visible by page dimension filtering. */ + RowFlagType maShowByPage; const ScDPCache* mpCache; }; diff --git a/sc/source/core/data/dpcachetable.cxx b/sc/source/core/data/dpcachetable.cxx index 7c5a41f6a430..11ac85fac2e9 100644 --- a/sc/source/core/data/dpcachetable.cxx +++ b/sc/source/core/data/dpcachetable.cxx @@ -125,7 +125,7 @@ ScDPCacheTable::Criterion::Criterion() : // ---------------------------------------------------------------------------- ScDPCacheTable::ScDPCacheTable(const ScDPCache* pCache) : - mpCache(pCache) + maShowByFilter(0, MAXROW+1, false), maShowByPage(0, MAXROW+1, true), mpCache(pCache) { } @@ -152,29 +152,26 @@ void ScDPCacheTable::fillTable( if (nRowCount <= 0 || nColCount <= 0) return; - maRowFlags.clear(); - maRowFlags.reserve(nRowCount); + maShowByFilter.clear(); + maShowByPage.clear(); // Process the non-empty data rows. for (SCROW nRow = 0; nRow < nDataSize; ++nRow) { - maRowFlags.push_back(RowFlag()); if (!getCache()->ValidQuery(nRow, rQuery)) continue; if (bIgnoreEmptyRows && getCache()->IsRowEmpty(nRow)) continue; - maRowFlags.back().mbShowByFilter = true; + maShowByFilter.insert_back(nRow, nRow+1, true); } // Process the trailing empty rows. - for (SCROW nRow = nDataSize; nRow < nRowCount; ++nRow) - { - maRowFlags.push_back(RowFlag()); - if (!bIgnoreEmptyRows) - maRowFlags.back().mbShowByFilter = true; - } + if (!bIgnoreEmptyRows) + maShowByFilter.insert_back(nDataSize, nRowCount, true); + + maShowByFilter.build_tree(); // Initialize field entries container. maFieldEntries.clear(); @@ -189,11 +186,25 @@ void ScDPCacheTable::fillTable( continue; std::vector aAdded(nMemCount, -1); - + bool bShow = false; + SCROW nEndSegment = -1; for (SCROW nRow = 0; nRow < nRowCount; ++nRow) { - if (!maRowFlags[nRow].mbShowByFilter) + if (nRow > nEndSegment) + { + if (!maShowByFilter.search_tree(nRow, bShow, NULL, &nEndSegment)) + { + OSL_FAIL("Tree search failed!"); + continue; + } + --nEndSegment; // End position is not inclusive. Move back one. + } + + if (!bShow) + { + nRow = nEndSegment; continue; + } SCROW nIndex = getCache()->GetItemDataId(nCol, nRow, bRepeatIfEmpty); SCROW nOrder = getOrder(nCol, nIndex); @@ -214,63 +225,66 @@ void ScDPCacheTable::fillTable() if (nRowCount <= 0 || nColCount <= 0) return; - maRowFlags.clear(); - maRowFlags.reserve(nRowCount); - - for (SCROW nRow = 0; nRow < nRowCount; ++nRow) - { - maRowFlags.push_back(RowFlag()); - maRowFlags.back().mbShowByFilter = true; - } - - // Initialize field entries container. - maFieldEntries.clear(); - maFieldEntries.reserve(nColCount); - - // Data rows - for (SCCOL nCol = 0; nCol < nColCount; ++nCol) - { - maFieldEntries.push_back( vector() ); - SCROW nMemCount = getCache()->GetDimMemberCount( nCol ); - if (!nMemCount) - continue; - - std::vector aAdded(nMemCount, -1); - - for (SCROW nRow = 0; nRow < nRowCount; ++nRow) - { - SCROW nIndex = getCache()->GetItemDataId(nCol, nRow, false); - SCROW nOrder = getOrder(nCol, nIndex); - aAdded[nOrder] = nIndex; - } - for (SCROW nRow = 0; nRow < nMemCount; ++nRow) - { - if (aAdded[nRow] != -1) - maFieldEntries.back().push_back(aAdded[nRow]); - } - } + maShowByFilter.clear(); + maShowByPage.clear(); + maShowByFilter.insert_front(0, nRowCount, true); + + // Initialize field entries container. + maFieldEntries.clear(); + maFieldEntries.reserve(nColCount); + + // Data rows + for (SCCOL nCol = 0; nCol < nColCount; ++nCol) + { + maFieldEntries.push_back( vector() ); + SCROW nMemCount = getCache()->GetDimMemberCount( nCol ); + if (!nMemCount) + continue; + + std::vector aAdded(nMemCount, -1); + + for (SCROW nRow = 0; nRow < nRowCount; ++nRow) + { + SCROW nIndex = getCache()->GetItemDataId(nCol, nRow, false); + SCROW nOrder = getOrder(nCol, nIndex); + aAdded[nOrder] = nIndex; + } + for (SCROW nRow = 0; nRow < nMemCount; ++nRow) + { + if (aAdded[nRow] != -1) + maFieldEntries.back().push_back(aAdded[nRow]); + } + } } -bool ScDPCacheTable::isRowActive(sal_Int32 nRow) const +bool ScDPCacheTable::isRowActive(sal_Int32 nRow, sal_Int32* pLastRow) const { - if (nRow < 0 || static_cast(nRow) >= maRowFlags.size()) - // row index out of bound - return false; + bool bFilter = false, bPage = true; + SCROW nLastRowFilter = MAXROW, nLastRowPage = MAXROW; + maShowByFilter.search_tree(nRow, bFilter, NULL, &nLastRowFilter); + maShowByPage.search_tree(nRow, bPage, NULL, &nLastRowPage); + if (pLastRow) + { + // Return the last row of current segment. + *pLastRow = nLastRowFilter < nLastRowPage ? nLastRowFilter : nLastRowPage; + *pLastRow -= 1; // End position is not inclusive. Move back one. + } - return maRowFlags[nRow].isActive(); + return bFilter && bPage; } void ScDPCacheTable::filterByPageDimension(const vector& rCriteria, const boost::unordered_set& rRepeatIfEmptyDims) { - sal_Int32 nRowSize = getRowSize(); - if (nRowSize != static_cast(maRowFlags.size())) + SCROW nRowSize = getRowSize(); + + maShowByPage.clear(); + for (SCROW nRow = 0; nRow < nRowSize; ++nRow) { - // sizes of the two tables differ! - return; + bool bShow = isRowQualified(nRow, rCriteria, rRepeatIfEmptyDims); + maShowByPage.insert_back(nRow, nRow+1, bShow); } - for (sal_Int32 nRow = 0; nRow < nRowSize; ++nRow) - maRowFlags[nRow].mbShowByPage = isRowQualified(nRow, rCriteria, rRepeatIfEmptyDims); + maShowByPage.build_tree(); } const ScDPItemData* ScDPCacheTable::getCell(SCCOL nCol, SCROW nRow, bool bRepeatIfEmpty) const @@ -340,12 +354,15 @@ void ScDPCacheTable::filterTable(const vector& rCriteria, Sequence< S } tableData.push_back(headerRow); - for (sal_Int32 nRow = 0; nRow < nRowSize; ++nRow) { - if (!maRowFlags[nRow].isActive()) + sal_Int32 nLastRow; + if (!isRowActive(nRow, &nLastRow)) + { // This row is filtered out. + nRow = nLastRow; continue; + } if (!isRowQualified(nRow, rCriteria, rRepeatIfEmptyDims)) continue; @@ -385,7 +402,8 @@ SCROW ScDPCacheTable::getOrder(long nDim, SCROW nIndex) const void ScDPCacheTable::clear() { maFieldEntries.clear(); - maRowFlags.clear(); + maShowByFilter.clear(); + maShowByPage.clear(); } bool ScDPCacheTable::empty() const diff --git a/sc/source/core/data/dpgroup.cxx b/sc/source/core/data/dpgroup.cxx index 232f7fc9a1e2..aba278556336 100644 --- a/sc/source/core/data/dpgroup.cxx +++ b/sc/source/core/data/dpgroup.cxx @@ -762,8 +762,12 @@ void ScDPGroupTableData::CalcResults(CalcInfo& rInfo, bool bAutoShow) sal_Int32 nRowSize = rCacheTable.getRowSize(); for (sal_Int32 nRow = 0; nRow < nRowSize; ++nRow) { - if (!rCacheTable.isRowActive(nRow)) + sal_Int32 nLastRow; + if (!rCacheTable.isRowActive(nRow, &nLastRow)) + { + nRow = nLastRow; continue; + } CalcRowData aData; FillRowDataFromCacheTable(nRow, rCacheTable, rInfo, aData); diff --git a/sc/source/core/data/dptabdat.cxx b/sc/source/core/data/dptabdat.cxx index 39f1b4f31ef0..f150d8d3ef23 100644 --- a/sc/source/core/data/dptabdat.cxx +++ b/sc/source/core/data/dptabdat.cxx @@ -221,8 +221,12 @@ void ScDPTableData::CalcResultsFromCacheTable(const ScDPCacheTable& rCacheTable, sal_Int32 nRowSize = rCacheTable.getRowSize(); for (sal_Int32 nRow = 0; nRow < nRowSize; ++nRow) { - if (!rCacheTable.isRowActive(nRow)) + sal_Int32 nLastRow; + if (!rCacheTable.isRowActive(nRow, &nLastRow)) + { + nRow = nLastRow; continue; + } CalcRowData aData; FillRowDataFromCacheTable(nRow, rCacheTable, rInfo, aData); -- cgit