1 /*
2  * Copyright 2019, The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #pragma once
18 
19 #include <inttypes.h>
20 #include "log.h"
21 
22 #include <chrono>
23 #include <unordered_map>
24 
25 // Default amount of time until a cache entry expires
26 static constexpr auto kDefaultCacheTimeout = std::chrono::seconds(30);
27 
28 template<typename Key,
29          typename Value,
30          typename Timestamp = std::chrono::steady_clock::time_point>
31 class Cache {
32 public:
33     using TimedValue = std::pair<Timestamp, Value>;
34 
35     using MapType = std::unordered_map<Key, TimedValue>;
36     using key_type = typename MapType::key_type;
37     using mapped_type = Value;
38 
39     class ConstIterator {
40     public:
41         class IterPair {
42         public:
IterPair(const Key & key,const Value & value)43             IterPair(const Key& key, const Value& value)
44                 : first(key), second(value) {
45             }
46 
47             const IterPair* operator->() const { return this; }
48             const Key& first;
49             const Value& second;
50         private:
51         };
52 
ConstIterator(typename MapType::const_iterator current)53         ConstIterator(typename MapType::const_iterator current)
54             : mCurrent(current) { }
55 
56         IterPair operator->() const {
57             return IterPair(mCurrent->first, mCurrent->second.second);
58         }
59 
60         IterPair operator*() const {
61             return IterPair(mCurrent->first, mCurrent->second.second);
62         }
63 
64         bool operator==(const ConstIterator& other) const {
65             return mCurrent == other.mCurrent;
66         }
67 
68         bool operator!=(const ConstIterator& other) const {
69             return mCurrent != other.mCurrent;
70         }
71 
internal()72         typename MapType::const_iterator internal() const { return mCurrent; }
73 
74     private:
75         typename MapType::const_iterator mCurrent;
76     };
77     class Iterator {
78     public:
79         class IterPair {
80         public:
IterPair(const Key & key,Value & value)81             IterPair(const Key& key, Value& value) : first(key), second(value) { }
82 
83             IterPair* operator->() { return this; }
84             const Key& first;
85             Value& second;
86         private:
87         };
88 
Iterator(typename MapType::iterator current)89         Iterator(typename MapType::iterator current) : mCurrent(current) { }
90 
91         IterPair operator->() {
92             return IterPair(mCurrent->first, mCurrent->second.second);
93         }
94 
95         IterPair operator*() {
96             return IterPair(mCurrent->first, mCurrent->second.second);
97         }
98 
99         bool operator==(const Iterator& other) const {
100             return mCurrent == other.mCurrent;
101         }
102 
103         bool operator!=(const Iterator& other) const {
104             return mCurrent != other.mCurrent;
105         }
106 
internal()107         typename MapType::iterator internal() { return mCurrent; }
108 
109     private:
110         typename MapType::iterator mCurrent;
111     };
112 
113     using iterator = Iterator;
114     using const_iterator = ConstIterator;
115     using insert_return_type = std::pair<const_iterator, bool>;
116 
117     Cache(std::chrono::milliseconds timeout = kDefaultCacheTimeout)
mTimeout(timeout)118         : mTimeout(timeout) {
119     }
120 
121     template<typename M>
insert_or_assign(const key_type & key,M && value)122     insert_return_type insert_or_assign(const key_type& key, M&& value) {
123         std::pair<typename MapType::iterator,bool> inserted =
124             mMap.insert_or_assign(key, TimedValue(mCurrentTime,
125                                                   std::move(value)));
126         return insert_return_type(inserted.first, inserted.second);
127     }
128 
129     mapped_type& operator[](const key_type& key) {
130         TimedValue& v = mMap[key];
131         v.first = mCurrentTime;
132         return v.second;
133     }
134 
find(const key_type & key)135     iterator find(const key_type& key) {
136         return iterator(mMap.find(key));
137     }
138 
find(const key_type & key)139     const_iterator find(const key_type& key) const {
140         return const_iterator(mMap.find(key));
141     }
142 
erase(const_iterator pos)143     iterator erase(const_iterator pos) {
144         return iterator(mMap.erase(pos.internal()));
145     }
146 
erase(iterator pos)147     iterator erase(iterator pos) {
148         return iterator(mMap.erase(pos.internal()));
149     }
150 
erase(const key_type & key)151     size_t erase(const key_type& key) {
152         return mMap.erase(key);
153     }
154 
begin()155     iterator begin() {
156         return iterator(mMap.begin());
157     }
158 
end()159     iterator end() {
160         return iterator(mMap.end());
161     }
162 
begin()163     const_iterator begin() const {
164         return const_iterator(mMap.begin());
165     }
166 
end()167     const_iterator end() const {
168         return const_iterator(mMap.end());
169     }
170 
setCurrentTime(Timestamp currentTime)171     void setCurrentTime(Timestamp currentTime) {
172         mCurrentTime = currentTime;
173     }
174 
expireEntries()175     void expireEntries() {
176         for (auto it = mMap.begin(); it != mMap.end(); ) {
177             const Timestamp timestamp = it->second.first;
178             if (mCurrentTime > timestamp &&
179                 (mCurrentTime - timestamp) > mTimeout) {
180                 // This entry has expired, remove it
181                 it = mMap.erase(it);
182             } else {
183                 ++it;
184             }
185         }
186     }
187 private:
188     const std::chrono::milliseconds mTimeout;
189     Timestamp mCurrentTime;
190     MapType mMap;
191 };
192 
193