summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--include/utils/LruCache.h153
-rw-r--r--libutils/tests/LruCache_test.cpp2
2 files changed, 83 insertions, 72 deletions
diff --git a/include/utils/LruCache.h b/include/utils/LruCache.h
index cd9d7f94a..7818b4e2e 100644
--- a/include/utils/LruCache.h
+++ b/include/utils/LruCache.h
@@ -17,8 +17,11 @@
#ifndef ANDROID_UTILS_LRU_CACHE_H
#define ANDROID_UTILS_LRU_CACHE_H
+#include <unordered_set>
+
#include <UniquePtr.h>
-#include <utils/BasicHashtable.h>
+
+#include "utils/TypeHelpers.h" // hash_t
namespace android {
@@ -36,6 +39,7 @@ template <typename TKey, typename TValue>
class LruCache {
public:
explicit LruCache(uint32_t maxCapacity);
+ virtual ~LruCache();
enum Capacity {
kUnlimitedCapacity,
@@ -50,32 +54,6 @@ public:
void clear();
const TValue& peekOldestValue();
- class Iterator {
- public:
- Iterator(const LruCache<TKey, TValue>& cache): mCache(cache), mIndex(-1) {
- }
-
- bool next() {
- mIndex = mCache.mTable->next(mIndex);
- return (ssize_t)mIndex != -1;
- }
-
- size_t index() const {
- return mIndex;
- }
-
- const TValue& value() const {
- return mCache.mTable->entryAt(mIndex).value;
- }
-
- const TKey& key() const {
- return mCache.mTable->entryAt(mIndex).key;
- }
- private:
- const LruCache<TKey, TValue>& mCache;
- size_t mIndex;
- };
-
private:
LruCache(const LruCache& that); // disallow copy constructor
@@ -90,27 +68,79 @@ private:
const TKey& getKey() const { return key; }
};
+ struct HashForEntry : public std::unary_function<Entry*, hash_t> {
+ size_t operator() (const Entry* entry) const {
+ return hash_type(entry->key);
+ };
+ };
+
+ struct EqualityForHashedEntries : public std::unary_function<Entry*, hash_t> {
+ bool operator() (const Entry* lhs, const Entry* rhs) const {
+ return lhs->key == rhs->key;
+ };
+ };
+
+ typedef std::unordered_set<Entry*, HashForEntry, EqualityForHashedEntries> LruCacheSet;
+
void attachToCache(Entry& entry);
void detachFromCache(Entry& entry);
- void rehash(size_t newCapacity);
- UniquePtr<BasicHashtable<TKey, Entry> > mTable;
+ typename LruCacheSet::iterator findByKey(const TKey& key) {
+ Entry entryForSearch(key, mNullValue);
+ typename LruCacheSet::iterator result = mSet->find(&entryForSearch);
+ return result;
+ }
+
+ UniquePtr<LruCacheSet> mSet;
OnEntryRemoved<TKey, TValue>* mListener;
Entry* mOldest;
Entry* mYoungest;
uint32_t mMaxCapacity;
TValue mNullValue;
+
+public:
+ class Iterator {
+ public:
+ Iterator(const LruCache<TKey, TValue>& cache): mCache(cache), mIterator(mCache.mSet->begin()) {
+ }
+
+ bool next() {
+ if (mIterator == mCache.mSet->end()) {
+ return false;
+ }
+ std::advance(mIterator, 1);
+ return mIterator != mCache.mSet->end();
+ }
+
+ const TValue& value() const {
+ return (*mIterator)->value;
+ }
+
+ const TKey& key() const {
+ return (*mIterator)->key;
+ }
+ private:
+ const LruCache<TKey, TValue>& mCache;
+ typename LruCacheSet::iterator mIterator;
+ };
};
// Implementation is here, because it's fully templated
template <typename TKey, typename TValue>
LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity)
- : mTable(new BasicHashtable<TKey, Entry>)
+ : mSet(new LruCacheSet())
, mListener(NULL)
, mOldest(NULL)
, mYoungest(NULL)
, mMaxCapacity(maxCapacity)
, mNullValue(NULL) {
+ mSet->max_load_factor(1.0);
+};
+
+template <typename TKey, typename TValue>
+LruCache<TKey, TValue>::~LruCache() {
+ // Need to delete created entries.
+ clear();
};
template<typename K, typename V>
@@ -120,20 +150,19 @@ void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
template <typename TKey, typename TValue>
size_t LruCache<TKey, TValue>::size() const {
- return mTable->size();
+ return mSet->size();
}
template <typename TKey, typename TValue>
const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
- hash_t hash = hash_type(key);
- ssize_t index = mTable->find(-1, hash, key);
- if (index == -1) {
+ typename LruCacheSet::const_iterator find_result = findByKey(key);
+ if (find_result == mSet->end()) {
return mNullValue;
}
- Entry& entry = mTable->editEntryAt(index);
- detachFromCache(entry);
- attachToCache(entry);
- return entry.value;
+ Entry *entry = *find_result;
+ detachFromCache(*entry);
+ attachToCache(*entry);
+ return entry->value;
}
template <typename TKey, typename TValue>
@@ -142,36 +171,29 @@ bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
removeOldest();
}
- hash_t hash = hash_type(key);
- ssize_t index = mTable->find(-1, hash, key);
- if (index >= 0) {
+ if (findByKey(key) != mSet->end()) {
return false;
}
- if (!mTable->hasMoreRoom()) {
- rehash(mTable->capacity() * 2);
- }
- // Would it be better to initialize a blank entry and assign key, value?
- Entry initEntry(key, value);
- index = mTable->add(hash, initEntry);
- Entry& entry = mTable->editEntryAt(index);
- attachToCache(entry);
+ Entry* newEntry = new Entry(key, value);
+ mSet->insert(newEntry);
+ attachToCache(*newEntry);
return true;
}
template <typename TKey, typename TValue>
bool LruCache<TKey, TValue>::remove(const TKey& key) {
- hash_t hash = hash_type(key);
- ssize_t index = mTable->find(-1, hash, key);
- if (index < 0) {
+ typename LruCacheSet::const_iterator find_result = findByKey(key);
+ if (find_result == mSet->end()) {
return false;
}
- Entry& entry = mTable->editEntryAt(index);
+ Entry* entry = *find_result;
if (mListener) {
- (*mListener)(entry.key, entry.value);
+ (*mListener)(entry->key, entry->value);
}
- detachFromCache(entry);
- mTable->removeAt(index);
+ detachFromCache(*entry);
+ mSet->erase(entry);
+ delete entry;
return true;
}
@@ -201,7 +223,10 @@ void LruCache<TKey, TValue>::clear() {
}
mYoungest = NULL;
mOldest = NULL;
- mTable->clear();
+ for (auto entry : *mSet.get()) {
+ delete entry;
+ }
+ mSet->clear();
}
template <typename TKey, typename TValue>
@@ -232,19 +257,5 @@ void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
entry.child = NULL;
}
-template <typename TKey, typename TValue>
-void LruCache<TKey, TValue>::rehash(size_t newCapacity) {
- UniquePtr<BasicHashtable<TKey, Entry> > oldTable(mTable.release());
- Entry* oldest = mOldest;
-
- mOldest = NULL;
- mYoungest = NULL;
- mTable.reset(new BasicHashtable<TKey, Entry>(newCapacity));
- for (Entry* p = oldest; p != NULL; p = p->child) {
- put(p->key, p->value);
- }
-}
-
}
-
#endif // ANDROID_UTILS_LRU_CACHE_H
diff --git a/libutils/tests/LruCache_test.cpp b/libutils/tests/LruCache_test.cpp
index 6155defd4..2ed84d700 100644
--- a/libutils/tests/LruCache_test.cpp
+++ b/libutils/tests/LruCache_test.cpp
@@ -221,7 +221,7 @@ TEST_F(LruCacheTest, NoLeak) {
cache.put(ComplexKey(0), ComplexValue(0));
cache.put(ComplexKey(1), ComplexValue(1));
EXPECT_EQ(2U, cache.size());
- assertInstanceCount(2, 3); // the null value counts as an instance
+ assertInstanceCount(2, 3); // the member mNullValue counts as an instance
}
TEST_F(LruCacheTest, Clear) {