4 * When included this file generates a "templated" (by way of macros)
5 * open-addressing hash table implementation specialized to user-defined
8 * It's probably not worthwhile to generate such a specialized implementation
9 * for hash tables that aren't performance or space sensitive.
11 * Compared to dynahash, simplehash has the following benefits:
13 * - Due to the "templated" code generation has known structure sizes and no
14 * indirect function calls (which show up substantially in dynahash
15 * profiles). These features considerably increase speed for small
17 * - Open addressing has better CPU cache behavior than dynahash's chained
19 * - The generated interface is type-safe and easier to use than dynahash,
20 * though at the cost of more complex setup.
21 * - Allocates memory in a MemoryContext or another allocator with a
22 * malloc/free style interface (which isn't easily usable in a shared
24 * - Does not require the overhead of a separate memory context.
28 * To generate a hash-table and associated functions for a use case several
29 * macros have to be #define'ed before this file is included. Including
30 * the file #undef's all those, so a new hash table can be generated
32 * The relevant parameters are:
33 * - SH_PREFIX - prefix for all symbol names generated. A prefix of 'foo'
34 * will result in hash table type 'foo_hash' and functions like
35 * 'foo_insert'/'foo_lookup' and so forth.
36 * - SH_ELEMENT_TYPE - type of the contained elements
37 * - SH_KEY_TYPE - type of the hashtable's key
38 * - SH_DECLARE - if defined function prototypes and type declarations are
40 * - SH_DEFINE - if defined function definitions are generated
41 * - SH_SCOPE - in which scope (e.g. extern, static inline) do function
43 * - SH_RAW_ALLOCATOR - if defined, memory contexts are not used; instead,
44 * use this to allocate bytes. The allocator must zero the returned space.
45 * - SH_USE_NONDEFAULT_ALLOCATOR - if defined no element allocator functions
46 * are defined, so you can supply your own
47 * The following parameters are only relevant when SH_DEFINE is defined:
48 * - SH_KEY - name of the element in SH_ELEMENT_TYPE containing the hash key
49 * - SH_EQUAL(table, a, b) - compare two table keys
50 * - SH_HASH_KEY(table, key) - generate hash for the key
51 * - SH_STORE_HASH - if defined the hash is stored in the elements
52 * - SH_GET_HASH(tb, a) - return the field to store the hash in
54 * The element type is required to contain a "status" member that can store
55 * the range of values defined in the SH_STATUS enum.
57 * While SH_STORE_HASH (and subsequently SH_GET_HASH) are optional, because
58 * the hash table implementation needs to compare hashes to move elements
59 * (particularly when growing the hash), it's preferable, if possible, to
60 * store the element's hash in the element's data type. If the hash is so
61 * stored, the hash table will also compare hashes before calling SH_EQUAL
62 * when comparing two keys.
64 * For convenience the hash table create functions accept a void pointer
65 * that will be stored in the hash table type's member private_data. This
66 * allows callbacks to reference caller provided data.
68 * For examples of usage look at tidbitmap.c (file local definition) and
69 * execnodes.h/execGrouping.c (exposed declaration, file local
74 * The hash table design chosen is a variant of linear open-addressing. The
75 * reason for doing so is that linear addressing is CPU cache & pipeline
76 * friendly. The biggest disadvantage of simple linear addressing schemes
77 * are highly variable lookup times due to clustering, and deletions
78 * leaving a lot of tombstones around. To address these issues a variant
79 * of "robin hood" hashing is employed. Robin hood hashing optimizes
80 * chaining lengths by moving elements close to their optimal bucket
81 * ("rich" elements), out of the way if a to-be-inserted element is further
82 * away from its optimal position (i.e. it's "poor"). While that can make
83 * insertions slower, the average lookup performance is a lot better, and
84 * higher fill factors can be used in a still performant manner. To avoid
85 * tombstones - which normally solve the issue that a deleted node's
86 * presence is relevant to determine whether a lookup needs to continue
87 * looking or is done - buckets following a deleted element are shifted
88 * backwards, unless they're empty or already at their optimal position.
90 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
91 * Portions Copyright (c) 1994, Regents of the University of California
93 * src/include/lib/simplehash.h
96 #include "port/pg_bitutils.h"
99 #define SH_MAKE_PREFIX(a) CppConcat(a,_)
100 #define SH_MAKE_NAME(name) SH_MAKE_NAME_(SH_MAKE_PREFIX(SH_PREFIX),name)
101 #define SH_MAKE_NAME_(a,b) CppConcat(a,b)
103 /* name macros for: */
105 /* type declarations */
106 #define SH_TYPE SH_MAKE_NAME(hash)
107 #define SH_STATUS SH_MAKE_NAME(status)
108 #define SH_STATUS_EMPTY SH_MAKE_NAME(SH_EMPTY)
109 #define SH_STATUS_IN_USE SH_MAKE_NAME(SH_IN_USE)
110 #define SH_ITERATOR SH_MAKE_NAME(iterator)
112 /* function declarations */
113 #define SH_CREATE SH_MAKE_NAME(create)
114 #define SH_DESTROY SH_MAKE_NAME(destroy)
115 #define SH_RESET SH_MAKE_NAME(reset)
116 #define SH_INSERT SH_MAKE_NAME(insert)
117 #define SH_INSERT_HASH SH_MAKE_NAME(insert_hash)
118 #define SH_DELETE_ITEM SH_MAKE_NAME(delete_item)
119 #define SH_DELETE SH_MAKE_NAME(delete)
120 #define SH_LOOKUP SH_MAKE_NAME(lookup)
121 #define SH_LOOKUP_HASH SH_MAKE_NAME(lookup_hash)
122 #define SH_GROW SH_MAKE_NAME(grow)
123 #define SH_START_ITERATE SH_MAKE_NAME(start_iterate)
124 #define SH_START_ITERATE_AT SH_MAKE_NAME(start_iterate_at)
125 #define SH_ITERATE SH_MAKE_NAME(iterate)
126 #define SH_ALLOCATE SH_MAKE_NAME(allocate)
127 #define SH_FREE SH_MAKE_NAME(free)
128 #define SH_STAT SH_MAKE_NAME(stat)
130 /* internal helper functions (no externally visible prototypes) */
131 #define SH_COMPUTE_PARAMETERS SH_MAKE_NAME(compute_parameters)
132 #define SH_NEXT SH_MAKE_NAME(next)
133 #define SH_PREV SH_MAKE_NAME(prev)
134 #define SH_DISTANCE_FROM_OPTIMAL SH_MAKE_NAME(distance)
135 #define SH_INITIAL_BUCKET SH_MAKE_NAME(initial_bucket)
136 #define SH_ENTRY_HASH SH_MAKE_NAME(entry_hash)
137 #define SH_INSERT_HASH_INTERNAL SH_MAKE_NAME(insert_hash_internal)
138 #define SH_LOOKUP_HASH_INTERNAL SH_MAKE_NAME(lookup_hash_internal)
140 /* generate forward declarations necessary to use the hash table */
143 /* type definitions */
144 typedef struct SH_TYPE
147 * Size of data / bucket array, 64 bits to handle UINT32_MAX sized hash
148 * tables. Note that the maximum number of elements is lower
149 * (SH_MAX_FILLFACTOR)
153 /* how many elements have valid contents */
156 /* mask for bucket and size calculations, based on size */
159 /* boundary after which to grow hashtable */
160 uint32 grow_threshold
;
163 SH_ELEMENT_TYPE
*data
;
165 #ifndef SH_RAW_ALLOCATOR
166 /* memory context to use for allocations */
170 /* user defined data, useful for callbacks */
174 typedef enum SH_STATUS
176 SH_STATUS_EMPTY
= 0x00,
177 SH_STATUS_IN_USE
= 0x01
180 typedef struct SH_ITERATOR
182 uint32 cur
; /* current element */
184 bool done
; /* iterator exhausted? */
187 /* externally visible function prototypes */
188 #ifdef SH_RAW_ALLOCATOR
189 /* <prefix>_hash <prefix>_create(uint32 nelements, void *private_data) */
190 SH_SCOPE SH_TYPE
*SH_CREATE(uint32 nelements
, void *private_data
);
193 * <prefix>_hash <prefix>_create(MemoryContext ctx, uint32 nelements,
194 * void *private_data)
196 SH_SCOPE SH_TYPE
*SH_CREATE(MemoryContext ctx
, uint32 nelements
,
200 /* void <prefix>_destroy(<prefix>_hash *tb) */
201 SH_SCOPE
void SH_DESTROY(SH_TYPE
* tb
);
203 /* void <prefix>_reset(<prefix>_hash *tb) */
204 SH_SCOPE
void SH_RESET(SH_TYPE
* tb
);
206 /* void <prefix>_grow(<prefix>_hash *tb, uint64 newsize) */
207 SH_SCOPE
void SH_GROW(SH_TYPE
* tb
, uint64 newsize
);
209 /* <element> *<prefix>_insert(<prefix>_hash *tb, <key> key, bool *found) */
210 SH_SCOPE SH_ELEMENT_TYPE
*SH_INSERT(SH_TYPE
* tb
, SH_KEY_TYPE key
, bool *found
);
213 * <element> *<prefix>_insert_hash(<prefix>_hash *tb, <key> key, uint32 hash,
216 SH_SCOPE SH_ELEMENT_TYPE
*SH_INSERT_HASH(SH_TYPE
* tb
, SH_KEY_TYPE key
,
217 uint32 hash
, bool *found
);
219 /* <element> *<prefix>_lookup(<prefix>_hash *tb, <key> key) */
220 SH_SCOPE SH_ELEMENT_TYPE
*SH_LOOKUP(SH_TYPE
* tb
, SH_KEY_TYPE key
);
222 /* <element> *<prefix>_lookup_hash(<prefix>_hash *tb, <key> key, uint32 hash) */
223 SH_SCOPE SH_ELEMENT_TYPE
*SH_LOOKUP_HASH(SH_TYPE
* tb
, SH_KEY_TYPE key
,
226 /* void <prefix>_delete_item(<prefix>_hash *tb, <element> *entry) */
227 SH_SCOPE
void SH_DELETE_ITEM(SH_TYPE
* tb
, SH_ELEMENT_TYPE
* entry
);
229 /* bool <prefix>_delete(<prefix>_hash *tb, <key> key) */
230 SH_SCOPE
bool SH_DELETE(SH_TYPE
* tb
, SH_KEY_TYPE key
);
232 /* void <prefix>_start_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
233 SH_SCOPE
void SH_START_ITERATE(SH_TYPE
* tb
, SH_ITERATOR
* iter
);
236 * void <prefix>_start_iterate_at(<prefix>_hash *tb, <prefix>_iterator *iter,
239 SH_SCOPE
void SH_START_ITERATE_AT(SH_TYPE
* tb
, SH_ITERATOR
* iter
, uint32 at
);
241 /* <element> *<prefix>_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
242 SH_SCOPE SH_ELEMENT_TYPE
*SH_ITERATE(SH_TYPE
* tb
, SH_ITERATOR
* iter
);
244 /* void <prefix>_stat(<prefix>_hash *tb */
245 SH_SCOPE
void SH_STAT(SH_TYPE
* tb
);
247 #endif /* SH_DECLARE */
250 /* generate implementation of the hash table */
253 #ifndef SH_RAW_ALLOCATOR
254 #include "utils/memutils.h"
257 /* max data array size,we allow up to PG_UINT32_MAX buckets, including 0 */
258 #define SH_MAX_SIZE (((uint64) PG_UINT32_MAX) + 1)
260 /* normal fillfactor, unless already close to maximum */
261 #ifndef SH_FILLFACTOR
262 #define SH_FILLFACTOR (0.9)
264 /* increase fillfactor if we otherwise would error out */
265 #define SH_MAX_FILLFACTOR (0.98)
266 /* grow if actual and optimal location bigger than */
267 #ifndef SH_GROW_MAX_DIB
268 #define SH_GROW_MAX_DIB 25
270 /* grow if more than elements to move when inserting */
271 #ifndef SH_GROW_MAX_MOVE
272 #define SH_GROW_MAX_MOVE 150
274 #ifndef SH_GROW_MIN_FILLFACTOR
275 /* but do not grow due to SH_GROW_MAX_* if below */
276 #define SH_GROW_MIN_FILLFACTOR 0.1
280 #define SH_COMPARE_KEYS(tb, ahash, akey, b) (ahash == SH_GET_HASH(tb, b) && SH_EQUAL(tb, b->SH_KEY, akey))
282 #define SH_COMPARE_KEYS(tb, ahash, akey, b) (SH_EQUAL(tb, b->SH_KEY, akey))
286 * Wrap the following definitions in include guards, to avoid multiple
287 * definition errors if this header is included more than once. The rest of
288 * the file deliberately has no include guards, because it can be included
289 * with different parameters to define functions and types with non-colliding
296 #define sh_error(...) \
297 do { pg_log_fatal(__VA_ARGS__); exit(1); } while(0)
298 #define sh_log(...) pg_log_info(__VA_ARGS__)
300 #define sh_error(...) elog(ERROR, __VA_ARGS__)
301 #define sh_log(...) elog(LOG, __VA_ARGS__)
307 * Compute sizing parameters for hashtable. Called when creating and growing
311 SH_COMPUTE_PARAMETERS(SH_TYPE
* tb
, uint64 newsize
)
315 /* supporting zero sized hashes would complicate matters */
316 size
= Max(newsize
, 2);
318 /* round up size to the next power of 2, that's how bucketing works */
319 size
= pg_nextpower2_64(size
);
320 Assert(size
<= SH_MAX_SIZE
);
323 * Verify that allocation of ->data is possible on this platform, without
326 if (unlikely((((uint64
) sizeof(SH_ELEMENT_TYPE
)) * size
) >= SIZE_MAX
/ 2))
327 sh_error("hash table too large");
331 tb
->sizemask
= (uint32
) (size
- 1);
334 * Compute the next threshold at which we need to grow the hash table
337 if (tb
->size
== SH_MAX_SIZE
)
338 tb
->grow_threshold
= ((double) tb
->size
) * SH_MAX_FILLFACTOR
;
340 tb
->grow_threshold
= ((double) tb
->size
) * SH_FILLFACTOR
;
343 /* return the optimal bucket for the hash */
345 SH_INITIAL_BUCKET(SH_TYPE
* tb
, uint32 hash
)
347 return hash
& tb
->sizemask
;
350 /* return next bucket after the current, handling wraparound */
352 SH_NEXT(SH_TYPE
* tb
, uint32 curelem
, uint32 startelem
)
354 curelem
= (curelem
+ 1) & tb
->sizemask
;
356 Assert(curelem
!= startelem
);
361 /* return bucket before the current, handling wraparound */
363 SH_PREV(SH_TYPE
* tb
, uint32 curelem
, uint32 startelem
)
365 curelem
= (curelem
- 1) & tb
->sizemask
;
367 Assert(curelem
!= startelem
);
372 /* return distance between bucket and its optimal position */
374 SH_DISTANCE_FROM_OPTIMAL(SH_TYPE
* tb
, uint32 optimal
, uint32 bucket
)
376 if (optimal
<= bucket
)
377 return bucket
- optimal
;
379 return (tb
->size
+ bucket
) - optimal
;
383 SH_ENTRY_HASH(SH_TYPE
* tb
, SH_ELEMENT_TYPE
* entry
)
386 return SH_GET_HASH(tb
, entry
);
388 return SH_HASH_KEY(tb
, entry
->SH_KEY
);
392 /* default memory allocator function */
393 static inline void *SH_ALLOCATE(SH_TYPE
* type
, Size size
);
394 static inline void SH_FREE(SH_TYPE
* type
, void *pointer
);
396 #ifndef SH_USE_NONDEFAULT_ALLOCATOR
398 /* default memory allocator function */
400 SH_ALLOCATE(SH_TYPE
* type
, Size size
)
402 #ifdef SH_RAW_ALLOCATOR
403 return SH_RAW_ALLOCATOR(size
);
405 return MemoryContextAllocExtended(type
->ctx
, size
,
406 MCXT_ALLOC_HUGE
| MCXT_ALLOC_ZERO
);
410 /* default memory free function */
412 SH_FREE(SH_TYPE
* type
, void *pointer
)
420 * Create a hash table with enough space for `nelements` distinct members.
421 * Memory for the hash table is allocated from the passed-in context. If
422 * desired, the array of elements can be allocated using a passed-in allocator;
423 * this could be useful in order to place the array of elements in a shared
424 * memory, or in a context that will outlive the rest of the hash table.
425 * Memory other than for the array of elements will still be allocated from
426 * the passed-in context.
428 #ifdef SH_RAW_ALLOCATOR
430 SH_CREATE(uint32 nelements
, void *private_data
)
433 SH_CREATE(MemoryContext ctx
, uint32 nelements
, void *private_data
)
439 #ifdef SH_RAW_ALLOCATOR
440 tb
= SH_RAW_ALLOCATOR(sizeof(SH_TYPE
));
442 tb
= MemoryContextAllocZero(ctx
, sizeof(SH_TYPE
));
445 tb
->private_data
= private_data
;
447 /* increase nelements by fillfactor, want to store nelements elements */
448 size
= Min((double) SH_MAX_SIZE
, ((double) nelements
) / SH_FILLFACTOR
);
450 SH_COMPUTE_PARAMETERS(tb
, size
);
452 tb
->data
= SH_ALLOCATE(tb
, sizeof(SH_ELEMENT_TYPE
) * tb
->size
);
457 /* destroy a previously created hash table */
459 SH_DESTROY(SH_TYPE
* tb
)
461 SH_FREE(tb
, tb
->data
);
465 /* reset the contents of a previously created hash table */
467 SH_RESET(SH_TYPE
* tb
)
469 memset(tb
->data
, 0, sizeof(SH_ELEMENT_TYPE
) * tb
->size
);
474 * Grow a hash table to at least `newsize` buckets.
476 * Usually this will automatically be called by insertions/deletions, when
477 * necessary. But resizing to the exact input size can be advantageous
478 * performance-wise, when known at some point.
481 SH_GROW(SH_TYPE
* tb
, uint64 newsize
)
483 uint64 oldsize
= tb
->size
;
484 SH_ELEMENT_TYPE
*olddata
= tb
->data
;
485 SH_ELEMENT_TYPE
*newdata
;
487 uint32 startelem
= 0;
490 Assert(oldsize
== pg_nextpower2_64(oldsize
));
491 Assert(oldsize
!= SH_MAX_SIZE
);
492 Assert(oldsize
< newsize
);
494 /* compute parameters for new table */
495 SH_COMPUTE_PARAMETERS(tb
, newsize
);
497 tb
->data
= SH_ALLOCATE(tb
, sizeof(SH_ELEMENT_TYPE
) * tb
->size
);
502 * Copy entries from the old data to newdata. We theoretically could use
503 * SH_INSERT here, to avoid code duplication, but that's more general than
504 * we need. We neither want tb->members increased, nor do we need to do
505 * deal with deleted elements, nor do we need to compare keys. So a
506 * special-cased implementation is lot faster. As resizing can be time
507 * consuming and frequent, that's worthwhile to optimize.
509 * To be able to simply move entries over, we have to start not at the
510 * first bucket (i.e olddata[0]), but find the first bucket that's either
511 * empty, or is occupied by an entry at its optimal position. Such a
512 * bucket has to exist in any table with a load factor under 1, as not all
513 * buckets are occupied, i.e. there always has to be an empty bucket. By
514 * starting at such a bucket we can move the entries to the larger table,
515 * without having to deal with conflicts.
518 /* search for the first element in the hash that's not wrapped around */
519 for (i
= 0; i
< oldsize
; i
++)
521 SH_ELEMENT_TYPE
*oldentry
= &olddata
[i
];
525 if (oldentry
->status
!= SH_STATUS_IN_USE
)
531 hash
= SH_ENTRY_HASH(tb
, oldentry
);
532 optimal
= SH_INITIAL_BUCKET(tb
, hash
);
541 /* and copy all elements in the old table */
542 copyelem
= startelem
;
543 for (i
= 0; i
< oldsize
; i
++)
545 SH_ELEMENT_TYPE
*oldentry
= &olddata
[copyelem
];
547 if (oldentry
->status
== SH_STATUS_IN_USE
)
552 SH_ELEMENT_TYPE
*newentry
;
554 hash
= SH_ENTRY_HASH(tb
, oldentry
);
555 startelem
= SH_INITIAL_BUCKET(tb
, hash
);
558 /* find empty element to put data into */
561 newentry
= &newdata
[curelem
];
563 if (newentry
->status
== SH_STATUS_EMPTY
)
568 curelem
= SH_NEXT(tb
, curelem
, startelem
);
571 /* copy entry to new slot */
572 memcpy(newentry
, oldentry
, sizeof(SH_ELEMENT_TYPE
));
575 /* can't use SH_NEXT here, would use new size */
577 if (copyelem
>= oldsize
)
583 SH_FREE(tb
, olddata
);
587 * This is a separate static inline function, so it can be reliably be inlined
588 * into its wrapper functions even if SH_SCOPE is extern.
590 static inline SH_ELEMENT_TYPE
*
591 SH_INSERT_HASH_INTERNAL(SH_TYPE
* tb
, SH_KEY_TYPE key
, uint32 hash
, bool *found
)
595 SH_ELEMENT_TYPE
*data
;
602 * We do the grow check even if the key is actually present, to avoid
603 * doing the check inside the loop. This also lets us avoid having to
604 * re-find our position in the hashtable after resizing.
606 * Note that this also reached when resizing the table due to
607 * SH_GROW_MAX_DIB / SH_GROW_MAX_MOVE.
609 if (unlikely(tb
->members
>= tb
->grow_threshold
))
611 if (unlikely(tb
->size
== SH_MAX_SIZE
))
612 sh_error("hash table size exceeded");
615 * When optimizing, it can be very useful to print these out.
618 SH_GROW(tb
, tb
->size
* 2);
622 /* perform insert, start bucket search at optimal location */
624 startelem
= SH_INITIAL_BUCKET(tb
, hash
);
631 SH_ELEMENT_TYPE
*entry
= &data
[curelem
];
633 /* any empty bucket can directly be used */
634 if (entry
->status
== SH_STATUS_EMPTY
)
639 SH_GET_HASH(tb
, entry
) = hash
;
641 entry
->status
= SH_STATUS_IN_USE
;
647 * If the bucket is not empty, we either found a match (in which case
648 * we're done), or we have to decide whether to skip over or move the
649 * colliding entry. When the colliding element's distance to its
650 * optimal position is smaller than the to-be-inserted entry's, we
651 * shift the colliding entry (and its followers) forward by one.
654 if (SH_COMPARE_KEYS(tb
, hash
, key
, entry
))
656 Assert(entry
->status
== SH_STATUS_IN_USE
);
661 curhash
= SH_ENTRY_HASH(tb
, entry
);
662 curoptimal
= SH_INITIAL_BUCKET(tb
, curhash
);
663 curdist
= SH_DISTANCE_FROM_OPTIMAL(tb
, curoptimal
, curelem
);
665 if (insertdist
> curdist
)
667 SH_ELEMENT_TYPE
*lastentry
= entry
;
668 uint32 emptyelem
= curelem
;
672 /* find next empty bucket */
675 SH_ELEMENT_TYPE
*emptyentry
;
677 emptyelem
= SH_NEXT(tb
, emptyelem
, startelem
);
678 emptyentry
= &data
[emptyelem
];
680 if (emptyentry
->status
== SH_STATUS_EMPTY
)
682 lastentry
= emptyentry
;
687 * To avoid negative consequences from overly imbalanced
688 * hashtables, grow the hashtable if collisions would require
689 * us to move a lot of entries. The most likely cause of such
690 * imbalance is filling a (currently) small table, from a
691 * currently big one, in hash-table order. Don't grow if the
692 * hashtable would be too empty, to prevent quick space
693 * explosion for some weird edge cases.
695 if (unlikely(++emptydist
> SH_GROW_MAX_MOVE
) &&
696 ((double) tb
->members
/ tb
->size
) >= SH_GROW_MIN_FILLFACTOR
)
698 tb
->grow_threshold
= 0;
703 /* shift forward, starting at last occupied element */
706 * TODO: This could be optimized to be one memcpy in many cases,
707 * excepting wrapping around at the end of ->data. Hasn't shown up
708 * in profiles so far though.
710 moveelem
= emptyelem
;
711 while (moveelem
!= curelem
)
713 SH_ELEMENT_TYPE
*moveentry
;
715 moveelem
= SH_PREV(tb
, moveelem
, startelem
);
716 moveentry
= &data
[moveelem
];
718 memcpy(lastentry
, moveentry
, sizeof(SH_ELEMENT_TYPE
));
719 lastentry
= moveentry
;
722 /* and fill the now empty spot */
727 SH_GET_HASH(tb
, entry
) = hash
;
729 entry
->status
= SH_STATUS_IN_USE
;
734 curelem
= SH_NEXT(tb
, curelem
, startelem
);
738 * To avoid negative consequences from overly imbalanced hashtables,
739 * grow the hashtable if collisions lead to large runs. The most
740 * likely cause of such imbalance is filling a (currently) small
741 * table, from a currently big one, in hash-table order. Don't grow
742 * if the hashtable would be too empty, to prevent quick space
743 * explosion for some weird edge cases.
745 if (unlikely(insertdist
> SH_GROW_MAX_DIB
) &&
746 ((double) tb
->members
/ tb
->size
) >= SH_GROW_MIN_FILLFACTOR
)
748 tb
->grow_threshold
= 0;
755 * Insert the key key into the hash-table, set *found to true if the key
756 * already exists, false otherwise. Returns the hash-table entry in either
759 SH_SCOPE SH_ELEMENT_TYPE
*
760 SH_INSERT(SH_TYPE
* tb
, SH_KEY_TYPE key
, bool *found
)
762 uint32 hash
= SH_HASH_KEY(tb
, key
);
764 return SH_INSERT_HASH_INTERNAL(tb
, key
, hash
, found
);
768 * Insert the key key into the hash-table using an already-calculated
769 * hash. Set *found to true if the key already exists, false
770 * otherwise. Returns the hash-table entry in either case.
772 SH_SCOPE SH_ELEMENT_TYPE
*
773 SH_INSERT_HASH(SH_TYPE
* tb
, SH_KEY_TYPE key
, uint32 hash
, bool *found
)
775 return SH_INSERT_HASH_INTERNAL(tb
, key
, hash
, found
);
779 * This is a separate static inline function, so it can be reliably be inlined
780 * into its wrapper functions even if SH_SCOPE is extern.
782 static inline SH_ELEMENT_TYPE
*
783 SH_LOOKUP_HASH_INTERNAL(SH_TYPE
* tb
, SH_KEY_TYPE key
, uint32 hash
)
785 const uint32 startelem
= SH_INITIAL_BUCKET(tb
, hash
);
786 uint32 curelem
= startelem
;
790 SH_ELEMENT_TYPE
*entry
= &tb
->data
[curelem
];
792 if (entry
->status
== SH_STATUS_EMPTY
)
797 Assert(entry
->status
== SH_STATUS_IN_USE
);
799 if (SH_COMPARE_KEYS(tb
, hash
, key
, entry
))
803 * TODO: we could stop search based on distance. If the current
804 * buckets's distance-from-optimal is smaller than what we've skipped
805 * already, the entry doesn't exist. Probably only do so if
806 * SH_STORE_HASH is defined, to avoid re-computing hashes?
809 curelem
= SH_NEXT(tb
, curelem
, startelem
);
814 * Lookup up entry in hash table. Returns NULL if key not present.
816 SH_SCOPE SH_ELEMENT_TYPE
*
817 SH_LOOKUP(SH_TYPE
* tb
, SH_KEY_TYPE key
)
819 uint32 hash
= SH_HASH_KEY(tb
, key
);
821 return SH_LOOKUP_HASH_INTERNAL(tb
, key
, hash
);
825 * Lookup up entry in hash table using an already-calculated hash.
827 * Returns NULL if key not present.
829 SH_SCOPE SH_ELEMENT_TYPE
*
830 SH_LOOKUP_HASH(SH_TYPE
* tb
, SH_KEY_TYPE key
, uint32 hash
)
832 return SH_LOOKUP_HASH_INTERNAL(tb
, key
, hash
);
836 * Delete entry from hash table by key. Returns whether to-be-deleted key was
840 SH_DELETE(SH_TYPE
* tb
, SH_KEY_TYPE key
)
842 uint32 hash
= SH_HASH_KEY(tb
, key
);
843 uint32 startelem
= SH_INITIAL_BUCKET(tb
, hash
);
844 uint32 curelem
= startelem
;
848 SH_ELEMENT_TYPE
*entry
= &tb
->data
[curelem
];
850 if (entry
->status
== SH_STATUS_EMPTY
)
853 if (entry
->status
== SH_STATUS_IN_USE
&&
854 SH_COMPARE_KEYS(tb
, hash
, key
, entry
))
856 SH_ELEMENT_TYPE
*lastentry
= entry
;
861 * Backward shift following elements till either an empty element
862 * or an element at its optimal position is encountered.
864 * While that sounds expensive, the average chain length is short,
865 * and deletions would otherwise require tombstones.
869 SH_ELEMENT_TYPE
*curentry
;
873 curelem
= SH_NEXT(tb
, curelem
, startelem
);
874 curentry
= &tb
->data
[curelem
];
876 if (curentry
->status
!= SH_STATUS_IN_USE
)
878 lastentry
->status
= SH_STATUS_EMPTY
;
882 curhash
= SH_ENTRY_HASH(tb
, curentry
);
883 curoptimal
= SH_INITIAL_BUCKET(tb
, curhash
);
885 /* current is at optimal position, done */
886 if (curoptimal
== curelem
)
888 lastentry
->status
= SH_STATUS_EMPTY
;
893 memcpy(lastentry
, curentry
, sizeof(SH_ELEMENT_TYPE
));
895 lastentry
= curentry
;
901 /* TODO: return false; if distance too big */
903 curelem
= SH_NEXT(tb
, curelem
, startelem
);
908 * Delete entry from hash table by entry pointer
911 SH_DELETE_ITEM(SH_TYPE
* tb
, SH_ELEMENT_TYPE
* entry
)
913 SH_ELEMENT_TYPE
*lastentry
= entry
;
914 uint32 hash
= SH_ENTRY_HASH(tb
, entry
);
915 uint32 startelem
= SH_INITIAL_BUCKET(tb
, hash
);
918 /* Calculate the index of 'entry' */
919 curelem
= entry
- &tb
->data
[0];
924 * Backward shift following elements till either an empty element or an
925 * element at its optimal position is encountered.
927 * While that sounds expensive, the average chain length is short, and
928 * deletions would otherwise require tombstones.
932 SH_ELEMENT_TYPE
*curentry
;
936 curelem
= SH_NEXT(tb
, curelem
, startelem
);
937 curentry
= &tb
->data
[curelem
];
939 if (curentry
->status
!= SH_STATUS_IN_USE
)
941 lastentry
->status
= SH_STATUS_EMPTY
;
945 curhash
= SH_ENTRY_HASH(tb
, curentry
);
946 curoptimal
= SH_INITIAL_BUCKET(tb
, curhash
);
948 /* current is at optimal position, done */
949 if (curoptimal
== curelem
)
951 lastentry
->status
= SH_STATUS_EMPTY
;
956 memcpy(lastentry
, curentry
, sizeof(SH_ELEMENT_TYPE
));
958 lastentry
= curentry
;
963 * Initialize iterator.
966 SH_START_ITERATE(SH_TYPE
* tb
, SH_ITERATOR
* iter
)
969 uint64 startelem
= PG_UINT64_MAX
;
972 * Search for the first empty element. As deletions during iterations are
973 * supported, we want to start/end at an element that cannot be affected
974 * by elements being shifted.
976 for (i
= 0; i
< tb
->size
; i
++)
978 SH_ELEMENT_TYPE
*entry
= &tb
->data
[i
];
980 if (entry
->status
!= SH_STATUS_IN_USE
)
987 Assert(startelem
< SH_MAX_SIZE
);
990 * Iterate backwards, that allows the current element to be deleted, even
991 * if there are backward shifts
993 iter
->cur
= startelem
;
994 iter
->end
= iter
->cur
;
999 * Initialize iterator to a specific bucket. That's really only useful for
1000 * cases where callers are partially iterating over the hashspace, and that
1001 * iteration deletes and inserts elements based on visited entries. Doing that
1002 * repeatedly could lead to an unbalanced keyspace when always starting at the
1006 SH_START_ITERATE_AT(SH_TYPE
* tb
, SH_ITERATOR
* iter
, uint32 at
)
1009 * Iterate backwards, that allows the current element to be deleted, even
1010 * if there are backward shifts.
1012 iter
->cur
= at
& tb
->sizemask
; /* ensure at is within a valid range */
1013 iter
->end
= iter
->cur
;
1018 * Iterate over all entries in the hash-table. Return the next occupied entry,
1021 * During iteration the current entry in the hash table may be deleted,
1022 * without leading to elements being skipped or returned twice. Additionally
1023 * the rest of the table may be modified (i.e. there can be insertions or
1024 * deletions), but if so, there's neither a guarantee that all nodes are
1025 * visited at least once, nor a guarantee that a node is visited at most once.
1027 SH_SCOPE SH_ELEMENT_TYPE
*
1028 SH_ITERATE(SH_TYPE
* tb
, SH_ITERATOR
* iter
)
1032 SH_ELEMENT_TYPE
*elem
;
1034 elem
= &tb
->data
[iter
->cur
];
1036 /* next element in backward direction */
1037 iter
->cur
= (iter
->cur
- 1) & tb
->sizemask
;
1039 if ((iter
->cur
& tb
->sizemask
) == (iter
->end
& tb
->sizemask
))
1041 if (elem
->status
== SH_STATUS_IN_USE
)
1051 * Report some statistics about the state of the hashtable. For
1052 * debugging/profiling purposes only.
1055 SH_STAT(SH_TYPE
* tb
)
1057 uint32 max_chain_length
= 0;
1058 uint32 total_chain_length
= 0;
1059 double avg_chain_length
;
1063 uint32
*collisions
= palloc0(tb
->size
* sizeof(uint32
));
1064 uint32 total_collisions
= 0;
1065 uint32 max_collisions
= 0;
1066 double avg_collisions
;
1068 for (i
= 0; i
< tb
->size
; i
++)
1073 SH_ELEMENT_TYPE
*elem
;
1075 elem
= &tb
->data
[i
];
1077 if (elem
->status
!= SH_STATUS_IN_USE
)
1080 hash
= SH_ENTRY_HASH(tb
, elem
);
1081 optimal
= SH_INITIAL_BUCKET(tb
, hash
);
1082 dist
= SH_DISTANCE_FROM_OPTIMAL(tb
, optimal
, i
);
1084 if (dist
> max_chain_length
)
1085 max_chain_length
= dist
;
1086 total_chain_length
+= dist
;
1088 collisions
[optimal
]++;
1091 for (i
= 0; i
< tb
->size
; i
++)
1093 uint32 curcoll
= collisions
[i
];
1098 /* single contained element is not a collision */
1100 total_collisions
+= curcoll
;
1101 if (curcoll
> max_collisions
)
1102 max_collisions
= curcoll
;
1105 if (tb
->members
> 0)
1107 fillfactor
= tb
->members
/ ((double) tb
->size
);
1108 avg_chain_length
= ((double) total_chain_length
) / tb
->members
;
1109 avg_collisions
= ((double) total_collisions
) / tb
->members
;
1114 avg_chain_length
= 0;
1118 sh_log("size: " UINT64_FORMAT
", members: %u, filled: %f, total chain: %u, max chain: %u, avg chain: %f, total_collisions: %u, max_collisions: %u, avg_collisions: %f",
1119 tb
->size
, tb
->members
, fillfactor
, total_chain_length
, max_chain_length
, avg_chain_length
,
1120 total_collisions
, max_collisions
, avg_collisions
);
1123 #endif /* SH_DEFINE */
1126 /* undefine external parameters, so next hash table can be defined */
1130 #undef SH_ELEMENT_TYPE
1136 #undef SH_STORE_HASH
1137 #undef SH_USE_NONDEFAULT_ALLOCATOR
1140 /* undefine locally declared macros */
1141 #undef SH_MAKE_PREFIX
1143 #undef SH_MAKE_NAME_
1144 #undef SH_FILLFACTOR
1145 #undef SH_MAX_FILLFACTOR
1146 #undef SH_GROW_MAX_DIB
1147 #undef SH_GROW_MAX_MOVE
1148 #undef SH_GROW_MIN_FILLFACTOR
1154 #undef SH_STATUS_EMPTY
1155 #undef SH_STATUS_IN_USE
1158 /* external function names */
1163 #undef SH_INSERT_HASH
1164 #undef SH_DELETE_ITEM
1167 #undef SH_LOOKUP_HASH
1169 #undef SH_START_ITERATE
1170 #undef SH_START_ITERATE_AT
1176 /* internal function names */
1177 #undef SH_COMPUTE_PARAMETERS
1178 #undef SH_COMPARE_KEYS
1179 #undef SH_INITIAL_BUCKET
1182 #undef SH_DISTANCE_FROM_OPTIMAL
1183 #undef SH_ENTRY_HASH
1184 #undef SH_INSERT_HASH_INTERNAL
1185 #undef SH_LOOKUP_HASH_INTERNAL