diff options
author | Noel Grandin <noel.grandin@collabora.co.uk> | 2019-04-17 15:19:25 +0200 |
---|---|---|
committer | Noel Grandin <noel.grandin@collabora.co.uk> | 2019-04-20 08:02:25 +0200 |
commit | ec7ba61a6164c805f5a71b077715b7e1521a2d62 (patch) | |
tree | 4d4f3fb1ad960465897754601b0842c78db564bf /svl | |
parent | 7d58f26bf4dbeb4e138c2a91f039d8bc7fa00f0c (diff) |
simplify SfxPoolItemArray_Impl (tdf#81765 related)
Since we want to look up items by pointer, just store them in a
std::unordered_set, which allows fast find().
This dramatically simplifies most operations on this data structure.
Fix a dodgy sd test that was relying on items with the same whichid
being in the pool being in a certain order.
Change-Id: I4d79fc718f95e3083a20788be1050fbe9fca7263
Reviewed-on: https://gerrit.libreoffice.org/70881
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>
Diffstat (limited to 'svl')
-rw-r--r-- | svl/qa/unit/items/test_itempool.cxx | 13 | ||||
-rw-r--r-- | svl/source/inc/poolio.hxx | 26 | ||||
-rw-r--r-- | svl/source/items/itempool.cxx | 141 | ||||
-rw-r--r-- | svl/source/items/poolio.cxx | 26 |
4 files changed, 56 insertions, 150 deletions
diff --git a/svl/qa/unit/items/test_itempool.cxx b/svl/qa/unit/items/test_itempool.cxx index cde5dee62f2c..9b5528532515 100644 --- a/svl/qa/unit/items/test_itempool.cxx +++ b/svl/qa/unit/items/test_itempool.cxx @@ -79,24 +79,17 @@ void PoolItemTest::testPool() CPPUNIT_ASSERT(&rVal2 != &rVal); } - // Test rehash - for (auto & pSlice : pImpl->maPoolItems) - { - if (pSlice) - pSlice->ReHash(); - } - // Test removal. SfxVoidItem aRemoveFour(4); SfxVoidItem aNotherFour(4); const SfxPoolItem &rKeyFour = pPool->Put(aRemoveFour); pPool->Put(aNotherFour); CPPUNIT_ASSERT(pImpl->maPoolItems[3]->size() > 0); - CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(0), pImpl->maPoolItems[3]->maFree.size()); + CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(2), pImpl->maPoolItems[3]->size()); pPool->Remove(rKeyFour); - CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(1), pImpl->maPoolItems[3]->maFree.size()); + CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(1), pImpl->maPoolItems[3]->size()); pPool->Put(aNotherFour); - CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(0), pImpl->maPoolItems[3]->maFree.size()); + CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(2), pImpl->maPoolItems[3]->size()); } diff --git a/svl/source/inc/poolio.hxx b/svl/source/inc/poolio.hxx index 270b1402a110..eb78be10e71a 100644 --- a/svl/source/inc/poolio.hxx +++ b/svl/source/inc/poolio.hxx @@ -25,8 +25,7 @@ #include <tools/debug.hxx> #include <deque> #include <memory> -#include <unordered_map> -#include <vector> +#include <o3tl/sorted_vector.hxx> class SfxPoolItem; class SfxItemPoolUser; @@ -41,27 +40,18 @@ static const sal_uInt32 SFX_ITEMS_DEFAULT = 0xfffffffe; */ struct SfxPoolItemArray_Impl { - typedef std::unordered_map<SfxPoolItem*,sal_uInt32> PoolItemPtrToIndexMap; private: - std::vector<SfxPoolItem*> maPoolItemVector; + o3tl::sorted_vector<SfxPoolItem*> maPoolItemSet; public: - /// Track list of indices into our array that contain an empty slot - std::vector<sal_uInt32> maFree; - /// Hash of SfxPoolItem pointer to index into our array that contains that slot - PoolItemPtrToIndexMap maPtrToIndex; - - SfxPoolItemArray_Impl () {} - SfxPoolItem*& operator[](size_t n) {return maPoolItemVector[n];} - std::vector<SfxPoolItem*>::iterator begin() {return maPoolItemVector.begin();} - std::vector<SfxPoolItem*>::iterator end() {return maPoolItemVector.end();} + o3tl::sorted_vector<SfxPoolItem*>::const_iterator begin() { return maPoolItemSet.begin(); } + o3tl::sorted_vector<SfxPoolItem*>::const_iterator end() { return maPoolItemSet.end(); } /// clear array of PoolItem variants after all PoolItems are deleted /// or all ref counts are decreased void clear(); - size_t size() const {return maPoolItemVector.size();} - void push_back(SfxPoolItem* pItem) {maPoolItemVector.push_back(pItem);} - - /// re-build the list of free slots and hash from clean - void SVL_DLLPUBLIC ReHash(); + size_t size() const {return maPoolItemSet.size();} + void insert(SfxPoolItem* pItem) { maPoolItemSet.insert(pItem); } + o3tl::sorted_vector<SfxPoolItem*>::const_iterator find(SfxPoolItem* pItem) { return maPoolItemSet.find(pItem); } + void erase(o3tl::sorted_vector<SfxPoolItem*>::const_iterator it) { return maPoolItemSet.erase(it); } }; struct SfxItemPool_Impl diff --git a/svl/source/items/itempool.cxx b/svl/source/items/itempool.cxx index 00bc517e0c85..3a0babf6a857 100644 --- a/svl/source/items/itempool.cxx +++ b/svl/source/items/itempool.cxx @@ -389,16 +389,11 @@ void SfxItemPool::SetSecondaryPool( SfxItemPool *pPool ) { if (!bOK) break; - if (rSecArrayPtr) + if (rSecArrayPtr && rSecArrayPtr->size()>0) { - for (const SfxPoolItem* pItem : *rSecArrayPtr) - if (pItem) - { - SAL_WARN("svl.items", "old secondary pool: " << pImpl->mpSecondary->pImpl->aName - << " of pool: " << pImpl->aName << " must be empty."); - bOK = false; - break; - } + SAL_WARN("svl.items", "old secondary pool: " << pImpl->mpSecondary->pImpl->aName + << " of pool: " << pImpl->aName << " must be empty."); + break; } } } @@ -489,11 +484,10 @@ void SfxItemPool::Delete() if (rArrayPtr) { for (auto& rItemPtr : *rArrayPtr) - if (rItemPtr) - { - ReleaseRef(*rItemPtr, rItemPtr->GetRefCount()); // for RefCount check in dtor - delete rItemPtr; - } + { + ReleaseRef(*rItemPtr, rItemPtr->GetRefCount()); // for RefCount check in dtor + delete rItemPtr; + } rArrayPtr->clear(); // let pImpl->DeleteItems() delete item arrays in maPoolItems } @@ -516,11 +510,10 @@ void SfxItemPool::Delete() if (rArrayPtr) { for (auto& rItemPtr : *rArrayPtr) - if (rItemPtr) - { - ReleaseRef(*rItemPtr, rItemPtr->GetRefCount()); // for RefCount check in dtor - delete rItemPtr; - } + { + ReleaseRef(*rItemPtr, rItemPtr->GetRefCount()); // for RefCount check in dtor + delete rItemPtr; + } rArrayPtr->clear(); // let pImpl->DeleteItems() delete item arrays in maPoolItems } @@ -627,9 +620,6 @@ const SfxPoolItem& SfxItemPool::Put( const SfxPoolItem& rItem, sal_uInt16 nWhich pItemArr = pImpl->maPoolItems[nIndex].get(); } - std::vector<SfxPoolItem*>::iterator ppFree; - bool ppFreeIsSet = false; - // Is this a 'poolable' item - ie. should we re-use and return // the same underlying item for equivalent (==) SfxPoolItems? if ( IsItemPoolable_Impl( nIndex ) ) @@ -637,10 +627,10 @@ const SfxPoolItem& SfxItemPool::Put( const SfxPoolItem& rItem, sal_uInt16 nWhich // if is already in a pool, then it is worth checking if it is in this one. if ( IsPooledItem(&rItem) ) { - auto it = pItemArr->maPtrToIndex.find(const_cast<SfxPoolItem *>(&rItem)); + auto it = pItemArr->find(const_cast<SfxPoolItem *>(&rItem)); // 1. search for an identical pointer in the pool - if (it != pItemArr->maPtrToIndex.cend()) + if (it != pItemArr->end()) { AddRef(rItem); return rItem; @@ -650,37 +640,11 @@ const SfxPoolItem& SfxItemPool::Put( const SfxPoolItem& rItem, sal_uInt16 nWhich // 2. search for an item with matching attributes. for (auto itr = pItemArr->begin(); itr != pItemArr->end(); ++itr) { - if (*itr) + if (**itr == rItem) { - if (**itr == rItem) - { - AddRef(**itr); - return **itr; - } + AddRef(**itr); + return **itr; } - else - { - if (!ppFreeIsSet) - { - ppFree = itr; - ppFreeIsSet = true; - } - } - } - } - else - { - // Unconditionally insert; check for a recently freed place - if (!pItemArr->maFree.empty()) - { - auto itr = pItemArr->begin(); - sal_uInt32 nIdx = pItemArr->maFree.back(); - pItemArr->maFree.pop_back(); - - assert(nIdx < pItemArr->size()); - std::advance(itr, nIdx); - ppFreeIsSet = true; - ppFree = itr; } } @@ -698,20 +662,8 @@ const SfxPoolItem& SfxItemPool::Put( const SfxPoolItem& rItem, sal_uInt16 nWhich AddRef( *pNewItem ); // 4. finally insert into the pointer array - assert( pItemArr->maPtrToIndex.find(pNewItem) == pItemArr->maPtrToIndex.end() ); - if ( !ppFreeIsSet ) - { - sal_uInt32 nOffset = pItemArr->size(); - pItemArr->maPtrToIndex.insert(std::make_pair(pNewItem, nOffset)); - pItemArr->push_back( pNewItem ); - } - else - { - sal_uInt32 nOffset = std::distance(pItemArr->begin(), ppFree); - pItemArr->maPtrToIndex.insert(std::make_pair(pNewItem, nOffset)); - assert(*ppFree == nullptr); - *ppFree = pNewItem; - } + assert( pItemArr->find(pNewItem) == pItemArr->end() ); + pItemArr->insert( pNewItem ); return *pNewItem; } @@ -755,17 +707,11 @@ void SfxItemPool::Remove( const SfxPoolItem& rItem ) SfxPoolItemArray_Impl* pItemArr = pImpl->maPoolItems[nIndex].get(); assert(pItemArr && "removing Item not in Pool"); - SfxPoolItemArray_Impl::PoolItemPtrToIndexMap::const_iterator it - = pItemArr->maPtrToIndex.find(const_cast<SfxPoolItem *>(&rItem)); - if (it != pItemArr->maPtrToIndex.end()) + auto it = pItemArr->find(const_cast<SfxPoolItem *>(&rItem)); + if (it != pItemArr->end()) { - sal_uInt32 nIdx = it->second; - assert(nIdx < pItemArr->size()); - SfxPoolItem*& p = (*pItemArr)[nIdx]; - assert(p == &rItem); - - if ( p->GetRefCount() ) //! - ReleaseRef( *p ); + if ( rItem.GetRefCount() ) //! + ReleaseRef( rItem ); else { assert(false && "removing Item without ref"); @@ -773,15 +719,10 @@ void SfxItemPool::Remove( const SfxPoolItem& rItem ) // FIXME: Hack, for as long as we have problems with the Outliner // See other MI-REF - if ( 0 == p->GetRefCount() && nWhich < 4000 ) + if ( 0 == rItem.GetRefCount() && nWhich < 4000 ) { - DELETEZ(p); - - // remove ourselves from the hash - pItemArr->maPtrToIndex.erase(it); - - // record that this slot is free - pItemArr->maFree.push_back( nIdx ); + delete &rItem; + pItemArr->erase(it); } return; @@ -859,28 +800,33 @@ const sal_uInt16* SfxItemPool::GetFrozenIdRanges() const const SfxPoolItem *SfxItemPool::GetItem2Default(sal_uInt16 nWhich) const { - return GetItem2(nWhich, SFX_ITEMS_DEFAULT); + if ( !IsInRange(nWhich) ) + { + if ( pImpl->mpSecondary ) + return pImpl->mpSecondary->GetItem2Default( nWhich ); + assert(false && "unknown WhichId - cannot resolve surrogate"); + return nullptr; + } + return (*pImpl->mpStaticDefaults)[ GetIndex_Impl(nWhich) ]; } -const SfxPoolItem *SfxItemPool::GetItem2(sal_uInt16 nWhich, sal_uInt32 nOfst) const +SfxItemPool::Item2Range SfxItemPool::GetItemSurrogates(sal_uInt16 nWhich) const { + static const o3tl::sorted_vector<SfxPoolItem*> EMPTY; + if ( !IsInRange(nWhich) ) { if ( pImpl->mpSecondary ) - return pImpl->mpSecondary->GetItem2( nWhich, nOfst ); + return pImpl->mpSecondary->GetItemSurrogates( nWhich ); assert(false && "unknown WhichId - cannot resolve surrogate"); - return nullptr; + return { EMPTY.end(), EMPTY.end() }; } - // default attribute? - if ( nOfst == SFX_ITEMS_DEFAULT ) - return (*pImpl->mpStaticDefaults)[ GetIndex_Impl(nWhich) ]; - SfxPoolItemArray_Impl* pItemArr = pImpl->maPoolItems[GetIndex_Impl(nWhich)].get(); - if( pItemArr && nOfst < pItemArr->size() ) - return (*pItemArr)[nOfst]; + if( pItemArr ) + return { pItemArr->begin(), pItemArr->end() }; - return nullptr; + return { EMPTY.end(), EMPTY.end() }; } sal_uInt32 SfxItemPool::GetItemCount2(sal_uInt16 nWhich) const @@ -969,8 +915,7 @@ void SfxItemPool::dumpAsXml(xmlTextWriterPtr pWriter) const for (auto const & rArrayPtr : pImpl->maPoolItems) if (rArrayPtr) for (auto const & rItem : *rArrayPtr) - if (rItem) - rItem->dumpAsXml(pWriter); + rItem->dumpAsXml(pWriter); xmlTextWriterEndElement(pWriter); } diff --git a/svl/source/items/poolio.cxx b/svl/source/items/poolio.cxx index c73e85c2b0ac..569f61c07d24 100644 --- a/svl/source/items/poolio.cxx +++ b/svl/source/items/poolio.cxx @@ -32,28 +32,7 @@ /// or all ref counts are decreased void SfxPoolItemArray_Impl::clear() { - maPoolItemVector.clear(); - maFree.clear(); - maPtrToIndex.clear(); -} - -/// Re-build our free list and pointer hash. -void SfxPoolItemArray_Impl::ReHash() -{ - maFree.clear(); - maPtrToIndex.clear(); - - for (size_t nIdx = 0; nIdx < size(); ++nIdx) - { - SfxPoolItem *pItem = (*this)[nIdx]; - if (!pItem) - maFree.push_back(nIdx); - else - { - maPtrToIndex.insert(std::make_pair(pItem,nIdx)); - assert(maPtrToIndex.find(pItem) != maPtrToIndex.end()); - } - } + maPoolItemSet.clear(); } sal_uInt16 SfxItemPool::GetFirstWhich() const @@ -107,9 +86,8 @@ bool SfxItemPool::CheckItemInPool(const SfxPoolItem *pItem) const SfxPoolItemArray_Impl* pItemArr = pImpl->maPoolItems[GetIndex_Impl(pItem->Which())].get(); DBG_ASSERT(pItemArr, "ItemArr is not available"); - for ( size_t i = 0; i < pItemArr->size(); ++i ) + for ( auto p : *pItemArr ) { - const SfxPoolItem *p = (*pItemArr)[i]; if ( p == pItem ) return true; } |