PostgreSQL Source Code  git master
simplehash.h
Go to the documentation of this file.
1 /*
2  * simplehash.h
3  *
4  * When included this file generates a "templated" (by way of macros)
5  * open-addressing hash table implementation specialized to user-defined
6  * types.
7  *
8  * It's probably not worthwhile to generate such a specialized implementation
9  * for hash tables that aren't performance or space sensitive.
10  *
11  * Compared to dynahash, simplehash has the following benefits:
12  *
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
16  * entries.
17  * - Open addressing has better CPU cache behavior than dynahash's chained
18  * hashtables.
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
23  * memory context)
24  * - Does not require the overhead of a separate memory context.
25  *
26  * Usage notes:
27  *
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
31  * afterwards.
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
39  * generated
40  * - SH_DEFINE - if defined function definitions are generated
41  * - SH_SCOPE - in which scope (e.g. extern, static inline) do function
42  * declarations reside
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
53  *
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.
56  *
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.
63  *
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.
67  *
68  * For examples of usage look at tidbitmap.c (file local definition) and
69  * execnodes.h/execGrouping.c (exposed declaration, file local
70  * implementation).
71  *
72  * Hash table design:
73  *
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.
89  *
90  * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
91  * Portions Copyright (c) 1994, Regents of the University of California
92  *
93  * src/include/lib/simplehash.h
94  */
95 
96 #include "port/pg_bitutils.h"
97 
98 /* helpers */
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)
102 
103 /* name macros for: */
104 
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)
111 
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)
129 
130 /* internal helper functions (no externally visible prototypes) */
131 #define SH_COMPUTE_SIZE SH_MAKE_NAME(compute_size)
132 #define SH_UPDATE_PARAMETERS SH_MAKE_NAME(update_parameters)
133 #define SH_NEXT SH_MAKE_NAME(next)
134 #define SH_PREV SH_MAKE_NAME(prev)
135 #define SH_DISTANCE_FROM_OPTIMAL SH_MAKE_NAME(distance)
136 #define SH_INITIAL_BUCKET SH_MAKE_NAME(initial_bucket)
137 #define SH_ENTRY_HASH SH_MAKE_NAME(entry_hash)
138 #define SH_INSERT_HASH_INTERNAL SH_MAKE_NAME(insert_hash_internal)
139 #define SH_LOOKUP_HASH_INTERNAL SH_MAKE_NAME(lookup_hash_internal)
140 
141 /* generate forward declarations necessary to use the hash table */
142 #ifdef SH_DECLARE
143 
144 /* type definitions */
145 typedef struct SH_TYPE
146 {
147  /*
148  * Size of data / bucket array, 64 bits to handle UINT32_MAX sized hash
149  * tables. Note that the maximum number of elements is lower
150  * (SH_MAX_FILLFACTOR)
151  */
152  uint64 size;
153 
154  /* how many elements have valid contents */
156 
157  /* mask for bucket and size calculations, based on size */
159 
160  /* boundary after which to grow hashtable */
162 
163  /* hash buckets */
165 
166 #ifndef SH_RAW_ALLOCATOR
167  /* memory context to use for allocations */
169 #endif
170 
171  /* user defined data, useful for callbacks */
174 
175 typedef enum SH_STATUS
176 {
178  SH_STATUS_IN_USE = 0x01
180 
181 typedef struct SH_ITERATOR
182 {
183  uint32 cur; /* current element */
185  bool done; /* iterator exhausted? */
187 
188 /* externally visible function prototypes */
189 #ifdef SH_RAW_ALLOCATOR
190 /* <prefix>_hash <prefix>_create(uint32 nelements, void *private_data) */
191 SH_SCOPE SH_TYPE *SH_CREATE(uint32 nelements, void *private_data);
192 #else
193 /*
194  * <prefix>_hash <prefix>_create(MemoryContext ctx, uint32 nelements,
195  * void *private_data)
196  */
198  void *private_data);
199 #endif
200 
201 /* void <prefix>_destroy(<prefix>_hash *tb) */
203 
204 /* void <prefix>_reset(<prefix>_hash *tb) */
206 
207 /* void <prefix>_grow(<prefix>_hash *tb, uint64 newsize) */
208 SH_SCOPE void SH_GROW(SH_TYPE * tb, uint64 newsize);
209 
210 /* <element> *<prefix>_insert(<prefix>_hash *tb, <key> key, bool *found) */
212 
213 /*
214  * <element> *<prefix>_insert_hash(<prefix>_hash *tb, <key> key, uint32 hash,
215  * bool *found)
216  */
218  uint32 hash, bool *found);
219 
220 /* <element> *<prefix>_lookup(<prefix>_hash *tb, <key> key) */
222 
223 /* <element> *<prefix>_lookup_hash(<prefix>_hash *tb, <key> key, uint32 hash) */
225  uint32 hash);
226 
227 /* void <prefix>_delete_item(<prefix>_hash *tb, <element> *entry) */
229 
230 /* bool <prefix>_delete(<prefix>_hash *tb, <key> key) */
232 
233 /* void <prefix>_start_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
235 
236 /*
237  * void <prefix>_start_iterate_at(<prefix>_hash *tb, <prefix>_iterator *iter,
238  * uint32 at)
239  */
241 
242 /* <element> *<prefix>_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
244 
245 /* void <prefix>_stat(<prefix>_hash *tb */
247 
248 #endif /* SH_DECLARE */
249 
250 
251 /* generate implementation of the hash table */
252 #ifdef SH_DEFINE
253 
254 #ifndef SH_RAW_ALLOCATOR
255 #include "utils/memutils.h"
256 #endif
257 
258 /* max data array size,we allow up to PG_UINT32_MAX buckets, including 0 */
259 #define SH_MAX_SIZE (((uint64) PG_UINT32_MAX) + 1)
260 
261 /* normal fillfactor, unless already close to maximum */
262 #ifndef SH_FILLFACTOR
263 #define SH_FILLFACTOR (0.9)
264 #endif
265 /* increase fillfactor if we otherwise would error out */
266 #define SH_MAX_FILLFACTOR (0.98)
267 /* grow if actual and optimal location bigger than */
268 #ifndef SH_GROW_MAX_DIB
269 #define SH_GROW_MAX_DIB 25
270 #endif
271 /* grow if more than elements to move when inserting */
272 #ifndef SH_GROW_MAX_MOVE
273 #define SH_GROW_MAX_MOVE 150
274 #endif
275 #ifndef SH_GROW_MIN_FILLFACTOR
276 /* but do not grow due to SH_GROW_MAX_* if below */
277 #define SH_GROW_MIN_FILLFACTOR 0.1
278 #endif
279 
280 #ifdef SH_STORE_HASH
281 #define SH_COMPARE_KEYS(tb, ahash, akey, b) (ahash == SH_GET_HASH(tb, b) && SH_EQUAL(tb, b->SH_KEY, akey))
282 #else
283 #define SH_COMPARE_KEYS(tb, ahash, akey, b) (SH_EQUAL(tb, b->SH_KEY, akey))
284 #endif
285 
286 /*
287  * Wrap the following definitions in include guards, to avoid multiple
288  * definition errors if this header is included more than once. The rest of
289  * the file deliberately has no include guards, because it can be included
290  * with different parameters to define functions and types with non-colliding
291  * names.
292  */
293 #ifndef SIMPLEHASH_H
294 #define SIMPLEHASH_H
295 
296 #ifdef FRONTEND
297 #define sh_error(...) pg_fatal(__VA_ARGS__)
298 #define sh_log(...) pg_log_info(__VA_ARGS__)
299 #else
300 #define sh_error(...) elog(ERROR, __VA_ARGS__)
301 #define sh_log(...) elog(LOG, __VA_ARGS__)
302 #endif
303 
304 #endif
305 
306 /*
307  * Compute allocation size for hashtable. Result can be passed to
308  * SH_UPDATE_PARAMETERS.
309  */
310 static inline uint64
311 SH_COMPUTE_SIZE(uint64 newsize)
312 {
313  uint64 size;
314 
315  /* supporting zero sized hashes would complicate matters */
316  size = Max(newsize, 2);
317 
318  /* round up size to the next power of 2, that's how bucketing works */
320  Assert(size <= SH_MAX_SIZE);
321 
322  /*
323  * Verify that allocation of ->data is possible on this platform, without
324  * overflowing Size.
325  */
326  if (unlikely((((uint64) sizeof(SH_ELEMENT_TYPE)) * size) >= SIZE_MAX / 2))
327  sh_error("hash table too large");
328 
329  return size;
330 }
331 
332 /*
333  * Update sizing parameters for hashtable. Called when creating and growing
334  * the hashtable.
335  */
336 static inline void
337 SH_UPDATE_PARAMETERS(SH_TYPE * tb, uint64 newsize)
338 {
339  uint64 size = SH_COMPUTE_SIZE(newsize);
340 
341  /* now set size */
342  tb->size = size;
343  tb->sizemask = (uint32) (size - 1);
344 
345  /*
346  * Compute the next threshold at which we need to grow the hash table
347  * again.
348  */
349  if (tb->size == SH_MAX_SIZE)
350  tb->grow_threshold = ((double) tb->size) * SH_MAX_FILLFACTOR;
351  else
352  tb->grow_threshold = ((double) tb->size) * SH_FILLFACTOR;
353 }
354 
355 /* return the optimal bucket for the hash */
356 static inline uint32
358 {
359  return hash & tb->sizemask;
360 }
361 
362 /* return next bucket after the current, handling wraparound */
363 static inline uint32
364 SH_NEXT(SH_TYPE * tb, uint32 curelem, uint32 startelem)
365 {
366  curelem = (curelem + 1) & tb->sizemask;
367 
368  Assert(curelem != startelem);
369 
370  return curelem;
371 }
372 
373 /* return bucket before the current, handling wraparound */
374 static inline uint32
375 SH_PREV(SH_TYPE * tb, uint32 curelem, uint32 startelem)
376 {
377  curelem = (curelem - 1) & tb->sizemask;
378 
379  Assert(curelem != startelem);
380 
381  return curelem;
382 }
383 
384 /* return distance between bucket and its optimal position */
385 static inline uint32
386 SH_DISTANCE_FROM_OPTIMAL(SH_TYPE * tb, uint32 optimal, uint32 bucket)
387 {
388  if (optimal <= bucket)
389  return bucket - optimal;
390  else
391  return (tb->size + bucket) - optimal;
392 }
393 
394 static inline uint32
396 {
397 #ifdef SH_STORE_HASH
398  return SH_GET_HASH(tb, entry);
399 #else
400  return SH_HASH_KEY(tb, entry->SH_KEY);
401 #endif
402 }
403 
404 /* default memory allocator function */
405 static inline void *SH_ALLOCATE(SH_TYPE * type, Size size);
406 static inline void SH_FREE(SH_TYPE * type, void *pointer);
407 
408 #ifndef SH_USE_NONDEFAULT_ALLOCATOR
409 
410 /* default memory allocator function */
411 static inline void *
413 {
414 #ifdef SH_RAW_ALLOCATOR
415  return SH_RAW_ALLOCATOR(size);
416 #else
417  return MemoryContextAllocExtended(type->ctx, size,
419 #endif
420 }
421 
422 /* default memory free function */
423 static inline void
424 SH_FREE(SH_TYPE * type, void *pointer)
425 {
426  pfree(pointer);
427 }
428 
429 #endif
430 
431 /*
432  * Create a hash table with enough space for `nelements` distinct members.
433  * Memory for the hash table is allocated from the passed-in context. If
434  * desired, the array of elements can be allocated using a passed-in allocator;
435  * this could be useful in order to place the array of elements in a shared
436  * memory, or in a context that will outlive the rest of the hash table.
437  * Memory other than for the array of elements will still be allocated from
438  * the passed-in context.
439  */
440 #ifdef SH_RAW_ALLOCATOR
442 SH_CREATE(uint32 nelements, void *private_data)
443 #else
445 SH_CREATE(MemoryContext ctx, uint32 nelements, void *private_data)
446 #endif
447 {
448  SH_TYPE *tb;
449  uint64 size;
450 
451 #ifdef SH_RAW_ALLOCATOR
452  tb = (SH_TYPE *) SH_RAW_ALLOCATOR(sizeof(SH_TYPE));
453 #else
454  tb = (SH_TYPE *) MemoryContextAllocZero(ctx, sizeof(SH_TYPE));
455  tb->ctx = ctx;
456 #endif
457  tb->private_data = private_data;
458 
459  /* increase nelements by fillfactor, want to store nelements elements */
460  size = Min((double) SH_MAX_SIZE, ((double) nelements) / SH_FILLFACTOR);
461 
463 
464  tb->data = (SH_ELEMENT_TYPE *) SH_ALLOCATE(tb, sizeof(SH_ELEMENT_TYPE) * size);
465 
467  return tb;
468 }
469 
470 /* destroy a previously created hash table */
471 SH_SCOPE void
472 SH_DESTROY(SH_TYPE * tb)
473 {
474  SH_FREE(tb, tb->data);
475  pfree(tb);
476 }
477 
478 /* reset the contents of a previously created hash table */
479 SH_SCOPE void
480 SH_RESET(SH_TYPE * tb)
481 {
482  memset(tb->data, 0, sizeof(SH_ELEMENT_TYPE) * tb->size);
483  tb->members = 0;
484 }
485 
486 /*
487  * Grow a hash table to at least `newsize` buckets.
488  *
489  * Usually this will automatically be called by insertions/deletions, when
490  * necessary. But resizing to the exact input size can be advantageous
491  * performance-wise, when known at some point.
492  */
493 SH_SCOPE void
494 SH_GROW(SH_TYPE * tb, uint64 newsize)
495 {
496  uint64 oldsize = tb->size;
497  SH_ELEMENT_TYPE *olddata = tb->data;
498  SH_ELEMENT_TYPE *newdata;
499  uint32 i;
500  uint32 startelem = 0;
501  uint32 copyelem;
502 
503  Assert(oldsize == pg_nextpower2_64(oldsize));
504  Assert(oldsize != SH_MAX_SIZE);
505  Assert(oldsize < newsize);
506 
507  newsize = SH_COMPUTE_SIZE(newsize);
508 
509  tb->data = (SH_ELEMENT_TYPE *) SH_ALLOCATE(tb, sizeof(SH_ELEMENT_TYPE) * newsize);
510 
511  /*
512  * Update parameters for new table after allocation succeeds to avoid
513  * inconsistent state on OOM.
514  */
515  SH_UPDATE_PARAMETERS(tb, newsize);
516 
517  newdata = tb->data;
518 
519  /*
520  * Copy entries from the old data to newdata. We theoretically could use
521  * SH_INSERT here, to avoid code duplication, but that's more general than
522  * we need. We neither want tb->members increased, nor do we need to do
523  * deal with deleted elements, nor do we need to compare keys. So a
524  * special-cased implementation is lot faster. As resizing can be time
525  * consuming and frequent, that's worthwhile to optimize.
526  *
527  * To be able to simply move entries over, we have to start not at the
528  * first bucket (i.e olddata[0]), but find the first bucket that's either
529  * empty, or is occupied by an entry at its optimal position. Such a
530  * bucket has to exist in any table with a load factor under 1, as not all
531  * buckets are occupied, i.e. there always has to be an empty bucket. By
532  * starting at such a bucket we can move the entries to the larger table,
533  * without having to deal with conflicts.
534  */
535 
536  /* search for the first element in the hash that's not wrapped around */
537  for (i = 0; i < oldsize; i++)
538  {
539  SH_ELEMENT_TYPE *oldentry = &olddata[i];
540  uint32 hash;
541  uint32 optimal;
542 
543  if (oldentry->status != SH_STATUS_IN_USE)
544  {
545  startelem = i;
546  break;
547  }
548 
549  hash = SH_ENTRY_HASH(tb, oldentry);
550  optimal = SH_INITIAL_BUCKET(tb, hash);
551 
552  if (optimal == i)
553  {
554  startelem = i;
555  break;
556  }
557  }
558 
559  /* and copy all elements in the old table */
560  copyelem = startelem;
561  for (i = 0; i < oldsize; i++)
562  {
563  SH_ELEMENT_TYPE *oldentry = &olddata[copyelem];
564 
565  if (oldentry->status == SH_STATUS_IN_USE)
566  {
567  uint32 hash;
568  uint32 startelem2;
569  uint32 curelem;
570  SH_ELEMENT_TYPE *newentry;
571 
572  hash = SH_ENTRY_HASH(tb, oldentry);
573  startelem2 = SH_INITIAL_BUCKET(tb, hash);
574  curelem = startelem2;
575 
576  /* find empty element to put data into */
577  while (true)
578  {
579  newentry = &newdata[curelem];
580 
581  if (newentry->status == SH_STATUS_EMPTY)
582  {
583  break;
584  }
585 
586  curelem = SH_NEXT(tb, curelem, startelem2);
587  }
588 
589  /* copy entry to new slot */
590  memcpy(newentry, oldentry, sizeof(SH_ELEMENT_TYPE));
591  }
592 
593  /* can't use SH_NEXT here, would use new size */
594  copyelem++;
595  if (copyelem >= oldsize)
596  {
597  copyelem = 0;
598  }
599  }
600 
601  SH_FREE(tb, olddata);
602 }
603 
604 /*
605  * This is a separate static inline function, so it can be reliably be inlined
606  * into its wrapper functions even if SH_SCOPE is extern.
607  */
608 static inline SH_ELEMENT_TYPE *
610 {
611  uint32 startelem;
612  uint32 curelem;
614  uint32 insertdist;
615 
616 restart:
617  insertdist = 0;
618 
619  /*
620  * We do the grow check even if the key is actually present, to avoid
621  * doing the check inside the loop. This also lets us avoid having to
622  * re-find our position in the hashtable after resizing.
623  *
624  * Note that this also reached when resizing the table due to
625  * SH_GROW_MAX_DIB / SH_GROW_MAX_MOVE.
626  */
627  if (unlikely(tb->members >= tb->grow_threshold))
628  {
629  if (unlikely(tb->size == SH_MAX_SIZE))
630  sh_error("hash table size exceeded");
631 
632  /*
633  * When optimizing, it can be very useful to print these out.
634  */
635  /* SH_STAT(tb); */
636  SH_GROW(tb, tb->size * 2);
637  /* SH_STAT(tb); */
638  }
639 
640  /* perform insert, start bucket search at optimal location */
641  data = tb->data;
642  startelem = SH_INITIAL_BUCKET(tb, hash);
643  curelem = startelem;
644  while (true)
645  {
646  uint32 curdist;
647  uint32 curhash;
648  uint32 curoptimal;
649  SH_ELEMENT_TYPE *entry = &data[curelem];
650 
651  /* any empty bucket can directly be used */
652  if (entry->status == SH_STATUS_EMPTY)
653  {
654  tb->members++;
655  entry->SH_KEY = key;
656 #ifdef SH_STORE_HASH
657  SH_GET_HASH(tb, entry) = hash;
658 #endif
659  entry->status = SH_STATUS_IN_USE;
660  *found = false;
661  return entry;
662  }
663 
664  /*
665  * If the bucket is not empty, we either found a match (in which case
666  * we're done), or we have to decide whether to skip over or move the
667  * colliding entry. When the colliding element's distance to its
668  * optimal position is smaller than the to-be-inserted entry's, we
669  * shift the colliding entry (and its followers) forward by one.
670  */
671 
672  if (SH_COMPARE_KEYS(tb, hash, key, entry))
673  {
674  Assert(entry->status == SH_STATUS_IN_USE);
675  *found = true;
676  return entry;
677  }
678 
679  curhash = SH_ENTRY_HASH(tb, entry);
680  curoptimal = SH_INITIAL_BUCKET(tb, curhash);
681  curdist = SH_DISTANCE_FROM_OPTIMAL(tb, curoptimal, curelem);
682 
683  if (insertdist > curdist)
684  {
685  SH_ELEMENT_TYPE *lastentry = entry;
686  uint32 emptyelem = curelem;
687  uint32 moveelem;
688  int32 emptydist = 0;
689 
690  /* find next empty bucket */
691  while (true)
692  {
693  SH_ELEMENT_TYPE *emptyentry;
694 
695  emptyelem = SH_NEXT(tb, emptyelem, startelem);
696  emptyentry = &data[emptyelem];
697 
698  if (emptyentry->status == SH_STATUS_EMPTY)
699  {
700  lastentry = emptyentry;
701  break;
702  }
703 
704  /*
705  * To avoid negative consequences from overly imbalanced
706  * hashtables, grow the hashtable if collisions would require
707  * us to move a lot of entries. The most likely cause of such
708  * imbalance is filling a (currently) small table, from a
709  * currently big one, in hash-table order. Don't grow if the
710  * hashtable would be too empty, to prevent quick space
711  * explosion for some weird edge cases.
712  */
713  if (unlikely(++emptydist > SH_GROW_MAX_MOVE) &&
714  ((double) tb->members / tb->size) >= SH_GROW_MIN_FILLFACTOR)
715  {
716  tb->grow_threshold = 0;
717  goto restart;
718  }
719  }
720 
721  /* shift forward, starting at last occupied element */
722 
723  /*
724  * TODO: This could be optimized to be one memcpy in many cases,
725  * excepting wrapping around at the end of ->data. Hasn't shown up
726  * in profiles so far though.
727  */
728  moveelem = emptyelem;
729  while (moveelem != curelem)
730  {
731  SH_ELEMENT_TYPE *moveentry;
732 
733  moveelem = SH_PREV(tb, moveelem, startelem);
734  moveentry = &data[moveelem];
735 
736  memcpy(lastentry, moveentry, sizeof(SH_ELEMENT_TYPE));
737  lastentry = moveentry;
738  }
739 
740  /* and fill the now empty spot */
741  tb->members++;
742 
743  entry->SH_KEY = key;
744 #ifdef SH_STORE_HASH
745  SH_GET_HASH(tb, entry) = hash;
746 #endif
747  entry->status = SH_STATUS_IN_USE;
748  *found = false;
749  return entry;
750  }
751 
752  curelem = SH_NEXT(tb, curelem, startelem);
753  insertdist++;
754 
755  /*
756  * To avoid negative consequences from overly imbalanced hashtables,
757  * grow the hashtable if collisions lead to large runs. The most
758  * likely cause of such imbalance is filling a (currently) small
759  * table, from a currently big one, in hash-table order. Don't grow
760  * if the hashtable would be too empty, to prevent quick space
761  * explosion for some weird edge cases.
762  */
763  if (unlikely(insertdist > SH_GROW_MAX_DIB) &&
764  ((double) tb->members / tb->size) >= SH_GROW_MIN_FILLFACTOR)
765  {
766  tb->grow_threshold = 0;
767  goto restart;
768  }
769  }
770 }
771 
772 /*
773  * Insert the key into the hash-table, set *found to true if the key already
774  * exists, false otherwise. Returns the hash-table entry in either case.
775  */
777 SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found)
778 {
779  uint32 hash = SH_HASH_KEY(tb, key);
780 
781  return SH_INSERT_HASH_INTERNAL(tb, key, hash, found);
782 }
783 
784 /*
785  * Insert the key into the hash-table using an already-calculated hash. Set
786  * *found to true if the key already exists, false otherwise. Returns the
787  * hash-table entry in either case.
788  */
790 SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool *found)
791 {
792  return SH_INSERT_HASH_INTERNAL(tb, key, hash, found);
793 }
794 
795 /*
796  * This is a separate static inline function, so it can be reliably be inlined
797  * into its wrapper functions even if SH_SCOPE is extern.
798  */
799 static inline SH_ELEMENT_TYPE *
801 {
802  const uint32 startelem = SH_INITIAL_BUCKET(tb, hash);
803  uint32 curelem = startelem;
804 
805  while (true)
806  {
807  SH_ELEMENT_TYPE *entry = &tb->data[curelem];
808 
809  if (entry->status == SH_STATUS_EMPTY)
810  {
811  return NULL;
812  }
813 
814  Assert(entry->status == SH_STATUS_IN_USE);
815 
816  if (SH_COMPARE_KEYS(tb, hash, key, entry))
817  return entry;
818 
819  /*
820  * TODO: we could stop search based on distance. If the current
821  * buckets's distance-from-optimal is smaller than what we've skipped
822  * already, the entry doesn't exist. Probably only do so if
823  * SH_STORE_HASH is defined, to avoid re-computing hashes?
824  */
825 
826  curelem = SH_NEXT(tb, curelem, startelem);
827  }
828 }
829 
830 /*
831  * Lookup entry in hash table. Returns NULL if key not present.
832  */
835 {
836  uint32 hash = SH_HASH_KEY(tb, key);
837 
838  return SH_LOOKUP_HASH_INTERNAL(tb, key, hash);
839 }
840 
841 /*
842  * Lookup entry in hash table using an already-calculated hash.
843  *
844  * Returns NULL if key not present.
845  */
848 {
849  return SH_LOOKUP_HASH_INTERNAL(tb, key, hash);
850 }
851 
852 /*
853  * Delete entry from hash table by key. Returns whether to-be-deleted key was
854  * present.
855  */
856 SH_SCOPE bool
858 {
859  uint32 hash = SH_HASH_KEY(tb, key);
860  uint32 startelem = SH_INITIAL_BUCKET(tb, hash);
861  uint32 curelem = startelem;
862 
863  while (true)
864  {
865  SH_ELEMENT_TYPE *entry = &tb->data[curelem];
866 
867  if (entry->status == SH_STATUS_EMPTY)
868  return false;
869 
870  if (entry->status == SH_STATUS_IN_USE &&
871  SH_COMPARE_KEYS(tb, hash, key, entry))
872  {
873  SH_ELEMENT_TYPE *lastentry = entry;
874 
875  tb->members--;
876 
877  /*
878  * Backward shift following elements till either an empty element
879  * or an element at its optimal position is encountered.
880  *
881  * While that sounds expensive, the average chain length is short,
882  * and deletions would otherwise require tombstones.
883  */
884  while (true)
885  {
886  SH_ELEMENT_TYPE *curentry;
887  uint32 curhash;
888  uint32 curoptimal;
889 
890  curelem = SH_NEXT(tb, curelem, startelem);
891  curentry = &tb->data[curelem];
892 
893  if (curentry->status != SH_STATUS_IN_USE)
894  {
895  lastentry->status = SH_STATUS_EMPTY;
896  break;
897  }
898 
899  curhash = SH_ENTRY_HASH(tb, curentry);
900  curoptimal = SH_INITIAL_BUCKET(tb, curhash);
901 
902  /* current is at optimal position, done */
903  if (curoptimal == curelem)
904  {
905  lastentry->status = SH_STATUS_EMPTY;
906  break;
907  }
908 
909  /* shift */
910  memcpy(lastentry, curentry, sizeof(SH_ELEMENT_TYPE));
911 
912  lastentry = curentry;
913  }
914 
915  return true;
916  }
917 
918  /* TODO: return false; if distance too big */
919 
920  curelem = SH_NEXT(tb, curelem, startelem);
921  }
922 }
923 
924 /*
925  * Delete entry from hash table by entry pointer
926  */
927 SH_SCOPE void
929 {
930  SH_ELEMENT_TYPE *lastentry = entry;
931  uint32 hash = SH_ENTRY_HASH(tb, entry);
932  uint32 startelem = SH_INITIAL_BUCKET(tb, hash);
933  uint32 curelem;
934 
935  /* Calculate the index of 'entry' */
936  curelem = entry - &tb->data[0];
937 
938  tb->members--;
939 
940  /*
941  * Backward shift following elements till either an empty element or an
942  * element at its optimal position is encountered.
943  *
944  * While that sounds expensive, the average chain length is short, and
945  * deletions would otherwise require tombstones.
946  */
947  while (true)
948  {
949  SH_ELEMENT_TYPE *curentry;
950  uint32 curhash;
951  uint32 curoptimal;
952 
953  curelem = SH_NEXT(tb, curelem, startelem);
954  curentry = &tb->data[curelem];
955 
956  if (curentry->status != SH_STATUS_IN_USE)
957  {
958  lastentry->status = SH_STATUS_EMPTY;
959  break;
960  }
961 
962  curhash = SH_ENTRY_HASH(tb, curentry);
963  curoptimal = SH_INITIAL_BUCKET(tb, curhash);
964 
965  /* current is at optimal position, done */
966  if (curoptimal == curelem)
967  {
968  lastentry->status = SH_STATUS_EMPTY;
969  break;
970  }
971 
972  /* shift */
973  memcpy(lastentry, curentry, sizeof(SH_ELEMENT_TYPE));
974 
975  lastentry = curentry;
976  }
977 }
978 
979 /*
980  * Initialize iterator.
981  */
982 SH_SCOPE void
984 {
985  uint64 startelem = PG_UINT64_MAX;
986 
987  /*
988  * Search for the first empty element. As deletions during iterations are
989  * supported, we want to start/end at an element that cannot be affected
990  * by elements being shifted.
991  */
992  for (uint32 i = 0; i < tb->size; i++)
993  {
994  SH_ELEMENT_TYPE *entry = &tb->data[i];
995 
996  if (entry->status != SH_STATUS_IN_USE)
997  {
998  startelem = i;
999  break;
1000  }
1001  }
1002 
1003  /* we should have found an empty element */
1004  Assert(startelem < SH_MAX_SIZE);
1005 
1006  /*
1007  * Iterate backwards, that allows the current element to be deleted, even
1008  * if there are backward shifts
1009  */
1010  iter->cur = startelem;
1011  iter->end = iter->cur;
1012  iter->done = false;
1013 }
1014 
1015 /*
1016  * Initialize iterator to a specific bucket. That's really only useful for
1017  * cases where callers are partially iterating over the hashspace, and that
1018  * iteration deletes and inserts elements based on visited entries. Doing that
1019  * repeatedly could lead to an unbalanced keyspace when always starting at the
1020  * same position.
1021  */
1022 SH_SCOPE void
1024 {
1025  /*
1026  * Iterate backwards, that allows the current element to be deleted, even
1027  * if there are backward shifts.
1028  */
1029  iter->cur = at & tb->sizemask; /* ensure at is within a valid range */
1030  iter->end = iter->cur;
1031  iter->done = false;
1032 }
1033 
1034 /*
1035  * Iterate over all entries in the hash-table. Return the next occupied entry,
1036  * or NULL if done.
1037  *
1038  * During iteration the current entry in the hash table may be deleted,
1039  * without leading to elements being skipped or returned twice. Additionally
1040  * the rest of the table may be modified (i.e. there can be insertions or
1041  * deletions), but if so, there's neither a guarantee that all nodes are
1042  * visited at least once, nor a guarantee that a node is visited at most once.
1043  */
1045 SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
1046 {
1047  while (!iter->done)
1048  {
1049  SH_ELEMENT_TYPE *elem;
1050 
1051  elem = &tb->data[iter->cur];
1052 
1053  /* next element in backward direction */
1054  iter->cur = (iter->cur - 1) & tb->sizemask;
1055 
1056  if ((iter->cur & tb->sizemask) == (iter->end & tb->sizemask))
1057  iter->done = true;
1058  if (elem->status == SH_STATUS_IN_USE)
1059  {
1060  return elem;
1061  }
1062  }
1063 
1064  return NULL;
1065 }
1066 
1067 /*
1068  * Report some statistics about the state of the hashtable. For
1069  * debugging/profiling purposes only.
1070  */
1071 SH_SCOPE void
1072 SH_STAT(SH_TYPE * tb)
1073 {
1074  uint32 max_chain_length = 0;
1075  uint32 total_chain_length = 0;
1076  double avg_chain_length;
1077  double fillfactor;
1078  uint32 i;
1079 
1080  uint32 *collisions = (uint32 *) palloc0(tb->size * sizeof(uint32));
1081  uint32 total_collisions = 0;
1082  uint32 max_collisions = 0;
1083  double avg_collisions;
1084 
1085  for (i = 0; i < tb->size; i++)
1086  {
1087  uint32 hash;
1088  uint32 optimal;
1089  uint32 dist;
1090  SH_ELEMENT_TYPE *elem;
1091 
1092  elem = &tb->data[i];
1093 
1094  if (elem->status != SH_STATUS_IN_USE)
1095  continue;
1096 
1097  hash = SH_ENTRY_HASH(tb, elem);
1098  optimal = SH_INITIAL_BUCKET(tb, hash);
1099  dist = SH_DISTANCE_FROM_OPTIMAL(tb, optimal, i);
1100 
1101  if (dist > max_chain_length)
1102  max_chain_length = dist;
1103  total_chain_length += dist;
1104 
1105  collisions[optimal]++;
1106  }
1107 
1108  for (i = 0; i < tb->size; i++)
1109  {
1110  uint32 curcoll = collisions[i];
1111 
1112  if (curcoll == 0)
1113  continue;
1114 
1115  /* single contained element is not a collision */
1116  curcoll--;
1117  total_collisions += curcoll;
1118  if (curcoll > max_collisions)
1119  max_collisions = curcoll;
1120  }
1121 
1122  if (tb->members > 0)
1123  {
1124  fillfactor = tb->members / ((double) tb->size);
1125  avg_chain_length = ((double) total_chain_length) / tb->members;
1126  avg_collisions = ((double) total_collisions) / tb->members;
1127  }
1128  else
1129  {
1130  fillfactor = 0;
1131  avg_chain_length = 0;
1132  avg_collisions = 0;
1133  }
1134 
1135  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",
1136  tb->size, tb->members, fillfactor, total_chain_length, max_chain_length, avg_chain_length,
1137  total_collisions, max_collisions, avg_collisions);
1138 }
1139 
1140 #endif /* SH_DEFINE */
1141 
1142 
1143 /* undefine external parameters, so next hash table can be defined */
1144 #undef SH_PREFIX
1145 #undef SH_KEY_TYPE
1146 #undef SH_KEY
1147 #undef SH_ELEMENT_TYPE
1148 #undef SH_HASH_KEY
1149 #undef SH_SCOPE
1150 #undef SH_DECLARE
1151 #undef SH_DEFINE
1152 #undef SH_GET_HASH
1153 #undef SH_STORE_HASH
1154 #undef SH_USE_NONDEFAULT_ALLOCATOR
1155 #undef SH_EQUAL
1156 
1157 /* undefine locally declared macros */
1158 #undef SH_MAKE_PREFIX
1159 #undef SH_MAKE_NAME
1160 #undef SH_MAKE_NAME_
1161 #undef SH_FILLFACTOR
1162 #undef SH_MAX_FILLFACTOR
1163 #undef SH_GROW_MAX_DIB
1164 #undef SH_GROW_MAX_MOVE
1165 #undef SH_GROW_MIN_FILLFACTOR
1166 #undef SH_MAX_SIZE
1167 
1168 /* types */
1169 #undef SH_TYPE
1170 #undef SH_STATUS
1171 #undef SH_STATUS_EMPTY
1172 #undef SH_STATUS_IN_USE
1173 #undef SH_ITERATOR
1174 
1175 /* external function names */
1176 #undef SH_CREATE
1177 #undef SH_DESTROY
1178 #undef SH_RESET
1179 #undef SH_INSERT
1180 #undef SH_INSERT_HASH
1181 #undef SH_DELETE_ITEM
1182 #undef SH_DELETE
1183 #undef SH_LOOKUP
1184 #undef SH_LOOKUP_HASH
1185 #undef SH_GROW
1186 #undef SH_START_ITERATE
1187 #undef SH_START_ITERATE_AT
1188 #undef SH_ITERATE
1189 #undef SH_ALLOCATE
1190 #undef SH_FREE
1191 #undef SH_STAT
1192 
1193 /* internal function names */
1194 #undef SH_COMPUTE_SIZE
1195 #undef SH_UPDATE_PARAMETERS
1196 #undef SH_COMPARE_KEYS
1197 #undef SH_INITIAL_BUCKET
1198 #undef SH_NEXT
1199 #undef SH_PREV
1200 #undef SH_DISTANCE_FROM_OPTIMAL
1201 #undef SH_ENTRY_HASH
1202 #undef SH_INSERT_HASH_INTERNAL
1203 #undef SH_LOOKUP_HASH_INTERNAL
#define SH_HASH_KEY(tb, key)
#define SH_ELEMENT_TYPE
#define SH_KEY_TYPE
#define SH_SCOPE
unsigned int uint32
Definition: c.h:493
#define Min(x, y)
Definition: c.h:991
signed int int32
Definition: c.h:481
#define Max(x, y)
Definition: c.h:985
#define UINT64_FORMAT
Definition: c.h:536
#define unlikely(x)
Definition: c.h:298
#define PG_UINT64_MAX
Definition: c.h:580
size_t Size
Definition: c.h:592
#define SH_GET_HASH(tb, a)
#define MCXT_ALLOC_ZERO
Definition: fe_memutils.h:18
#define MCXT_ALLOC_HUGE
Definition: fe_memutils.h:16
int i
Definition: isn.c:73
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
Assert(fmt[strlen(fmt) - 1] !='\n')
#define SH_RAW_ALLOCATOR
Definition: load_manifest.c:49
void pfree(void *pointer)
Definition: mcxt.c:1508
void * palloc0(Size size)
Definition: mcxt.c:1334
void * MemoryContextAllocZero(MemoryContext context, Size size)
Definition: mcxt.c:1202
void * MemoryContextAllocExtended(MemoryContext context, Size size, int flags)
Definition: mcxt.c:1225
static uint64 pg_nextpower2_64(uint64 num)
Definition: pg_bitutils.h:212
const void * data
int fillfactor
Definition: pgbench.c:187
static unsigned hash(unsigned *uv, int n)
Definition: rege_dfa.c:715
#define SH_GROW
Definition: simplehash.h:122
#define SH_COMPUTE_SIZE
Definition: simplehash.h:131
SH_STATUS
Definition: simplehash.h:176
#define SH_STAT
Definition: simplehash.h:128
#define SH_INITIAL_BUCKET
Definition: simplehash.h:136
#define SH_UPDATE_PARAMETERS
Definition: simplehash.h:132
#define SH_INSERT_HASH
Definition: simplehash.h:117
#define SH_PREV
Definition: simplehash.h:134
#define SH_STATUS
Definition: simplehash.h:107
#define SH_CREATE
Definition: simplehash.h:113
#define SH_LOOKUP_HASH
Definition: simplehash.h:121
#define SH_START_ITERATE
Definition: simplehash.h:123
#define SH_FREE
Definition: simplehash.h:127
#define SH_STATUS_IN_USE
Definition: simplehash.h:109
#define SH_DISTANCE_FROM_OPTIMAL
Definition: simplehash.h:135
#define SH_LOOKUP_HASH_INTERNAL
Definition: simplehash.h:139
#define SH_ITERATOR
Definition: simplehash.h:110
#define SH_NEXT
Definition: simplehash.h:133
#define SH_ITERATE
Definition: simplehash.h:125
#define SH_DELETE
Definition: simplehash.h:119
#define SH_INSERT
Definition: simplehash.h:116
#define SH_INSERT_HASH_INTERNAL
Definition: simplehash.h:138
#define SH_RESET
Definition: simplehash.h:115
#define SH_ENTRY_HASH
Definition: simplehash.h:137
#define SH_DELETE_ITEM
Definition: simplehash.h:118
#define SH_ALLOCATE
Definition: simplehash.h:126
#define SH_LOOKUP
Definition: simplehash.h:120
#define SH_TYPE
Definition: simplehash.h:106
#define SH_START_ITERATE_AT
Definition: simplehash.h:124
#define SH_STATUS_EMPTY
Definition: simplehash.h:108
#define SH_DESTROY
Definition: simplehash.h:114
static pg_noinline void Size size
Definition: slab.c:607
uint32 cur
Definition: simplehash.h:183
uint32 end
Definition: simplehash.h:184
MemoryContext ctx
Definition: simplehash.h:168
uint32 members
Definition: simplehash.h:155
SH_ELEMENT_TYPE * data
Definition: simplehash.h:164
uint32 grow_threshold
Definition: simplehash.h:161
uint32 sizemask
Definition: simplehash.h:158
void * private_data
Definition: simplehash.h:172
uint64 size
Definition: simplehash.h:152
const char * type