PostgreSQL Source Code  git master
simplehash.h
Go to the documentation of this file.
1 /*
2  * simplehash.h
3  *
4  * Hash table implementation which will be specialized to user-defined
5  * types, by including this file to generate the required code. It's
6  * probably not worthwhile to do so for hash tables that aren't performance
7  * or space sensitive.
8  *
9  * Usage notes:
10  *
11  * To generate a hash-table and associated functions for a use case several
12  * macros have to be #define'ed before this file is included. Including
13  * the file #undef's all those, so a new hash table can be generated
14  * afterwards.
15  * The relevant parameters are:
16  * - SH_PREFIX - prefix for all symbol names generated. A prefix of 'foo'
17  * will result in hash table type 'foo_hash' and functions like
18  * 'foo_insert'/'foo_lookup' and so forth.
19  * - SH_ELEMENT_TYPE - type of the contained elements
20  * - SH_KEY_TYPE - type of the hashtable's key
21  * - SH_DECLARE - if defined function prototypes and type declarations are
22  * generated
23  * - SH_DEFINE - if defined function definitions are generated
24  * - SH_SCOPE - in which scope (e.g. extern, static inline) do function
25  * declarations reside
26  * - SH_RAW_ALLOCATOR - if defined, memory contexts are not used; instead,
27  * use this to allocate bytes
28  * - SH_USE_NONDEFAULT_ALLOCATOR - if defined no element allocator functions
29  * are defined, so you can supply your own
30  * The following parameters are only relevant when SH_DEFINE is defined:
31  * - SH_KEY - name of the element in SH_ELEMENT_TYPE containing the hash key
32  * - SH_EQUAL(table, a, b) - compare two table keys
33  * - SH_HASH_KEY(table, key) - generate hash for the key
34  * - SH_STORE_HASH - if defined the hash is stored in the elements
35  * - SH_GET_HASH(tb, a) - return the field to store the hash in
36  *
37  * For examples of usage look at tidbitmap.c (file local definition) and
38  * execnodes.h/execGrouping.c (exposed declaration, file local
39  * implementation).
40  *
41  * Hash table design:
42  *
43  * The hash table design chosen is a variant of linear open-addressing. The
44  * reason for doing so is that linear addressing is CPU cache & pipeline
45  * friendly. The biggest disadvantage of simple linear addressing schemes
46  * are highly variable lookup times due to clustering, and deletions
47  * leaving a lot of tombstones around. To address these issues a variant
48  * of "robin hood" hashing is employed. Robin hood hashing optimizes
49  * chaining lengths by moving elements close to their optimal bucket
50  * ("rich" elements), out of the way if a to-be-inserted element is further
51  * away from its optimal position (i.e. it's "poor"). While that can make
52  * insertions slower, the average lookup performance is a lot better, and
53  * higher fill factors can be used in a still performant manner. To avoid
54  * tombstones - which normally solve the issue that a deleted node's
55  * presence is relevant to determine whether a lookup needs to continue
56  * looking or is done - buckets following a deleted element are shifted
57  * backwards, unless they're empty or already at their optimal position.
58  */
59 
60 /* helpers */
61 #define SH_MAKE_PREFIX(a) CppConcat(a,_)
62 #define SH_MAKE_NAME(name) SH_MAKE_NAME_(SH_MAKE_PREFIX(SH_PREFIX),name)
63 #define SH_MAKE_NAME_(a,b) CppConcat(a,b)
64 
65 /* name macros for: */
66 
67 /* type declarations */
68 #define SH_TYPE SH_MAKE_NAME(hash)
69 #define SH_STATUS SH_MAKE_NAME(status)
70 #define SH_STATUS_EMPTY SH_MAKE_NAME(SH_EMPTY)
71 #define SH_STATUS_IN_USE SH_MAKE_NAME(SH_IN_USE)
72 #define SH_ITERATOR SH_MAKE_NAME(iterator)
73 
74 /* function declarations */
75 #define SH_CREATE SH_MAKE_NAME(create)
76 #define SH_DESTROY SH_MAKE_NAME(destroy)
77 #define SH_RESET SH_MAKE_NAME(reset)
78 #define SH_INSERT SH_MAKE_NAME(insert)
79 #define SH_INSERT_HASH SH_MAKE_NAME(insert_hash)
80 #define SH_DELETE SH_MAKE_NAME(delete)
81 #define SH_LOOKUP SH_MAKE_NAME(lookup)
82 #define SH_LOOKUP_HASH SH_MAKE_NAME(lookup_hash)
83 #define SH_GROW SH_MAKE_NAME(grow)
84 #define SH_START_ITERATE SH_MAKE_NAME(start_iterate)
85 #define SH_START_ITERATE_AT SH_MAKE_NAME(start_iterate_at)
86 #define SH_ITERATE SH_MAKE_NAME(iterate)
87 #define SH_ALLOCATE SH_MAKE_NAME(allocate)
88 #define SH_FREE SH_MAKE_NAME(free)
89 #define SH_STAT SH_MAKE_NAME(stat)
90 
91 /* internal helper functions (no externally visible prototypes) */
92 #define SH_COMPUTE_PARAMETERS SH_MAKE_NAME(compute_parameters)
93 #define SH_NEXT SH_MAKE_NAME(next)
94 #define SH_PREV SH_MAKE_NAME(prev)
95 #define SH_DISTANCE_FROM_OPTIMAL SH_MAKE_NAME(distance)
96 #define SH_INITIAL_BUCKET SH_MAKE_NAME(initial_bucket)
97 #define SH_ENTRY_HASH SH_MAKE_NAME(entry_hash)
98 #define SH_INSERT_HASH_INTERNAL SH_MAKE_NAME(insert_hash_internal)
99 #define SH_LOOKUP_HASH_INTERNAL SH_MAKE_NAME(lookup_hash_internal)
100 
101 /* generate forward declarations necessary to use the hash table */
102 #ifdef SH_DECLARE
103 
104 /* type definitions */
105 typedef struct SH_TYPE
106 {
107  /*
108  * Size of data / bucket array, 64 bits to handle UINT32_MAX sized hash
109  * tables. Note that the maximum number of elements is lower
110  * (SH_MAX_FILLFACTOR)
111  */
112  uint64 size;
113 
114  /* how many elements have valid contents */
115  uint32 members;
116 
117  /* mask for bucket and size calculations, based on size */
118  uint32 sizemask;
119 
120  /* boundary after which to grow hashtable */
121  uint32 grow_threshold;
122 
123  /* hash buckets */
124  SH_ELEMENT_TYPE *data;
125 
126 #ifndef SH_RAW_ALLOCATOR
127  /* memory context to use for allocations */
128  MemoryContext ctx;
129 #endif
130 
131  /* user defined data, useful for callbacks */
132  void *private_data;
133 } SH_TYPE;
134 
135 typedef enum SH_STATUS
136 {
137  SH_STATUS_EMPTY = 0x00,
138  SH_STATUS_IN_USE = 0x01
139 } SH_STATUS;
140 
141 typedef struct SH_ITERATOR
142 {
143  uint32 cur; /* current element */
144  uint32 end;
145  bool done; /* iterator exhausted? */
146 } SH_ITERATOR;
147 
148 /* externally visible function prototypes */
149 #ifdef SH_RAW_ALLOCATOR
150 SH_SCOPE SH_TYPE *SH_CREATE(uint32 nelements, void *private_data);
151 #else
153  void *private_data);
154 #endif
155 SH_SCOPE void SH_DESTROY(SH_TYPE * tb);
156 SH_SCOPE void SH_RESET(SH_TYPE * tb);
157 SH_SCOPE void SH_GROW(SH_TYPE * tb, uint32 newsize);
160  uint32 hash, bool *found);
163  uint32 hash);
165 SH_SCOPE void SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter);
166 SH_SCOPE void SH_START_ITERATE_AT(SH_TYPE * tb, SH_ITERATOR * iter, uint32 at);
168 SH_SCOPE void SH_STAT(SH_TYPE * tb);
169 
170 #endif /* SH_DECLARE */
171 
172 
173 /* generate implementation of the hash table */
174 #ifdef SH_DEFINE
175 
176 #ifndef SH_RAW_ALLOCATOR
177 #include "utils/memutils.h"
178 #endif
179 
180 /* max data array size,we allow up to PG_UINT32_MAX buckets, including 0 */
181 #define SH_MAX_SIZE (((uint64) PG_UINT32_MAX) + 1)
182 
183 /* normal fillfactor, unless already close to maximum */
184 #ifndef SH_FILLFACTOR
185 #define SH_FILLFACTOR (0.9)
186 #endif
187 /* increase fillfactor if we otherwise would error out */
188 #define SH_MAX_FILLFACTOR (0.98)
189 /* grow if actual and optimal location bigger than */
190 #ifndef SH_GROW_MAX_DIB
191 #define SH_GROW_MAX_DIB 25
192 #endif
193 /* grow if more than elements to move when inserting */
194 #ifndef SH_GROW_MAX_MOVE
195 #define SH_GROW_MAX_MOVE 150
196 #endif
197 #ifndef SH_GROW_MIN_FILLFACTOR
198 /* but do not grow due to SH_GROW_MAX_* if below */
199 #define SH_GROW_MIN_FILLFACTOR 0.1
200 #endif
201 
202 #ifdef SH_STORE_HASH
203 #define SH_COMPARE_KEYS(tb, ahash, akey, b) (ahash == SH_GET_HASH(tb, b) && SH_EQUAL(tb, b->SH_KEY, akey))
204 #else
205 #define SH_COMPARE_KEYS(tb, ahash, akey, b) (SH_EQUAL(tb, b->SH_KEY, akey))
206 #endif
207 
208 /*
209  * Wrap the following definitions in include guards, to avoid multiple
210  * definition errors if this header is included more than once. The rest of
211  * the file deliberately has no include guards, because it can be included
212  * with different parameters to define functions and types with non-colliding
213  * names.
214  */
215 #ifndef SIMPLEHASH_H
216 #define SIMPLEHASH_H
217 
218 /* FIXME: can we move these to a central location? */
219 
220 /* calculate ceil(log base 2) of num */
221 static inline uint64
222 sh_log2(uint64 num)
223 {
224  int i;
225  uint64 limit;
226 
227  for (i = 0, limit = 1; limit < num; i++, limit <<= 1)
228  ;
229  return i;
230 }
231 
232 /* calculate first power of 2 >= num */
233 static inline uint64
234 sh_pow2(uint64 num)
235 {
236  return ((uint64) 1) << sh_log2(num);
237 }
238 
239 #ifdef FRONTEND
240 #define sh_error(...) pg_log_error(__VA_ARGS__)
241 #define sh_log(...) pg_log_info(__VA_ARGS__)
242 #else
243 #define sh_error(...) elog(ERROR, __VA_ARGS__)
244 #define sh_log(...) elog(LOG, __VA_ARGS__)
245 #endif
246 
247 #endif
248 
249 /*
250  * Compute sizing parameters for hashtable. Called when creating and growing
251  * the hashtable.
252  */
253 static inline void
254 SH_COMPUTE_PARAMETERS(SH_TYPE * tb, uint32 newsize)
255 {
256  uint64 size;
257 
258  /* supporting zero sized hashes would complicate matters */
259  size = Max(newsize, 2);
260 
261  /* round up size to the next power of 2, that's how bucketing works */
262  size = sh_pow2(size);
263  Assert(size <= SH_MAX_SIZE);
264 
265  /*
266  * Verify that allocation of ->data is possible on this platform, without
267  * overflowing Size.
268  */
269  if ((((uint64) sizeof(SH_ELEMENT_TYPE)) * size) >= SIZE_MAX / 2)
270  sh_error("hash table too large");
271 
272  /* now set size */
273  tb->size = size;
274 
275  if (tb->size == SH_MAX_SIZE)
276  tb->sizemask = 0;
277  else
278  tb->sizemask = tb->size - 1;
279 
280  /*
281  * Compute the next threshold at which we need to grow the hash table
282  * again.
283  */
284  if (tb->size == SH_MAX_SIZE)
285  tb->grow_threshold = ((double) tb->size) * SH_MAX_FILLFACTOR;
286  else
287  tb->grow_threshold = ((double) tb->size) * SH_FILLFACTOR;
288 }
289 
290 /* return the optimal bucket for the hash */
291 static inline uint32
293 {
294  return hash & tb->sizemask;
295 }
296 
297 /* return next bucket after the current, handling wraparound */
298 static inline uint32
299 SH_NEXT(SH_TYPE * tb, uint32 curelem, uint32 startelem)
300 {
301  curelem = (curelem + 1) & tb->sizemask;
302 
303  Assert(curelem != startelem);
304 
305  return curelem;
306 }
307 
308 /* return bucket before the current, handling wraparound */
309 static inline uint32
310 SH_PREV(SH_TYPE * tb, uint32 curelem, uint32 startelem)
311 {
312  curelem = (curelem - 1) & tb->sizemask;
313 
314  Assert(curelem != startelem);
315 
316  return curelem;
317 }
318 
319 /* return distance between bucket and its optimal position */
320 static inline uint32
321 SH_DISTANCE_FROM_OPTIMAL(SH_TYPE * tb, uint32 optimal, uint32 bucket)
322 {
323  if (optimal <= bucket)
324  return bucket - optimal;
325  else
326  return (tb->size + bucket) - optimal;
327 }
328 
329 static inline uint32
331 {
332 #ifdef SH_STORE_HASH
333  return SH_GET_HASH(tb, entry);
334 #else
335  return SH_HASH_KEY(tb, entry->SH_KEY);
336 #endif
337 }
338 
339 /* default memory allocator function */
340 static inline void *SH_ALLOCATE(SH_TYPE * type, Size size);
341 static inline void SH_FREE(SH_TYPE * type, void *pointer);
342 
343 #ifndef SH_USE_NONDEFAULT_ALLOCATOR
344 
345 /* default memory allocator function */
346 static inline void *
347 SH_ALLOCATE(SH_TYPE * type, Size size)
348 {
349 #ifdef SH_RAW_ALLOCATOR
350  return SH_RAW_ALLOCATOR(size);
351 #else
352  return MemoryContextAllocExtended(type->ctx, size,
354 #endif
355 }
356 
357 /* default memory free function */
358 static inline void
359 SH_FREE(SH_TYPE * type, void *pointer)
360 {
361  pfree(pointer);
362 }
363 
364 #endif
365 
366 /*
367  * Create a hash table with enough space for `nelements` distinct members.
368  * Memory for the hash table is allocated from the passed-in context. If
369  * desired, the array of elements can be allocated using a passed-in allocator;
370  * this could be useful in order to place the array of elements in a shared
371  * memory, or in a context that will outlive the rest of the hash table.
372  * Memory other than for the array of elements will still be allocated from
373  * the passed-in context.
374  */
375 #ifdef SH_RAW_ALLOCATOR
377 SH_CREATE(uint32 nelements, void *private_data)
378 #else
380 SH_CREATE(MemoryContext ctx, uint32 nelements, void *private_data)
381 #endif
382 {
383  SH_TYPE *tb;
384  uint64 size;
385 
386 #ifdef SH_RAW_ALLOCATOR
387  tb = SH_RAW_ALLOCATOR(sizeof(SH_TYPE));
388 #else
389  tb = MemoryContextAllocZero(ctx, sizeof(SH_TYPE));
390  tb->ctx = ctx;
391 #endif
392  tb->private_data = private_data;
393 
394  /* increase nelements by fillfactor, want to store nelements elements */
395  size = Min((double) SH_MAX_SIZE, ((double) nelements) / SH_FILLFACTOR);
396 
397  SH_COMPUTE_PARAMETERS(tb, size);
398 
399  tb->data = SH_ALLOCATE(tb, sizeof(SH_ELEMENT_TYPE) * tb->size);
400 
401  return tb;
402 }
403 
404 /* destroy a previously created hash table */
405 SH_SCOPE void
406 SH_DESTROY(SH_TYPE * tb)
407 {
408  SH_FREE(tb, tb->data);
409  pfree(tb);
410 }
411 
412 /* reset the contents of a previously created hash table */
413 SH_SCOPE void
414 SH_RESET(SH_TYPE * tb)
415 {
416  memset(tb->data, 0, sizeof(SH_ELEMENT_TYPE) * tb->size);
417  tb->members = 0;
418 }
419 
420 /*
421  * Grow a hash table to at least `newsize` buckets.
422  *
423  * Usually this will automatically be called by insertions/deletions, when
424  * necessary. But resizing to the exact input size can be advantageous
425  * performance-wise, when known at some point.
426  */
427 SH_SCOPE void
428 SH_GROW(SH_TYPE * tb, uint32 newsize)
429 {
430  uint64 oldsize = tb->size;
431  SH_ELEMENT_TYPE *olddata = tb->data;
432  SH_ELEMENT_TYPE *newdata;
433  uint32 i;
434  uint32 startelem = 0;
435  uint32 copyelem;
436 
437  Assert(oldsize == sh_pow2(oldsize));
438  Assert(oldsize != SH_MAX_SIZE);
439  Assert(oldsize < newsize);
440 
441  /* compute parameters for new table */
442  SH_COMPUTE_PARAMETERS(tb, newsize);
443 
444  tb->data = SH_ALLOCATE(tb, sizeof(SH_ELEMENT_TYPE) * tb->size);
445 
446  newdata = tb->data;
447 
448  /*
449  * Copy entries from the old data to newdata. We theoretically could use
450  * SH_INSERT here, to avoid code duplication, but that's more general than
451  * we need. We neither want tb->members increased, nor do we need to do
452  * deal with deleted elements, nor do we need to compare keys. So a
453  * special-cased implementation is lot faster. As resizing can be time
454  * consuming and frequent, that's worthwhile to optimize.
455  *
456  * To be able to simply move entries over, we have to start not at the
457  * first bucket (i.e olddata[0]), but find the first bucket that's either
458  * empty, or is occupied by an entry at its optimal position. Such a
459  * bucket has to exist in any table with a load factor under 1, as not all
460  * buckets are occupied, i.e. there always has to be an empty bucket. By
461  * starting at such a bucket we can move the entries to the larger table,
462  * without having to deal with conflicts.
463  */
464 
465  /* search for the first element in the hash that's not wrapped around */
466  for (i = 0; i < oldsize; i++)
467  {
468  SH_ELEMENT_TYPE *oldentry = &olddata[i];
469  uint32 hash;
470  uint32 optimal;
471 
472  if (oldentry->status != SH_STATUS_IN_USE)
473  {
474  startelem = i;
475  break;
476  }
477 
478  hash = SH_ENTRY_HASH(tb, oldentry);
479  optimal = SH_INITIAL_BUCKET(tb, hash);
480 
481  if (optimal == i)
482  {
483  startelem = i;
484  break;
485  }
486  }
487 
488  /* and copy all elements in the old table */
489  copyelem = startelem;
490  for (i = 0; i < oldsize; i++)
491  {
492  SH_ELEMENT_TYPE *oldentry = &olddata[copyelem];
493 
494  if (oldentry->status == SH_STATUS_IN_USE)
495  {
496  uint32 hash;
497  uint32 startelem;
498  uint32 curelem;
499  SH_ELEMENT_TYPE *newentry;
500 
501  hash = SH_ENTRY_HASH(tb, oldentry);
502  startelem = SH_INITIAL_BUCKET(tb, hash);
503  curelem = startelem;
504 
505  /* find empty element to put data into */
506  while (true)
507  {
508  newentry = &newdata[curelem];
509 
510  if (newentry->status == SH_STATUS_EMPTY)
511  {
512  break;
513  }
514 
515  curelem = SH_NEXT(tb, curelem, startelem);
516  }
517 
518  /* copy entry to new slot */
519  memcpy(newentry, oldentry, sizeof(SH_ELEMENT_TYPE));
520  }
521 
522  /* can't use SH_NEXT here, would use new size */
523  copyelem++;
524  if (copyelem >= oldsize)
525  {
526  copyelem = 0;
527  }
528  }
529 
530  SH_FREE(tb, olddata);
531 }
532 
533 /*
534  * This is a separate static inline function, so it can be reliably be inlined
535  * into its wrapper functions even if SH_SCOPE is extern.
536  */
537 static inline SH_ELEMENT_TYPE *
539 {
540  uint32 startelem;
541  uint32 curelem;
542  SH_ELEMENT_TYPE *data;
543  uint32 insertdist;
544 
545 restart:
546  insertdist = 0;
547 
548  /*
549  * We do the grow check even if the key is actually present, to avoid
550  * doing the check inside the loop. This also lets us avoid having to
551  * re-find our position in the hashtable after resizing.
552  *
553  * Note that this also reached when resizing the table due to
554  * SH_GROW_MAX_DIB / SH_GROW_MAX_MOVE.
555  */
556  if (unlikely(tb->members >= tb->grow_threshold))
557  {
558  if (tb->size == SH_MAX_SIZE)
559  {
560  sh_error("hash table size exceeded");
561  }
562 
563  /*
564  * When optimizing, it can be very useful to print these out.
565  */
566  /* SH_STAT(tb); */
567  SH_GROW(tb, tb->size * 2);
568  /* SH_STAT(tb); */
569  }
570 
571  /* perform insert, start bucket search at optimal location */
572  data = tb->data;
573  startelem = SH_INITIAL_BUCKET(tb, hash);
574  curelem = startelem;
575  while (true)
576  {
577  uint32 curdist;
578  uint32 curhash;
579  uint32 curoptimal;
580  SH_ELEMENT_TYPE *entry = &data[curelem];
581 
582  /* any empty bucket can directly be used */
583  if (entry->status == SH_STATUS_EMPTY)
584  {
585  tb->members++;
586  entry->SH_KEY = key;
587 #ifdef SH_STORE_HASH
588  SH_GET_HASH(tb, entry) = hash;
589 #endif
590  entry->status = SH_STATUS_IN_USE;
591  *found = false;
592  return entry;
593  }
594 
595  /*
596  * If the bucket is not empty, we either found a match (in which case
597  * we're done), or we have to decide whether to skip over or move the
598  * colliding entry. When the colliding element's distance to its
599  * optimal position is smaller than the to-be-inserted entry's, we
600  * shift the colliding entry (and its followers) forward by one.
601  */
602 
603  if (SH_COMPARE_KEYS(tb, hash, key, entry))
604  {
605  Assert(entry->status == SH_STATUS_IN_USE);
606  *found = true;
607  return entry;
608  }
609 
610  curhash = SH_ENTRY_HASH(tb, entry);
611  curoptimal = SH_INITIAL_BUCKET(tb, curhash);
612  curdist = SH_DISTANCE_FROM_OPTIMAL(tb, curoptimal, curelem);
613 
614  if (insertdist > curdist)
615  {
616  SH_ELEMENT_TYPE *lastentry = entry;
617  uint32 emptyelem = curelem;
618  uint32 moveelem;
619  int32 emptydist = 0;
620 
621  /* find next empty bucket */
622  while (true)
623  {
624  SH_ELEMENT_TYPE *emptyentry;
625 
626  emptyelem = SH_NEXT(tb, emptyelem, startelem);
627  emptyentry = &data[emptyelem];
628 
629  if (emptyentry->status == SH_STATUS_EMPTY)
630  {
631  lastentry = emptyentry;
632  break;
633  }
634 
635  /*
636  * To avoid negative consequences from overly imbalanced
637  * hashtables, grow the hashtable if collisions would require
638  * us to move a lot of entries. The most likely cause of such
639  * imbalance is filling a (currently) small table, from a
640  * currently big one, in hash-table order. Don't grow if the
641  * hashtable would be too empty, to prevent quick space
642  * explosion for some weird edge cases.
643  */
644  if (unlikely(++emptydist > SH_GROW_MAX_MOVE) &&
645  ((double) tb->members / tb->size) >= SH_GROW_MIN_FILLFACTOR)
646  {
647  tb->grow_threshold = 0;
648  goto restart;
649  }
650  }
651 
652  /* shift forward, starting at last occupied element */
653 
654  /*
655  * TODO: This could be optimized to be one memcpy in may cases,
656  * excepting wrapping around at the end of ->data. Hasn't shown up
657  * in profiles so far though.
658  */
659  moveelem = emptyelem;
660  while (moveelem != curelem)
661  {
662  SH_ELEMENT_TYPE *moveentry;
663 
664  moveelem = SH_PREV(tb, moveelem, startelem);
665  moveentry = &data[moveelem];
666 
667  memcpy(lastentry, moveentry, sizeof(SH_ELEMENT_TYPE));
668  lastentry = moveentry;
669  }
670 
671  /* and fill the now empty spot */
672  tb->members++;
673 
674  entry->SH_KEY = key;
675 #ifdef SH_STORE_HASH
676  SH_GET_HASH(tb, entry) = hash;
677 #endif
678  entry->status = SH_STATUS_IN_USE;
679  *found = false;
680  return entry;
681  }
682 
683  curelem = SH_NEXT(tb, curelem, startelem);
684  insertdist++;
685 
686  /*
687  * To avoid negative consequences from overly imbalanced hashtables,
688  * grow the hashtable if collisions lead to large runs. The most
689  * likely cause of such imbalance is filling a (currently) small
690  * table, from a currently big one, in hash-table order. Don't grow
691  * if the hashtable would be too empty, to prevent quick space
692  * explosion for some weird edge cases.
693  */
694  if (unlikely(insertdist > SH_GROW_MAX_DIB) &&
695  ((double) tb->members / tb->size) >= SH_GROW_MIN_FILLFACTOR)
696  {
697  tb->grow_threshold = 0;
698  goto restart;
699  }
700  }
701 }
702 
703 /*
704  * Insert the key key into the hash-table, set *found to true if the key
705  * already exists, false otherwise. Returns the hash-table entry in either
706  * case.
707  */
709 SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found)
710 {
711  uint32 hash = SH_HASH_KEY(tb, key);
712 
713  return SH_INSERT_HASH_INTERNAL(tb, key, hash, found);
714 }
715 
716 /*
717  * Insert the key key into the hash-table using an already-calculated
718  * hash. Set *found to true if the key already exists, false
719  * otherwise. Returns the hash-table entry in either case.
720  */
722 SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool *found)
723 {
724  return SH_INSERT_HASH_INTERNAL(tb, key, hash, found);
725 }
726 
727 /*
728  * This is a separate static inline function, so it can be reliably be inlined
729  * into its wrapper functions even if SH_SCOPE is extern.
730  */
731 static inline SH_ELEMENT_TYPE *
733 {
734  const uint32 startelem = SH_INITIAL_BUCKET(tb, hash);
735  uint32 curelem = startelem;
736 
737  while (true)
738  {
739  SH_ELEMENT_TYPE *entry = &tb->data[curelem];
740 
741  if (entry->status == SH_STATUS_EMPTY)
742  {
743  return NULL;
744  }
745 
746  Assert(entry->status == SH_STATUS_IN_USE);
747 
748  if (SH_COMPARE_KEYS(tb, hash, key, entry))
749  return entry;
750 
751  /*
752  * TODO: we could stop search based on distance. If the current
753  * buckets's distance-from-optimal is smaller than what we've skipped
754  * already, the entry doesn't exist. Probably only do so if
755  * SH_STORE_HASH is defined, to avoid re-computing hashes?
756  */
757 
758  curelem = SH_NEXT(tb, curelem, startelem);
759  }
760 }
761 
762 /*
763  * Lookup up entry in hash table. Returns NULL if key not present.
764  */
767 {
768  uint32 hash = SH_HASH_KEY(tb, key);
769 
770  return SH_LOOKUP_HASH_INTERNAL(tb, key, hash);
771 }
772 
773 /*
774  * Lookup up entry in hash table using an already-calculated hash.
775  *
776  * Returns NULL if key not present.
777  */
780 {
781  return SH_LOOKUP_HASH_INTERNAL(tb, key, hash);
782 }
783 
784 /*
785  * Delete entry from hash table. Returns whether to-be-deleted key was
786  * present.
787  */
788 SH_SCOPE bool
790 {
791  uint32 hash = SH_HASH_KEY(tb, key);
792  uint32 startelem = SH_INITIAL_BUCKET(tb, hash);
793  uint32 curelem = startelem;
794 
795  while (true)
796  {
797  SH_ELEMENT_TYPE *entry = &tb->data[curelem];
798 
799  if (entry->status == SH_STATUS_EMPTY)
800  return false;
801 
802  if (entry->status == SH_STATUS_IN_USE &&
803  SH_COMPARE_KEYS(tb, hash, key, entry))
804  {
805  SH_ELEMENT_TYPE *lastentry = entry;
806 
807  tb->members--;
808 
809  /*
810  * Backward shift following elements till either an empty element
811  * or an element at its optimal position is encountered.
812  *
813  * While that sounds expensive, the average chain length is short,
814  * and deletions would otherwise require tombstones.
815  */
816  while (true)
817  {
818  SH_ELEMENT_TYPE *curentry;
819  uint32 curhash;
820  uint32 curoptimal;
821 
822  curelem = SH_NEXT(tb, curelem, startelem);
823  curentry = &tb->data[curelem];
824 
825  if (curentry->status != SH_STATUS_IN_USE)
826  {
827  lastentry->status = SH_STATUS_EMPTY;
828  break;
829  }
830 
831  curhash = SH_ENTRY_HASH(tb, curentry);
832  curoptimal = SH_INITIAL_BUCKET(tb, curhash);
833 
834  /* current is at optimal position, done */
835  if (curoptimal == curelem)
836  {
837  lastentry->status = SH_STATUS_EMPTY;
838  break;
839  }
840 
841  /* shift */
842  memcpy(lastentry, curentry, sizeof(SH_ELEMENT_TYPE));
843 
844  lastentry = curentry;
845  }
846 
847  return true;
848  }
849 
850  /* TODO: return false; if distance too big */
851 
852  curelem = SH_NEXT(tb, curelem, startelem);
853  }
854 }
855 
856 /*
857  * Initialize iterator.
858  */
859 SH_SCOPE void
861 {
862  int i;
863  uint64 startelem = PG_UINT64_MAX;
864 
865  /*
866  * Search for the first empty element. As deletions during iterations are
867  * supported, we want to start/end at an element that cannot be affected
868  * by elements being shifted.
869  */
870  for (i = 0; i < tb->size; i++)
871  {
872  SH_ELEMENT_TYPE *entry = &tb->data[i];
873 
874  if (entry->status != SH_STATUS_IN_USE)
875  {
876  startelem = i;
877  break;
878  }
879  }
880 
881  Assert(startelem < SH_MAX_SIZE);
882 
883  /*
884  * Iterate backwards, that allows the current element to be deleted, even
885  * if there are backward shifts
886  */
887  iter->cur = startelem;
888  iter->end = iter->cur;
889  iter->done = false;
890 }
891 
892 /*
893  * Initialize iterator to a specific bucket. That's really only useful for
894  * cases where callers are partially iterating over the hashspace, and that
895  * iteration deletes and inserts elements based on visited entries. Doing that
896  * repeatedly could lead to an unbalanced keyspace when always starting at the
897  * same position.
898  */
899 SH_SCOPE void
901 {
902  /*
903  * Iterate backwards, that allows the current element to be deleted, even
904  * if there are backward shifts.
905  */
906  iter->cur = at & tb->sizemask; /* ensure at is within a valid range */
907  iter->end = iter->cur;
908  iter->done = false;
909 }
910 
911 /*
912  * Iterate over all entries in the hash-table. Return the next occupied entry,
913  * or NULL if done.
914  *
915  * During iteration the current entry in the hash table may be deleted,
916  * without leading to elements being skipped or returned twice. Additionally
917  * the rest of the table may be modified (i.e. there can be insertions or
918  * deletions), but if so, there's neither a guarantee that all nodes are
919  * visited at least once, nor a guarantee that a node is visited at most once.
920  */
922 SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
923 {
924  while (!iter->done)
925  {
926  SH_ELEMENT_TYPE *elem;
927 
928  elem = &tb->data[iter->cur];
929 
930  /* next element in backward direction */
931  iter->cur = (iter->cur - 1) & tb->sizemask;
932 
933  if ((iter->cur & tb->sizemask) == (iter->end & tb->sizemask))
934  iter->done = true;
935  if (elem->status == SH_STATUS_IN_USE)
936  {
937  return elem;
938  }
939  }
940 
941  return NULL;
942 }
943 
944 /*
945  * Report some statistics about the state of the hashtable. For
946  * debugging/profiling purposes only.
947  */
948 SH_SCOPE void
949 SH_STAT(SH_TYPE * tb)
950 {
951  uint32 max_chain_length = 0;
952  uint32 total_chain_length = 0;
953  double avg_chain_length;
954  double fillfactor;
955  uint32 i;
956 
957  uint32 *collisions = palloc0(tb->size * sizeof(uint32));
958  uint32 total_collisions = 0;
959  uint32 max_collisions = 0;
960  double avg_collisions;
961 
962  for (i = 0; i < tb->size; i++)
963  {
964  uint32 hash;
965  uint32 optimal;
966  uint32 dist;
967  SH_ELEMENT_TYPE *elem;
968 
969  elem = &tb->data[i];
970 
971  if (elem->status != SH_STATUS_IN_USE)
972  continue;
973 
974  hash = SH_ENTRY_HASH(tb, elem);
975  optimal = SH_INITIAL_BUCKET(tb, hash);
976  dist = SH_DISTANCE_FROM_OPTIMAL(tb, optimal, i);
977 
978  if (dist > max_chain_length)
979  max_chain_length = dist;
980  total_chain_length += dist;
981 
982  collisions[optimal]++;
983  }
984 
985  for (i = 0; i < tb->size; i++)
986  {
987  uint32 curcoll = collisions[i];
988 
989  if (curcoll == 0)
990  continue;
991 
992  /* single contained element is not a collision */
993  curcoll--;
994  total_collisions += curcoll;
995  if (curcoll > max_collisions)
996  max_collisions = curcoll;
997  }
998 
999  if (tb->members > 0)
1000  {
1001  fillfactor = tb->members / ((double) tb->size);
1002  avg_chain_length = ((double) total_chain_length) / tb->members;
1003  avg_collisions = ((double) total_collisions) / tb->members;
1004  }
1005  else
1006  {
1007  fillfactor = 0;
1008  avg_chain_length = 0;
1009  avg_collisions = 0;
1010  }
1011 
1012  sh_log("size: " UINT64_FORMAT ", members: %u, filled: %f, total chain: %u, max chain: %u, avg chain: %f, total_collisions: %u, max_collisions: %i, avg_collisions: %f",
1013  tb->size, tb->members, fillfactor, total_chain_length, max_chain_length, avg_chain_length,
1014  total_collisions, max_collisions, avg_collisions);
1015 }
1016 
1017 #endif /* SH_DEFINE */
1018 
1019 
1020 /* undefine external parameters, so next hash table can be defined */
1021 #undef SH_PREFIX
1022 #undef SH_KEY_TYPE
1023 #undef SH_KEY
1024 #undef SH_ELEMENT_TYPE
1025 #undef SH_HASH_KEY
1026 #undef SH_SCOPE
1027 #undef SH_DECLARE
1028 #undef SH_DEFINE
1029 #undef SH_GET_HASH
1030 #undef SH_STORE_HASH
1031 #undef SH_USE_NONDEFAULT_ALLOCATOR
1032 #undef SH_EQUAL
1033 
1034 /* undefine locally declared macros */
1035 #undef SH_MAKE_PREFIX
1036 #undef SH_MAKE_NAME
1037 #undef SH_MAKE_NAME_
1038 #undef SH_FILLFACTOR
1039 #undef SH_MAX_FILLFACTOR
1040 #undef SH_GROW_MAX_DIB
1041 #undef SH_GROW_MAX_MOVE
1042 #undef SH_GROW_MIN_FILLFACTOR
1043 #undef SH_MAX_SIZE
1044 
1045 /* types */
1046 #undef SH_TYPE
1047 #undef SH_STATUS
1048 #undef SH_STATUS_EMPTY
1049 #undef SH_STATUS_IN_USE
1050 #undef SH_ITERATOR
1051 
1052 /* external function names */
1053 #undef SH_CREATE
1054 #undef SH_DESTROY
1055 #undef SH_RESET
1056 #undef SH_INSERT
1057 #undef SH_INSERT_HASH
1058 #undef SH_DELETE
1059 #undef SH_LOOKUP
1060 #undef SH_LOOKUP_HASH
1061 #undef SH_GROW
1062 #undef SH_START_ITERATE
1063 #undef SH_START_ITERATE_AT
1064 #undef SH_ITERATE
1065 #undef SH_ALLOCATE
1066 #undef SH_FREE
1067 #undef SH_STAT
1068 
1069 /* internal function names */
1070 #undef SH_COMPUTE_PARAMETERS
1071 #undef SH_COMPARE_KEYS
1072 #undef SH_INITIAL_BUCKET
1073 #undef SH_NEXT
1074 #undef SH_PREV
1075 #undef SH_DISTANCE_FROM_OPTIMAL
1076 #undef SH_ENTRY_HASH
1077 #undef SH_INSERT_HASH_INTERNAL
1078 #undef SH_LOOKUP_HASH_INTERNAL
#define SH_ALLOCATE
Definition: simplehash.h:87
#define SH_COMPUTE_PARAMETERS
Definition: simplehash.h:92
#define SH_KEY_TYPE
Definition: execGrouping.c:41
#define SH_START_ITERATE
Definition: simplehash.h:84
#define PG_UINT64_MAX
Definition: c.h:454
#define MCXT_ALLOC_HUGE
Definition: fe_memutils.h:16
void * MemoryContextAllocExtended(MemoryContext context, Size size, int flags)
Definition: mcxt.c:912
#define SH_DELETE
Definition: simplehash.h:80
#define SH_START_ITERATE_AT
Definition: simplehash.h:85
#define Min(x, y)
Definition: c.h:920
struct cursor * cur
Definition: ecpg.c:28
#define SH_STATUS_EMPTY
Definition: simplehash.h:70
#define SH_LOOKUP
Definition: simplehash.h:81
#define SH_INSERT_HASH
Definition: simplehash.h:79
#define SH_RESET
Definition: simplehash.h:77
#define SH_GROW
Definition: simplehash.h:83
#define SH_NEXT
Definition: simplehash.h:93
#define SH_STAT
Definition: simplehash.h:89
#define SH_PREV
Definition: simplehash.h:94
signed int int32
Definition: c.h:355
#define SH_STATUS_IN_USE
Definition: simplehash.h:71
#define SH_ITERATOR
Definition: simplehash.h:72
void pfree(void *pointer)
Definition: mcxt.c:1056
#define SH_INSERT_HASH_INTERNAL
Definition: simplehash.h:98
int fillfactor
Definition: pgbench.c:159
#define SH_DESTROY
Definition: simplehash.h:76
unsigned int uint32
Definition: c.h:367
#define SH_FREE
Definition: simplehash.h:88
#define SH_GET_HASH(tb, a)
Definition: execGrouping.c:47
void * palloc0(Size size)
Definition: mcxt.c:980
#define SH_STATUS
Definition: simplehash.h:69
void * MemoryContextAllocZero(MemoryContext context, Size size)
Definition: mcxt.c:839
#define SH_DISTANCE_FROM_OPTIMAL
Definition: simplehash.h:95
#define Max(x, y)
Definition: c.h:914
#define Assert(condition)
Definition: c.h:738
#define SH_INSERT
Definition: simplehash.h:78
#define MCXT_ALLOC_ZERO
Definition: fe_memutils.h:19
size_t Size
Definition: c.h:466
#define SH_ITERATE
Definition: simplehash.h:86
#define SH_TYPE
Definition: simplehash.h:68
#define SH_ELEMENT_TYPE
Definition: execGrouping.c:40
#define SH_INITIAL_BUCKET
Definition: simplehash.h:96
int i
#define SH_LOOKUP_HASH
Definition: simplehash.h:82
#define unlikely(x)
Definition: c.h:206
#define SH_CREATE
Definition: simplehash.h:75
#define SH_ENTRY_HASH
Definition: simplehash.h:97
#define SH_HASH_KEY(tb, key)
Definition: execGrouping.c:43
static unsigned hash(unsigned *uv, int n)
Definition: rege_dfa.c:541
#define UINT64_FORMAT
Definition: c.h:410
#define SH_SCOPE
Definition: execGrouping.c:45
#define SH_LOOKUP_HASH_INTERNAL
Definition: simplehash.h:99