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

diff --git a/libs/utils/JenkinsHash.cpp b/libs/utils/JenkinsHash.cpp
new file mode 100644
index 0000000000..52c9bb7df8
--- /dev/null
+++ b/libs/utils/JenkinsHash.cpp
@@ -0,0 +1,64 @@
+/*
+ * 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.
+ */
+
+/* Implementation of Jenkins one-at-a-time hash function. These choices are
+ * optimized for code size and portability, rather than raw speed. But speed
+ * should still be quite good.
+ **/
+
+#include <utils/JenkinsHash.h>
+
+namespace android {
+
+hash_t JenkinsHashWhiten(uint32_t hash) {
+    hash += (hash << 3);
+    hash ^= (hash >> 11);
+    hash += (hash << 15);
+    return hash;
+}
+
+uint32_t JenkinsHashMixBytes(uint32_t hash, const uint8_t* bytes, size_t size) {
+    hash = JenkinsHashMix(hash, (uint32_t)size);
+    size_t i;
+    for (i = 0; i < (size & -4); i += 4) {
+        uint32_t data = bytes[i] | (bytes[i+1] << 8) | (bytes[i+2] << 16) | (bytes[i+3] << 24);
+        hash = JenkinsHashMix(hash, data);
+    }
+    if (size & 3) {
+        uint32_t data = bytes[i];
+        data |= ((size & 3) > 1) ? (bytes[i+1] << 8) : 0;
+        data |= ((size & 3) > 2) ? (bytes[i+2] << 16) : 0;
+        hash = JenkinsHashMix(hash, data);
+    }
+    return hash;
+}
+
+uint32_t JenkinsHashMixShorts(uint32_t hash, const uint16_t* shorts, size_t size) {
+    hash = JenkinsHashMix(hash, (uint32_t)size);
+    size_t i;
+    for (i = 0; i < (size & -2); i += 2) {
+        uint32_t data = shorts[i] | (shorts[i+1] << 16);
+        hash = JenkinsHashMix(hash, data);
+    }
+    if (size & 1) {
+        uint32_t data = shorts[i];
+        hash = JenkinsHashMix(hash, data);
+    }
+    return hash;
+}
+
+}
+