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