Add an LRU cache plus hashing primitives

This patch adds a hashtable-based LRU cache. This should be
significantly higher performance than the GenerationCache it is intended
to replace. It is a large part of the fix for bug 7271109
TextLayoutCache low-level performance issues.

We added a new method to BasicHashtable to detect when rehashing is
needed, because the internal linked list pointers would get invalidated
by that rehashing.

Also, the hash_type specialized to pointers had a small flaw.

Change-Id: I950c2083f96519777b851dbe157100e0a334caec

1 files changed, 199 insertions, 0 deletions

diff --git a/include/utils/LruCache.h b/include/utils/LruCache.h
new file mode 100644
index 0000000000..af39315962
--- /dev/null
+++ b/include/utils/LruCache.h
@@ -0,0 +1,199 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <utils/BasicHashtable.h>
+#include <utils/GenerationCache.h>
+#include <utils/UniquePtr.h>
+
+namespace android {
+
+// OnEntryRemoved is defined in GenerationCache.h, but maybe should move here.
+
+template <typename TKey, typename TValue>
+class LruCache {
+public:
+    explicit LruCache(uint32_t maxCapacity);
+
+    enum Capacity {
+        kUnlimitedCapacity,
+    };
+
+    void setOnEntryRemovedListener(OnEntryRemoved<TKey, TValue>* listener);
+    size_t size() const;
+    const TValue& get(const TKey& key);
+    bool put(const TKey& key, const TValue& value);
+    bool remove(const TKey& key);
+    bool removeOldest();
+    void clear();
+
+private:
+    LruCache(const LruCache& that);  // disallow copy constructor
+
+    struct Entry {
+        TKey key;
+        TValue value;
+        Entry* parent;
+        Entry* child;
+
+        Entry(TKey key_, TValue value_) : key(key_), value(value_), parent(NULL), child(NULL) {
+        }
+        const TKey& getKey() const { return key; }
+    };
+
+    void attachToCache(Entry& entry);
+    void detachFromCache(Entry& entry);
+    void rehash(size_t newCapacity);
+
+    UniquePtr<BasicHashtable<TKey, Entry> > mTable;
+    OnEntryRemoved<TKey, TValue>* mListener;
+    Entry* mOldest;
+    Entry* mYoungest;
+    uint32_t mMaxCapacity;
+    TValue mNullValue;
+};
+
+// Implementation is here, because it's fully templated
+template <typename TKey, typename TValue>
+LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity): mMaxCapacity(maxCapacity),
+    mNullValue(NULL), mTable(new BasicHashtable<TKey, Entry>), mYoungest(NULL), mOldest(NULL),
+    mListener(NULL) {
+};
+
+template<typename K, typename V>
+void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
+    mListener = listener;
+}
+
+template <typename TKey, typename TValue>
+size_t LruCache<TKey, TValue>::size() const {
+    return mTable->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) {
+        return mNullValue;
+    }
+    Entry& entry = mTable->editEntryAt(index);
+    detachFromCache(entry);
+    attachToCache(entry);
+    return entry.value;
+}
+
+template <typename TKey, typename TValue>
+bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
+    if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
+        removeOldest();
+    }
+
+    hash_t hash = hash_type(key);
+    ssize_t index = mTable->find(-1, hash, key);
+    if (index >= 0) {
+        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);
+    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) {
+        return false;
+    }
+    Entry& entry = mTable->editEntryAt(index);
+    if (mListener) {
+        (*mListener)(entry.key, entry.value);
+    }
+    detachFromCache(entry);
+    mTable->removeAt(index);
+    return true;
+}
+
+template <typename TKey, typename TValue>
+bool LruCache<TKey, TValue>::removeOldest() {
+    if (mOldest != NULL) {
+        return remove(mOldest->key);
+        // TODO: should probably abort if false
+    }
+    return false;
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::clear() {
+    if (mListener) {
+        for (Entry* p = mOldest; p != NULL; p = p->child) {
+            (*mListener)(p->key, p->value);
+        }
+    }
+    mYoungest = NULL;
+    mOldest = NULL;
+    mTable->clear();
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
+    if (mYoungest == NULL) {
+        mYoungest = mOldest = &entry;
+    } else {
+        entry.parent = mYoungest;
+        mYoungest->child = &entry;
+        mYoungest = &entry;
+    }
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
+    if (entry.parent != NULL) {
+        entry.parent->child = entry.child;
+    } else {
+        mOldest = entry.child;
+    }
+    if (entry.child != NULL) {
+        entry.child->parent = entry.parent;
+    } else {
+        mYoungest = entry.parent;
+    }
+
+    entry.parent = NULL;
+    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);
+    }
+}
+
+}