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, 8 insertions, 0 deletions

diff --git a/include/utils/BasicHashtable.h b/include/utils/BasicHashtable.h
index fdf97385f9..7a6c96cefc 100644
--- a/include/utils/BasicHashtable.h
+++ b/include/utils/BasicHashtable.h
@@ -328,6 +328,14 @@ public:
         BasicHashtableImpl::rehash(minimumCapacity, loadFactor);
     }
 
+    /* Determines whether there is room to add another entry without rehashing.
+     * When this returns true, a subsequent add() operation is guaranteed to
+     * complete without performing a rehash.
+     */
+    inline bool hasMoreRoom() const {
+        return mCapacity > mFilledBuckets;
+    }
+
 protected:
     static inline const TEntry& entryFor(const Bucket& bucket) {
         return reinterpret_cast<const TEntry&>(bucket.entry);