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 <list>
  15 #include <unordered_map>
  16
  17 namespace o3tl
  18 {
  19
  20 /** LRU map
  21  *
  22  * Similar to unordered_map (it actually uses it) with additionally functionality
  23  * which removes the entries that have been "least recently used" when the size
  24  * hits the specified capacity.
  25  *
  26  * It only implements the minimal methods needed and the implementation is NOT
  27  * thread safe.
  28  *
  29  * The implementation is as simple as possible but it still uses O(1) complexity
  30  * for most of the operations with a combination unordered map and linked list.
  31  *
  32  **/
  33 template<typename Key, typename Value, class KeyHash = std::hash<Key>>
  34 class lru_map final
  35 {
  36 private:
  37     typedef typename std::pair<Key, Value> key_value_pair_t;
  38     typedef std::list<key_value_pair_t> list_t;
  39     typedef typename list_t::iterator list_iterator_t;
  40     typedef typename list_t::const_iterator list_const_iterator_t;
  41
  42     typedef std::unordered_map<Key, list_iterator_t, KeyHash> map_t;
  43     typedef typename map_t::iterator map_iterator_t;
  44     typedef typename map_t::const_iterator map_const_iterator_t;
  45
  46     list_t mLruList;
  47     map_t mLruMap;
  48     const size_t mMaxSize;
  49
  50     void checkLRU()
  51     {
  52         if (mLruMap.size() > mMaxSize)
  53         {
  54             // remove from map
  55             mLruMap.erase(mLruList.back().first);
  56             // remove from list
  57             mLruList.pop_back();
  58         }
  59     }
  60 public:
  61     typedef list_iterator_t iterator;
  62     typedef list_const_iterator_t const_iterator;
  63
  64     lru_map(size_t nMaxSize)
  65         : mMaxSize(nMaxSize)
  66     {}
  67
  68     void insert(key_value_pair_t& rPair)
  69     {
  70         map_iterator_t iterator = mLruMap.find(rPair.first);
  71
  72         if (iterator == mLruMap.end()) // doesn't exist -> add to queue and map
  73         {
  74             // add to front of the list
  75             mLruList.push_front(rPair);
  76             // add the list position (iterator) to the map
  77             mLruMap[rPair.first] = mLruList.begin();
  78             checkLRU();
  79         }
  80         else // already exists -> replace value
  81         {
  82             // replace value
  83             iterator->second->second = rPair.second;
  84             // bring to front of the lru list
  85             mLruList.splice(mLruList.begin(), mLruList, iterator->second);
  86         }
  87     }
  88
  89     void insert(key_value_pair_t&& rPair)
  90     {
  91         map_iterator_t iterator = mLruMap.find(rPair.first);
  92
  93         if (iterator == mLruMap.end()) // doesn't exist -> add to list and map
  94         {
  95             // add to front of the list
  96             mLruList.push_front(std::move(rPair));
  97             // add the list position (iterator) to the map
  98             mLruMap[rPair.first] = mLruList.begin();
  99             checkLRU();
 100         }
 101         else // already exists -> replace value
 102         {
 103             // replace value
 104             iterator->second->second = std::move(rPair.second);
 105             // push to back of the lru list
 106             mLruList.splice(mLruList.begin(), mLruList, iterator->second);
 107         }
 108     }
 109
 110     const list_const_iterator_t find(const Key& key)
 111     {
 112         const map_iterator_t iterator = mLruMap.find(key);
 113         if (iterator == mLruMap.cend()) // can't find entry for the key
 114         {
 115             // return empty iterator
 116             return mLruList.cend();
 117         }
 118         else
 119         {
 120             // push to back of the lru list
 121             mLruList.splice(mLruList.begin(), mLruList, iterator->second);
 122             return iterator->second;
 123         }
 124     }
 125
 126     const list_const_iterator_t end() const
 127     {
 128         return mLruList.end();
 129     }
 130
 131     size_t size() const
 132     {
 133         return mLruList.size();
 134     }
 135 };
 136
 137 }
 138
 139 #endif /* INCLUDED_O3TL_LRU_MAP_HXX */
 140
 141 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */