Flutter Engine
LruCache.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2012 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 #ifndef ANDROID_UTILS_LRU_CACHE_H
18 #define ANDROID_UTILS_LRU_CACHE_H
19 
20 #include <memory>
21 #include <unordered_set>
22 
23 #include "utils/TypeHelpers.h" // hash_t
24 
25 namespace android {
26 
27 /**
28  * GenerationCache callback used when an item is removed
29  */
30 template <typename EntryKey, typename EntryValue>
32  public:
33  virtual ~OnEntryRemoved(){};
34  virtual void operator()(EntryKey& key, EntryValue& value) = 0;
35 }; // class OnEntryRemoved
36 
37 template <typename TKey, typename TValue>
38 class LruCache {
39  public:
40  explicit LruCache(uint32_t maxCapacity);
41  virtual ~LruCache();
42 
43  enum Capacity {
45  };
46 
47  void setOnEntryRemovedListener(OnEntryRemoved<TKey, TValue>* listener);
48  size_t size() const;
49  const TValue& get(const TKey& key);
50  bool put(const TKey& key, const TValue& value);
51  bool remove(const TKey& key);
52  bool removeOldest();
53  void clear();
54  const TValue& peekOldestValue();
55 
56  private:
57  LruCache(const LruCache& that); // disallow copy constructor
58 
59  // Super class so that we can have entries having only a key reference, for
60  // searches.
61  class KeyedEntry {
62  public:
63  virtual const TKey& getKey() const = 0;
64  // Make sure the right destructor is executed so that keys and values are
65  // deleted.
66  virtual ~KeyedEntry() {}
67  };
68 
69  class Entry final : public KeyedEntry {
70  public:
71  TKey key;
72  TValue value;
73  Entry* parent;
74  Entry* child;
75 
76  Entry(TKey _key, TValue _value)
77  : key(_key), value(_value), parent(NULL), child(NULL) {}
78  const TKey& getKey() const final { return key; }
79  };
80 
81  class EntryForSearch : public KeyedEntry {
82  public:
83  const TKey& key;
84  EntryForSearch(const TKey& key_) : key(key_) {}
85  const TKey& getKey() const final { return key; }
86  };
87 
88  struct HashForEntry {
89  size_t operator()(const KeyedEntry* entry) const {
90  return hash_type(entry->getKey());
91  };
92  };
93 
94  struct EqualityForHashedEntries {
95  bool operator()(const KeyedEntry* lhs, const KeyedEntry* rhs) const {
96  return lhs->getKey() == rhs->getKey();
97  };
98  };
99 
100  // All entries in the set will be Entry*. Using the weaker KeyedEntry as to
101  // allow entries that have only a key reference, for searching.
102  typedef std::
103  unordered_set<KeyedEntry*, HashForEntry, EqualityForHashedEntries>
104  LruCacheSet;
105 
106  void attachToCache(Entry& entry);
107  void detachFromCache(Entry& entry);
108 
109  typename LruCacheSet::iterator findByKey(const TKey& key) {
110  EntryForSearch entryForSearch(key);
111  typename LruCacheSet::iterator result = mSet->find(&entryForSearch);
112  return result;
113  }
114 
115  std::unique_ptr<LruCacheSet> mSet;
116  OnEntryRemoved<TKey, TValue>* mListener;
117  Entry* mOldest;
118  Entry* mYoungest;
119  uint32_t mMaxCapacity;
120  TValue mNullValue;
121 
122  public:
123  // To be used like:
124  // while (it.next()) {
125  // it.value(); it.key();
126  // }
127  class Iterator {
128  public:
130  : mCache(cache),
131  mIterator(mCache.mSet->begin()),
132  mBeginReturned(false) {}
133 
134  bool next() {
135  if (mIterator == mCache.mSet->end()) {
136  return false;
137  }
138  if (!mBeginReturned) {
139  // mIterator has been initialized to the beginning and
140  // hasn't been returned. Do not advance:
141  mBeginReturned = true;
142  } else {
143  std::advance(mIterator, 1);
144  }
145  bool ret = (mIterator != mCache.mSet->end());
146  return ret;
147  }
148 
149  const TValue& value() const {
150  // All the elements in the set are of type Entry. See comment in the
151  // definition of LruCacheSet above.
152  return reinterpret_cast<Entry*>(*mIterator)->value;
153  }
154 
155  const TKey& key() const { return (*mIterator)->getKey(); }
156 
157  private:
158  const LruCache<TKey, TValue>& mCache;
159  typename LruCacheSet::iterator mIterator;
160  bool mBeginReturned;
161  };
162 };
163 
164 // Implementation is here, because it's fully templated
165 template <typename TKey, typename TValue>
166 LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity)
167  : mSet(new LruCacheSet()),
168  mListener(NULL),
169  mOldest(NULL),
170  mYoungest(NULL),
171  mMaxCapacity(maxCapacity),
172  mNullValue(0) {
173  mSet->max_load_factor(1.0);
174 };
175 
176 template <typename TKey, typename TValue>
178  // Need to delete created entries.
179  clear();
180 };
181 
182 template <typename K, typename V>
184  mListener = listener;
185 }
186 
187 template <typename TKey, typename TValue>
189  return mSet->size();
190 }
191 
192 template <typename TKey, typename TValue>
193 const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
194  typename LruCacheSet::const_iterator find_result = findByKey(key);
195  if (find_result == mSet->end()) {
196  return mNullValue;
197  }
198  // All the elements in the set are of type Entry. See comment in the
199  // definition of LruCacheSet above.
200  Entry* entry = reinterpret_cast<Entry*>(*find_result);
201  detachFromCache(*entry);
202  attachToCache(*entry);
203  return entry->value;
204 }
205 
206 template <typename TKey, typename TValue>
207 bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
208  if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
209  removeOldest();
210  }
211 
212  if (findByKey(key) != mSet->end()) {
213  return false;
214  }
215 
216  Entry* newEntry = new Entry(key, value);
217  mSet->insert(newEntry);
218  attachToCache(*newEntry);
219  return true;
220 }
221 
222 template <typename TKey, typename TValue>
223 bool LruCache<TKey, TValue>::remove(const TKey& key) {
224  typename LruCacheSet::const_iterator find_result = findByKey(key);
225  if (find_result == mSet->end()) {
226  return false;
227  }
228  // All the elements in the set are of type Entry. See comment in the
229  // definition of LruCacheSet above.
230  Entry* entry = reinterpret_cast<Entry*>(*find_result);
231  mSet->erase(entry);
232  if (mListener) {
233  (*mListener)(entry->key, entry->value);
234  }
235  detachFromCache(*entry);
236  delete entry;
237  return true;
238 }
239 
240 template <typename TKey, typename TValue>
242  if (mOldest != NULL) {
243  return remove(mOldest->key);
244  // TODO: should probably abort if false
245  }
246  return false;
247 }
248 
249 template <typename TKey, typename TValue>
251  if (mOldest) {
252  return mOldest->value;
253  }
254  return mNullValue;
255 }
256 
257 template <typename TKey, typename TValue>
259  if (mListener) {
260  for (Entry* p = mOldest; p != NULL; p = p->child) {
261  (*mListener)(p->key, p->value);
262  }
263  }
264  mYoungest = NULL;
265  mOldest = NULL;
266  for (auto entry : *mSet.get()) {
267  delete entry;
268  }
269  mSet->clear();
270 }
271 
272 template <typename TKey, typename TValue>
273 void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
274  if (mYoungest == NULL) {
275  mYoungest = mOldest = &entry;
276  } else {
277  entry.parent = mYoungest;
278  mYoungest->child = &entry;
279  mYoungest = &entry;
280  }
281 }
282 
283 template <typename TKey, typename TValue>
284 void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
285  if (entry.parent != NULL) {
286  entry.parent->child = entry.child;
287  } else {
288  mOldest = entry.child;
289  }
290  if (entry.child != NULL) {
291  entry.child->parent = entry.parent;
292  } else {
293  mYoungest = entry.parent;
294  }
295 
296  entry.parent = NULL;
297  entry.child = NULL;
298 }
299 
300 } // namespace android
301 #endif // ANDROID_UTILS_LRU_CACHE_H
virtual ~OnEntryRemoved()
Definition: LruCache.h:33
const TValue & get(const TKey &key)
Definition: LruCache.h:193
virtual ~LruCache()
Definition: LruCache.h:177
const TValue & peekOldestValue()
Definition: LruCache.h:250
virtual void operator()(EntryKey &key, EntryValue &value)=0
LruCache(uint32_t maxCapacity)
Definition: LruCache.h:166
const TKey & key() const
Definition: LruCache.h:155
size_t size() const
Definition: LruCache.h:188
constexpr std::size_t size(T(&array)[N])
Definition: size.h:13
bool removeOldest()
Definition: LruCache.h:241
Iterator(const LruCache< TKey, TValue > &cache)
Definition: LruCache.h:129
const TValue & value() const
Definition: LruCache.h:149
uint8_t value
bool remove(const TKey &key)
Definition: LruCache.h:223
Definition: LruCache.h:31
hash_t hash_type(const TKey &key)
void setOnEntryRemovedListener(OnEntryRemoved< TKey, TValue > *listener)
Definition: LruCache.h:183
bool put(const TKey &key, const TValue &value)
Definition: LruCache.h:207