From ac4877d1e7b64da6caead189b85813fb5fed81a0 Mon Sep 17 00:00:00 2001 From: Jeff Davis Date: Tue, 16 Jul 2019 12:07:37 -0700 Subject: [PATCH] Allow simplehash to use already-calculated hash values. Add _lookup_hash and _insert_hash functions for callers that have already calculated the hash value of the key. This is intended for use with hash algorithms that write to disk in partitions. The hash value can be calculated once, used to perform a lookup, used to select the partition, then written to the partition along with the tuple. When the tuple is read back, the hash value does not need to be recalculated. --- src/include/lib/simplehash.h | 36 ++++++++++++++++++++++++++++++++++-- 1 file changed, 34 insertions(+), 2 deletions(-) diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h index 5c6bd93bc7..065062ee96 100644 --- a/src/include/lib/simplehash.h +++ b/src/include/lib/simplehash.h @@ -74,8 +74,10 @@ #define SH_DESTROY SH_MAKE_NAME(destroy) #define SH_RESET SH_MAKE_NAME(reset) #define SH_INSERT SH_MAKE_NAME(insert) +#define SH_INSERT_HASH SH_MAKE_NAME(insert_hash) #define SH_DELETE SH_MAKE_NAME(delete) #define SH_LOOKUP SH_MAKE_NAME(lookup) +#define SH_LOOKUP_HASH SH_MAKE_NAME(lookup_hash) #define SH_GROW SH_MAKE_NAME(grow) #define SH_START_ITERATE SH_MAKE_NAME(start_iterate) #define SH_START_ITERATE_AT SH_MAKE_NAME(start_iterate_at) @@ -144,7 +146,11 @@ SH_SCOPE void SH_DESTROY(SH_TYPE * tb); SH_SCOPE void SH_RESET(SH_TYPE * tb); SH_SCOPE void SH_GROW(SH_TYPE * tb, uint32 newsize); SH_SCOPE SH_ELEMENT_TYPE *SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found); +SH_SCOPE SH_ELEMENT_TYPE *SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key, + uint32 hash, bool *found); SH_SCOPE SH_ELEMENT_TYPE *SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key); +SH_SCOPE SH_ELEMENT_TYPE *SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key, + uint32 hash); SH_SCOPE bool SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key); SH_SCOPE void SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter); SH_SCOPE void SH_START_ITERATE_AT(SH_TYPE * tb, SH_ITERATOR * iter, uint32 at); @@ -499,7 +505,19 @@ SH_GROW(SH_TYPE * tb, uint32 newsize) SH_SCOPE SH_ELEMENT_TYPE * SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found) { - uint32 hash = SH_HASH_KEY(tb, key); + uint32 hash = SH_HASH_KEY(tb, key); + + return SH_INSERT_HASH(tb, key, hash, found); +} + +/* + * Insert the key key into the hash-table using an already-calculated + * hash. Set *found to true if the key already exists, false + * otherwise. Returns the hash-table entry in either case. + */ +SH_SCOPE SH_ELEMENT_TYPE * +SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool *found) +{ uint32 startelem; uint32 curelem; SH_ELEMENT_TYPE *data; @@ -669,7 +687,19 @@ restart: SH_SCOPE SH_ELEMENT_TYPE * SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key) { - uint32 hash = SH_HASH_KEY(tb, key); + uint32 hash = SH_HASH_KEY(tb, key); + + return SH_LOOKUP_HASH(tb, key, hash); +} + +/* + * Lookup up entry in hash table using an already-calculated hash. + * + * Returns NULL if key not present. + */ +SH_SCOPE SH_ELEMENT_TYPE * +SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash) +{ const uint32 startelem = SH_INITIAL_BUCKET(tb, hash); uint32 curelem = startelem; @@ -971,8 +1001,10 @@ SH_STAT(SH_TYPE * tb) #undef SH_DESTROY #undef SH_RESET #undef SH_INSERT +#undef SH_INSERT_HASH #undef SH_DELETE #undef SH_LOOKUP +#undef SH_LOOKUP_HASH #undef SH_GROW #undef SH_START_ITERATE #undef SH_START_ITERATE_AT -- 2.17.1