structure: CHash: add option to indicate entry hashes can be obtained efficiently, and use this to speed up lookups.

3 files changed, 8 insertions, 1 deletions

diff --git a/structure/CHash_footer.h b/structure/CHash_footer.h
index 33c3fe0..10b4141 100644
--- a/structure/CHash_footer.h
+++ b/structure/CHash_footer.h
@@ -37,6 +37,7 @@
 #undef CHASH_PARAM_DEREF
 #undef CHASH_PARAM_ENTRYHASH
 #undef CHASH_PARAM_KEYHASH
+#undef CHASH_PARAM_ENTRYHASH_IS_CHEAP
 #undef CHASH_PARAM_COMPARE_ENTRIES
 #undef CHASH_PARAM_COMPARE_KEY_ENTRY
 #undef CHASH_PARAM_ENTRY_NEXT
diff --git a/structure/CHash_header.h b/structure/CHash_header.h
index b59bdc6..b0fa160 100644
--- a/structure/CHash_header.h
+++ b/structure/CHash_header.h
@@ -37,6 +37,7 @@
 // CHASH_PARAM_DEREF(arg, link) - dereference a non-null link
 // CHASH_PARAM_ENTRYHASH(arg, entry) - hash function for entries; returns size_t
 // CHASH_PARAM_KEYHASH(arg, key) - hash function for keys; returns size_t
+// CHASH_PARAM_ENTRYHASH_IS_CHEAP - define to 1 if CHASH_PARAM_ENTRYHASH is cheap (e.g. hashes are precomputed)
 // CHASH_PARAM_COMPARE_ENTRIES(arg, entry1, entry2) - compares two entries; returns 1 for equality, 0 otherwise
 // CHASH_PARAM_COMPARE_KEY_ENTRY(arg, key1, entry2) - compares key and entry; returns 1 for equality, 0 otherwise
 // CHASH_PARAM_ENTRY_NEXT - next member in entry
diff --git a/structure/CHash_impl.h b/structure/CHash_impl.h
index dc37473..c7f8874 100644
--- a/structure/CHash_impl.h
+++ b/structure/CHash_impl.h
@@ -177,12 +177,17 @@ static void CHash_Remove (CHash *o, CHashArg arg, CHashRef entry)
 
 static CHashRef CHash_Lookup (const CHash *o, CHashArg arg, CHashKey key) 
 {
-    size_t index = CHASH_PARAM_KEYHASH(arg, key) % o->num_buckets;
+    size_t hash = CHASH_PARAM_KEYHASH(arg, key);
+    size_t index = hash % o->num_buckets;
     
     CHashLink link = o->buckets[index];
     while (link != CHashNullLink()) {
         CHashRef cur = CHashDerefNonNull(arg, link);
+#if CHASH_PARAM_ENTRYHASH_IS_CHEAP
+        if (CHASH_PARAM_ENTRYHASH(arg, cur) == hash && CHASH_PARAM_COMPARE_KEY_ENTRY(arg, key, cur)) {
+#else
         if (CHASH_PARAM_COMPARE_KEY_ENTRY(arg, key, cur)) {
+#endif
             return cur;
         }
         link = CHash_next(cur);