std::unordered_set<T*> -> o3tl::sorted_vector

which is much better for CPU cache, since the representation is more
compact, and since we almost always do insert() in pointer order,
there is surprisingly little sorting

Also add a count() method for compatibility with std::set and the
proposed std::flat_set

Change-Id: I2a3211dc59919cfec5cac1497530a4c3600d50ca
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/87793
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>

12 files changed, 29 insertions, 35 deletions

diff --git a/include/o3tl/sorted_vector.hxx b/include/o3tl/sorted_vector.hxx
index 088f5a2aa214..28ef75817fa7 100644
--- a/include/o3tl/sorted_vector.hxx
+++ b/include/o3tl/sorted_vector.hxx
@@ -198,6 +198,11 @@ public:
         return (ret.second) ? ret.first : m_vector.end();
     }
 
+    size_type count(const Value& v) const
+    {
+        return find(v) != end() ? 1 : 0;
+    }
+
     bool operator==(const sorted_vector & other) const
     {
         return m_vector == other.m_vector;
diff --git a/sc/inc/externalrefmgr.hxx b/sc/inc/externalrefmgr.hxx
index b95d6d1a0fd1..128feab61894 100644
--- a/sc/inc/externalrefmgr.hxx
+++ b/sc/inc/externalrefmgr.hxx
@@ -39,6 +39,7 @@
 #include <unordered_set>
 #include <vector>
 #include <set>
+#include <o3tl/sorted_vector.hxx>
 #include <formula/ExternalReferenceHelper.hxx>
 
 class ScTokenArray;
@@ -381,14 +382,6 @@ public:
         LinkListener();
         virtual ~LinkListener() COVERITY_NOEXCEPT_FALSE = 0;
         virtual void notify(sal_uInt16 nFileId, LinkUpdateType eType) = 0;
-
-        struct Hash
-        {
-            size_t operator() (const LinkListener* p) const
-            {
-                return reinterpret_cast<size_t>(p);
-            }
-        };
     };
 
     /**
@@ -421,7 +414,7 @@ private:
 
     typedef std::unordered_map<sal_uInt16, SvNumberFormatterMergeMap> NumFmtMap;
 
-    typedef std::unordered_set<LinkListener*, LinkListener::Hash>  LinkListeners;
+    typedef o3tl::sorted_vector<LinkListener*>                     LinkListeners;
     typedef std::unordered_map<sal_uInt16, LinkListeners>          LinkListenerMap;
 
 public:
diff --git a/sc/inc/recursionhelper.hxx b/sc/inc/recursionhelper.hxx
index 9988a676203b..f741aa8bab67 100644
--- a/sc/inc/recursionhelper.hxx
+++ b/sc/inc/recursionhelper.hxx
@@ -25,7 +25,7 @@
 #include <list>
 #include <vector>
 #include <stack>
-#include <unordered_set>
+#include <o3tl/sorted_vector.hxx>
 
 class ScFormulaCell;
 
@@ -65,7 +65,7 @@ class ScRecursionHelper
     bool                                bConverging;
     bool                                bGroupsIndependent;
     std::vector< ScFormulaCell* >       aTemporaryGroupCells;
-    std::unordered_set< ScFormulaCellGroup* >* pFGSet;
+    o3tl::sorted_vector< ScFormulaCellGroup* >* pFGSet;
 
     void Init();
     void ResetIteration();
@@ -120,7 +120,7 @@ public:
     void AddTemporaryGroupCell(ScFormulaCell* cell);
     void CleanTemporaryGroupCells();
 
-    void SetFormulaGroupSet(std::unordered_set<ScFormulaCellGroup*>* pSet) { pFGSet = pSet; }
+    void SetFormulaGroupSet(o3tl::sorted_vector<ScFormulaCellGroup*>* pSet) { pFGSet = pSet; }
     bool HasFormulaGroupSet() { return pFGSet != nullptr; }
     bool CheckFGIndependence(ScFormulaCellGroup* pFG);
     void SetGroupsIndependent(bool bSet) { bGroupsIndependent = bSet; }
@@ -157,7 +157,7 @@ class ScCheckIndependentFGGuard
 public:
     ScCheckIndependentFGGuard() = delete;
     ScCheckIndependentFGGuard(ScRecursionHelper& rRecursionHelper,
-                              std::unordered_set<ScFormulaCellGroup*>* pSet);
+                              o3tl::sorted_vector<ScFormulaCellGroup*>* pSet);
     ~ScCheckIndependentFGGuard();
 
     bool AreGroupsIndependent();
diff --git a/sc/source/core/data/formulacell.cxx b/sc/source/core/data/formulacell.cxx
index c39b21341bd5..e1cb04eb3ad2 100644
--- a/sc/source/core/data/formulacell.cxx
+++ b/sc/source/core/data/formulacell.cxx
@@ -4717,7 +4717,7 @@ bool ScFormulaCell::CheckComputeDependencies(sc::FormulaLogger::GroupScope& rSco
 }
 
 static SCCOL lcl_probeLeftOrRightFGs(const ScFormulaCellGroupRef& xGroup, const ScDocument& rDoc,
-                                     std::unordered_set<ScFormulaCellGroup*>& rFGSet,
+                                     o3tl::sorted_vector<ScFormulaCellGroup*>& rFGSet,
                                      std::map<SCCOL, ScFormulaCell*>& rFGMap, bool bLeft)
 {
     const SCROW nLen = xGroup->mnLength;
@@ -4856,7 +4856,7 @@ bool ScFormulaCell::InterpretFormulaGroupThreading(sc::FormulaLogger::GroupScope
 
         SAL_INFO("sc.threaded", "Running " << nThreadCount << " threads");
 
-        std::unordered_set<ScFormulaCellGroup*> aFGSet;
+        o3tl::sorted_vector<ScFormulaCellGroup*> aFGSet;
         std::map<SCCOL, ScFormulaCell*> aFGMap;
         aFGSet.insert(mxGroup.get());
 
diff --git a/sc/source/core/tool/recursionhelper.cxx b/sc/source/core/tool/recursionhelper.cxx
index a13c60edf6fb..efbf924ab853 100644
--- a/sc/source/core/tool/recursionhelper.cxx
+++ b/sc/source/core/tool/recursionhelper.cxx
@@ -253,7 +253,7 @@ ScFormulaGroupDependencyComputeGuard::~ScFormulaGroupDependencyComputeGuard()
 }
 
 ScCheckIndependentFGGuard::ScCheckIndependentFGGuard(ScRecursionHelper& rRecursionHelper,
-                                                     std::unordered_set<ScFormulaCellGroup*>* pSet) :
+                                                     o3tl::sorted_vector<ScFormulaCellGroup*>* pSet) :
     mrRecHelper(rRecursionHelper),
     mbUsedFGSet(false)
 {
diff --git a/sc/source/filter/inc/xetable.hxx b/sc/source/filter/inc/xetable.hxx
index c4648533eb7e..de00784cc889 100644
--- a/sc/source/filter/inc/xetable.hxx
+++ b/sc/source/filter/inc/xetable.hxx
@@ -31,7 +31,7 @@
 #include <map>
 #include <memory>
 #include <unordered_map>
-#include <unordered_set>
+#include <o3tl/sorted_vector.hxx>
 
 class XclExtLst;
 
@@ -195,7 +195,7 @@ private:
     bool IsValidTokenArray( const ScTokenArray& rArray ) const;
 
     typedef std::unordered_map<const ScTokenArray*, XclExpShrfmlaRef> TokensType;
-    typedef std::unordered_set<const ScTokenArray*> BadTokenArraysType;
+    typedef o3tl::sorted_vector<const ScTokenArray*> BadTokenArraysType;
 
     TokensType         maRecMap;    /// Map containing the SHRFMLA records.
     BadTokenArraysType maBadTokens; /// shared tokens we should *not* export as SHRFMLA
diff --git a/stoc/source/invocation_adapterfactory/iafactory.cxx b/stoc/source/invocation_adapterfactory/iafactory.cxx
index 7e2aca96856e..060170fe420f 100644
--- a/stoc/source/invocation_adapterfactory/iafactory.cxx
+++ b/stoc/source/invocation_adapterfactory/iafactory.cxx
@@ -21,6 +21,7 @@
 #include <osl/diagnose.h>
 #include <osl/interlck.h>
 #include <osl/mutex.hxx>
+#include <o3tl/sorted_vector.hxx>
 #include <sal/log.hxx>
 
 #include <uno/dispatcher.h>
@@ -78,7 +79,7 @@ struct hash_ptr
 
 }
 
-typedef std::unordered_set< void *, hash_ptr > t_ptr_set;
+typedef o3tl::sorted_vector< void * > t_ptr_set;
 typedef std::unordered_map< void *, t_ptr_set, hash_ptr > t_ptr_map;
 
 namespace {
@@ -825,7 +826,7 @@ Reference< XInterface > FactoryImpl::createAdapter(
                 &adapter_set, m_receiver2adapters, xKey.get(), rTypes );
             if (nullptr == that) // again no entry
             {
-                pair< t_ptr_set::iterator, bool > i(adapter_set->insert(pNew));
+                pair< t_ptr_set::const_iterator, bool > i(adapter_set->insert(pNew));
                 SAL_WARN_IF(
                     !i.second, "stoc",
                     "set already contains " << *(i.first) << " != " << pNew);
diff --git a/sw/inc/swwait.hxx b/sw/inc/swwait.hxx
index ed256de76c12..ff9a4ad773a2 100644
--- a/sw/inc/swwait.hxx
+++ b/sw/inc/swwait.hxx
@@ -21,7 +21,7 @@
 
 #include "swdllapi.h"
 
-#include <unordered_set>
+#include <o3tl/sorted_vector.hxx>
 
 class SwDocShell;
 class SfxDispatcher;
@@ -42,7 +42,7 @@ private:
 
     SwDocShell& mrDoc;
     const bool mbLockUnlockDispatcher;
-    std::unordered_set< SfxDispatcher* > mpLockedDispatchers;
+    o3tl::sorted_vector< SfxDispatcher* > mpLockedDispatchers;
 };
 
 #endif
diff --git a/sw/source/core/doc/docnew.cxx b/sw/source/core/doc/docnew.cxx
index 1547ebf19abc..8c64c6a2862c 100644
--- a/sw/source/core/doc/docnew.cxx
+++ b/sw/source/core/doc/docnew.cxx
@@ -19,7 +19,7 @@
 
 #include <config_features.h>
 
-#include <unordered_set>
+#include <o3tl/sorted_vector.hxx>
 
 #include <doc.hxx>
 #include <proofreadingiterator.hxx>
@@ -915,7 +915,7 @@ static OUString lcl_FindUniqueName(SwWrtShell* pTargetShell, const OUString& rSt
 static bool lcl_PageDescOrFollowContainsHeaderFooter(const SwPageDesc& rPageDesc)
 {
     // remember already checked page descs to avoid cycle
-    std::unordered_set<const SwPageDesc*> aCheckedPageDescs;
+    o3tl::sorted_vector<const SwPageDesc*> aCheckedPageDescs;
     const SwPageDesc* pCurPageDesc = &rPageDesc;
     while (aCheckedPageDescs.count(pCurPageDesc) == 0)
     {
diff --git a/vcl/inc/graphic/Manager.hxx b/vcl/inc/graphic/Manager.hxx
index f1413877bb08..d127201266f5 100644
--- a/vcl/inc/graphic/Manager.hxx
+++ b/vcl/inc/graphic/Manager.hxx
@@ -21,7 +21,7 @@
 #include <memory>
 #include <mutex>
 #include <chrono>
-#include <unordered_set>
+#include <o3tl/sorted_vector.hxx>
 
 class ImpGraphic;
 
@@ -33,7 +33,7 @@ class Manager final
 {
 private:
     std::recursive_mutex maMutex; // instead of SolarMutex because graphics can live past vcl main
-    std::unordered_set<ImpGraphic*> m_pImpGraphicList;
+    o3tl::sorted_vector<ImpGraphic*> m_pImpGraphicList;
     std::chrono::seconds mnAllowedIdleTime;
     bool mbSwapEnabled;
     sal_Int64 mnMemoryLimit;
diff --git a/vcl/inc/salusereventlist.hxx b/vcl/inc/salusereventlist.hxx
index bf0e2a4fccbb..cc5aa88c930c 100644
--- a/vcl/inc/salusereventlist.hxx
+++ b/vcl/inc/salusereventlist.hxx
@@ -26,18 +26,12 @@
 #include <osl/thread.hxx>
 
 #include <list>
-#include <unordered_set>
+#include <o3tl/sorted_vector.hxx>
 
 class SalFrame;
 enum class SalEvent;
 
-struct SalFrameHash : public std::hash<sal_IntPtr>
-{
-    size_t operator()(const SalFrame* frame) const
-        { return std::hash<sal_IntPtr>::operator()( reinterpret_cast<sal_IntPtr>(frame) ); }
-};
-
-typedef std::unordered_set< SalFrame*, SalFrameHash > SalFrameSet;
+typedef o3tl::sorted_vector< SalFrame* > SalFrameSet;
 
 class VCL_PLUGIN_PUBLIC SalUserEventList
 {
diff --git a/vcl/inc/win/winlayout.hxx b/vcl/inc/win/winlayout.hxx
index c8da95d3fb3c..11ab6d553ca6 100644
--- a/vcl/inc/win/winlayout.hxx
+++ b/vcl/inc/win/winlayout.hxx
@@ -25,6 +25,7 @@
 #include <sallayout.hxx>
 #include <svsys.h>
 #include <win/salgdi.h>
+#include <o3tl/sorted_vector.hxx>
 
 class WinFontInstance;
 
@@ -60,7 +61,7 @@ class WinGlyphCache;
 
 struct GlobalWinGlyphCache
 {
-    std::unordered_set<WinGlyphCache*> maWinGlyphCaches;
+    o3tl::sorted_vector<WinGlyphCache*> maWinGlyphCaches;
 
     static GlobalWinGlyphCache * get();