1 /****************************************************************************** 2 * 3 * Copyright 2020 Google, Inc. 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at: 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 ******************************************************************************/ 18 19 #pragma once 20 21 #include <functional> 22 #include <iterator> 23 #include <list> 24 #include <mutex> 25 #include <optional> 26 #include <thread> 27 #include <unordered_map> 28 29 #include <base/logging.h> 30 31 namespace bluetooth { 32 33 namespace common { 34 35 template <typename K, typename V> 36 class LegacyLruCache { 37 public: 38 using Node = std::pair<K, V>; 39 /** 40 * Constructor of the cache 41 * 42 * @param capacity maximum size of the cache 43 * @param log_tag, keyword to put at the head of log. 44 */ LegacyLruCache(const size_t & capacity,const std::string & log_tag)45 LegacyLruCache(const size_t& capacity, const std::string& log_tag) 46 : capacity_(capacity) { 47 if (capacity_ == 0) { 48 // don't allow invalid capacity 49 LOG(FATAL) << log_tag << " unable to have 0 LRU Cache capacity"; 50 } 51 } 52 53 // delete copy constructor 54 LegacyLruCache(LegacyLruCache const&) = delete; 55 LegacyLruCache& operator=(LegacyLruCache const&) = delete; 56 ~LegacyLruCache()57 ~LegacyLruCache() { Clear(); } 58 59 /** 60 * Clear the cache 61 */ Clear()62 void Clear() { 63 std::lock_guard<std::recursive_mutex> lock(lru_mutex_); 64 lru_map_.clear(); 65 node_list_.clear(); 66 } 67 68 /** 69 * Same as Get, but return an iterator to the accessed element 70 * 71 * Modifying the returned iterator does not warm up the cache 72 * 73 * @param key 74 * @return pointer to the underlying value to allow in-place modification 75 * nullptr when not found, will be invalidated when the key is evicted 76 */ Find(const K & key)77 V* Find(const K& key) { 78 std::lock_guard<std::recursive_mutex> lock(lru_mutex_); 79 auto map_iterator = lru_map_.find(key); 80 if (map_iterator == lru_map_.end()) { 81 return nullptr; 82 } 83 node_list_.splice(node_list_.begin(), node_list_, map_iterator->second); 84 return &(map_iterator->second->second); 85 } 86 87 /** 88 * Get the value of a key, and move the key to the head of cache, if there is 89 * one 90 * 91 * @param key 92 * @param value, output parameter of value of the key 93 * @return true if the cache has the key 94 */ Get(const K & key,V * value)95 bool Get(const K& key, V* value) { 96 CHECK(value != nullptr); 97 std::lock_guard<std::recursive_mutex> lock(lru_mutex_); 98 auto value_ptr = Find(key); 99 if (value_ptr == nullptr) { 100 return false; 101 } 102 *value = *value_ptr; 103 return true; 104 } 105 106 /** 107 * Check if the cache has the input key, move the key to the head 108 * if there is one 109 * 110 * @param key 111 * @return true if the cache has the key 112 */ HasKey(const K & key)113 bool HasKey(const K& key) { 114 std::lock_guard<std::recursive_mutex> lock(lru_mutex_); 115 return Find(key) != nullptr; 116 } 117 118 /** 119 * Put a key-value pair to the head of cache 120 * 121 * @param key 122 * @param value 123 * @return evicted node if tail value is popped, std::nullopt if no value 124 * is popped. std::optional can be treated as a boolean as well 125 */ Put(const K & key,V value)126 std::optional<Node> Put(const K& key, V value) { 127 std::lock_guard<std::recursive_mutex> lock(lru_mutex_); 128 auto value_ptr = Find(key); 129 if (value_ptr != nullptr) { 130 // hasKey() calls get(), therefore already move the node to the head 131 *value_ptr = std::move(value); 132 return std::nullopt; 133 } 134 135 // remove tail 136 std::optional<Node> ret = std::nullopt; 137 if (lru_map_.size() == capacity_) { 138 lru_map_.erase(node_list_.back().first); 139 ret = std::move(node_list_.back()); 140 node_list_.pop_back(); 141 } 142 // insert to dummy next; 143 node_list_.emplace_front(key, std::move(value)); 144 lru_map_.emplace(key, node_list_.begin()); 145 return ret; 146 } 147 148 /** 149 * Delete a key from cache 150 * 151 * @param key 152 * @return true if deleted successfully 153 */ Remove(const K & key)154 bool Remove(const K& key) { 155 std::lock_guard<std::recursive_mutex> lock(lru_mutex_); 156 auto map_iterator = lru_map_.find(key); 157 if (map_iterator == lru_map_.end()) { 158 return false; 159 } 160 161 // remove from the list 162 node_list_.erase(map_iterator->second); 163 164 // delete key from map 165 lru_map_.erase(map_iterator); 166 167 return true; 168 } 169 170 /** 171 * Return size of the cache 172 * 173 * @return size of the cache 174 */ Size()175 int Size() const { 176 std::lock_guard<std::recursive_mutex> lock(lru_mutex_); 177 return lru_map_.size(); 178 } 179 180 private: 181 std::list<Node> node_list_; 182 size_t capacity_; 183 std::unordered_map<K, typename std::list<Node>::iterator> lru_map_; 184 mutable std::recursive_mutex lru_mutex_; 185 }; 186 187 } // namespace common 188 } // namespace bluetooth 189