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