am 730fdbb1: Merge "system/core: change LruCache to use unordered_set instead of BasicHashTable"
* commit '730fdbb1ca4c39a4d69868f7a261b023f2bea296':
system/core: change LruCache to use unordered_set instead of BasicHashTable
diff --git a/include/utils/LruCache.h b/include/utils/LruCache.h
index cd9d7f9..7818b4e 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 @@
class LruCache {
public:
explicit LruCache(uint32_t maxCapacity);
+ virtual ~LruCache();
enum Capacity {
kUnlimitedCapacity,
@@ -50,32 +54,6 @@
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 @@
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 @@
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 @@
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 @@
}
mYoungest = NULL;
mOldest = NULL;
- mTable->clear();
+ for (auto entry : *mSet.get()) {
+ delete entry;
+ }
+ mSet->clear();
}
template <typename TKey, typename TValue>
@@ -232,19 +257,5 @@
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 6155def..2ed84d7 100644
--- a/libutils/tests/LruCache_test.cpp
+++ b/libutils/tests/LruCache_test.cpp
@@ -221,7 +221,7 @@
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) {