diff options
Diffstat (limited to 'include/o3tl/lru_map.hxx')
| -rw-r--r-- | include/o3tl/lru_map.hxx | 299 |
1 files changed, 299 insertions, 0 deletions
diff --git a/include/o3tl/lru_map.hxx b/include/o3tl/lru_map.hxx new file mode 100644 index 000000000..859617e5d --- /dev/null +++ b/include/o3tl/lru_map.hxx @@ -0,0 +1,299 @@ +/* -*- 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 <algorithm> +#include <cassert> +#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 + * 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: */ |