1 //
2 // Copyright 2017 The ANGLE Project Authors. All rights reserved.
3 // Use of this source code is governed by a BSD-style license that can be
4 // found in the LICENSE file.
5 //
6 // SizedMRUCache.h: A hashing map that stores blobs of sized, untyped data.
7
8 #ifndef LIBANGLE_SIZED_MRU_CACHE_H_
9 #define LIBANGLE_SIZED_MRU_CACHE_H_
10
11 #include <anglebase/containers/mru_cache.h>
12
13 namespace angle
14 {
15
16 template <typename Key, typename Value>
17 class SizedMRUCache final : angle::NonCopyable
18 {
19 public:
SizedMRUCache(size_t maximumTotalSize)20 SizedMRUCache(size_t maximumTotalSize)
21 : mMaximumTotalSize(maximumTotalSize),
22 mCurrentSize(0),
23 mStore(SizedMRUCacheStore::NO_AUTO_EVICT)
24 {}
25
26 // Returns nullptr on failure.
put(const Key & key,Value && value,size_t size)27 const Value *put(const Key &key, Value &&value, size_t size)
28 {
29 if (size > mMaximumTotalSize)
30 {
31 return nullptr;
32 }
33
34 // Check for existing key.
35 eraseByKey(key);
36
37 auto retVal = mStore.Put(key, ValueAndSize(std::move(value), size));
38 mCurrentSize += size;
39
40 shrinkToSize(mMaximumTotalSize);
41
42 return &retVal->second.value;
43 }
44
get(const Key & key,const Value ** valueOut)45 bool get(const Key &key, const Value **valueOut)
46 {
47 const auto &iter = mStore.Get(key);
48 if (iter == mStore.end())
49 {
50 return false;
51 }
52 *valueOut = &iter->second.value;
53 return true;
54 }
55
getAt(size_t index,const Key ** keyOut,const Value ** valueOut)56 bool getAt(size_t index, const Key **keyOut, const Value **valueOut)
57 {
58 if (index < mStore.size())
59 {
60 auto it = mStore.begin();
61 std::advance(it, index);
62 *keyOut = &it->first;
63 *valueOut = &it->second.value;
64 return true;
65 }
66 *valueOut = nullptr;
67 return false;
68 }
69
empty()70 bool empty() const { return mStore.empty(); }
71
clear()72 void clear()
73 {
74 mStore.Clear();
75 mCurrentSize = 0;
76 }
77
eraseByKey(const Key & key)78 bool eraseByKey(const Key &key)
79 {
80 // Check for existing key.
81 auto existing = mStore.Peek(key);
82 if (existing != mStore.end())
83 {
84 mCurrentSize -= existing->second.size;
85 mStore.Erase(existing);
86 return true;
87 }
88
89 return false;
90 }
91
entryCount()92 size_t entryCount() const { return mStore.size(); }
93
size()94 size_t size() const { return mCurrentSize; }
95
96 // Also discards the cache contents.
resize(size_t maximumTotalSize)97 void resize(size_t maximumTotalSize)
98 {
99 clear();
100 mMaximumTotalSize = maximumTotalSize;
101 }
102
103 // Reduce current memory usage.
shrinkToSize(size_t limit)104 size_t shrinkToSize(size_t limit)
105 {
106 size_t initialSize = mCurrentSize;
107
108 while (mCurrentSize > limit)
109 {
110 ASSERT(!mStore.empty());
111 auto iter = mStore.rbegin();
112 mCurrentSize -= iter->second.size;
113 mStore.Erase(iter);
114 }
115
116 return (initialSize - mCurrentSize);
117 }
118
maxSize()119 size_t maxSize() const { return mMaximumTotalSize; }
120
121 private:
122 struct ValueAndSize
123 {
ValueAndSizeValueAndSize124 ValueAndSize() : value(), size(0) {}
ValueAndSizeValueAndSize125 ValueAndSize(Value &&value, size_t size) : value(std::move(value)), size(size) {}
ValueAndSizeValueAndSize126 ValueAndSize(ValueAndSize &&other) : ValueAndSize() { *this = std::move(other); }
127 ValueAndSize &operator=(ValueAndSize &&other)
128 {
129 std::swap(value, other.value);
130 std::swap(size, other.size);
131 return *this;
132 }
133
134 Value value;
135 size_t size;
136 };
137
138 using SizedMRUCacheStore = base::HashingMRUCache<Key, ValueAndSize>;
139
140 size_t mMaximumTotalSize;
141 size_t mCurrentSize;
142 SizedMRUCacheStore mStore;
143 };
144
145 // Helper function used in a few places.
146 template <typename T>
TrimCache(size_t maxStates,size_t gcLimit,const char * name,T * cache)147 void TrimCache(size_t maxStates, size_t gcLimit, const char *name, T *cache)
148 {
149 const size_t kGarbageCollectionLimit = maxStates / 2 + gcLimit;
150
151 if (cache->size() >= kGarbageCollectionLimit)
152 {
153 WARN() << "Overflowed the " << name << " cache limit of " << (maxStates / 2)
154 << " elements, removing the least recently used to make room.";
155 cache->ShrinkToSize(maxStates / 2);
156 }
157 }
158 } // namespace angle
159 #endif // LIBANGLE_SIZED_MRU_CACHE_H_
160