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
  18 namespace o3tl
  19 {
  20
  21 /** LRU map
  22  *
  23  * Similar to unordered_map (it actually uses it) with additionally functionality
  24  * which removes the entries that have been "least recently used" when the size
  25  * hits the specified capacity.
  26  *
  27  * It only implements the minimal methods needed and the implementation is NOT
  28  * thread safe.
  29  *
  30  * The implementation is as simple as possible but it still uses O(1) complexity
  31  * for most of the operations with a combination unordered map and linked list.
  32  *
  33  **/
  34 template<typename Key, typename Value, class KeyHash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
  35 class lru_map final
  36 {
  37 public:
  38     typedef typename std::pair<Key, Value> key_value_pair_t;
  39
  40 private:
  41     typedef std::list<key_value_pair_t> list_t;
  42     typedef typename list_t::iterator list_iterator_t;
  43     typedef typename list_t::const_iterator list_const_iterator_t;
  44
  45     typedef std::unordered_map<Key, list_iterator_t, KeyHash, KeyEqual> map_t;
  46     typedef typename map_t::iterator map_iterator_t;
  47     typedef typename map_t::const_iterator map_const_iterator_t;
  48
  49     list_t mLruList;
  50     map_t mLruMap;
  51     const size_t mMaxSize;
  52
  53     void checkLRU()
  54     {
  55         if (mLruMap.size() > mMaxSize)
  56         {
  57             // remove from map
  58             mLruMap.erase(mLruList.back().first);
  59             // remove from list
  60             mLruList.pop_back();
  61         }
  62     }
  63
  64 public:
  65     typedef list_iterator_t iterator;
  66     typedef list_const_iterator_t const_iterator;
  67
  68     // a size of 0 effectively disables the LRU cleanup code
  69     lru_map(size_t nMaxSize)
  70         : mMaxSize(nMaxSize ? nMaxSize : std::min(mLruMap.max_size(), mLruList.max_size()))
  71     {}
  72     ~lru_map()
  73     {
  74         // Some code .e.g. SalBitmap likes to remove itself from a cache during it's destructor, which means we
  75         // get calls into lru_map while we are in destruction, so use the swap-and-clear idiom to avoid those problems.
  76         mLruMap.clear();
  77         list_t aLruListTemp;
  78         aLruListTemp.swap(mLruList);
  79     }
  80
  81     void insert(key_value_pair_t& rPair)
  82     {
  83         map_iterator_t i = mLruMap.find(rPair.first);
  84
  85         if (i == mLruMap.end()) // doesn't exist -> add to queue and map
  86         {
  87             // add to front of the list
  88             mLruList.push_front(rPair);
  89             // add the list position (iterator) to the map
  90             auto it = mLruList.begin();
  91             mLruMap[it->first] = it;
  92             checkLRU();
  93         }
  94         else // already exists -> replace value
  95         {
  96             // replace value
  97             i->second->second = rPair.second;
  98             // bring to front of the lru list
  99             mLruList.splice(mLruList.begin(), mLruList, i->second);
 100         }
 101     }
 102
 103     void insert(key_value_pair_t&& rPair)
 104     {
 105         map_iterator_t i = mLruMap.find(rPair.first);
 106
 107         if (i == mLruMap.end()) // doesn't exist -> add to list and map
 108         {
 109             // add to front of the list
 110             mLruList.push_front(std::move(rPair));
 111             // add the list position (iterator) to the map
 112             auto it = mLruList.begin();
 113             mLruMap[it->first] = it;
 114             checkLRU();
 115         }
 116         else // already exists -> replace value
 117         {
 118             // replace value
 119             i->second->second = std::move(rPair.second);
 120             // push to back of the lru list
 121             mLruList.splice(mLruList.begin(), mLruList, i->second);
 122         }
 123     }
 124
 125     const list_const_iterator_t find(const Key& key)
 126     {
 127         const map_iterator_t i = mLruMap.find(key);
 128         if (i == mLruMap.cend()) // can't find entry for the key
 129         {
 130             // return empty iterator
 131             return mLruList.cend();
 132         }
 133         else
 134         {
 135             // push to back of the lru list
 136             mLruList.splice(mLruList.begin(), mLruList, i->second);
 137             return i->second;
 138         }
 139     }
 140
 141     // reverse-iterates the list removing all items matching the predicate
 142     template<class UnaryPredicate>
 143     void remove_if(UnaryPredicate pred)
 144     {
 145         auto it = mLruList.rbegin();
 146         while (it != mLruList.rend())
 147         {
 148             if (pred(*it))
 149             {
 150                 mLruMap.erase(it->first);
 151                 it = decltype(it){ mLruList.erase(std::next(it).base()) };
 152             }
 153             else
 154                 ++it;
 155         }
 156     }
 157
 158     const list_const_iterator_t begin() const
 159     {
 160         return mLruList.cbegin();
 161     }
 162
 163     const list_const_iterator_t end() const
 164     {
 165         return mLruList.cend();
 166     }
 167
 168     size_t size() const
 169     {
 170         assert(mLruMap.size() == mLruList.size());
 171         return mLruMap.size();
 172     }
 173
 174     void clear()
 175     {
 176         mLruMap.clear();
 177         mLruList.clear();
 178     }
 179 };
 180
 181 }
 182
 183 #endif /* INCLUDED_O3TL_LRU_MAP_HXX */
 184
 185 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */