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