1 2 /** 3 * Copyright (C) 2018-present MongoDB, Inc. 4 * 5 * This program is free software: you can redistribute it and/or modify 6 * it under the terms of the Server Side Public License, version 1, 7 * as published by MongoDB, Inc. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * Server Side Public License for more details. 13 * 14 * You should have received a copy of the Server Side Public License 15 * along with this program. If not, see 16 * <http://www.mongodb.com/licensing/server-side-public-license>. 17 * 18 * As a special exception, the copyright holders give permission to link the 19 * code of portions of this program with the OpenSSL library under certain 20 * conditions as described in each individual source file and distribute 21 * linked combinations including the program with the OpenSSL library. You 22 * must comply with the Server Side Public License in all respects for 23 * all of the code used other than as permitted herein. If you modify file(s) 24 * with this exception, you may extend this exception to your version of the 25 * file(s), but you are not obligated to do so. If you do not wish to do so, 26 * delete this exception statement from your version. If you delete this 27 * exception statement from all source files in the program, then also delete 28 * it in the license file. 29 */ 30 31 #pragma once 32 33 #include <cstdlib> 34 #include <iterator> 35 #include <list> 36 37 #include <boost/optional.hpp> 38 39 #include "mongo/base/disallow_copying.h" 40 #include "mongo/stdx/unordered_map.h" 41 42 namespace mongo { 43 44 /** 45 * A caching structure with a least recently used (LRU) replacement policy. 46 * The number of entries allowed in the cache is set upon construction. 47 * 48 * This cache is not thread safe. 49 * 50 * Internally, this structure holds two containers: a list for LRU ordering and an 51 * unordered_map for fast lookup. The add(), get(), and remove() operations are all O(1). 52 * 53 * Iteration over the cache will visit elements in order of last use, from most 54 * recently used to least recently used. 55 */ 56 template <typename K, 57 typename V, 58 typename Hash = typename stdx::unordered_map<K, V>::hasher, 59 typename KeyEqual = typename stdx::unordered_map<K, V, Hash>::key_equal> 60 class LRUCache { 61 MONGO_DISALLOW_COPYING(LRUCache); 62 63 public: LRUCache(std::size_t maxSize)64 explicit LRUCache(std::size_t maxSize) : _maxSize(maxSize) {} 65 66 LRUCache(LRUCache&&) = delete; 67 LRUCache& operator=(LRUCache&&) = delete; 68 69 using ListEntry = std::pair<K, V>; 70 using List = std::list<ListEntry>; 71 72 using iterator = typename List::iterator; 73 using const_iterator = typename List::const_iterator; 74 75 using Map = stdx::unordered_map<K, iterator, Hash, KeyEqual>; 76 77 using key_type = K; 78 using mapped_type = V; 79 80 /** 81 * Inserts a new entry into the cache. If the given key already exists in the cache, 82 * then we will drop the old entry and replace it with the given new entry. The cache 83 * takes ownership of the new entry. 84 * 85 * If the cache is full when add() is called, the least recently used entry will be 86 * evicted from the cache and returned to the caller. 87 * 88 * This method does not provide the strong exception safe guarantee. If a call 89 * to this method throws, the cache may be left in an inconsistent state. 90 */ add(const K & key,V entry)91 boost::optional<V> add(const K& key, V entry) { 92 // If the key already exists, delete it first. 93 auto i = this->_map.find(key); 94 if (i != this->_map.end()) { 95 this->_list.erase(i->second); 96 } 97 98 this->_list.push_front(std::make_pair(key, std::move(entry))); 99 this->_map[key] = this->_list.begin(); 100 101 // If the store has grown beyond its allowed size, 102 // evict the least recently used entry. 103 if (this->size() > this->_maxSize) { 104 auto pair = std::move(this->_list.back()); 105 auto result = std::move(pair.second); 106 107 this->_map.erase(pair.first); 108 this->_list.pop_back(); 109 110 invariant(this->size() <= this->_maxSize); 111 return std::move(result); 112 } 113 114 invariant(this->size() <= this->_maxSize); 115 return boost::none; 116 } 117 118 /** 119 * Finds an element in the cache by key. 120 */ find(const K & key)121 iterator find(const K& key) { 122 return this->promote(key); 123 } 124 125 /** 126 * Finds and element in the cache by key, without promoting the found 127 * element to be the least recently used. 128 * 129 * This method is meant for testing and other callers that wish to "observe" 130 * items in the cache without actually using them. Using this method over 131 * the find(...) method above will prevent the LRUCache from functioning 132 * properly. 133 */ cfind(const K & key)134 const_iterator cfind(const K& key) const { 135 auto it = this->_map.find(key); 136 // TODO(SERVER-28890): Remove the function-style cast when MSVC's 137 // `std::list< ... >::iterator` implementation doesn't conflict with their `/Zc:ternary` 138 // flag support . 139 return (it == this->_map.end()) ? this->end() : const_iterator(it->second); 140 } 141 142 /** 143 * Promotes the element matching the given key, if one exists in the cache, 144 * to the least recently used element. 145 */ promote(const K & key)146 iterator promote(const K& key) { 147 auto it = this->_map.find(key); 148 return (it == this->_map.end()) ? this->end() : this->promote(it->second); 149 } 150 151 /** 152 * Promotes the element pointed to by the given iterator to be the least 153 * recently used element in the cache. 154 */ promote(const iterator & iter)155 iterator promote(const iterator& iter) { 156 if (iter == this->_list.end()) { 157 return iter; 158 } 159 160 this->_list.splice(this->_list.begin(), this->_list, iter); 161 return this->_list.begin(); 162 } 163 164 /** 165 * Promotes the element pointed to by the given const_iterator to be the 166 * least recently used element in the cache. 167 */ promote(const const_iterator & iter)168 const_iterator promote(const const_iterator& iter) { 169 if (iter == this->_list.cend()) { 170 return iter; 171 } 172 173 this->_list.splice(this->_list.begin(), this->_list, iter); 174 return this->_list.begin(); 175 } 176 177 /** 178 * Removes the element in the cache stored for this key, if one 179 * exists. Returns the count of elements erased. 180 */ erase(const K & key)181 typename Map::size_type erase(const K& key) { 182 auto it = this->_map.find(key); 183 if (it == this->_map.end()) { 184 return 0; 185 } 186 187 this->_list.erase(it->second); 188 this->_map.erase(it); 189 return 1; 190 } 191 192 /** 193 * Removes the element pointed to by the given iterator from this 194 * cache, and returns an iterator to the next least recently used 195 * element, or the end iterator, if no such element exists. 196 */ erase(iterator it)197 iterator erase(iterator it) { 198 invariant(it != this->_list.end()); 199 invariant(this->_map.erase(it->first) == 1); 200 return this->_list.erase(it); 201 } 202 203 /** 204 * Removes all items from the cache. 205 */ clear()206 void clear() { 207 this->_map.clear(); 208 this->_list.clear(); 209 } 210 211 /** 212 * If the given key has a matching element stored in the cache, returns true. 213 * Otherwise, returns false. 214 */ hasKey(const K & key)215 bool hasKey(const K& key) const { 216 return _map.find(key) != this->_map.end(); 217 } 218 219 /** 220 * Returns the number of elements currently in the cache. 221 */ size()222 std::size_t size() const { 223 return this->_list.size(); 224 } 225 empty()226 bool empty() const { 227 return this->_list.empty(); 228 } 229 230 /** 231 * Returns an iterator pointing to the most recently used element in the cache. 232 */ begin()233 iterator begin() { 234 return this->_list.begin(); 235 } 236 237 /** 238 * Returns an iterator pointing past the least recently used element in the cache. 239 */ end()240 iterator end() { 241 return this->_list.end(); 242 } 243 244 /** 245 * Returns a const_iterator pointing to the most recently used element in the cache. 246 */ begin()247 const_iterator begin() const { 248 return this->_list.begin(); 249 } 250 251 /** 252 * Returns a const_iterafor pointing past the least recently used element in the cache. 253 */ end()254 const_iterator end() const { 255 return this->_list.end(); 256 } 257 258 /** 259 * Returns a const_iterator pointing to the most recently used element in the cache. 260 */ cbegin()261 const_iterator cbegin() const { 262 return this->_list.cbegin(); 263 } 264 265 /** 266 * Returns a const_iterator pointing past the least recently used element in the cache. 267 */ cend()268 const_iterator cend() const { 269 return this->_list.cend(); 270 } 271 count(const K & key)272 typename Map::size_type count(const K& key) const { 273 return this->_map.count(key); 274 } 275 276 private: 277 // The maximum allowable number of entries in the cache. 278 const std::size_t _maxSize; 279 280 // (K, V) pairs are stored in this std::list. They are sorted in order 281 // of use, where the front is the most recently used and the back is the 282 // least recently used. 283 List _list; 284 285 // Maps from a key to the corresponding std::list entry. 286 Map _map; 287 }; 288 289 } // namespace mongo 290