• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 <utils/BasicHashtable.h>
21 #include <utils/UniquePtr.h>
22 
23 namespace android {
24 
25 /**
26  * GenerationCache callback used when an item is removed
27  */
28 template<typename EntryKey, typename EntryValue>
29 class OnEntryRemoved {
30 public:
~OnEntryRemoved()31     virtual ~OnEntryRemoved() { };
32     virtual void operator()(EntryKey& key, EntryValue& value) = 0;
33 }; // class OnEntryRemoved
34 
35 template <typename TKey, typename TValue>
36 class LruCache {
37 public:
38     explicit LruCache(uint32_t maxCapacity);
39 
40     enum Capacity {
41         kUnlimitedCapacity,
42     };
43 
44     void setOnEntryRemovedListener(OnEntryRemoved<TKey, TValue>* listener);
45     size_t size() const;
46     const TValue& get(const TKey& key);
47     bool put(const TKey& key, const TValue& value);
48     bool remove(const TKey& key);
49     bool removeOldest();
50     void clear();
51 
52     class Iterator {
53     public:
Iterator(const LruCache<TKey,TValue> & cache)54         Iterator(const LruCache<TKey, TValue>& cache): mCache(cache), mIndex(-1) {
55         }
56 
next()57         bool next() {
58             mIndex = mCache.mTable->next(mIndex);
59             return mIndex != -1;
60         }
61 
index()62         size_t index() const {
63             return mIndex;
64         }
65 
value()66         const TValue& value() const {
67             return mCache.mTable->entryAt(mIndex).value;
68         }
69 
key()70         const TKey& key() const {
71             return mCache.mTable->entryAt(mIndex).key;
72         }
73     private:
74         const LruCache<TKey, TValue>& mCache;
75         size_t mIndex;
76     };
77 
78 private:
79     LruCache(const LruCache& that);  // disallow copy constructor
80 
81     struct Entry {
82         TKey key;
83         TValue value;
84         Entry* parent;
85         Entry* child;
86 
EntryEntry87         Entry(TKey key_, TValue value_) : key(key_), value(value_), parent(NULL), child(NULL) {
88         }
getKeyEntry89         const TKey& getKey() const { return key; }
90     };
91 
92     void attachToCache(Entry& entry);
93     void detachFromCache(Entry& entry);
94     void rehash(size_t newCapacity);
95 
96     UniquePtr<BasicHashtable<TKey, Entry> > mTable;
97     OnEntryRemoved<TKey, TValue>* mListener;
98     Entry* mOldest;
99     Entry* mYoungest;
100     uint32_t mMaxCapacity;
101     TValue mNullValue;
102 };
103 
104 // Implementation is here, because it's fully templated
105 template <typename TKey, typename TValue>
LruCache(uint32_t maxCapacity)106 LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity): mMaxCapacity(maxCapacity),
107     mNullValue(NULL), mTable(new BasicHashtable<TKey, Entry>), mYoungest(NULL), mOldest(NULL),
108     mListener(NULL) {
109 };
110 
111 template<typename K, typename V>
setOnEntryRemovedListener(OnEntryRemoved<K,V> * listener)112 void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
113     mListener = listener;
114 }
115 
116 template <typename TKey, typename TValue>
size()117 size_t LruCache<TKey, TValue>::size() const {
118     return mTable->size();
119 }
120 
121 template <typename TKey, typename TValue>
get(const TKey & key)122 const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
123     hash_t hash = hash_type(key);
124     ssize_t index = mTable->find(-1, hash, key);
125     if (index == -1) {
126         return mNullValue;
127     }
128     Entry& entry = mTable->editEntryAt(index);
129     detachFromCache(entry);
130     attachToCache(entry);
131     return entry.value;
132 }
133 
134 template <typename TKey, typename TValue>
put(const TKey & key,const TValue & value)135 bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
136     if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
137         removeOldest();
138     }
139 
140     hash_t hash = hash_type(key);
141     ssize_t index = mTable->find(-1, hash, key);
142     if (index >= 0) {
143         return false;
144     }
145     if (!mTable->hasMoreRoom()) {
146         rehash(mTable->capacity() * 2);
147     }
148 
149     // Would it be better to initialize a blank entry and assign key, value?
150     Entry initEntry(key, value);
151     index = mTable->add(hash, initEntry);
152     Entry& entry = mTable->editEntryAt(index);
153     attachToCache(entry);
154     return true;
155 }
156 
157 template <typename TKey, typename TValue>
remove(const TKey & key)158 bool LruCache<TKey, TValue>::remove(const TKey& key) {
159     hash_t hash = hash_type(key);
160     ssize_t index = mTable->find(-1, hash, key);
161     if (index < 0) {
162         return false;
163     }
164     Entry& entry = mTable->editEntryAt(index);
165     if (mListener) {
166         (*mListener)(entry.key, entry.value);
167     }
168     detachFromCache(entry);
169     mTable->removeAt(index);
170     return true;
171 }
172 
173 template <typename TKey, typename TValue>
removeOldest()174 bool LruCache<TKey, TValue>::removeOldest() {
175     if (mOldest != NULL) {
176         return remove(mOldest->key);
177         // TODO: should probably abort if false
178     }
179     return false;
180 }
181 
182 template <typename TKey, typename TValue>
clear()183 void LruCache<TKey, TValue>::clear() {
184     if (mListener) {
185         for (Entry* p = mOldest; p != NULL; p = p->child) {
186             (*mListener)(p->key, p->value);
187         }
188     }
189     mYoungest = NULL;
190     mOldest = NULL;
191     mTable->clear();
192 }
193 
194 template <typename TKey, typename TValue>
attachToCache(Entry & entry)195 void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
196     if (mYoungest == NULL) {
197         mYoungest = mOldest = &entry;
198     } else {
199         entry.parent = mYoungest;
200         mYoungest->child = &entry;
201         mYoungest = &entry;
202     }
203 }
204 
205 template <typename TKey, typename TValue>
detachFromCache(Entry & entry)206 void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
207     if (entry.parent != NULL) {
208         entry.parent->child = entry.child;
209     } else {
210         mOldest = entry.child;
211     }
212     if (entry.child != NULL) {
213         entry.child->parent = entry.parent;
214     } else {
215         mYoungest = entry.parent;
216     }
217 
218     entry.parent = NULL;
219     entry.child = NULL;
220 }
221 
222 template <typename TKey, typename TValue>
rehash(size_t newCapacity)223 void LruCache<TKey, TValue>::rehash(size_t newCapacity) {
224     UniquePtr<BasicHashtable<TKey, Entry> > oldTable(mTable.release());
225     Entry* oldest = mOldest;
226 
227     mOldest = NULL;
228     mYoungest = NULL;
229     mTable.reset(new BasicHashtable<TKey, Entry>(newCapacity));
230     for (Entry* p = oldest; p != NULL; p = p->child) {
231         put(p->key, p->value);
232     }
233 }
234 
235 }
236 
237 #endif // ANDROID_UTILS_LRU_CACHE_H
238