Adding upstream version 4:24.2.0.upstream/4%24.2.0

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 297 insertions, 0 deletions

diff --git a/include/o3tl/lru_map.hxx b/include/o3tl/lru_map.hxx
new file mode 100644
index 0000000000..7e046fd1db
--- /dev/null
+++ b/include/o3tl/lru_map.hxx
@@ -0,0 +1,297 @@
+/* -*- 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/.
+ *
+ */
+
+#ifndef INCLUDED_O3TL_LRU_MAP_HXX
+#define INCLUDED_O3TL_LRU_MAP_HXX
+
+#include <cassert>
+#include <list>
+#include <unordered_map>
+#include <cstddef>
+
+namespace o3tl
+{
+namespace detail
+{
+// Helper base class to keep total cost for lru_map with custom item size.
+// Custom size is specified by the ValueSize functor, the default of each
+// item counting as 1 is specified using the void type.
+template <class ValueSize> class lru_map_base
+{
+public:
+    // Returns total of ValueSize for all items.
+    size_t total_size() const { return mCurrentSize; }
+
+protected:
+    size_t mCurrentSize = 0; // sum of ValueSize for all items
+};
+
+// By default cost of each item is 1, so it doesn't need to be tracked.
+template <> class lru_map_base<void>
+{
+};
+} // namespace
+
+/** LRU map
+ *
+ * Similar to unordered_map (it actually uses it) with additionally functionality
+ * which removes the entries that have been "least recently used" when the size
+ * hits the specified capacity.
+ *
+ * It only implements the minimal methods needed and the implementation is NOT
+ * thread safe.
+ *
+ * The implementation is as simple as possible but it still uses O(1) complexity
+ * for most of the operations with a combination unordered map and linked list.
+ *
+ * It is optionally possible to specify a function for ValueSize template
+ * argument (that can be called as 'size_t func(Value)') that will return
+ * a size (cost) for an item instead of the default size of 1 for each item.
+ * The size of an item must not change for an item (if needed, re-insert
+ * the item). A newly inserted item is guaranteed to be in the container,
+ * even if its size exceeds the maximum size.
+ *
+ **/
+template <typename Key, typename Value, class KeyHash = std::hash<Key>,
+          class KeyEqual = std::equal_to<Key>, class ValueSize = void>
+class lru_map final : public detail::lru_map_base<ValueSize>
+{
+public:
+    typedef typename std::pair<Key, Value> key_value_pair_t;
+
+private:
+    typedef std::list<key_value_pair_t> list_t;
+    typedef typename list_t::iterator list_iterator_t;
+    typedef typename list_t::const_iterator list_const_iterator_t;
+
+    typedef std::unordered_map<Key, list_iterator_t, KeyHash, KeyEqual> map_t;
+    typedef typename map_t::iterator map_iterator_t;
+    typedef typename map_t::const_iterator map_const_iterator_t;
+
+    list_t mLruList;
+    map_t mLruMap;
+    size_t mMaxSize;
+
+    void addSize(const Value& value)
+    {
+        // by default total size is equal to number of items
+        if constexpr (!std::is_void_v<ValueSize>)
+            this->mCurrentSize += ValueSize()(value);
+    }
+
+    void removeSize(const Value& value)
+    {
+        // by default total size is equal to number of items
+        if constexpr (!std::is_void_v<ValueSize>)
+        {
+            size_t itemSize = ValueSize()(value);
+            assert(itemSize <= this->mCurrentSize);
+            this->mCurrentSize -= itemSize;
+        }
+    }
+
+    void removeOldestItem()
+    {
+        removeSize(mLruList.back().second);
+        // remove from map
+        mLruMap.erase(mLruList.back().first);
+        // remove from list
+        mLruList.pop_back();
+    }
+
+    void checkLRUItemInsert()
+    {
+        if constexpr (std::is_void_v<ValueSize>)
+        { // One added, so it's enough to remove one, if needed.
+            if (mLruMap.size() > mMaxSize)
+                removeOldestItem();
+        }
+        else
+        {
+            // This must leave at least one item (it's called from insert).
+            while (this->mCurrentSize > mMaxSize && mLruList.size() > 1)
+                removeOldestItem();
+        }
+    }
+
+    void checkLRUItemUpdate()
+    {
+        // Item update does not change total size by default.
+        if constexpr (!std::is_void_v<ValueSize>)
+        {
+            // This must leave at least one item (it's called from insert).
+            while (this->mCurrentSize > mMaxSize && mLruList.size() > 1)
+                removeOldestItem();
+        }
+    }
+
+    void checkLRUMaxSize()
+    {
+        if constexpr (std::is_void_v<ValueSize>)
+        {
+            while (mLruMap.size() > mMaxSize)
+                removeOldestItem();
+        }
+        else
+        {
+            while (this->mCurrentSize > mMaxSize)
+                removeOldestItem();
+        }
+    }
+
+    void clearSize()
+    {
+        if constexpr (!std::is_void_v<ValueSize>)
+        {
+#ifdef DBG_UTIL
+            for (const key_value_pair_t& item : mLruList)
+                removeSize(item.second);
+            assert(this->mCurrentSize == 0);
+#else
+            this->mCurrentSize = 0;
+#endif
+        }
+    }
+
+public:
+    typedef list_iterator_t iterator;
+    typedef list_const_iterator_t const_iterator;
+
+    lru_map(size_t nMaxSize)
+        : mMaxSize(nMaxSize)
+    {
+        assert(mMaxSize > 0);
+    }
+    ~lru_map()
+    {
+        clearSize();
+        // Some code .e.g. SalBitmap likes to remove itself from a cache during it's destructor, which means we
+        // get calls into lru_map while we are in destruction, so use the swap-and-clear idiom to avoid those problems.
+        mLruMap.clear();
+        list_t().swap(mLruList);
+    }
+
+    void setMaxSize(size_t nMaxSize)
+    {
+        mMaxSize = nMaxSize;
+        assert(mMaxSize > 0);
+        checkLRUMaxSize();
+    }
+
+    void insert(key_value_pair_t& rPair)
+    {
+        map_iterator_t i = mLruMap.find(rPair.first);
+
+        if (i == mLruMap.end()) // doesn't exist -> add to queue and map
+        {
+            addSize(rPair.second);
+            // add to front of the list
+            mLruList.push_front(rPair);
+            // add the list position (iterator) to the map
+            auto it = mLruList.begin();
+            mLruMap[it->first] = it;
+            checkLRUItemInsert();
+        }
+        else // already exists -> replace value
+        {
+            // update total cost
+            removeSize(i->second->second);
+            addSize(rPair.second);
+            // replace value
+            i->second->second = rPair.second;
+            // bring to front of the lru list
+            mLruList.splice(mLruList.begin(), mLruList, i->second);
+            checkLRUItemUpdate();
+        }
+    }
+
+    void insert(key_value_pair_t&& rPair)
+    {
+        map_iterator_t i = mLruMap.find(rPair.first);
+
+        if (i == mLruMap.end()) // doesn't exist -> add to list and map
+        {
+            addSize(rPair.second);
+            // add to front of the list
+            mLruList.push_front(std::move(rPair));
+            // add the list position (iterator) to the map
+            auto it = mLruList.begin();
+            mLruMap[it->first] = it;
+            checkLRUItemInsert();
+        }
+        else // already exists -> replace value
+        {
+            removeSize(i->second->second);
+            addSize(rPair.second);
+            // replace value
+            i->second->second = std::move(rPair.second);
+            // push to back of the lru list
+            mLruList.splice(mLruList.begin(), mLruList, i->second);
+            checkLRUItemUpdate();
+        }
+    }
+
+    list_const_iterator_t find(const Key& key)
+    {
+        const map_iterator_t i = mLruMap.find(key);
+        if (i == mLruMap.cend()) // can't find entry for the key
+        {
+            // return empty iterator
+            return mLruList.cend();
+        }
+        else
+        {
+            // push to back of the lru list
+            mLruList.splice(mLruList.begin(), mLruList, i->second);
+            return i->second;
+        }
+    }
+
+    // reverse-iterates the list removing all items matching the predicate
+    template <class UnaryPredicate> void remove_if(UnaryPredicate pred)
+    {
+        auto it = mLruList.rbegin();
+        while (it != mLruList.rend())
+        {
+            if (pred(*it))
+            {
+                removeSize(it->second);
+                mLruMap.erase(it->first);
+                it = decltype(it){ mLruList.erase(std::next(it).base()) };
+            }
+            else
+                ++it;
+        }
+    }
+
+    list_const_iterator_t begin() const { return mLruList.cbegin(); }
+
+    list_const_iterator_t end() const { return mLruList.cend(); }
+
+    size_t size() const
+    {
+        assert(mLruMap.size() == mLruList.size());
+        return mLruMap.size();
+    }
+
+    // size_t total_size() const; - only if custom ValueSize
+
+    void clear()
+    {
+        clearSize();
+        mLruMap.clear();
+        mLruList.clear();
+    }
+};
+}
+
+#endif /* INCLUDED_O3TL_LRU_MAP_HXX */
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */