commit b6ea175b6b4d0aaac85ed6cd8ccac01ab896486b
author Raph Levien <raph@google.com> Thu Oct 25 23:11:13 2012 -0700
committer Alex Ray <aray@google.com> Tue Jul 30 13:57:00 2013 -0700
tree 9a0508bd7bc39c01724baab9450fcb4eb180b836
parent fe34e45c217e67e32fa56b7e01fd4163a621c647

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

libs/utils/tests/Android.mk

diff --git a/libs/utils/tests/Android.mk b/libs/utils/tests/Android.mk
index 5b2b5b1..a2ca9c8 100644
--- a/libs/utils/tests/Android.mk
+++ b/libs/utils/tests/Android.mk
@@ -7,6 +7,7 @@
     BasicHashtable_test.cpp \
     BlobCache_test.cpp \
     Looper_test.cpp \
+    LruCache_test.cpp \
     String8_test.cpp \
     Unicode_test.cpp \
     Vector_test.cpp \