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>

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;
     }