include/o3tl/lru_map.hxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  */
  10
  11 #ifndef INCLUDED_O3TL_LRU_MAP_HXX
  12 #define INCLUDED_O3TL_LRU_MAP_HXX
  13
  14 #include <cassert>
  15 #include <list>
  16 #include <unordered_map>
  17 #include <cstddef>
  18
  19 namespace o3tl
  20 {
  21 namespace detail
  22 {
  23 // Helper base class to keep total cost for lru_map with custom item size.
  24 // Custom size is specified by the ValueSize functor, the default of each
  25 // item counting as 1 is specified using the void type.
  26 template <class ValueSize> class lru_map_base
  27 {
  28 public:
  29     // Returns total of ValueSize for all items.
  30     size_t total_size() const { return mCurrentSize; }
  31
  32 protected:
  33     size_t mCurrentSize = 0; // sum of ValueSize for all items
  34 };
  35
  36 // By default cost of each item is 1, so it doesn't need to be tracked.
  37 template <> class lru_map_base<void>
  38 {
  39 };
  40 } // namespace
  41
  42 /** LRU map
  43  *
  44  * Similar to unordered_map (it actually uses it) with additionally functionality
  45  * which removes the entries that have been "least recently used" when the size
  46  * hits the specified capacity.
  47  *
  48  * It only implements the minimal methods needed and the implementation is NOT
  49  * thread safe.
  50  *
  51  * The implementation is as simple as possible but it still uses O(1) complexity
  52  * for most of the operations with a combination unordered map and linked list.
  53  *
  54  * It is optionally possible to specify a function for ValueSize template
  55  * argument (that can be called as 'size_t func(Value)') that will return
  56  * a size (cost) for an item instead of the default size of 1 for each item.
  57  * The size of an item must not change for an item (if needed, re-insert
  58  * the item). A newly inserted item is guaranteed to be in the container,
  59  * even if its size exceeds the maximum size.
  60  *
  61  **/
  62 template <typename Key, typename Value, class KeyHash = std::hash<Key>,
  63           class KeyEqual = std::equal_to<Key>, class ValueSize = void>
  64 class lru_map final : public detail::lru_map_base<ValueSize>
  65 {
  66 public:
  67     typedef typename std::pair<Key, Value> key_value_pair_t;
  68
  69 private:
  70     typedef std::list<key_value_pair_t> list_t;
  71     typedef typename list_t::iterator list_iterator_t;
  72     typedef typename list_t::const_iterator list_const_iterator_t;
  73
  74     typedef std::unordered_map<Key, list_iterator_t, KeyHash, KeyEqual> map_t;
  75     typedef typename map_t::iterator map_iterator_t;
  76     typedef typename map_t::const_iterator map_const_iterator_t;
  77
  78     list_t mLruList;
  79     map_t mLruMap;
  80     size_t mMaxSize;
  81
  82     void addSize(const Value& value)
  83     {
  84         // by default total size is equal to number of items
  85         if constexpr (!std::is_void_v<ValueSize>)
  86             this->mCurrentSize += ValueSize()(value);
  87     }
  88
  89     void removeSize(const Value& value)
  90     {
  91         // by default total size is equal to number of items
  92         if constexpr (!std::is_void_v<ValueSize>)
  93         {
  94             size_t itemSize = ValueSize()(value);
  95             assert(itemSize <= this->mCurrentSize);
  96             this->mCurrentSize -= itemSize;
  97         }
  98     }
  99
 100     void removeOldestItem()
 101     {
 102         removeSize(mLruList.back().second);
 103         // remove from map
 104         mLruMap.erase(mLruList.back().first);
 105         // remove from list
 106         mLruList.pop_back();
 107     }
 108
 109     void checkLRUItemInsert()
 110     {
 111         if constexpr (std::is_void_v<ValueSize>)
 112         { // One added, so it's enough to remove one, if needed.
 113             if (mLruMap.size() > mMaxSize)
 114                 removeOldestItem();
 115         }
 116         else
 117         {
 118             // This must leave at least one item (it's called from insert).
 119             while (this->mCurrentSize > mMaxSize && mLruMap.size() > 1)
 120                 removeOldestItem();
 121         }
 122     }
 123
 124     void checkLRUItemUpdate()
 125     {
 126         // Item update does not change total size by default.
 127         if constexpr (!std::is_void_v<ValueSize>)
 128         {
 129             // This must leave at least one item (it's called from insert).
 130             while (this->mCurrentSize > mMaxSize && mLruMap.size() > 1)
 131                 removeOldestItem();
 132         }
 133     }
 134
 135     void checkLRUMaxSize()
 136     {
 137         if constexpr (std::is_void_v<ValueSize>)
 138         {
 139             while (mLruMap.size() > mMaxSize)
 140                 removeOldestItem();
 141         }
 142         else
 143         {
 144             while (this->mCurrentSize > mMaxSize)
 145                 removeOldestItem();
 146         }
 147     }
 148
 149     void clearSize()
 150     {
 151         if constexpr (!std::is_void_v<ValueSize>)
 152         {
 153 #ifdef DBG_UTIL
 154             for (const key_value_pair_t& item : mLruList)
 155                 removeSize(item.second);
 156             assert(this->mCurrentSize == 0);
 157 #else
 158             this->mCurrentSize = 0;
 159 #endif
 160         }
 161     }
 162
 163 public:
 164     typedef list_iterator_t iterator;
 165     typedef list_const_iterator_t const_iterator;
 166
 167     lru_map(size_t nMaxSize)
 168         : mMaxSize(nMaxSize)
 169     {
 170         assert(mMaxSize > 0);
 171     }
 172     ~lru_map()
 173     {
 174         clearSize();
 175         // Some code .e.g. SalBitmap likes to remove itself from a cache during it's destructor, which means we
 176         // get calls into lru_map while we are in destruction, so use the swap-and-clear idiom to avoid those problems.
 177         mLruMap.clear();
 178         list_t().swap(mLruList);
 179     }
 180
 181     void setMaxSize(size_t nMaxSize)
 182     {
 183         mMaxSize = nMaxSize;
 184         assert(mMaxSize > 0);
 185         checkLRUMaxSize();
 186     }
 187
 188     void insert(key_value_pair_t& rPair)
 189     {
 190         map_iterator_t i = mLruMap.find(rPair.first);
 191
 192         if (i == mLruMap.end()) // doesn't exist -> add to queue and map
 193         {
 194             addSize(rPair.second);
 195             // add to front of the list
 196             mLruList.push_front(rPair);
 197             // add the list position (iterator) to the map
 198             auto it = mLruList.begin();
 199             mLruMap[it->first] = it;
 200             checkLRUItemInsert();
 201         }
 202         else // already exists -> replace value
 203         {
 204             // update total cost
 205             removeSize(i->second->second);
 206             addSize(rPair.second);
 207             // replace value
 208             i->second->second = rPair.second;
 209             // bring to front of the lru list
 210             mLruList.splice(mLruList.begin(), mLruList, i->second);
 211             checkLRUItemUpdate();
 212         }
 213     }
 214
 215     void insert(key_value_pair_t&& rPair)
 216     {
 217         map_iterator_t i = mLruMap.find(rPair.first);
 218
 219         if (i == mLruMap.end()) // doesn't exist -> add to list and map
 220         {
 221             addSize(rPair.second);
 222             // add to front of the list
 223             mLruList.push_front(std::move(rPair));
 224             // add the list position (iterator) to the map
 225             auto it = mLruList.begin();
 226             mLruMap[it->first] = it;
 227             checkLRUItemInsert();
 228         }
 229         else // already exists -> replace value
 230         {
 231             removeSize(i->second->second);
 232             addSize(rPair.second);
 233             // replace value
 234             i->second->second = std::move(rPair.second);
 235             // push to back of the lru list
 236             mLruList.splice(mLruList.begin(), mLruList, i->second);
 237             checkLRUItemUpdate();
 238         }
 239     }
 240
 241     list_const_iterator_t find(const Key& key)
 242     {
 243         const map_iterator_t i = mLruMap.find(key);
 244         if (i == mLruMap.cend()) // can't find entry for the key
 245         {
 246             // return empty iterator
 247             return mLruList.cend();
 248         }
 249         else
 250         {
 251             // push to back of the lru list
 252             mLruList.splice(mLruList.begin(), mLruList, i->second);
 253             return i->second;
 254         }
 255     }
 256
 257     // reverse-iterates the list removing all items matching the predicate
 258     template <class UnaryPredicate> void remove_if(UnaryPredicate pred)
 259     {
 260         auto it = mLruList.rbegin();
 261         while (it != mLruList.rend())
 262         {
 263             if (pred(*it))
 264             {
 265                 removeSize(it->second);
 266                 mLruMap.erase(it->first);
 267                 it = decltype(it){ mLruList.erase(std::next(it).base()) };
 268             }
 269             else
 270                 ++it;
 271         }
 272     }
 273
 274     list_const_iterator_t begin() const { return mLruList.cbegin(); }
 275
 276     list_const_iterator_t end() const { return mLruList.cend(); }
 277
 278     size_t size() const
 279     {
 280         assert(mLruMap.size() == mLruList.size());
 281         return mLruMap.size();
 282     }
 283
 284     // size_t total_size() const; - only if custom ValueSize
 285
 286     void clear()
 287     {
 288         clearSize();
 289         mLruMap.clear();
 290         mLruList.clear();
 291     }
 292 };
 293 }
 294
 295 #endif /* INCLUDED_O3TL_LRU_MAP_HXX */
 296
 297 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */