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 LruCache {
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    */
LruCache(const size_t & capacity,const std::string & log_tag)45   LruCache(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   LruCache(LruCache const&) = delete;
55   LruCache& operator=(LruCache const&) = delete;
56 
~LruCache()57   ~LruCache() { 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