Line data Source code
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 */
155 : uint32 members;
156 :
157 : /* mask for bucket and size calculations, based on size */
158 : uint32 sizemask;
159 :
160 : /* boundary after which to grow hashtable */
161 : uint32 grow_threshold;
162 :
163 : /* hash buckets */
164 : SH_ELEMENT_TYPE *data;
165 :
166 : #ifndef SH_RAW_ALLOCATOR
167 : /* memory context to use for allocations */
168 : MemoryContext ctx;
169 : #endif
170 :
171 : /* user defined data, useful for callbacks */
172 : void *private_data;
173 : } SH_TYPE;
174 :
175 : typedef enum SH_STATUS
176 : {
177 : SH_STATUS_EMPTY = 0x00,
178 : SH_STATUS_IN_USE = 0x01
179 : } SH_STATUS;
180 :
181 : typedef struct SH_ITERATOR
182 : {
183 : uint32 cur; /* current element */
184 : uint32 end;
185 : bool done; /* iterator exhausted? */
186 : } SH_ITERATOR;
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 : */
197 : SH_SCOPE SH_TYPE *SH_CREATE(MemoryContext ctx, uint32 nelements,
198 : void *private_data);
199 : #endif
200 :
201 : /* void <prefix>_destroy(<prefix>_hash *tb) */
202 : SH_SCOPE void SH_DESTROY(SH_TYPE * tb);
203 :
204 : /* void <prefix>_reset(<prefix>_hash *tb) */
205 : SH_SCOPE void SH_RESET(SH_TYPE * 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) */
211 : SH_SCOPE SH_ELEMENT_TYPE *SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found);
212 :
213 : /*
214 : * <element> *<prefix>_insert_hash(<prefix>_hash *tb, <key> key, uint32 hash,
215 : * bool *found)
216 : */
217 : SH_SCOPE SH_ELEMENT_TYPE *SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key,
218 : uint32 hash, bool *found);
219 :
220 : /* <element> *<prefix>_lookup(<prefix>_hash *tb, <key> key) */
221 : SH_SCOPE SH_ELEMENT_TYPE *SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key);
222 :
223 : /* <element> *<prefix>_lookup_hash(<prefix>_hash *tb, <key> key, uint32 hash) */
224 : SH_SCOPE SH_ELEMENT_TYPE *SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key,
225 : uint32 hash);
226 :
227 : /* void <prefix>_delete_item(<prefix>_hash *tb, <element> *entry) */
228 : SH_SCOPE void SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry);
229 :
230 : /* bool <prefix>_delete(<prefix>_hash *tb, <key> key) */
231 : SH_SCOPE bool SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key);
232 :
233 : /* void <prefix>_start_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
234 : SH_SCOPE void SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter);
235 :
236 : /*
237 : * void <prefix>_start_iterate_at(<prefix>_hash *tb, <prefix>_iterator *iter,
238 : * uint32 at)
239 : */
240 : SH_SCOPE void SH_START_ITERATE_AT(SH_TYPE * tb, SH_ITERATOR * iter, uint32 at);
241 :
242 : /* <element> *<prefix>_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
243 : SH_SCOPE SH_ELEMENT_TYPE *SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter);
244 :
245 : /* void <prefix>_stat(<prefix>_hash *tb */
246 : SH_SCOPE void SH_STAT(SH_TYPE * 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 175996 : SH_COMPUTE_SIZE(uint64 newsize)
312 : {
313 : uint64 size;
314 :
315 : /* supporting zero sized hashes would complicate matters */
316 175996 : size = Max(newsize, 2);
317 :
318 : /* round up size to the next power of 2, that's how bucketing works */
319 175996 : size = pg_nextpower2_64(size);
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 175996 : if (unlikely((((uint64) sizeof(SH_ELEMENT_TYPE)) * size) >= SIZE_MAX / 2))
327 0 : sh_error("hash table too large");
328 :
329 175996 : 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 87998 : SH_UPDATE_PARAMETERS(SH_TYPE * tb, uint64 newsize)
338 : {
339 87998 : uint64 size = SH_COMPUTE_SIZE(newsize);
340 :
341 : /* now set size */
342 87998 : tb->size = size;
343 87998 : 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 87998 : if (tb->size == SH_MAX_SIZE)
350 0 : tb->grow_threshold = ((double) tb->size) * SH_MAX_FILLFACTOR;
351 : else
352 87998 : tb->grow_threshold = ((double) tb->size) * SH_FILLFACTOR;
353 87998 : }
354 :
355 : /* return the optimal bucket for the hash */
356 : static inline uint32
357 38242220 : SH_INITIAL_BUCKET(SH_TYPE * tb, uint32 hash)
358 : {
359 38242220 : return hash & tb->sizemask;
360 : }
361 :
362 : /* return next bucket after the current, handling wraparound */
363 : static inline uint32
364 16634280 : SH_NEXT(SH_TYPE * tb, uint32 curelem, uint32 startelem)
365 : {
366 16634280 : curelem = (curelem + 1) & tb->sizemask;
367 :
368 : Assert(curelem != startelem);
369 :
370 16634280 : return curelem;
371 : }
372 :
373 : /* return bucket before the current, handling wraparound */
374 : static inline uint32
375 2702930 : SH_PREV(SH_TYPE * tb, uint32 curelem, uint32 startelem)
376 : {
377 2702930 : curelem = (curelem - 1) & tb->sizemask;
378 :
379 : Assert(curelem != startelem);
380 :
381 2702930 : return curelem;
382 : }
383 :
384 : /* return distance between bucket and its optimal position */
385 : static inline uint32
386 8451156 : SH_DISTANCE_FROM_OPTIMAL(SH_TYPE * tb, uint32 optimal, uint32 bucket)
387 : {
388 8451156 : if (optimal <= bucket)
389 8412608 : return bucket - optimal;
390 : else
391 38548 : return (tb->size + bucket) - optimal;
392 : }
393 :
394 : static inline uint32
395 9615542 : SH_ENTRY_HASH(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
396 : {
397 : #ifdef SH_STORE_HASH
398 3850544 : return SH_GET_HASH(tb, entry);
399 : #else
400 5764998 : 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 *
412 79346 : SH_ALLOCATE(SH_TYPE * type, Size size)
413 : {
414 : #ifdef SH_RAW_ALLOCATOR
415 646 : return SH_RAW_ALLOCATOR(size);
416 : #else
417 78700 : return MemoryContextAllocExtended(type->ctx, size,
418 : MCXT_ALLOC_HUGE | MCXT_ALLOC_ZERO);
419 : #endif
420 : }
421 :
422 : /* default memory free function */
423 : static inline void
424 34710 : SH_FREE(SH_TYPE * type, void *pointer)
425 : {
426 34710 : pfree(pointer);
427 34710 : }
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
441 : SH_SCOPE SH_TYPE *
442 636 : SH_CREATE(uint32 nelements, void *private_data)
443 : #else
444 : SH_SCOPE SH_TYPE *
445 83362 : 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 636 : tb = (SH_TYPE *) SH_RAW_ALLOCATOR(sizeof(SH_TYPE));
453 : #else
454 83362 : tb = (SH_TYPE *) MemoryContextAllocZero(ctx, sizeof(SH_TYPE));
455 83362 : tb->ctx = ctx;
456 : #endif
457 83998 : tb->private_data = private_data;
458 :
459 : /* increase nelements by fillfactor, want to store nelements elements */
460 83998 : size = Min((double) SH_MAX_SIZE, ((double) nelements) / SH_FILLFACTOR);
461 :
462 83998 : size = SH_COMPUTE_SIZE(size);
463 :
464 83998 : tb->data = (SH_ELEMENT_TYPE *) SH_ALLOCATE(tb, sizeof(SH_ELEMENT_TYPE) * size);
465 :
466 83998 : SH_UPDATE_PARAMETERS(tb, size);
467 83998 : return tb;
468 : }
469 :
470 : /* destroy a previously created hash table */
471 : SH_SCOPE void
472 39360 : SH_DESTROY(SH_TYPE * tb)
473 : {
474 39360 : SH_FREE(tb, tb->data);
475 39360 : pfree(tb);
476 39360 : }
477 :
478 : /* reset the contents of a previously created hash table */
479 : SH_SCOPE void
480 193328 : SH_RESET(SH_TYPE * tb)
481 : {
482 193328 : memset(tb->data, 0, sizeof(SH_ELEMENT_TYPE) * tb->size);
483 193328 : tb->members = 0;
484 193328 : }
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 4000 : SH_GROW(SH_TYPE * tb, uint64 newsize)
495 : {
496 4000 : uint64 oldsize = tb->size;
497 4000 : SH_ELEMENT_TYPE *olddata = tb->data;
498 : SH_ELEMENT_TYPE *newdata;
499 : uint32 i;
500 4000 : 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 4000 : newsize = SH_COMPUTE_SIZE(newsize);
508 :
509 4000 : 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 4000 : SH_UPDATE_PARAMETERS(tb, newsize);
516 :
517 4000 : 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 43216 : for (i = 0; i < oldsize; i++)
538 : {
539 43216 : SH_ELEMENT_TYPE *oldentry = &olddata[i];
540 : uint32 hash;
541 : uint32 optimal;
542 :
543 43216 : if (oldentry->status != SH_STATUS_IN_USE)
544 : {
545 2284 : startelem = i;
546 2284 : break;
547 : }
548 :
549 40932 : hash = SH_ENTRY_HASH(tb, oldentry);
550 40932 : optimal = SH_INITIAL_BUCKET(tb, hash);
551 :
552 40932 : if (optimal == i)
553 : {
554 1716 : startelem = i;
555 1716 : break;
556 : }
557 : }
558 :
559 : /* and copy all elements in the old table */
560 4000 : copyelem = startelem;
561 1085852 : for (i = 0; i < oldsize; i++)
562 : {
563 1081852 : SH_ELEMENT_TYPE *oldentry = &olddata[copyelem];
564 :
565 1081852 : if (oldentry->status == SH_STATUS_IN_USE)
566 : {
567 : uint32 hash;
568 : uint32 startelem2;
569 : uint32 curelem;
570 : SH_ELEMENT_TYPE *newentry;
571 :
572 947004 : hash = SH_ENTRY_HASH(tb, oldentry);
573 947004 : startelem2 = SH_INITIAL_BUCKET(tb, hash);
574 947004 : curelem = startelem2;
575 :
576 : /* find empty element to put data into */
577 : while (true)
578 : {
579 1311596 : newentry = &newdata[curelem];
580 :
581 1311596 : if (newentry->status == SH_STATUS_EMPTY)
582 : {
583 947004 : break;
584 : }
585 :
586 364592 : curelem = SH_NEXT(tb, curelem, startelem2);
587 : }
588 :
589 : /* copy entry to new slot */
590 947004 : memcpy(newentry, oldentry, sizeof(SH_ELEMENT_TYPE));
591 : }
592 :
593 : /* can't use SH_NEXT here, would use new size */
594 1081852 : copyelem++;
595 1081852 : if (copyelem >= oldsize)
596 : {
597 4000 : copyelem = 0;
598 : }
599 : }
600 :
601 4000 : SH_FREE(tb, olddata);
602 4000 : }
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 *
609 19285872 : SH_INSERT_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool *found)
610 : {
611 : uint32 startelem;
612 : uint32 curelem;
613 : SH_ELEMENT_TYPE *data;
614 : uint32 insertdist;
615 :
616 19285872 : restart:
617 19285872 : 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 19285872 : if (unlikely(tb->members >= tb->grow_threshold))
628 : {
629 4000 : if (unlikely(tb->size == SH_MAX_SIZE))
630 0 : 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 4000 : SH_GROW(tb, tb->size * 2);
637 : /* SH_STAT(tb); */
638 : }
639 :
640 : /* perform insert, start bucket search at optimal location */
641 19285872 : data = tb->data;
642 19285872 : startelem = SH_INITIAL_BUCKET(tb, hash);
643 19285872 : curelem = startelem;
644 : while (true)
645 8022090 : {
646 : uint32 curdist;
647 : uint32 curhash;
648 : uint32 curoptimal;
649 27307962 : SH_ELEMENT_TYPE *entry = &data[curelem];
650 :
651 : /* any empty bucket can directly be used */
652 27307962 : if (entry->status == SH_STATUS_EMPTY)
653 : {
654 3956380 : tb->members++;
655 3956380 : entry->SH_KEY = key;
656 : #ifdef SH_STORE_HASH
657 1868048 : SH_GET_HASH(tb, entry) = hash;
658 : #endif
659 3956380 : entry->status = SH_STATUS_IN_USE;
660 3956380 : *found = false;
661 3956380 : 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 23351582 : if (SH_COMPARE_KEYS(tb, hash, key, entry))
673 : {
674 : Assert(entry->status == SH_STATUS_IN_USE);
675 14900426 : *found = true;
676 14900426 : return entry;
677 : }
678 :
679 8451156 : curhash = SH_ENTRY_HASH(tb, entry);
680 8451156 : curoptimal = SH_INITIAL_BUCKET(tb, curhash);
681 8451156 : curdist = SH_DISTANCE_FROM_OPTIMAL(tb, curoptimal, curelem);
682 :
683 8451156 : if (insertdist > curdist)
684 : {
685 429066 : SH_ELEMENT_TYPE *lastentry = entry;
686 429066 : uint32 emptyelem = curelem;
687 : uint32 moveelem;
688 429066 : int32 emptydist = 0;
689 :
690 : /* find next empty bucket */
691 : while (true)
692 2300440 : {
693 : SH_ELEMENT_TYPE *emptyentry;
694 :
695 2729506 : emptyelem = SH_NEXT(tb, emptyelem, startelem);
696 2729506 : emptyentry = &data[emptyelem];
697 :
698 2729506 : if (emptyentry->status == SH_STATUS_EMPTY)
699 : {
700 428890 : lastentry = emptyentry;
701 428890 : 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 2300616 : if (unlikely(++emptydist > SH_GROW_MAX_MOVE) &&
714 176 : ((double) tb->members / tb->size) >= SH_GROW_MIN_FILLFACTOR)
715 : {
716 176 : tb->grow_threshold = 0;
717 176 : 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 428890 : moveelem = emptyelem;
729 3131820 : while (moveelem != curelem)
730 : {
731 : SH_ELEMENT_TYPE *moveentry;
732 :
733 2702930 : moveelem = SH_PREV(tb, moveelem, startelem);
734 2702930 : moveentry = &data[moveelem];
735 :
736 2702930 : memcpy(lastentry, moveentry, sizeof(SH_ELEMENT_TYPE));
737 2702930 : lastentry = moveentry;
738 : }
739 :
740 : /* and fill the now empty spot */
741 428890 : tb->members++;
742 :
743 428890 : entry->SH_KEY = key;
744 : #ifdef SH_STORE_HASH
745 238808 : SH_GET_HASH(tb, entry) = hash;
746 : #endif
747 428890 : entry->status = SH_STATUS_IN_USE;
748 428890 : *found = false;
749 428890 : return entry;
750 : }
751 :
752 8022090 : curelem = SH_NEXT(tb, curelem, startelem);
753 8022090 : 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 8022090 : if (unlikely(insertdist > SH_GROW_MAX_DIB) &&
764 0 : ((double) tb->members / tb->size) >= SH_GROW_MIN_FILLFACTOR)
765 : {
766 0 : tb->grow_threshold = 0;
767 0 : 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 : */
776 : SH_SCOPE SH_ELEMENT_TYPE *
777 13265886 : SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found)
778 : {
779 13265886 : uint32 hash = SH_HASH_KEY(tb, key);
780 :
781 13265886 : 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 : */
789 : SH_SCOPE SH_ELEMENT_TYPE *
790 6019810 : SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool *found)
791 : {
792 6019810 : 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 *
800 7507426 : SH_LOOKUP_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash)
801 : {
802 7507426 : const uint32 startelem = SH_INITIAL_BUCKET(tb, hash);
803 7507426 : uint32 curelem = startelem;
804 :
805 : while (true)
806 3192166 : {
807 10699592 : SH_ELEMENT_TYPE *entry = &tb->data[curelem];
808 :
809 10699592 : if (entry->status == SH_STATUS_EMPTY)
810 : {
811 2675756 : return NULL;
812 : }
813 :
814 : Assert(entry->status == SH_STATUS_IN_USE);
815 :
816 8023836 : if (SH_COMPARE_KEYS(tb, hash, key, entry))
817 4831670 : 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 3192166 : curelem = SH_NEXT(tb, curelem, startelem);
827 : }
828 : }
829 :
830 : /*
831 : * Lookup entry in hash table. Returns NULL if key not present.
832 : */
833 : SH_SCOPE SH_ELEMENT_TYPE *
834 6388784 : SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key)
835 : {
836 6388784 : uint32 hash = SH_HASH_KEY(tb, key);
837 :
838 6388784 : 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 : */
846 : SH_SCOPE SH_ELEMENT_TYPE *
847 1118642 : SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash)
848 : {
849 1118642 : 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
857 1833380 : SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
858 : {
859 1833380 : uint32 hash = SH_HASH_KEY(tb, key);
860 1833380 : uint32 startelem = SH_INITIAL_BUCKET(tb, hash);
861 1833380 : uint32 curelem = startelem;
862 :
863 : while (true)
864 525764 : {
865 2359144 : SH_ELEMENT_TYPE *entry = &tb->data[curelem];
866 :
867 2359144 : if (entry->status == SH_STATUS_EMPTY)
868 145652 : return false;
869 :
870 4400234 : if (entry->status == SH_STATUS_IN_USE &&
871 2213492 : SH_COMPARE_KEYS(tb, hash, key, entry))
872 : {
873 1687728 : SH_ELEMENT_TYPE *lastentry = entry;
874 :
875 1687728 : 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 105270 : {
886 : SH_ELEMENT_TYPE *curentry;
887 : uint32 curhash;
888 : uint32 curoptimal;
889 :
890 1792998 : curelem = SH_NEXT(tb, curelem, startelem);
891 1792998 : curentry = &tb->data[curelem];
892 :
893 1792998 : if (curentry->status != SH_STATUS_IN_USE)
894 : {
895 1624870 : lastentry->status = SH_STATUS_EMPTY;
896 1624870 : break;
897 : }
898 :
899 168128 : curhash = SH_ENTRY_HASH(tb, curentry);
900 168128 : curoptimal = SH_INITIAL_BUCKET(tb, curhash);
901 :
902 : /* current is at optimal position, done */
903 168128 : if (curoptimal == curelem)
904 : {
905 62858 : lastentry->status = SH_STATUS_EMPTY;
906 62858 : break;
907 : }
908 :
909 : /* shift */
910 105270 : memcpy(lastentry, curentry, sizeof(SH_ELEMENT_TYPE));
911 :
912 105270 : lastentry = curentry;
913 : }
914 :
915 1687728 : return true;
916 : }
917 :
918 : /* TODO: return false; if distance too big */
919 :
920 525764 : curelem = SH_NEXT(tb, curelem, startelem);
921 : }
922 : }
923 :
924 : /*
925 : * Delete entry from hash table by entry pointer
926 : */
927 : SH_SCOPE void
928 2388 : SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
929 : {
930 2388 : SH_ELEMENT_TYPE *lastentry = entry;
931 2388 : uint32 hash = SH_ENTRY_HASH(tb, entry);
932 2388 : uint32 startelem = SH_INITIAL_BUCKET(tb, hash);
933 : uint32 curelem;
934 :
935 : /* Calculate the index of 'entry' */
936 2388 : curelem = entry - &tb->data[0];
937 :
938 2388 : 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 4776 : {
949 : SH_ELEMENT_TYPE *curentry;
950 : uint32 curhash;
951 : uint32 curoptimal;
952 :
953 7164 : curelem = SH_NEXT(tb, curelem, startelem);
954 7164 : curentry = &tb->data[curelem];
955 :
956 7164 : if (curentry->status != SH_STATUS_IN_USE)
957 : {
958 1230 : lastentry->status = SH_STATUS_EMPTY;
959 1230 : break;
960 : }
961 :
962 5934 : curhash = SH_ENTRY_HASH(tb, curentry);
963 5934 : curoptimal = SH_INITIAL_BUCKET(tb, curhash);
964 :
965 : /* current is at optimal position, done */
966 5934 : if (curoptimal == curelem)
967 : {
968 1158 : lastentry->status = SH_STATUS_EMPTY;
969 1158 : break;
970 : }
971 :
972 : /* shift */
973 4776 : memcpy(lastentry, curentry, sizeof(SH_ELEMENT_TYPE));
974 :
975 4776 : lastentry = curentry;
976 : }
977 2388 : }
978 :
979 : /*
980 : * Initialize iterator.
981 : */
982 : SH_SCOPE void
983 195090 : SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
984 : {
985 195090 : 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 274686 : for (uint32 i = 0; i < tb->size; i++)
993 : {
994 274686 : SH_ELEMENT_TYPE *entry = &tb->data[i];
995 :
996 274686 : if (entry->status != SH_STATUS_IN_USE)
997 : {
998 195090 : startelem = i;
999 195090 : 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 195090 : iter->cur = startelem;
1011 195090 : iter->end = iter->cur;
1012 195090 : iter->done = false;
1013 195090 : }
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
1023 24 : SH_START_ITERATE_AT(SH_TYPE * tb, SH_ITERATOR * iter, uint32 at)
1024 : {
1025 : /*
1026 : * Iterate backwards, that allows the current element to be deleted, even
1027 : * if there are backward shifts.
1028 : */
1029 24 : iter->cur = at & tb->sizemask; /* ensure at is within a valid range */
1030 24 : iter->end = iter->cur;
1031 24 : iter->done = false;
1032 24 : }
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 : */
1044 : SH_SCOPE SH_ELEMENT_TYPE *
1045 3831504 : SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
1046 : {
1047 20136156 : while (!iter->done)
1048 : {
1049 : SH_ELEMENT_TYPE *elem;
1050 :
1051 19941184 : elem = &tb->data[iter->cur];
1052 :
1053 : /* next element in backward direction */
1054 19941184 : iter->cur = (iter->cur - 1) & tb->sizemask;
1055 :
1056 19941184 : if ((iter->cur & tb->sizemask) == (iter->end & tb->sizemask))
1057 194972 : iter->done = true;
1058 19941184 : if (elem->status == SH_STATUS_IN_USE)
1059 : {
1060 3636532 : return elem;
1061 : }
1062 : }
1063 :
1064 194972 : 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 0 : SH_STAT(SH_TYPE * tb)
1073 : {
1074 0 : uint32 max_chain_length = 0;
1075 0 : uint32 total_chain_length = 0;
1076 : double avg_chain_length;
1077 : double fillfactor;
1078 : uint32 i;
1079 :
1080 0 : uint32 *collisions = (uint32 *) palloc0(tb->size * sizeof(uint32));
1081 0 : uint32 total_collisions = 0;
1082 0 : uint32 max_collisions = 0;
1083 : double avg_collisions;
1084 :
1085 0 : for (i = 0; i < tb->size; i++)
1086 : {
1087 : uint32 hash;
1088 : uint32 optimal;
1089 : uint32 dist;
1090 : SH_ELEMENT_TYPE *elem;
1091 :
1092 0 : elem = &tb->data[i];
1093 :
1094 0 : if (elem->status != SH_STATUS_IN_USE)
1095 0 : continue;
1096 :
1097 0 : hash = SH_ENTRY_HASH(tb, elem);
1098 0 : optimal = SH_INITIAL_BUCKET(tb, hash);
1099 0 : dist = SH_DISTANCE_FROM_OPTIMAL(tb, optimal, i);
1100 :
1101 0 : if (dist > max_chain_length)
1102 0 : max_chain_length = dist;
1103 0 : total_chain_length += dist;
1104 :
1105 0 : collisions[optimal]++;
1106 : }
1107 :
1108 0 : for (i = 0; i < tb->size; i++)
1109 : {
1110 0 : uint32 curcoll = collisions[i];
1111 :
1112 0 : if (curcoll == 0)
1113 0 : continue;
1114 :
1115 : /* single contained element is not a collision */
1116 0 : curcoll--;
1117 0 : total_collisions += curcoll;
1118 0 : if (curcoll > max_collisions)
1119 0 : max_collisions = curcoll;
1120 : }
1121 :
1122 : /* large enough to be worth freeing, even if just used for debugging */
1123 0 : pfree(collisions);
1124 :
1125 0 : if (tb->members > 0)
1126 : {
1127 0 : fillfactor = tb->members / ((double) tb->size);
1128 0 : avg_chain_length = ((double) total_chain_length) / tb->members;
1129 0 : avg_collisions = ((double) total_collisions) / tb->members;
1130 : }
1131 : else
1132 : {
1133 0 : fillfactor = 0;
1134 0 : avg_chain_length = 0;
1135 0 : avg_collisions = 0;
1136 : }
1137 :
1138 0 : 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",
1139 : tb->size, tb->members, fillfactor, total_chain_length, max_chain_length, avg_chain_length,
1140 : total_collisions, max_collisions, avg_collisions);
1141 0 : }
1142 :
1143 : #endif /* SH_DEFINE */
1144 :
1145 :
1146 : /* undefine external parameters, so next hash table can be defined */
1147 : #undef SH_PREFIX
1148 : #undef SH_KEY_TYPE
1149 : #undef SH_KEY
1150 : #undef SH_ELEMENT_TYPE
1151 : #undef SH_HASH_KEY
1152 : #undef SH_SCOPE
1153 : #undef SH_DECLARE
1154 : #undef SH_DEFINE
1155 : #undef SH_GET_HASH
1156 : #undef SH_STORE_HASH
1157 : #undef SH_USE_NONDEFAULT_ALLOCATOR
1158 : #undef SH_EQUAL
1159 :
1160 : /* undefine locally declared macros */
1161 : #undef SH_MAKE_PREFIX
1162 : #undef SH_MAKE_NAME
1163 : #undef SH_MAKE_NAME_
1164 : #undef SH_FILLFACTOR
1165 : #undef SH_MAX_FILLFACTOR
1166 : #undef SH_GROW_MAX_DIB
1167 : #undef SH_GROW_MAX_MOVE
1168 : #undef SH_GROW_MIN_FILLFACTOR
1169 : #undef SH_MAX_SIZE
1170 :
1171 : /* types */
1172 : #undef SH_TYPE
1173 : #undef SH_STATUS
1174 : #undef SH_STATUS_EMPTY
1175 : #undef SH_STATUS_IN_USE
1176 : #undef SH_ITERATOR
1177 :
1178 : /* external function names */
1179 : #undef SH_CREATE
1180 : #undef SH_DESTROY
1181 : #undef SH_RESET
1182 : #undef SH_INSERT
1183 : #undef SH_INSERT_HASH
1184 : #undef SH_DELETE_ITEM
1185 : #undef SH_DELETE
1186 : #undef SH_LOOKUP
1187 : #undef SH_LOOKUP_HASH
1188 : #undef SH_GROW
1189 : #undef SH_START_ITERATE
1190 : #undef SH_START_ITERATE_AT
1191 : #undef SH_ITERATE
1192 : #undef SH_ALLOCATE
1193 : #undef SH_FREE
1194 : #undef SH_STAT
1195 :
1196 : /* internal function names */
1197 : #undef SH_COMPUTE_SIZE
1198 : #undef SH_UPDATE_PARAMETERS
1199 : #undef SH_COMPARE_KEYS
1200 : #undef SH_INITIAL_BUCKET
1201 : #undef SH_NEXT
1202 : #undef SH_PREV
1203 : #undef SH_DISTANCE_FROM_OPTIMAL
1204 : #undef SH_ENTRY_HASH
1205 : #undef SH_INSERT_HASH_INTERNAL
1206 : #undef SH_LOOKUP_HASH_INTERNAL
|
