LruCache: avoid copying keys in lookup
Create objects of type KeyedEntry for lookups that only have
a key reference
Bug: 27567036
Change-Id: I5e609a3db63d3b9277ff1547a3cca37dce70251c
diff --git a/include/utils/LruCache.h b/include/utils/LruCache.h
index ed96fe4..f4e225a 100644
--- a/include/utils/LruCache.h
+++ b/include/utils/LruCache.h
@@ -56,36 +56,55 @@
private:
LruCache(const LruCache& that); // disallow copy constructor
- struct Entry {
+ // Super class so that we can have entries having only a key reference, for searches.
+ class KeyedEntry {
+ public:
+ virtual const TKey& getKey() const = 0;
+ // Make sure the right destructor is executed so that keys and values are deleted.
+ virtual ~KeyedEntry() {}
+ };
+
+ class Entry final : public KeyedEntry {
+ public:
TKey key;
TValue value;
Entry* parent;
Entry* child;
- Entry(TKey key_, TValue value_) : key(key_), value(value_), parent(NULL), child(NULL) {
+ Entry(TKey _key, TValue _value) : key(_key), value(_value), parent(NULL), child(NULL) {
}
- const TKey& getKey() const { return key; }
+ const TKey& getKey() const final { return key; }
};
- struct HashForEntry : public std::unary_function<Entry*, hash_t> {
- size_t operator() (const Entry* entry) const {
- return hash_type(entry->key);
+ class EntryForSearch : public KeyedEntry {
+ public:
+ const TKey& key;
+ EntryForSearch(const TKey& key_) : key(key_) {
+ }
+ const TKey& getKey() const final { return key; }
+ };
+
+ struct HashForEntry : public std::unary_function<KeyedEntry*, hash_t> {
+ size_t operator() (const KeyedEntry* entry) const {
+ return hash_type(entry->getKey());
};
};
- struct EqualityForHashedEntries : public std::unary_function<Entry*, hash_t> {
- bool operator() (const Entry* lhs, const Entry* rhs) const {
- return lhs->key == rhs->key;
+ struct EqualityForHashedEntries : public std::unary_function<KeyedEntry*, hash_t> {
+ bool operator() (const KeyedEntry* lhs, const KeyedEntry* rhs) const {
+ return lhs->getKey() == rhs->getKey();
};
};
- typedef std::unordered_set<Entry*, HashForEntry, EqualityForHashedEntries> LruCacheSet;
+ // All entries in the set will be Entry*. Using the weaker KeyedEntry as to allow entries
+ // that have only a key reference, for searching.
+ typedef std::unordered_set<KeyedEntry*, HashForEntry, EqualityForHashedEntries> LruCacheSet;
void attachToCache(Entry& entry);
void detachFromCache(Entry& entry);
typename LruCacheSet::iterator findByKey(const TKey& key) {
- Entry entryForSearch(key, mNullValue);
+ EntryForSearch entryForSearch(key);
typename LruCacheSet::iterator result = mSet->find(&entryForSearch);
return result;
}
@@ -124,11 +143,13 @@
}
const TValue& value() const {
- return (*mIterator)->value;
+ // All the elements in the set are of type Entry. See comment in the definition
+ // of LruCacheSet above.
+ return reinterpret_cast<Entry *>(*mIterator)->value;
}
const TKey& key() const {
- return (*mIterator)->key;
+ return (*mIterator)->getKey();
}
private:
const LruCache<TKey, TValue>& mCache;
@@ -171,7 +192,9 @@
if (find_result == mSet->end()) {
return mNullValue;
}
- Entry *entry = *find_result;
+ // All the elements in the set are of type Entry. See comment in the definition
+ // of LruCacheSet above.
+ Entry *entry = reinterpret_cast<Entry*>(*find_result);
detachFromCache(*entry);
attachToCache(*entry);
return entry->value;
@@ -199,7 +222,9 @@
if (find_result == mSet->end()) {
return false;
}
- Entry* entry = *find_result;
+ // All the elements in the set are of type Entry. See comment in the definition
+ // of LruCacheSet above.
+ Entry* entry = reinterpret_cast<Entry*>(*find_result);
mSet->erase(entry);
if (mListener) {
(*mListener)(entry->key, entry->value);
diff --git a/libutils/tests/LruCache_test.cpp b/libutils/tests/LruCache_test.cpp
index dd95c57..de440fd 100644
--- a/libutils/tests/LruCache_test.cpp
+++ b/libutils/tests/LruCache_test.cpp
@@ -80,6 +80,14 @@
}
};
+struct KeyFailsOnCopy : public ComplexKey {
+ public:
+ KeyFailsOnCopy(const KeyFailsOnCopy& key) : ComplexKey(key) {
+ ADD_FAILURE();
+ }
+ KeyFailsOnCopy(int key) : ComplexKey(key) { }
+};
+
} // namespace
@@ -95,6 +103,10 @@
return hash_type(*value.ptr);
}
+template<> inline android::hash_t hash_type(const KeyFailsOnCopy& value) {
+ return hash_type<ComplexKey>(value);
+}
+
class EntryRemovedCallback : public OnEntryRemoved<SimpleKey, StringValue> {
public:
EntryRemovedCallback() : callbackCount(0), lastKey(-1), lastValue(NULL) { }
@@ -437,4 +449,10 @@
EXPECT_EQ(std::unordered_set<int>({ 4, 5, 6 }), returnedValues);
}
+TEST_F(LruCacheTest, DontCopyKeyInGet) {
+ LruCache<KeyFailsOnCopy, KeyFailsOnCopy> cache(1);
+ // Check that get doesn't copy the key
+ cache.get(KeyFailsOnCopy(0));
+}
+
}