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 #include "check.h" 32 33 namespace bluetooth { 34 35 namespace common { 36 37 template <typename K, typename V> 38 class LegacyLruCache { 39 public: 40 using Node = std::pair<K, V>; 41 /** 42 * Constructor of the cache 43 * 44 * @param capacity maximum size of the cache 45 * @param log_tag, keyword to put at the head of log. 46 */ LegacyLruCache(const size_t & capacity,const std::string & log_tag)47 LegacyLruCache(const size_t& capacity, const std::string& log_tag) 48 : capacity_(capacity) { 49 if (capacity_ == 0) { 50 // don't allow invalid capacity 51 LOG(FATAL) << log_tag << " unable to have 0 LRU Cache capacity"; 52 } 53 } 54 55 // delete copy constructor 56 LegacyLruCache(LegacyLruCache const&) = delete; 57 LegacyLruCache& operator=(LegacyLruCache const&) = delete; 58 ~LegacyLruCache()59 ~LegacyLruCache() { Clear(); } 60 61 /** 62 * Clear the cache 63 */ Clear()64 void Clear() { 65 std::lock_guard<std::recursive_mutex> lock(lru_mutex_); 66 lru_map_.clear(); 67 node_list_.clear(); 68 } 69 70 /** 71 * Same as Get, but return an iterator to the accessed element 72 * 73 * Modifying the returned iterator does not warm up the cache 74 * 75 * @param key 76 * @return pointer to the underlying value to allow in-place modification 77 * nullptr when not found, will be invalidated when the key is evicted 78 */ Find(const K & key)79 V* Find(const K& key) { 80 std::lock_guard<std::recursive_mutex> lock(lru_mutex_); 81 auto map_iterator = lru_map_.find(key); 82 if (map_iterator == lru_map_.end()) { 83 return nullptr; 84 } 85 node_list_.splice(node_list_.begin(), node_list_, map_iterator->second); 86 return &(map_iterator->second->second); 87 } 88 89 /** 90 * Get the value of a key, and move the key to the head of cache, if there is 91 * one 92 * 93 * @param key 94 * @param value, output parameter of value of the key 95 * @return true if the cache has the key 96 */ Get(const K & key,V * value)97 bool Get(const K& key, V* value) { 98 CHECK(value != nullptr); 99 std::lock_guard<std::recursive_mutex> lock(lru_mutex_); 100 auto value_ptr = Find(key); 101 if (value_ptr == nullptr) { 102 return false; 103 } 104 *value = *value_ptr; 105 return true; 106 } 107 108 /** 109 * Check if the cache has the input key, move the key to the head 110 * if there is one 111 * 112 * @param key 113 * @return true if the cache has the key 114 */ HasKey(const K & key)115 bool HasKey(const K& key) { 116 std::lock_guard<std::recursive_mutex> lock(lru_mutex_); 117 return Find(key) != nullptr; 118 } 119 120 /** 121 * Put a key-value pair to the head of cache 122 * 123 * @param key 124 * @param value 125 * @return evicted node if tail value is popped, std::nullopt if no value 126 * is popped. std::optional can be treated as a boolean as well 127 */ Put(const K & key,V value)128 std::optional<Node> Put(const K& key, V value) { 129 std::lock_guard<std::recursive_mutex> lock(lru_mutex_); 130 auto value_ptr = Find(key); 131 if (value_ptr != nullptr) { 132 // hasKey() calls get(), therefore already move the node to the head 133 *value_ptr = std::move(value); 134 return std::nullopt; 135 } 136 137 // remove tail 138 std::optional<Node> ret = std::nullopt; 139 if (lru_map_.size() == capacity_) { 140 lru_map_.erase(node_list_.back().first); 141 ret = std::move(node_list_.back()); 142 node_list_.pop_back(); 143 } 144 // insert to dummy next; 145 node_list_.emplace_front(key, std::move(value)); 146 lru_map_.emplace(key, node_list_.begin()); 147 return ret; 148 } 149 150 /** 151 * Delete a key from cache 152 * 153 * @param key 154 * @return true if deleted successfully 155 */ Remove(const K & key)156 bool Remove(const K& key) { 157 std::lock_guard<std::recursive_mutex> lock(lru_mutex_); 158 auto map_iterator = lru_map_.find(key); 159 if (map_iterator == lru_map_.end()) { 160 return false; 161 } 162 163 // remove from the list 164 node_list_.erase(map_iterator->second); 165 166 // delete key from map 167 lru_map_.erase(map_iterator); 168 169 return true; 170 } 171 172 /** 173 * Return size of the cache 174 * 175 * @return size of the cache 176 */ Size()177 int Size() const { 178 std::lock_guard<std::recursive_mutex> lock(lru_mutex_); 179 return lru_map_.size(); 180 } 181 182 private: 183 std::list<Node> node_list_; 184 size_t capacity_; 185 std::unordered_map<K, typename std::list<Node>::iterator> lru_map_; 186 mutable std::recursive_mutex lru_mutex_; 187 }; 188 189 } // namespace common 190 } // namespace bluetooth 191