OSDN Git Service

Add an LRU cache plus hashing primitives
authorRaph Levien <raph@google.com>
Fri, 26 Oct 2012 06:11:13 +0000 (23:11 -0700)
committerRaph Levien <raph@google.com>
Fri, 26 Oct 2012 23:09:22 +0000 (16:09 -0700)
commit8185e47822465a5c7a9cc6e56a11f16996855d79
treea3faed051d830bd856e0c59fef93b8187a3f2bf9
parentba0b9cca697a84947c08983338ce4e7f30920fd8
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
include/utils/BasicHashtable.h
include/utils/JenkinsHash.h [new file with mode: 0644]
include/utils/LruCache.h [new file with mode: 0644]
include/utils/TypeHelpers.h
libs/utils/Android.mk
libs/utils/BasicHashtable.cpp
libs/utils/JenkinsHash.cpp [new file with mode: 0644]
libs/utils/tests/Android.mk
libs/utils/tests/LruCache_test.cpp [new file with mode: 0644]