From 8185e47822465a5c7a9cc6e56a11f16996855d79 Mon Sep 17 00:00:00 2001 From: Raph Levien Date: Thu, 25 Oct 2012 23:11:13 -0700 Subject: 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 | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'include/utils/BasicHashtable.h') 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(bucket.entry); -- cgit v1.2.3-59-g8ed1b