1 // Copyright 2022 The Android Open Source Project 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #pragma once 16 17 #include <list> 18 #include <unordered_map> 19 20 template <typename Key, typename Value> 21 class LruCache { 22 public: LruCache(std::size_t maxSize)23 LruCache(std::size_t maxSize) : m_maxSize(maxSize) { 24 m_table.reserve(maxSize); 25 } 26 get(const Key & key)27 Value* get(const Key& key) { 28 auto tableIt = m_table.find(key); 29 if (tableIt == m_table.end()) { 30 return nullptr; 31 } 32 33 // Move to front. 34 auto elementsIt = tableIt->second; 35 m_elements.splice(elementsIt, m_elements, m_elements.begin()); 36 return &elementsIt->value; 37 } 38 set(const Key & key,Value && value)39 void set(const Key& key, Value&& value) { 40 auto tableIt = m_table.find(key); 41 if (tableIt == m_table.end()) { 42 if (m_table.size() >= m_maxSize) { 43 auto& kv = m_elements.back(); 44 m_table.erase(kv.key); 45 m_elements.pop_back(); 46 } 47 } else { 48 auto elementsIt = tableIt->second; 49 m_elements.erase(elementsIt); 50 } 51 m_elements.emplace_front(KeyValue{ 52 key, 53 std::forward<Value>(value), 54 }); 55 m_table[key] = m_elements.begin(); 56 } 57 remove(const Key & key)58 void remove(const Key& key) { 59 auto tableIt = m_table.find(key); 60 if (tableIt == m_table.end()) { 61 return; 62 } 63 auto elementsIt = tableIt->second; 64 m_elements.erase(elementsIt); 65 m_table.erase(tableIt); 66 } 67 clear()68 void clear() { 69 m_elements.clear(); 70 m_table.clear(); 71 } 72 73 private: 74 struct KeyValue { 75 Key key; 76 Value value; 77 }; 78 79 const std::size_t m_maxSize; 80 // Front is the most recently used and back is the least recently used. 81 std::list<KeyValue> m_elements; 82 std::unordered_map<Key, typename std::list<KeyValue>::iterator> m_table; 83 }; 84