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
23namespace android {
24
25/**
26 * GenerationCache callback used when an item is removed
27 */
28template<typename EntryKey, typename EntryValue>
29class OnEntryRemoved {
30public:
31    virtual ~OnEntryRemoved() { };
32    virtual void operator()(EntryKey& key, EntryValue& value) = 0;
33}; // class OnEntryRemoved
34
35template <typename TKey, typename TValue>
36class LruCache {
37public:
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:
54        Iterator(const LruCache<TKey, TValue>& cache): mCache(cache), mIndex(-1) {
55        }
56
57        bool next() {
58            mIndex = mCache.mTable->next(mIndex);
59            return mIndex != -1;
60        }
61
62        size_t index() const {
63            return mIndex;
64        }
65
66        const TValue& value() const {
67            return mCache.mTable->entryAt(mIndex).value;
68        }
69
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
78private:
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
87        Entry(TKey key_, TValue value_) : key(key_), value(value_), parent(NULL), child(NULL) {
88        }
89        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
105template <typename TKey, typename TValue>
106LruCache<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
111template<typename K, typename V>
112void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
113    mListener = listener;
114}
115
116template <typename TKey, typename TValue>
117size_t LruCache<TKey, TValue>::size() const {
118    return mTable->size();
119}
120
121template <typename TKey, typename TValue>
122const 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
134template <typename TKey, typename TValue>
135bool 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
157template <typename TKey, typename TValue>
158bool 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
173template <typename TKey, typename TValue>
174bool 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
182template <typename TKey, typename TValue>
183void 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
194template <typename TKey, typename TValue>
195void 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
205template <typename TKey, typename TValue>
206void 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
222template <typename TKey, typename TValue>
223void 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