• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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