summaryrefslogtreecommitdiffstats
path: root/include/o3tl/lru_map.hxx
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-15 05:54:39 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-15 05:54:39 +0000
commit267c6f2ac71f92999e969232431ba04678e7437e (patch)
tree358c9467650e1d0a1d7227a21dac2e3d08b622b2 /include/o3tl/lru_map.hxx
parentInitial commit. (diff)
downloadlibreoffice-267c6f2ac71f92999e969232431ba04678e7437e.tar.xz
libreoffice-267c6f2ac71f92999e969232431ba04678e7437e.zip
Adding upstream version 4:24.2.0.upstream/4%24.2.0
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'include/o3tl/lru_map.hxx')
-rw-r--r--include/o3tl/lru_map.hxx297
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: */