1 /*
2  * Copyright (C) 2021 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_BASE_MRUCACHE_
18 #define ANDROID_BASE_MRUCACHE_
19 
20 #include <algorithm>
21 #include <list>
22 #include <map>
23 
24 namespace android {
25 namespace base {
26 
27 // A trivial MRU cache. Not thread-safe.
28 template <class K, class V>
29 class MruCache {
30    public:
31     template <class S>
32     struct EntryWithSize {
EntryWithSizeEntryWithSize33         EntryWithSize(const S&& d) : EntryWithSize(std::move(d), 0) {}
34 
EntryWithSizeEntryWithSize35         EntryWithSize(const S&& d, const size_t ds) : data(std::move(d)), dataSize(ds) {
36             static_assert(std::is_same<S, K>::value || std::is_same<S, V>::value,
37                           "Cache entry instantiated with invalid types");
38         }
39 
40         const S data;
41         size_t dataSize;
42 
43         bool operator==(const EntryWithSize& rhs) const { return data == rhs.data; }
44         bool operator<(const EntryWithSize& rhs) const { return data < rhs.data; }
45     };
46 
47     class MruCacheObserver {
48        public:
49         virtual void cacheChanged() = 0;
~MruCacheObserver()50         virtual ~MruCacheObserver() {}
51     };
52 
53     class CacheFlattener {
54        public:
55         virtual void handleFlatten(std::map<EntryWithSize<K>, EntryWithSize<V>>& mCache, void* buf,
56                                    size_t bufSize) = 0;
~CacheFlattener()57         virtual ~CacheFlattener() {}
58     };
59 
MruCache(size_t maxEntries,CacheFlattener * cacheFlattener)60     MruCache(size_t maxEntries, CacheFlattener* cacheFlattener)
61         : mMaxEntries(maxEntries), mCacheFlattener(cacheFlattener) {}
62 
put(const K & key,size_t keySize,V && value,size_t valueSize)63     bool put(const K& key, size_t keySize, V&& value, size_t valueSize) {
64         evictIfNecessary();
65 
66         EntryWithSize<K> cacheKey(std::move(key), keySize);
67         EntryWithSize<V> cacheValue(std::move(value), valueSize);
68 
69         auto exists = mCache.find(cacheKey);
70         if (exists != mCache.end()) {
71             auto iter = std::find(mMostRecents.begin(), mMostRecents.end(), cacheKey);
72             mMostRecents.splice(mMostRecents.begin(), mMostRecents, iter);
73             mCache.erase(exists);
74         } else {
75             mMostRecents.push_front(cacheKey);
76         }
77 
78         const auto [_, res] = mCache.insert({cacheKey, std::move(cacheValue)});
79 
80         if (mCacheObserver != nullptr && res) {
81             mCacheObserver->cacheChanged();
82         }
83 
84         return res;
85     }
86 
flatten(void * buf,size_t bufSize)87     void flatten(void* buf, size_t bufSize) {
88         if (mCacheFlattener) {
89             mCacheFlattener->handleFlatten(mCache, buf, bufSize);
90         }
91     }
92 
get(const K & key,const V ** value)93     bool get(const K& key, const V** value) {
94         EntryWithSize<K> cacheKey(std::move(key));
95         auto res = mCache.find(cacheKey);
96 
97         if (res == mCache.end()) {
98             return false;
99         }
100 
101         *value = &(res->second.data);
102         auto iter = std::find(mMostRecents.begin(), mMostRecents.end(), cacheKey);
103         mMostRecents.splice(mMostRecents.begin(), mMostRecents, iter);
104 
105         return true;
106     }
107 
setObserver(MruCacheObserver * observer)108     void setObserver(MruCacheObserver* observer) { mCacheObserver = observer; }
109 
110    private:
111     using MruCacheMap = std::map<EntryWithSize<K>, EntryWithSize<V>>;
112     using MostRecentList = std::list<EntryWithSize<K>>;
113 
evictIfNecessary()114     void evictIfNecessary() {
115         auto entryCount = mMostRecents.size();
116         if (entryCount >= mMaxEntries) {
117             auto threshold = entryCount * 0.9;
118 
119             for (int i = mMostRecents.size(); i > threshold; i--) {
120                 EntryWithSize<K> key = mMostRecents.front();
121                 mMostRecents.pop_front();
122                 mCache.erase(key);
123             }
124         }
125     }
126 
127     MruCacheMap mCache;
128     MostRecentList mMostRecents;
129     MruCacheObserver* mCacheObserver;
130     CacheFlattener* mCacheFlattener;
131     const size_t mMaxEntries;
132 };
133 
134 }  // namespace base
135 }  // namespace android
136 
137 #endif
138