From 6ae4e8eae78e0781633f7b40a1b5cc189bc40923 Mon Sep 17 00:00:00 2001 From: Jeff Davis Date: Thu, 1 Aug 2019 14:52:43 -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. The immediate use case is for 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. Author: Jeff Davis Reviewed-by: Andres Freund Discussion: https://postgr.es/m/48abe675e1330f0c264ab2fe0d4ff23eb244f9ef.camel%40j-davis.com --- src/include/lib/simplehash.h | 74 +++++++++++++++++++++++++++++++----- 1 file changed, 65 insertions(+), 9 deletions(-) diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h index 5c6bd93bc7..d827270a6a 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) @@ -91,6 +93,8 @@ #define SH_DISTANCE_FROM_OPTIMAL SH_MAKE_NAME(distance) #define SH_INITIAL_BUCKET SH_MAKE_NAME(initial_bucket) #define SH_ENTRY_HASH SH_MAKE_NAME(entry_hash) +#define SH_INSERT_HASH_INTERNAL SH_MAKE_NAME(insert_hash_internal) +#define SH_LOOKUP_HASH_INTERNAL SH_MAKE_NAME(lookup_hash_internal) /* generate forward declarations necessary to use the hash table */ #ifdef SH_DECLARE @@ -144,7 +148,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); @@ -492,14 +500,12 @@ SH_GROW(SH_TYPE * tb, uint32 newsize) } /* - * Insert the key key into the hash-table, set *found to true if the key - * already exists, false otherwise. Returns the hash-table entry in either - * case. + * This is a separate static inline function, so it can be reliably be inlined + * into its wrapper functions even if SH_SCOPE is extern. */ -SH_SCOPE SH_ELEMENT_TYPE * -SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found) +static inline SH_ELEMENT_TYPE * +SH_INSERT_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool *found) { - uint32 hash = SH_HASH_KEY(tb, key); uint32 startelem; uint32 curelem; SH_ELEMENT_TYPE *data; @@ -664,12 +670,36 @@ restart: } /* - * Lookup up entry in hash table. Returns NULL if key not present. + * Insert the key key into the hash-table, 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_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key) +SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found) +{ + uint32 hash = SH_HASH_KEY(tb, key); + + return SH_INSERT_HASH_INTERNAL(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) +{ + return SH_INSERT_HASH_INTERNAL(tb, key, hash, found); +} + +/* + * This is a separate static inline function, so it can be reliably be inlined + * into its wrapper functions even if SH_SCOPE is extern. + */ +static inline SH_ELEMENT_TYPE * +SH_LOOKUP_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash) { - uint32 hash = SH_HASH_KEY(tb, key); const uint32 startelem = SH_INITIAL_BUCKET(tb, hash); uint32 curelem = startelem; @@ -698,6 +728,28 @@ SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key) } } +/* + * Lookup up entry in hash table. Returns NULL if key not present. + */ +SH_SCOPE SH_ELEMENT_TYPE * +SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key) +{ + uint32 hash = SH_HASH_KEY(tb, key); + + return SH_LOOKUP_HASH_INTERNAL(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) +{ + return SH_LOOKUP_HASH_INTERNAL(tb, key, hash); +} + /* * Delete entry from hash table. Returns whether to-be-deleted key was * present. @@ -971,8 +1023,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 @@ -989,3 +1043,5 @@ SH_STAT(SH_TYPE * tb) #undef SH_PREV #undef SH_DISTANCE_FROM_OPTIMAL #undef SH_ENTRY_HASH +#undef SH_INSERT_HASH_INTERNAL +#undef SH_LOOKUP_HASH_INTERNAL -- 2.40.0