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