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 checkLRU()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 lru_map(size_t nMaxSize)69 lru_map(size_t nMaxSize) 70 : mMaxSize(nMaxSize ? nMaxSize : std::min(mLruMap.max_size(), mLruList.max_size())) 71 {} ~lru_map()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 insert(key_value_pair_t & rPair)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 insert(key_value_pair_t && rPair)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 find(const Key & key)125 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> remove_if(UnaryPredicate pred)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 begin() const158 list_const_iterator_t begin() const 159 { 160 return mLruList.cbegin(); 161 } 162 end() const163 list_const_iterator_t end() const 164 { 165 return mLruList.cend(); 166 } 167 size() const168 size_t size() const 169 { 170 assert(mLruMap.size() == mLruList.size()); 171 return mLruMap.size(); 172 } 173 clear()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: */ 186