include/o3tl/lru_map.hxx | 136 ++++++++++++++++++++++++++++++++++++++++++-----
o3tl/qa/test-lru_map.cxx | 30 ++++++++++
2 files changed, 154 insertions(+), 12 deletions(-)
New commits:
commit 46097559ed1ca17c08fd77943e088451d633adfe
Author: Luboš Luňák <l.lu...@collabora.com>
AuthorDate: Sun May 1 18:52:19 2022 +0200
Commit: Tomaž Vajngerl <qui...@gmail.com>
CommitDate: Mon May 2 09:26:31 2022 +0200
support custom item size (cost) for o3tl::lru_map
When used with items that may vary significantly in size (such
as SalLayoutGlyphsCache storing glyphs for texts of different sizes)
limiting lru_map to just the number of items performs poorly,
since it may use only small amount of memory if items are small
or it may spent a huge amount of memory if items are large.
As extra optional template argument to o3tl::lru_map that is a functor
that provides cost of item each, and the total size is based on this
instead of each item having cost 1.
Change-Id: I2b326754fe63eb4bd20010d4cea615187407e26c
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/133672
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.gran...@collabora.co.uk>
Reviewed-by: Tomaž Vajngerl <qui...@gmail.com>
diff --git a/include/o3tl/lru_map.hxx b/include/o3tl/lru_map.hxx
index 41c215255c7a..b3c90621edf2 100644
--- a/include/o3tl/lru_map.hxx
+++ b/include/o3tl/lru_map.hxx
@@ -16,9 +16,31 @@
#include <list>
#include <unordered_map>
#include <cstddef>
+#include <type_traits>
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
@@ -31,10 +53,17 @@ namespace o3tl
* 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 istead 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 lru_map final
+ 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;
@@ -52,14 +81,84 @@ private:
map_t mLruMap;
size_t mMaxSize;
- void checkLRU()
+ 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 (mLruMap.size() > mMaxSize)
+ if constexpr (std::is_void_v<ValueSize>)
+ { // One added, so it's enough to remove one, if needed.
+ if (mLruMap.size() > mMaxSize)
+ removeOldestItem();
+ }
+ else
{
- // remove from map
- mLruMap.erase(mLruList.back().first);
- // remove from list
- mLruList.pop_back();
+ // 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
}
}
@@ -74,6 +173,7 @@ public:
}
~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();
@@ -83,8 +183,7 @@ public:
void setMaxSize(size_t nMaxSize)
{
mMaxSize = nMaxSize ? nMaxSize : std::min(mLruMap.max_size(),
mLruList.max_size());
- while (mLruMap.size() > mMaxSize)
- checkLRU();
+ checkLRUMaxSize();
}
void insert(key_value_pair_t& rPair)
@@ -93,19 +192,24 @@ public:
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;
- checkLRU();
+ 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();
}
}
@@ -115,19 +219,23 @@ public:
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;
- checkLRU();
+ 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();
}
}
@@ -155,6 +263,7 @@ public:
{
if (pred(*it))
{
+ removeSize(it->second);
mLruMap.erase(it->first);
it = decltype(it){ mLruList.erase(std::next(it).base()) };
}
@@ -173,8 +282,11 @@ public:
return mLruMap.size();
}
+ // size_t total_size() const; - only if custom ValueSize
+
void clear()
{
+ clearSize();
mLruMap.clear();
mLruList.clear();
}
diff --git a/o3tl/qa/test-lru_map.cxx b/o3tl/qa/test-lru_map.cxx
index e749e7bd85ec..edc9d7e1bf98 100644
--- a/o3tl/qa/test-lru_map.cxx
+++ b/o3tl/qa/test-lru_map.cxx
@@ -29,6 +29,7 @@ public:
void testRemoveIf();
void testNoAutoCleanup();
void testChangeMaxSize();
+ void testCustomItemSize();
CPPUNIT_TEST_SUITE(lru_map_test);
CPPUNIT_TEST(testBaseUsage);
@@ -39,6 +40,7 @@ public:
CPPUNIT_TEST(testRemoveIf);
CPPUNIT_TEST(testNoAutoCleanup);
CPPUNIT_TEST(testChangeMaxSize);
+ CPPUNIT_TEST(testCustomItemSize);
CPPUNIT_TEST_SUITE_END();
};
@@ -323,6 +325,34 @@ void lru_map_test::testChangeMaxSize()
CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
}
+void lru_map_test::testCustomItemSize()
+{
+ struct cost_is_value
+ {
+ size_t operator()(int i) { return i; };
+ };
+ o3tl::lru_map<int, int, std::hash<int>, std::equal_to<int>, cost_is_value>
lru(5);
+ lru.insert({ 1, 1 });
+ lru.insert({ 2, 2 });
+ // Adding this one will remove the first one, since then the total
+ // cost would be 6, more than the maximum 5.
+ lru.insert({ 3, 3 });
+ CPPUNIT_ASSERT_EQUAL(size_t(2), lru.size());
+ CPPUNIT_ASSERT_EQUAL(size_t(5), lru.total_size());
+ // Drop the last item.
+ lru.remove_if([](std::pair<int, int> i) { return i.first == 3; });
+ CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
+ CPPUNIT_ASSERT_EQUAL(size_t(2), lru.total_size());
+ // This should drop everything except for keeping this one (an exception
that
+ // keeps the last item inserted regardless of limit).
+ lru.insert({ 4, 4 });
+ CPPUNIT_ASSERT_EQUAL(size_t(1), lru.size());
+ CPPUNIT_ASSERT_EQUAL(size_t(4), lru.total_size());
+ lru.clear();
+ CPPUNIT_ASSERT_EQUAL(size_t(0), lru.size());
+ CPPUNIT_ASSERT_EQUAL(size_t(0), lru.total_size());
+}
+
CPPUNIT_TEST_SUITE_REGISTRATION(lru_map_test);
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
