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 void 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 }
87 }
88
entryCount()89 size_t entryCount() const { return mStore.size(); }
90
size()91 size_t size() const { return mCurrentSize; }
92
93 // Also discards the cache contents.
resize(size_t maximumTotalSize)94 void resize(size_t maximumTotalSize)
95 {
96 clear();
97 mMaximumTotalSize = maximumTotalSize;
98 }
99
100 // Reduce current memory usage.
shrinkToSize(size_t limit)101 size_t shrinkToSize(size_t limit)
102 {
103 size_t initialSize = mCurrentSize;
104
105 while (mCurrentSize > limit)
106 {
107 ASSERT(!mStore.empty());
108 auto iter = mStore.rbegin();
109 mCurrentSize -= iter->second.size;
110 mStore.Erase(iter);
111 }
112
113 return (initialSize - mCurrentSize);
114 }
115
maxSize()116 size_t maxSize() const { return mMaximumTotalSize; }
117
118 private:
119 struct ValueAndSize
120 {
ValueAndSizeValueAndSize121 ValueAndSize() : value(), size(0) {}
ValueAndSizeValueAndSize122 ValueAndSize(Value &&value, size_t size) : value(std::move(value)), size(size) {}
ValueAndSizeValueAndSize123 ValueAndSize(ValueAndSize &&other) : ValueAndSize() { *this = std::move(other); }
124 ValueAndSize &operator=(ValueAndSize &&other)
125 {
126 std::swap(value, other.value);
127 std::swap(size, other.size);
128 return *this;
129 }
130
131 Value value;
132 size_t size;
133 };
134
135 using SizedMRUCacheStore = base::HashingMRUCache<Key, ValueAndSize>;
136
137 size_t mMaximumTotalSize;
138 size_t mCurrentSize;
139 SizedMRUCacheStore mStore;
140 };
141
142 // Helper function used in a few places.
143 template <typename T>
TrimCache(size_t maxStates,size_t gcLimit,const char * name,T * cache)144 void TrimCache(size_t maxStates, size_t gcLimit, const char *name, T *cache)
145 {
146 const size_t kGarbageCollectionLimit = maxStates / 2 + gcLimit;
147
148 if (cache->size() >= kGarbageCollectionLimit)
149 {
150 WARN() << "Overflowed the " << name << " cache limit of " << (maxStates / 2)
151 << " elements, removing the least recently used to make room.";
152 cache->ShrinkToSize(maxStates / 2);
153 }
154 }
155 } // namespace angle
156 #endif // LIBANGLE_SIZED_MRU_CACHE_H_
157