Ruby 4.0.10p0 (2026-11-19 revision a704b7cd95a42cc0cf5f307137bf3aac0285b915)
st.c
1/* This is a public domain general purpose hash table package
2 originally written by Peter Moore @ UCB.
3
4 The hash table data structures were redesigned and the package was
5 rewritten by Vladimir Makarov <vmakarov@redhat.com>. */
6
7/* The original package implemented classic bucket-based hash tables
8 with entries doubly linked for an access by their insertion order.
9 To decrease pointer chasing and as a consequence to improve a data
10 locality the current implementation is based on storing entries in
11 an array and using hash tables with open addressing. The current
12 entries are more compact in comparison with the original ones and
13 this also improves the data locality.
14
15 The hash table has two arrays called *bins* and *entries*.
16
17 bins:
18 -------
19 | | entries array:
20 |-------| --------------------------------
21 | index | | | entry: | | |
22 |-------| | | | | |
23 | ... | | ... | hash | ... | ... |
24 |-------| | | key | | |
25 | empty | | | record | | |
26 |-------| --------------------------------
27 | ... | ^ ^
28 |-------| |_ entries start |_ entries bound
29 |deleted|
30 -------
31
32 o The entry array contains table entries in the same order as they
33 were inserted.
34
35 When the first entry is deleted, a variable containing index of
36 the current first entry (*entries start*) is changed. In all
37 other cases of the deletion, we just mark the entry as deleted by
38 using a reserved hash value.
39
40 Such organization of the entry storage makes operations of the
41 table shift and the entries traversal very fast.
42
43 o The bins provide access to the entries by their keys. The
44 key hash is mapped to a bin containing *index* of the
45 corresponding entry in the entry array.
46
47 The bin array size is always power of two, it makes mapping very
48 fast by using the corresponding lower bits of the hash.
49 Generally it is not a good idea to ignore some part of the hash.
50 But alternative approach is worse. For example, we could use a
51 modulo operation for mapping and a prime number for the size of
52 the bin array. Unfortunately, the modulo operation for big
53 64-bit numbers are extremely slow (it takes more than 100 cycles
54 on modern Intel CPUs).
55
56 Still other bits of the hash value are used when the mapping
57 results in a collision. In this case we use a secondary hash
58 value which is a result of a function of the collision bin
59 index and the original hash value. The function choice
60 guarantees that we can traverse all bins and finally find the
61 corresponding bin as after several iterations the function
62 becomes a full cycle linear congruential generator because it
63 satisfies requirements of the Hull-Dobell theorem.
64
65 When an entry is removed from the table besides marking the
66 hash in the corresponding entry described above, we also mark
67 the bin by a special value in order to find entries which had
68 a collision with the removed entries.
69
70 There are two reserved values for the bins. One denotes an
71 empty bin, another one denotes a bin for a deleted entry.
72
73 o The length of the bin array is at least two times more than the
74 entry array length. This keeps the table load factor healthy.
75 The trigger of rebuilding the table is always a case when we can
76 not insert an entry anymore at the entries bound. We could
77 change the entries bound too in case of deletion but than we need
78 a special code to count bins with corresponding deleted entries
79 and reset the bin values when there are too many bins
80 corresponding deleted entries
81
82 Table rebuilding is done by creation of a new entry array and
83 bins of an appropriate size. We also try to reuse the arrays
84 in some cases by compacting the array and removing deleted
85 entries.
86
87 o To save memory very small tables have no allocated arrays
88 bins. We use a linear search for an access by a key.
89
90 o To save more memory we use 8-, 16-, 32- and 64- bit indexes in
91 bins depending on the current hash table size.
92
93 o The implementation takes into account that the table can be
94 rebuilt during hashing or comparison functions. It can happen if
95 the functions are implemented in Ruby and a thread switch occurs
96 during their execution.
97
98 This implementation speeds up the Ruby hash table benchmarks in
99 average by more 40% on Intel Haswell CPU.
100
101*/
102
103#ifdef NOT_RUBY
104#include "regint.h"
105#include "st.h"
106#include <assert.h>
107#elif defined RUBY_EXPORT
108#include "internal.h"
109#include "internal/bits.h"
110#include "internal/hash.h"
111#include "internal/sanitizers.h"
112#include "internal/set_table.h"
113#include "internal/static_assert.h"
114#include "internal/st.h"
115#include "ruby_assert.h"
116#endif
117
118#include <stdio.h>
119#ifdef HAVE_STDLIB_H
120#include <stdlib.h>
121#endif
122#include <string.h>
123
124#ifdef __GNUC__
125#define PREFETCH(addr, write_p) __builtin_prefetch(addr, write_p)
126#define EXPECT(expr, val) __builtin_expect(expr, val)
127#define ATTRIBUTE_UNUSED __attribute__((unused))
128#else
129#define PREFETCH(addr, write_p)
130#define EXPECT(expr, val) (expr)
131#define ATTRIBUTE_UNUSED
132#endif
133
134/* The type of hashes. */
135typedef st_index_t st_hash_t;
136
138 st_hash_t hash;
139 st_data_t key;
140 st_data_t record;
141};
142
143#define type_numhash st_hashtype_num
144static const struct st_hash_type st_hashtype_num = {
145 st_numcmp,
146 st_numhash,
147};
148
149static int st_strcmp(st_data_t, st_data_t);
150static st_index_t strhash(st_data_t);
151static const struct st_hash_type type_strhash = {
152 st_strcmp,
153 strhash,
154};
155
156static int st_locale_insensitive_strcasecmp_i(st_data_t lhs, st_data_t rhs);
157static st_index_t strcasehash(st_data_t);
158static const struct st_hash_type type_strcasehash = {
159 st_locale_insensitive_strcasecmp_i,
160 strcasehash,
161};
162
163/* Value used to catch uninitialized entries/bins during debugging.
164 There is a possibility for a false alarm, but its probability is
165 extremely small. */
166#define ST_INIT_VAL 0xafafafafafafafaf
167#define ST_INIT_VAL_BYTE 0xafa
168
169#ifdef RUBY
170#undef malloc
171#undef realloc
172#undef calloc
173#undef free
174#define malloc ruby_xmalloc
175#define calloc ruby_xcalloc
176#define realloc ruby_xrealloc
177#define free ruby_xfree
178#endif
179
180#define EQUAL(tab,x,y) ((x) == (y) || (*(tab)->type->compare)((x),(y)) == 0)
181#define PTR_EQUAL(tab, ptr, hash_val, key_) \
182 ((ptr)->hash == (hash_val) && EQUAL((tab), (key_), (ptr)->key))
183
184/* As PTR_EQUAL only its result is returned in RES. REBUILT_P is set
185 up to TRUE if the table is rebuilt during the comparison. */
186#define DO_PTR_EQUAL_CHECK(tab, ptr, hash_val, key, res, rebuilt_p) \
187 do { \
188 unsigned int _old_rebuilds_num = (tab)->rebuilds_num; \
189 res = PTR_EQUAL(tab, ptr, hash_val, key); \
190 rebuilt_p = _old_rebuilds_num != (tab)->rebuilds_num; \
191 } while (FALSE)
192
193/* Features of a table. */
195 /* Power of 2 used for number of allocated entries. */
196 unsigned char entry_power;
197 /* Power of 2 used for number of allocated bins. Depending on the
198 table size, the number of bins is 2-4 times more than the
199 number of entries. */
200 unsigned char bin_power;
201 /* Enumeration of sizes of bins (8-bit, 16-bit etc). */
202 unsigned char size_ind;
203 /* Bins are packed in words of type st_index_t. The following is
204 a size of bins counted by words. */
205 st_index_t bins_words;
206};
207
208/* Features of all possible size tables. */
209#if SIZEOF_ST_INDEX_T == 8
210#define MAX_POWER2 58
211static const struct st_features features[] = {
212 {0, 1, 0, 0x0},
213 {1, 2, 0, 0x1},
214 {2, 3, 0, 0x1},
215 {3, 4, 0, 0x2},
216 {4, 5, 0, 0x4},
217 {5, 6, 0, 0x8},
218 {6, 7, 0, 0x10},
219 {7, 8, 0, 0x20},
220 {8, 9, 1, 0x80},
221 {9, 10, 1, 0x100},
222 {10, 11, 1, 0x200},
223 {11, 12, 1, 0x400},
224 {12, 13, 1, 0x800},
225 {13, 14, 1, 0x1000},
226 {14, 15, 1, 0x2000},
227 {15, 16, 1, 0x4000},
228 {16, 17, 2, 0x10000},
229 {17, 18, 2, 0x20000},
230 {18, 19, 2, 0x40000},
231 {19, 20, 2, 0x80000},
232 {20, 21, 2, 0x100000},
233 {21, 22, 2, 0x200000},
234 {22, 23, 2, 0x400000},
235 {23, 24, 2, 0x800000},
236 {24, 25, 2, 0x1000000},
237 {25, 26, 2, 0x2000000},
238 {26, 27, 2, 0x4000000},
239 {27, 28, 2, 0x8000000},
240 {28, 29, 2, 0x10000000},
241 {29, 30, 2, 0x20000000},
242 {30, 31, 2, 0x40000000},
243 {31, 32, 2, 0x80000000},
244 {32, 33, 3, 0x200000000},
245 {33, 34, 3, 0x400000000},
246 {34, 35, 3, 0x800000000},
247 {35, 36, 3, 0x1000000000},
248 {36, 37, 3, 0x2000000000},
249 {37, 38, 3, 0x4000000000},
250 {38, 39, 3, 0x8000000000},
251 {39, 40, 3, 0x10000000000},
252 {40, 41, 3, 0x20000000000},
253 {41, 42, 3, 0x40000000000},
254 {42, 43, 3, 0x80000000000},
255 {43, 44, 3, 0x100000000000},
256 {44, 45, 3, 0x200000000000},
257 {45, 46, 3, 0x400000000000},
258 {46, 47, 3, 0x800000000000},
259 {47, 48, 3, 0x1000000000000},
260 {48, 49, 3, 0x2000000000000},
261 {49, 50, 3, 0x4000000000000},
262 {50, 51, 3, 0x8000000000000},
263 {51, 52, 3, 0x10000000000000},
264 {52, 53, 3, 0x20000000000000},
265 {53, 54, 3, 0x40000000000000},
266 {54, 55, 3, 0x80000000000000},
267 {55, 56, 3, 0x100000000000000},
268 {56, 57, 3, 0x200000000000000},
269 {57, 58, 3, 0x400000000000000},
270#define MAX_BINS_WORDS 0x800000000000000
271 {58, 59, 3, MAX_BINS_WORDS},
272};
273
274#else
275#define MAX_POWER2 27
276
277static const struct st_features features[] = {
278 {0, 1, 0, 0x1},
279 {1, 2, 0, 0x1},
280 {2, 3, 0, 0x2},
281 {3, 4, 0, 0x4},
282 {4, 5, 0, 0x8},
283 {5, 6, 0, 0x10},
284 {6, 7, 0, 0x20},
285 {7, 8, 0, 0x40},
286 {8, 9, 1, 0x100},
287 {9, 10, 1, 0x200},
288 {10, 11, 1, 0x400},
289 {11, 12, 1, 0x800},
290 {12, 13, 1, 0x1000},
291 {13, 14, 1, 0x2000},
292 {14, 15, 1, 0x4000},
293 {15, 16, 1, 0x8000},
294 {16, 17, 2, 0x20000},
295 {17, 18, 2, 0x40000},
296 {18, 19, 2, 0x80000},
297 {19, 20, 2, 0x100000},
298 {20, 21, 2, 0x200000},
299 {21, 22, 2, 0x400000},
300 {22, 23, 2, 0x800000},
301 {23, 24, 2, 0x1000000},
302 {24, 25, 2, 0x2000000},
303 {25, 26, 2, 0x4000000},
304 {26, 27, 2, 0x8000000},
305#define MAX_BINS_WORDS 0x10000000
306 {27, 28, 2, MAX_BINS_WORDS},
307};
308
309#endif
310
311#ifdef STATIC_ASSERT
312// Ensure MAX_POWER2 result in entries and bins memsize < SIZE_MAX.
313#define MAX_ADDRESSABLE_ENTRIES (SIZE_MAX / sizeof(st_table_entry))
314#define MAX_ENTRIES (((st_index_t) 1)<<MAX_POWER2)
315STATIC_ASSERT(max_power_entries_overflow, MAX_ENTRIES < MAX_ADDRESSABLE_ENTRIES);
316#define MAX_BINS_SIZE (SIZE_MAX - (MAX_ENTRIES * sizeof(st_table_entry)))
317STATIC_ASSERT(max_power_bins_overflow, (MAX_BINS_SIZE / sizeof(st_index_t)) > MAX_BINS_WORDS);
318#endif
319
320/* The reserved hash value and its substitution. */
321#define RESERVED_HASH_VAL (~(st_hash_t) 0)
322#define RESERVED_HASH_SUBSTITUTION_VAL ((st_hash_t) 0)
323
324static inline st_hash_t
325normalize_hash_value(st_hash_t hash)
326{
327 /* RESERVED_HASH_VAL is used for a deleted entry. Map it into
328 another value. Such mapping should be extremely rare. */
329 return hash == RESERVED_HASH_VAL ? RESERVED_HASH_SUBSTITUTION_VAL : hash;
330}
331
332/* Return hash value of KEY for table TAB. */
333static inline st_hash_t
334do_hash(st_data_t key, st_table *tab)
335{
336 st_hash_t hash = (st_hash_t)(tab->type->hash)(key);
337 return normalize_hash_value(hash);
338}
339
340/* Power of 2 defining the minimal number of allocated entries. */
341#define MINIMAL_POWER2 2
342
343#if MINIMAL_POWER2 < 2
344#error "MINIMAL_POWER2 should be >= 2"
345#endif
346
347/* If the power2 of the allocated `entries` is less than the following
348 value, don't allocate bins and use a linear search. */
349#define MAX_POWER2_FOR_TABLES_WITHOUT_BINS 4
350
351/* Return smallest n >= MINIMAL_POWER2 such 2^n > SIZE. */
352static int
353get_power2(st_index_t size)
354{
355 unsigned int n = ST_INDEX_BITS - nlz_intptr(size);
356 if (n <= MAX_POWER2)
357 return n < MINIMAL_POWER2 ? MINIMAL_POWER2 : n;
358#ifdef RUBY
359 /* Ran out of the table entries */
360 rb_raise(rb_eRuntimeError, "st_table too big");
361#endif
362 /* should raise exception */
363 return -1;
364}
365
366/* Return value of N-th bin in array BINS of table with bins size
367 index S. */
368static inline st_index_t
369get_bin(st_index_t *bins, int s, st_index_t n)
370{
371 return (s == 0 ? ((unsigned char *) bins)[n]
372 : s == 1 ? ((unsigned short *) bins)[n]
373 : s == 2 ? ((unsigned int *) bins)[n]
374 : ((st_index_t *) bins)[n]);
375}
376
377/* Set up N-th bin in array BINS of table with bins size index S to
378 value V. */
379static inline void
380set_bin(st_index_t *bins, int s, st_index_t n, st_index_t v)
381{
382 if (s == 0) ((unsigned char *) bins)[n] = (unsigned char) v;
383 else if (s == 1) ((unsigned short *) bins)[n] = (unsigned short) v;
384 else if (s == 2) ((unsigned int *) bins)[n] = (unsigned int) v;
385 else ((st_index_t *) bins)[n] = v;
386}
387
388/* These macros define reserved values for empty table bin and table
389 bin which contains a deleted entry. We will never use such values
390 for an entry index in bins. */
391#define EMPTY_BIN 0
392#define DELETED_BIN 1
393/* Base of a real entry index in the bins. */
394#define ENTRY_BASE 2
395
396/* Mark I-th bin of table TAB as empty, in other words not
397 corresponding to any entry. */
398#define MARK_BIN_EMPTY(tab, i) (set_bin((tab)->bins, get_size_ind(tab), i, EMPTY_BIN))
399
400/* Values used for not found entry and bin with given
401 characteristics. */
402#define UNDEFINED_ENTRY_IND (~(st_index_t) 0)
403#define UNDEFINED_BIN_IND (~(st_index_t) 0)
404
405/* Entry and bin values returned when we found a table rebuild during
406 the search. */
407#define REBUILT_TABLE_ENTRY_IND (~(st_index_t) 1)
408#define REBUILT_TABLE_BIN_IND (~(st_index_t) 1)
409
410/* Mark I-th bin of table TAB as corresponding to a deleted table
411 entry. Update number of entries in the table and number of bins
412 corresponding to deleted entries. */
413#define MARK_BIN_DELETED(tab, i) \
414 do { \
415 set_bin((tab)->bins, get_size_ind(tab), i, DELETED_BIN); \
416 } while (0)
417
418/* Macros to check that value B is used empty bins and bins
419 corresponding deleted entries. */
420#define EMPTY_BIN_P(b) ((b) == EMPTY_BIN)
421#define DELETED_BIN_P(b) ((b) == DELETED_BIN)
422#define EMPTY_OR_DELETED_BIN_P(b) ((b) <= DELETED_BIN)
423
424/* Macros to check empty bins and bins corresponding to deleted
425 entries. Bins are given by their index I in table TAB. */
426#define IND_EMPTY_BIN_P(tab, i) (EMPTY_BIN_P(get_bin((tab)->bins, get_size_ind(tab), i)))
427#define IND_DELETED_BIN_P(tab, i) (DELETED_BIN_P(get_bin((tab)->bins, get_size_ind(tab), i)))
428#define IND_EMPTY_OR_DELETED_BIN_P(tab, i) (EMPTY_OR_DELETED_BIN_P(get_bin((tab)->bins, get_size_ind(tab), i)))
429
430/* Macros for marking and checking deleted entries given by their
431 pointer E_PTR. */
432#define MARK_ENTRY_DELETED(e_ptr) ((e_ptr)->hash = RESERVED_HASH_VAL)
433#define DELETED_ENTRY_P(e_ptr) ((e_ptr)->hash == RESERVED_HASH_VAL)
434
435/* Return bin size index of table TAB. */
436static inline unsigned int
437get_size_ind(const st_table *tab)
438{
439 return tab->size_ind;
440}
441
442/* Return the number of allocated bins of table TAB. */
443static inline st_index_t
444get_bins_num(const st_table *tab)
445{
446 return ((st_index_t) 1)<<tab->bin_power;
447}
448
449/* Return mask for a bin index in table TAB. */
450static inline st_index_t
451bins_mask(const st_table *tab)
452{
453 return get_bins_num(tab) - 1;
454}
455
456/* Return the index of table TAB bin corresponding to
457 HASH_VALUE. */
458static inline st_index_t
459hash_bin(st_hash_t hash_value, st_table *tab)
460{
461 return hash_value & bins_mask(tab);
462}
463
464/* Return the number of allocated entries of table TAB. */
465static inline st_index_t
466get_allocated_entries(const st_table *tab)
467{
468 return ((st_index_t) 1)<<tab->entry_power;
469}
470
471/* Return size of the allocated bins of table TAB. */
472static inline st_index_t
473bins_size(const st_table *tab)
474{
475 return features[tab->entry_power].bins_words * sizeof (st_index_t);
476}
477
478/* Mark all bins of table TAB as empty. */
479static void
480initialize_bins(st_table *tab)
481{
482 memset(tab->bins, 0, bins_size(tab));
483}
484
485/* Make table TAB empty. */
486static void
487make_tab_empty(st_table *tab)
488{
489 tab->num_entries = 0;
490 tab->entries_start = tab->entries_bound = 0;
491 if (tab->bins != NULL)
492 initialize_bins(tab);
493}
494
495#ifdef HASH_LOG
496#ifdef HAVE_UNISTD_H
497#include <unistd.h>
498#endif
499static struct {
500 int all, total, num, str, strcase;
501} collision;
502
503/* Flag switching off output of package statistics at the end of
504 program. */
505static int init_st = 0;
506
507/* Output overall number of table searches and collisions into a
508 temporary file. */
509static void
510stat_col(void)
511{
512 char fname[10+sizeof(long)*3];
513 FILE *f;
514 if (!collision.total) return;
515 f = fopen((snprintf(fname, sizeof(fname), "/tmp/col%ld", (long)getpid()), fname), "w");
516 if (f == NULL)
517 return;
518 fprintf(f, "collision: %d / %d (%6.2f)\n", collision.all, collision.total,
519 ((double)collision.all / (collision.total)) * 100);
520 fprintf(f, "num: %d, str: %d, strcase: %d\n", collision.num, collision.str, collision.strcase);
521 fclose(f);
522}
523#endif
524
525st_table *
526st_init_existing_table_with_size(st_table *tab, const struct st_hash_type *type, st_index_t size)
527{
528 int n;
529
530#ifdef HASH_LOG
531#if HASH_LOG+0 < 0
532 {
533 const char *e = getenv("ST_HASH_LOG");
534 if (!e || !*e) init_st = 1;
535 }
536#endif
537 if (init_st == 0) {
538 init_st = 1;
539 atexit(stat_col);
540 }
541#endif
542
543 n = get_power2(size);
544#ifndef RUBY
545 if (n < 0)
546 return NULL;
547#endif
548
549 tab->type = type;
550 tab->entry_power = n;
551 tab->bin_power = features[n].bin_power;
552 tab->size_ind = features[n].size_ind;
553 if (n <= MAX_POWER2_FOR_TABLES_WITHOUT_BINS)
554 tab->bins = NULL;
555 else {
556 tab->bins = (st_index_t *) malloc(bins_size(tab));
557#ifndef RUBY
558 if (tab->bins == NULL) {
559 free(tab);
560 return NULL;
561 }
562#endif
563 }
564 tab->entries = (st_table_entry *) malloc(get_allocated_entries(tab)
565 * sizeof(st_table_entry));
566#ifndef RUBY
567 if (tab->entries == NULL) {
568 st_free_table(tab);
569 return NULL;
570 }
571#endif
572 make_tab_empty(tab);
573 tab->rebuilds_num = 0;
574 return tab;
575}
576
577/* Create and return table with TYPE which can hold at least SIZE
578 entries. The real number of entries which the table can hold is
579 the nearest power of two for SIZE. */
580st_table *
581st_init_table_with_size(const struct st_hash_type *type, st_index_t size)
582{
583 st_table *tab = malloc(sizeof(st_table));
584#ifndef RUBY
585 if (tab == NULL)
586 return NULL;
587#endif
588
589#ifdef RUBY
590 st_init_existing_table_with_size(tab, type, size);
591#else
592 if (st_init_existing_table_with_size(tab, type, size) == NULL) {
593 free(tab);
594 return NULL;
595 }
596#endif
597
598 return tab;
599}
600
601size_t
602st_table_size(const struct st_table *tbl)
603{
604 return tbl->num_entries;
605}
606
607/* Create and return table with TYPE which can hold a minimal number
608 of entries (see comments for get_power2). */
609st_table *
610st_init_table(const struct st_hash_type *type)
611{
612 return st_init_table_with_size(type, 0);
613}
614
615/* Create and return table which can hold a minimal number of
616 numbers. */
617st_table *
618st_init_numtable(void)
619{
620 return st_init_table(&type_numhash);
621}
622
623/* Create and return table which can hold SIZE numbers. */
624st_table *
625st_init_numtable_with_size(st_index_t size)
626{
627 return st_init_table_with_size(&type_numhash, size);
628}
629
630/* Create and return table which can hold a minimal number of
631 strings. */
632st_table *
633st_init_strtable(void)
634{
635 return st_init_table(&type_strhash);
636}
637
638/* Create and return table which can hold SIZE strings. */
639st_table *
640st_init_strtable_with_size(st_index_t size)
641{
642 return st_init_table_with_size(&type_strhash, size);
643}
644
645/* Create and return table which can hold a minimal number of strings
646 whose character case is ignored. */
647st_table *
648st_init_strcasetable(void)
649{
650 return st_init_table(&type_strcasehash);
651}
652
653/* Create and return table which can hold SIZE strings whose character
654 case is ignored. */
655st_table *
656st_init_strcasetable_with_size(st_index_t size)
657{
658 return st_init_table_with_size(&type_strcasehash, size);
659}
660
661/* Make table TAB empty. */
662void
663st_clear(st_table *tab)
664{
665 make_tab_empty(tab);
666 tab->rebuilds_num++;
667}
668
669/* Free table TAB space. */
670void
671st_free_table(st_table *tab)
672{
673 free(tab->bins);
674 free(tab->entries);
675 free(tab);
676}
677
678/* Return byte size of memory allocated for table TAB. */
679size_t
680st_memsize(const st_table *tab)
681{
682 RUBY_ASSERT(tab != NULL);
683 return(sizeof(st_table)
684 + (tab->bins == NULL ? 0 : bins_size(tab))
685 + get_allocated_entries(tab) * sizeof(st_table_entry));
686}
687
688static st_index_t
689find_table_entry_ind(st_table *tab, st_hash_t hash_value, st_data_t key);
690
691static st_index_t
692find_table_bin_ind(st_table *tab, st_hash_t hash_value, st_data_t key);
693
694static st_index_t
695find_table_bin_ind_direct(st_table *table, st_hash_t hash_value, st_data_t key);
696
697static st_index_t
698find_table_bin_ptr_and_reserve(st_table *tab, st_hash_t *hash_value,
699 st_data_t key, st_index_t *bin_ind);
700
701#ifdef HASH_LOG
702static void
703count_collision(const struct st_hash_type *type)
704{
705 collision.all++;
706 if (type == &type_numhash) {
707 collision.num++;
708 }
709 else if (type == &type_strhash) {
710 collision.strcase++;
711 }
712 else if (type == &type_strcasehash) {
713 collision.str++;
714 }
715}
716
717#define COLLISION (collision_check ? count_collision(tab->type) : (void)0)
718#define FOUND_BIN (collision_check ? collision.total++ : (void)0)
719#define collision_check 0
720#else
721#define COLLISION
722#define FOUND_BIN
723#endif
724
725/* If the number of entries in the table is at least REBUILD_THRESHOLD
726 times less than the entry array length, decrease the table
727 size. */
728#define REBUILD_THRESHOLD 4
729
730#if REBUILD_THRESHOLD < 2
731#error "REBUILD_THRESHOLD should be >= 2"
732#endif
733
734static void rebuild_table_with(st_table *const new_tab, st_table *const tab);
735static void rebuild_move_table(st_table *const new_tab, st_table *const tab);
736static void rebuild_cleanup(st_table *const tab);
737
738/* Rebuild table TAB. Rebuilding removes all deleted bins and entries
739 and can change size of the table entries and bins arrays.
740 Rebuilding is implemented by creation of a new table or by
741 compaction of the existing one. */
742static void
743rebuild_table(st_table *tab)
744{
745 if ((2 * tab->num_entries <= get_allocated_entries(tab)
746 && REBUILD_THRESHOLD * tab->num_entries > get_allocated_entries(tab))
747 || tab->num_entries < (1 << MINIMAL_POWER2)) {
748 /* Compaction: */
749 tab->num_entries = 0;
750 if (tab->bins != NULL)
751 initialize_bins(tab);
752 rebuild_table_with(tab, tab);
753 }
754 else {
755 st_table *new_tab;
756 /* This allocation could trigger GC and compaction. If tab is the
757 * gen_fields_tbl, then tab could have changed in size due to objects being
758 * freed and/or moved. Do not store attributes of tab before this line. */
759 new_tab = st_init_table_with_size(tab->type,
760 2 * tab->num_entries - 1);
761 rebuild_table_with(new_tab, tab);
762 rebuild_move_table(new_tab, tab);
763 }
764 rebuild_cleanup(tab);
765}
766
767static void
768rebuild_table_with(st_table *const new_tab, st_table *const tab)
769{
770 st_index_t i, ni;
771 unsigned int size_ind;
772 st_table_entry *new_entries;
773 st_table_entry *curr_entry_ptr;
774 st_index_t *bins;
775 st_index_t bin_ind;
776
777 new_entries = new_tab->entries;
778
779 ni = 0;
780 bins = new_tab->bins;
781 size_ind = get_size_ind(new_tab);
782 st_index_t bound = tab->entries_bound;
783 st_table_entry *entries = tab->entries;
784
785 for (i = tab->entries_start; i < bound; i++) {
786 curr_entry_ptr = &entries[i];
787 PREFETCH(entries + i + 1, 0);
788 if (EXPECT(DELETED_ENTRY_P(curr_entry_ptr), 0))
789 continue;
790 if (&new_entries[ni] != curr_entry_ptr)
791 new_entries[ni] = *curr_entry_ptr;
792 if (EXPECT(bins != NULL, 1)) {
793 bin_ind = find_table_bin_ind_direct(new_tab, curr_entry_ptr->hash,
794 curr_entry_ptr->key);
795 set_bin(bins, size_ind, bin_ind, ni + ENTRY_BASE);
796 }
797 new_tab->num_entries++;
798 ni++;
799 }
800
801 assert(new_tab->num_entries == tab->num_entries);
802}
803
804static void
805rebuild_move_table(st_table *const new_tab, st_table *const tab)
806{
807 tab->entry_power = new_tab->entry_power;
808 tab->bin_power = new_tab->bin_power;
809 tab->size_ind = new_tab->size_ind;
810 free(tab->bins);
811 tab->bins = new_tab->bins;
812 free(tab->entries);
813 tab->entries = new_tab->entries;
814 free(new_tab);
815}
816
817static void
818rebuild_cleanup(st_table *const tab)
819{
820 tab->entries_start = 0;
821 tab->entries_bound = tab->num_entries;
822 tab->rebuilds_num++;
823}
824
825/* Return the next secondary hash index for table TAB using previous
826 index IND and PERTURB. Finally modulo of the function becomes a
827 full *cycle linear congruential generator*, in other words it
828 guarantees traversing all table bins in extreme case.
829
830 According the Hull-Dobell theorem a generator
831 "Xnext = (a*Xprev + c) mod m" is a full cycle generator if and only if
832 o m and c are relatively prime
833 o a-1 is divisible by all prime factors of m
834 o a-1 is divisible by 4 if m is divisible by 4.
835
836 For our case a is 5, c is 1, and m is a power of two. */
837static inline st_index_t
838secondary_hash(st_index_t ind, st_table *tab, st_index_t *perturb)
839{
840 *perturb >>= 11;
841 ind = (ind << 2) + ind + *perturb + 1;
842 return hash_bin(ind, tab);
843}
844
845/* Find an entry with HASH_VALUE and KEY in TABLE using a linear
846 search. Return the index of the found entry in array `entries`.
847 If it is not found, return UNDEFINED_ENTRY_IND. If the table was
848 rebuilt during the search, return REBUILT_TABLE_ENTRY_IND. */
849static inline st_index_t
850find_entry(st_table *tab, st_hash_t hash_value, st_data_t key)
851{
852 int eq_p, rebuilt_p;
853 st_index_t i, bound;
854 st_table_entry *entries;
855
856 bound = tab->entries_bound;
857 entries = tab->entries;
858 for (i = tab->entries_start; i < bound; i++) {
859 DO_PTR_EQUAL_CHECK(tab, &entries[i], hash_value, key, eq_p, rebuilt_p);
860 if (EXPECT(rebuilt_p, 0))
861 return REBUILT_TABLE_ENTRY_IND;
862 if (eq_p)
863 return i;
864 }
865 return UNDEFINED_ENTRY_IND;
866}
867
868/* Use the quadratic probing. The method has a better data locality
869 but more collisions than the current approach. In average it
870 results in a bit slower search. */
871/*#define QUADRATIC_PROBE*/
872
873/* Return index of entry with HASH_VALUE and KEY in table TAB. If
874 there is no such entry, return UNDEFINED_ENTRY_IND. If the table
875 was rebuilt during the search, return REBUILT_TABLE_ENTRY_IND. */
876static st_index_t
877find_table_entry_ind(st_table *tab, st_hash_t hash_value, st_data_t key)
878{
879 int eq_p, rebuilt_p;
880 st_index_t ind;
881#ifdef QUADRATIC_PROBE
882 st_index_t d;
883#else
884 st_index_t perturb;
885#endif
886 st_index_t bin;
887 st_table_entry *entries = tab->entries;
888
889 ind = hash_bin(hash_value, tab);
890#ifdef QUADRATIC_PROBE
891 d = 1;
892#else
893 perturb = hash_value;
894#endif
895 FOUND_BIN;
896 for (;;) {
897 bin = get_bin(tab->bins, get_size_ind(tab), ind);
898 if (! EMPTY_OR_DELETED_BIN_P(bin)) {
899 DO_PTR_EQUAL_CHECK(tab, &entries[bin - ENTRY_BASE], hash_value, key, eq_p, rebuilt_p);
900 if (EXPECT(rebuilt_p, 0))
901 return REBUILT_TABLE_ENTRY_IND;
902 if (eq_p)
903 break;
904 }
905 else if (EMPTY_BIN_P(bin))
906 return UNDEFINED_ENTRY_IND;
907#ifdef QUADRATIC_PROBE
908 ind = hash_bin(ind + d, tab);
909 d++;
910#else
911 ind = secondary_hash(ind, tab, &perturb);
912#endif
913 COLLISION;
914 }
915 return bin;
916}
917
918/* Find and return index of table TAB bin corresponding to an entry
919 with HASH_VALUE and KEY. If there is no such bin, return
920 UNDEFINED_BIN_IND. If the table was rebuilt during the search,
921 return REBUILT_TABLE_BIN_IND. */
922static st_index_t
923find_table_bin_ind(st_table *tab, st_hash_t hash_value, st_data_t key)
924{
925 int eq_p, rebuilt_p;
926 st_index_t ind;
927#ifdef QUADRATIC_PROBE
928 st_index_t d;
929#else
930 st_index_t perturb;
931#endif
932 st_index_t bin;
933 st_table_entry *entries = tab->entries;
934
935 ind = hash_bin(hash_value, tab);
936#ifdef QUADRATIC_PROBE
937 d = 1;
938#else
939 perturb = hash_value;
940#endif
941 FOUND_BIN;
942 for (;;) {
943 bin = get_bin(tab->bins, get_size_ind(tab), ind);
944 if (! EMPTY_OR_DELETED_BIN_P(bin)) {
945 DO_PTR_EQUAL_CHECK(tab, &entries[bin - ENTRY_BASE], hash_value, key, eq_p, rebuilt_p);
946 if (EXPECT(rebuilt_p, 0))
947 return REBUILT_TABLE_BIN_IND;
948 if (eq_p)
949 break;
950 }
951 else if (EMPTY_BIN_P(bin))
952 return UNDEFINED_BIN_IND;
953#ifdef QUADRATIC_PROBE
954 ind = hash_bin(ind + d, tab);
955 d++;
956#else
957 ind = secondary_hash(ind, tab, &perturb);
958#endif
959 COLLISION;
960 }
961 return ind;
962}
963
964/* Find and return index of table TAB bin corresponding to an entry
965 with HASH_VALUE and KEY. The entry should be in the table
966 already. */
967static st_index_t
968find_table_bin_ind_direct(st_table *tab, st_hash_t hash_value, st_data_t key)
969{
970 st_index_t ind;
971#ifdef QUADRATIC_PROBE
972 st_index_t d;
973#else
974 st_index_t perturb;
975#endif
976 st_index_t bin;
977
978 ind = hash_bin(hash_value, tab);
979#ifdef QUADRATIC_PROBE
980 d = 1;
981#else
982 perturb = hash_value;
983#endif
984 FOUND_BIN;
985 for (;;) {
986 bin = get_bin(tab->bins, get_size_ind(tab), ind);
987 if (EMPTY_OR_DELETED_BIN_P(bin))
988 return ind;
989#ifdef QUADRATIC_PROBE
990 ind = hash_bin(ind + d, tab);
991 d++;
992#else
993 ind = secondary_hash(ind, tab, &perturb);
994#endif
995 COLLISION;
996 }
997}
998
999/* Return index of table TAB bin for HASH_VALUE and KEY through
1000 BIN_IND and the pointed value as the function result. Reserve the
1001 bin for inclusion of the corresponding entry into the table if it
1002 is not there yet. We always find such bin as bins array length is
1003 bigger entries array. Although we can reuse a deleted bin, the
1004 result bin value is always empty if the table has no entry with
1005 KEY. Return the entries array index of the found entry or
1006 UNDEFINED_ENTRY_IND if it is not found. If the table was rebuilt
1007 during the search, return REBUILT_TABLE_ENTRY_IND. */
1008static st_index_t
1009find_table_bin_ptr_and_reserve(st_table *tab, st_hash_t *hash_value,
1010 st_data_t key, st_index_t *bin_ind)
1011{
1012 int eq_p, rebuilt_p;
1013 st_index_t ind;
1014 st_hash_t curr_hash_value = *hash_value;
1015#ifdef QUADRATIC_PROBE
1016 st_index_t d;
1017#else
1018 st_index_t perturb;
1019#endif
1020 st_index_t entry_index;
1021 st_index_t first_deleted_bin_ind;
1022 st_table_entry *entries;
1023
1024 ind = hash_bin(curr_hash_value, tab);
1025#ifdef QUADRATIC_PROBE
1026 d = 1;
1027#else
1028 perturb = curr_hash_value;
1029#endif
1030 FOUND_BIN;
1031 first_deleted_bin_ind = UNDEFINED_BIN_IND;
1032 entries = tab->entries;
1033 for (;;) {
1034 entry_index = get_bin(tab->bins, get_size_ind(tab), ind);
1035 if (EMPTY_BIN_P(entry_index)) {
1036 tab->num_entries++;
1037 entry_index = UNDEFINED_ENTRY_IND;
1038 if (first_deleted_bin_ind != UNDEFINED_BIN_IND) {
1039 /* We can reuse bin of a deleted entry. */
1040 ind = first_deleted_bin_ind;
1041 MARK_BIN_EMPTY(tab, ind);
1042 }
1043 break;
1044 }
1045 else if (! DELETED_BIN_P(entry_index)) {
1046 DO_PTR_EQUAL_CHECK(tab, &entries[entry_index - ENTRY_BASE], curr_hash_value, key, eq_p, rebuilt_p);
1047 if (EXPECT(rebuilt_p, 0))
1048 return REBUILT_TABLE_ENTRY_IND;
1049 if (eq_p)
1050 break;
1051 }
1052 else if (first_deleted_bin_ind == UNDEFINED_BIN_IND)
1053 first_deleted_bin_ind = ind;
1054#ifdef QUADRATIC_PROBE
1055 ind = hash_bin(ind + d, tab);
1056 d++;
1057#else
1058 ind = secondary_hash(ind, tab, &perturb);
1059#endif
1060 COLLISION;
1061 }
1062 *bin_ind = ind;
1063 return entry_index;
1064}
1065
1066/* Find an entry with KEY in table TAB. Return non-zero if we found
1067 it. Set up *RECORD to the found entry record. */
1068int
1069st_lookup(st_table *tab, st_data_t key, st_data_t *value)
1070{
1071 st_index_t bin;
1072 st_hash_t hash = do_hash(key, tab);
1073
1074 retry:
1075 if (tab->bins == NULL) {
1076 bin = find_entry(tab, hash, key);
1077 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
1078 goto retry;
1079 if (bin == UNDEFINED_ENTRY_IND)
1080 return 0;
1081 }
1082 else {
1083 bin = find_table_entry_ind(tab, hash, key);
1084 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
1085 goto retry;
1086 if (bin == UNDEFINED_ENTRY_IND)
1087 return 0;
1088 bin -= ENTRY_BASE;
1089 }
1090 if (value != 0)
1091 *value = tab->entries[bin].record;
1092 return 1;
1093}
1094
1095/* Find an entry with KEY in table TAB. Return non-zero if we found
1096 it. Set up *RESULT to the found table entry key. */
1097int
1098st_get_key(st_table *tab, st_data_t key, st_data_t *result)
1099{
1100 st_index_t bin;
1101 st_hash_t hash = do_hash(key, tab);
1102
1103 retry:
1104 if (tab->bins == NULL) {
1105 bin = find_entry(tab, hash, key);
1106 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
1107 goto retry;
1108 if (bin == UNDEFINED_ENTRY_IND)
1109 return 0;
1110 }
1111 else {
1112 bin = find_table_entry_ind(tab, hash, key);
1113 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
1114 goto retry;
1115 if (bin == UNDEFINED_ENTRY_IND)
1116 return 0;
1117 bin -= ENTRY_BASE;
1118 }
1119 if (result != 0)
1120 *result = tab->entries[bin].key;
1121 return 1;
1122}
1123
1124/* Check the table and rebuild it if it is necessary. */
1125static inline void
1126rebuild_table_if_necessary (st_table *tab)
1127{
1128 st_index_t bound = tab->entries_bound;
1129
1130 if (bound == get_allocated_entries(tab))
1131 rebuild_table(tab);
1132}
1133
1134/* Insert (KEY, VALUE) into table TAB and return zero. If there is
1135 already entry with KEY in the table, return nonzero and update
1136 the value of the found entry. */
1137int
1138st_insert(st_table *tab, st_data_t key, st_data_t value)
1139{
1140 st_table_entry *entry;
1141 st_index_t bin;
1142 st_index_t ind;
1143 st_hash_t hash_value;
1144 st_index_t bin_ind;
1145 int new_p;
1146
1147 hash_value = do_hash(key, tab);
1148 retry:
1149 rebuild_table_if_necessary(tab);
1150 if (tab->bins == NULL) {
1151 bin = find_entry(tab, hash_value, key);
1152 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
1153 goto retry;
1154 new_p = bin == UNDEFINED_ENTRY_IND;
1155 if (new_p)
1156 tab->num_entries++;
1157 bin_ind = UNDEFINED_BIN_IND;
1158 }
1159 else {
1160 bin = find_table_bin_ptr_and_reserve(tab, &hash_value,
1161 key, &bin_ind);
1162 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
1163 goto retry;
1164 new_p = bin == UNDEFINED_ENTRY_IND;
1165 bin -= ENTRY_BASE;
1166 }
1167 if (new_p) {
1168 ind = tab->entries_bound++;
1169 entry = &tab->entries[ind];
1170 entry->hash = hash_value;
1171 entry->key = key;
1172 entry->record = value;
1173 if (bin_ind != UNDEFINED_BIN_IND)
1174 set_bin(tab->bins, get_size_ind(tab), bin_ind, ind + ENTRY_BASE);
1175 return 0;
1176 }
1177 tab->entries[bin].record = value;
1178 return 1;
1179}
1180
1181/* Insert (KEY, VALUE, HASH) into table TAB. The table should not have
1182 entry with KEY before the insertion. */
1183static inline void
1184st_add_direct_with_hash(st_table *tab,
1185 st_data_t key, st_data_t value, st_hash_t hash)
1186{
1187 st_table_entry *entry;
1188 st_index_t ind;
1189 st_index_t bin_ind;
1190
1191 assert(hash != RESERVED_HASH_VAL);
1192
1193 rebuild_table_if_necessary(tab);
1194 ind = tab->entries_bound++;
1195 entry = &tab->entries[ind];
1196 entry->hash = hash;
1197 entry->key = key;
1198 entry->record = value;
1199 tab->num_entries++;
1200 if (tab->bins != NULL) {
1201 bin_ind = find_table_bin_ind_direct(tab, hash, key);
1202 set_bin(tab->bins, get_size_ind(tab), bin_ind, ind + ENTRY_BASE);
1203 }
1204}
1205
1206void
1207rb_st_add_direct_with_hash(st_table *tab,
1208 st_data_t key, st_data_t value, st_hash_t hash)
1209{
1210 st_add_direct_with_hash(tab, key, value, normalize_hash_value(hash));
1211}
1212
1213/* Insert (KEY, VALUE) into table TAB. The table should not have
1214 entry with KEY before the insertion. */
1215void
1216st_add_direct(st_table *tab, st_data_t key, st_data_t value)
1217{
1218 st_hash_t hash_value;
1219
1220 hash_value = do_hash(key, tab);
1221 st_add_direct_with_hash(tab, key, value, hash_value);
1222}
1223
1224/* Insert (FUNC(KEY), VALUE) into table TAB and return zero. If
1225 there is already entry with KEY in the table, return nonzero and
1226 update the value of the found entry. */
1227int
1228st_insert2(st_table *tab, st_data_t key, st_data_t value,
1229 st_data_t (*func)(st_data_t))
1230{
1231 st_table_entry *entry;
1232 st_index_t bin;
1233 st_index_t ind;
1234 st_hash_t hash_value;
1235 st_index_t bin_ind;
1236 int new_p;
1237
1238 hash_value = do_hash(key, tab);
1239 retry:
1240 rebuild_table_if_necessary (tab);
1241 if (tab->bins == NULL) {
1242 bin = find_entry(tab, hash_value, key);
1243 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
1244 goto retry;
1245 new_p = bin == UNDEFINED_ENTRY_IND;
1246 if (new_p)
1247 tab->num_entries++;
1248 bin_ind = UNDEFINED_BIN_IND;
1249 }
1250 else {
1251 bin = find_table_bin_ptr_and_reserve(tab, &hash_value,
1252 key, &bin_ind);
1253 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
1254 goto retry;
1255 new_p = bin == UNDEFINED_ENTRY_IND;
1256 bin -= ENTRY_BASE;
1257 }
1258 if (new_p) {
1259 key = (*func)(key);
1260 ind = tab->entries_bound++;
1261 entry = &tab->entries[ind];
1262 entry->hash = hash_value;
1263 entry->key = key;
1264 entry->record = value;
1265 if (bin_ind != UNDEFINED_BIN_IND)
1266 set_bin(tab->bins, get_size_ind(tab), bin_ind, ind + ENTRY_BASE);
1267 return 0;
1268 }
1269 tab->entries[bin].record = value;
1270 return 1;
1271}
1272
1273/* Create a copy of old_tab into new_tab. */
1274st_table *
1275st_replace(st_table *new_tab, st_table *old_tab)
1276{
1277 *new_tab = *old_tab;
1278 if (old_tab->bins == NULL)
1279 new_tab->bins = NULL;
1280 else {
1281 new_tab->bins = (st_index_t *) malloc(bins_size(old_tab));
1282#ifndef RUBY
1283 if (new_tab->bins == NULL) {
1284 return NULL;
1285 }
1286#endif
1287 }
1288 new_tab->entries = (st_table_entry *) malloc(get_allocated_entries(old_tab)
1289 * sizeof(st_table_entry));
1290#ifndef RUBY
1291 if (new_tab->entries == NULL) {
1292 return NULL;
1293 }
1294#endif
1295 MEMCPY(new_tab->entries, old_tab->entries, st_table_entry,
1296 get_allocated_entries(old_tab));
1297 if (old_tab->bins != NULL)
1298 MEMCPY(new_tab->bins, old_tab->bins, char, bins_size(old_tab));
1299
1300 return new_tab;
1301}
1302
1303/* Create and return a copy of table OLD_TAB. */
1304st_table *
1305st_copy(st_table *old_tab)
1306{
1307 st_table *new_tab;
1308
1309 new_tab = (st_table *) malloc(sizeof(st_table));
1310#ifndef RUBY
1311 if (new_tab == NULL)
1312 return NULL;
1313#endif
1314
1315 if (st_replace(new_tab, old_tab) == NULL) {
1316 st_free_table(new_tab);
1317 return NULL;
1318 }
1319
1320 return new_tab;
1321}
1322
1323/* Update the entries start of table TAB after removing an entry
1324 with index N in the array entries. */
1325static inline void
1326update_range_for_deleted(st_table *tab, st_index_t n)
1327{
1328 /* Do not update entries_bound here. Otherwise, we can fill all
1329 bins by deleted entry value before rebuilding the table. */
1330 if (tab->entries_start == n) {
1331 st_index_t start = n + 1;
1332 st_index_t bound = tab->entries_bound;
1333 st_table_entry *entries = tab->entries;
1334 while (start < bound && DELETED_ENTRY_P(&entries[start])) start++;
1335 tab->entries_start = start;
1336 }
1337}
1338
1339/* Delete entry with KEY from table TAB, set up *VALUE (unless
1340 VALUE is zero) from deleted table entry, and return non-zero. If
1341 there is no entry with KEY in the table, clear *VALUE (unless VALUE
1342 is zero), and return zero. */
1343static int
1344st_general_delete(st_table *tab, st_data_t *key, st_data_t *value)
1345{
1346 st_table_entry *entry;
1347 st_index_t bin;
1348 st_index_t bin_ind;
1349 st_hash_t hash;
1350
1351 hash = do_hash(*key, tab);
1352 retry:
1353 if (tab->bins == NULL) {
1354 bin = find_entry(tab, hash, *key);
1355 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
1356 goto retry;
1357 if (bin == UNDEFINED_ENTRY_IND) {
1358 if (value != 0) *value = 0;
1359 return 0;
1360 }
1361 }
1362 else {
1363 bin_ind = find_table_bin_ind(tab, hash, *key);
1364 if (EXPECT(bin_ind == REBUILT_TABLE_BIN_IND, 0))
1365 goto retry;
1366 if (bin_ind == UNDEFINED_BIN_IND) {
1367 if (value != 0) *value = 0;
1368 return 0;
1369 }
1370 bin = get_bin(tab->bins, get_size_ind(tab), bin_ind) - ENTRY_BASE;
1371 MARK_BIN_DELETED(tab, bin_ind);
1372 }
1373 entry = &tab->entries[bin];
1374 *key = entry->key;
1375 if (value != 0) *value = entry->record;
1376 MARK_ENTRY_DELETED(entry);
1377 tab->num_entries--;
1378 update_range_for_deleted(tab, bin);
1379 return 1;
1380}
1381
1382int
1383st_delete(st_table *tab, st_data_t *key, st_data_t *value)
1384{
1385 return st_general_delete(tab, key, value);
1386}
1387
1388/* The function and other functions with suffix '_safe' or '_check'
1389 are originated from the previous implementation of the hash tables.
1390 It was necessary for correct deleting entries during traversing
1391 tables. The current implementation permits deletion during
1392 traversing without a specific way to do this. */
1393int
1394st_delete_safe(st_table *tab, st_data_t *key, st_data_t *value,
1395 st_data_t never ATTRIBUTE_UNUSED)
1396{
1397 return st_general_delete(tab, key, value);
1398}
1399
1400/* If table TAB is empty, clear *VALUE (unless VALUE is zero), and
1401 return zero. Otherwise, remove the first entry in the table.
1402 Return its key through KEY and its record through VALUE (unless
1403 VALUE is zero). */
1404int
1405st_shift(st_table *tab, st_data_t *key, st_data_t *value)
1406{
1407 st_index_t i, bound;
1408 st_index_t bin;
1409 st_table_entry *entries, *curr_entry_ptr;
1410 st_index_t bin_ind;
1411
1412 entries = tab->entries;
1413 bound = tab->entries_bound;
1414 for (i = tab->entries_start; i < bound; i++) {
1415 curr_entry_ptr = &entries[i];
1416 if (! DELETED_ENTRY_P(curr_entry_ptr)) {
1417 st_hash_t entry_hash = curr_entry_ptr->hash;
1418 st_data_t entry_key = curr_entry_ptr->key;
1419
1420 if (value != 0) *value = curr_entry_ptr->record;
1421 *key = entry_key;
1422 retry:
1423 if (tab->bins == NULL) {
1424 bin = find_entry(tab, entry_hash, entry_key);
1425 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0)) {
1426 entries = tab->entries;
1427 goto retry;
1428 }
1429 curr_entry_ptr = &entries[bin];
1430 }
1431 else {
1432 bin_ind = find_table_bin_ind(tab, entry_hash, entry_key);
1433 if (EXPECT(bin_ind == REBUILT_TABLE_BIN_IND, 0)) {
1434 entries = tab->entries;
1435 goto retry;
1436 }
1437 curr_entry_ptr = &entries[get_bin(tab->bins, get_size_ind(tab), bin_ind)
1438 - ENTRY_BASE];
1439 MARK_BIN_DELETED(tab, bin_ind);
1440 }
1441 MARK_ENTRY_DELETED(curr_entry_ptr);
1442 tab->num_entries--;
1443 update_range_for_deleted(tab, i);
1444 return 1;
1445 }
1446 }
1447 if (value != 0) *value = 0;
1448 return 0;
1449}
1450
1451/* See comments for function st_delete_safe. */
1452void
1453st_cleanup_safe(st_table *tab ATTRIBUTE_UNUSED,
1454 st_data_t never ATTRIBUTE_UNUSED)
1455{
1456}
1457
1458/* Find entry with KEY in table TAB, call FUNC with pointers to copies
1459 of the key and the value of the found entry, and non-zero as the
1460 3rd argument. If the entry is not found, call FUNC with a pointer
1461 to KEY, a pointer to zero, and a zero argument. If the call
1462 returns ST_CONTINUE, the table will have an entry with key and
1463 value returned by FUNC through the 1st and 2nd parameters. If the
1464 call of FUNC returns ST_DELETE, the table will not have entry with
1465 KEY. The function returns flag of that the entry with KEY was in
1466 the table before the call. */
1467int
1468st_update(st_table *tab, st_data_t key,
1469 st_update_callback_func *func, st_data_t arg)
1470{
1471 st_table_entry *entry = NULL; /* to avoid uninitialized value warning */
1472 st_index_t bin = 0; /* Ditto */
1473 st_table_entry *entries;
1474 st_index_t bin_ind;
1475 st_data_t value = 0, old_key;
1476 int retval, existing;
1477 st_hash_t hash = do_hash(key, tab);
1478
1479 retry:
1480 entries = tab->entries;
1481 if (tab->bins == NULL) {
1482 bin = find_entry(tab, hash, key);
1483 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
1484 goto retry;
1485 existing = bin != UNDEFINED_ENTRY_IND;
1486 entry = &entries[bin];
1487 bin_ind = UNDEFINED_BIN_IND;
1488 }
1489 else {
1490 bin_ind = find_table_bin_ind(tab, hash, key);
1491 if (EXPECT(bin_ind == REBUILT_TABLE_BIN_IND, 0))
1492 goto retry;
1493 existing = bin_ind != UNDEFINED_BIN_IND;
1494 if (existing) {
1495 bin = get_bin(tab->bins, get_size_ind(tab), bin_ind) - ENTRY_BASE;
1496 entry = &entries[bin];
1497 }
1498 }
1499 if (existing) {
1500 key = entry->key;
1501 value = entry->record;
1502 }
1503 old_key = key;
1504
1505 unsigned int rebuilds_num = tab->rebuilds_num;
1506
1507 retval = (*func)(&key, &value, arg, existing);
1508
1509 // We need to make sure that the callback didn't cause a table rebuild
1510 // Ideally we would make sure no operations happened
1511 assert(rebuilds_num == tab->rebuilds_num);
1512 (void)rebuilds_num;
1513
1514 switch (retval) {
1515 case ST_CONTINUE:
1516 if (! existing) {
1517 st_add_direct_with_hash(tab, key, value, hash);
1518 break;
1519 }
1520 if (old_key != key) {
1521 entry->key = key;
1522 }
1523 entry->record = value;
1524 break;
1525 case ST_DELETE:
1526 if (existing) {
1527 if (bin_ind != UNDEFINED_BIN_IND)
1528 MARK_BIN_DELETED(tab, bin_ind);
1529 MARK_ENTRY_DELETED(entry);
1530 tab->num_entries--;
1531 update_range_for_deleted(tab, bin);
1532 }
1533 break;
1534 }
1535 return existing;
1536}
1537
1538/* Traverse all entries in table TAB calling FUNC with current entry
1539 key and value and zero. If the call returns ST_STOP, stop
1540 traversing. If the call returns ST_DELETE, delete the current
1541 entry from the table. In case of ST_CHECK or ST_CONTINUE, continue
1542 traversing. The function returns zero unless an error is found.
1543 CHECK_P is flag of st_foreach_check call. The behavior is a bit
1544 different for ST_CHECK and when the current element is removed
1545 during traversing. */
1546static inline int
1547st_general_foreach(st_table *tab, st_foreach_check_callback_func *func, st_update_callback_func *replace, st_data_t arg,
1548 int check_p)
1549{
1550 st_index_t bin;
1551 st_index_t bin_ind;
1552 st_table_entry *entries, *curr_entry_ptr;
1553 enum st_retval retval;
1554 st_index_t i, rebuilds_num;
1555 st_hash_t hash;
1556 st_data_t key;
1557 int error_p, packed_p = tab->bins == NULL;
1558
1559 entries = tab->entries;
1560 /* The bound can change inside the loop even without rebuilding
1561 the table, e.g. by an entry insertion. */
1562 for (i = tab->entries_start; i < tab->entries_bound; i++) {
1563 curr_entry_ptr = &entries[i];
1564 if (EXPECT(DELETED_ENTRY_P(curr_entry_ptr), 0))
1565 continue;
1566 key = curr_entry_ptr->key;
1567 rebuilds_num = tab->rebuilds_num;
1568 hash = curr_entry_ptr->hash;
1569 retval = (*func)(key, curr_entry_ptr->record, arg, 0);
1570
1571 if (retval == ST_REPLACE && replace) {
1572 st_data_t value;
1573 value = curr_entry_ptr->record;
1574 retval = (*replace)(&key, &value, arg, TRUE);
1575 curr_entry_ptr->key = key;
1576 curr_entry_ptr->record = value;
1577 }
1578
1579 if (rebuilds_num != tab->rebuilds_num) {
1580 retry:
1581 entries = tab->entries;
1582 packed_p = tab->bins == NULL;
1583 if (packed_p) {
1584 i = find_entry(tab, hash, key);
1585 if (EXPECT(i == REBUILT_TABLE_ENTRY_IND, 0))
1586 goto retry;
1587 error_p = i == UNDEFINED_ENTRY_IND;
1588 }
1589 else {
1590 i = find_table_entry_ind(tab, hash, key);
1591 if (EXPECT(i == REBUILT_TABLE_ENTRY_IND, 0))
1592 goto retry;
1593 error_p = i == UNDEFINED_ENTRY_IND;
1594 i -= ENTRY_BASE;
1595 }
1596 if (error_p && check_p) {
1597 /* call func with error notice */
1598 retval = (*func)(0, 0, arg, 1);
1599 return 1;
1600 }
1601 curr_entry_ptr = &entries[i];
1602 }
1603 switch (retval) {
1604 case ST_REPLACE:
1605 break;
1606 case ST_CONTINUE:
1607 break;
1608 case ST_CHECK:
1609 if (check_p)
1610 break;
1611 case ST_STOP:
1612 return 0;
1613 case ST_DELETE: {
1614 st_data_t key = curr_entry_ptr->key;
1615
1616 again:
1617 if (packed_p) {
1618 bin = find_entry(tab, hash, key);
1619 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
1620 goto again;
1621 if (bin == UNDEFINED_ENTRY_IND)
1622 break;
1623 }
1624 else {
1625 bin_ind = find_table_bin_ind(tab, hash, key);
1626 if (EXPECT(bin_ind == REBUILT_TABLE_BIN_IND, 0))
1627 goto again;
1628 if (bin_ind == UNDEFINED_BIN_IND)
1629 break;
1630 bin = get_bin(tab->bins, get_size_ind(tab), bin_ind) - ENTRY_BASE;
1631 MARK_BIN_DELETED(tab, bin_ind);
1632 }
1633 curr_entry_ptr = &entries[bin];
1634 MARK_ENTRY_DELETED(curr_entry_ptr);
1635 tab->num_entries--;
1636 update_range_for_deleted(tab, bin);
1637 break;
1638 }
1639 }
1640 }
1641 return 0;
1642}
1643
1644int
1645st_foreach_with_replace(st_table *tab, st_foreach_check_callback_func *func, st_update_callback_func *replace, st_data_t arg)
1646{
1647 return st_general_foreach(tab, func, replace, arg, TRUE);
1648}
1649
1650struct functor {
1651 st_foreach_callback_func *func;
1652 st_data_t arg;
1653};
1654
1655static int
1656apply_functor(st_data_t k, st_data_t v, st_data_t d, int _)
1657{
1658 const struct functor *f = (void *)d;
1659 return f->func(k, v, f->arg);
1660}
1661
1662int
1663st_foreach(st_table *tab, st_foreach_callback_func *func, st_data_t arg)
1664{
1665 const struct functor f = { func, arg };
1666 return st_general_foreach(tab, apply_functor, 0, (st_data_t)&f, FALSE);
1667}
1668
1669/* See comments for function st_delete_safe. */
1670int
1671st_foreach_check(st_table *tab, st_foreach_check_callback_func *func, st_data_t arg,
1672 st_data_t never ATTRIBUTE_UNUSED)
1673{
1674 return st_general_foreach(tab, func, 0, arg, TRUE);
1675}
1676
1677/* Set up array KEYS by at most SIZE keys of head table TAB entries.
1678 Return the number of keys set up in array KEYS. */
1679static inline st_index_t
1680st_general_keys(st_table *tab, st_data_t *keys, st_index_t size)
1681{
1682 st_index_t i, bound;
1683 st_data_t key, *keys_start, *keys_end;
1684 st_table_entry *curr_entry_ptr, *entries = tab->entries;
1685
1686 bound = tab->entries_bound;
1687 keys_start = keys;
1688 keys_end = keys + size;
1689 for (i = tab->entries_start; i < bound; i++) {
1690 if (keys == keys_end)
1691 break;
1692 curr_entry_ptr = &entries[i];
1693 key = curr_entry_ptr->key;
1694 if (! DELETED_ENTRY_P(curr_entry_ptr))
1695 *keys++ = key;
1696 }
1697
1698 return keys - keys_start;
1699}
1700
1701st_index_t
1702st_keys(st_table *tab, st_data_t *keys, st_index_t size)
1703{
1704 return st_general_keys(tab, keys, size);
1705}
1706
1707/* See comments for function st_delete_safe. */
1708st_index_t
1709st_keys_check(st_table *tab, st_data_t *keys, st_index_t size,
1710 st_data_t never ATTRIBUTE_UNUSED)
1711{
1712 return st_general_keys(tab, keys, size);
1713}
1714
1715/* Set up array VALUES by at most SIZE values of head table TAB
1716 entries. Return the number of values set up in array VALUES. */
1717static inline st_index_t
1718st_general_values(st_table *tab, st_data_t *values, st_index_t size)
1719{
1720 st_index_t i, bound;
1721 st_data_t *values_start, *values_end;
1722 st_table_entry *curr_entry_ptr, *entries = tab->entries;
1723
1724 values_start = values;
1725 values_end = values + size;
1726 bound = tab->entries_bound;
1727 for (i = tab->entries_start; i < bound; i++) {
1728 if (values == values_end)
1729 break;
1730 curr_entry_ptr = &entries[i];
1731 if (! DELETED_ENTRY_P(curr_entry_ptr))
1732 *values++ = curr_entry_ptr->record;
1733 }
1734
1735 return values - values_start;
1736}
1737
1738st_index_t
1739st_values(st_table *tab, st_data_t *values, st_index_t size)
1740{
1741 return st_general_values(tab, values, size);
1742}
1743
1744/* See comments for function st_delete_safe. */
1745st_index_t
1746st_values_check(st_table *tab, st_data_t *values, st_index_t size,
1747 st_data_t never ATTRIBUTE_UNUSED)
1748{
1749 return st_general_values(tab, values, size);
1750}
1751
1752#define FNV1_32A_INIT 0x811c9dc5
1753
1754/*
1755 * 32 bit magic FNV-1a prime
1756 */
1757#define FNV_32_PRIME 0x01000193
1758
1759/* __POWERPC__ added to accommodate Darwin case. */
1760#ifndef UNALIGNED_WORD_ACCESS
1761# if defined(__i386) || defined(__i386__) || defined(_M_IX86) || \
1762 defined(__x86_64) || defined(__x86_64__) || defined(_M_AMD64) || \
1763 defined(__powerpc64__) || defined(__POWERPC__) || defined(__aarch64__) || \
1764 defined(__mc68020__)
1765# define UNALIGNED_WORD_ACCESS 1
1766# endif
1767#endif
1768#ifndef UNALIGNED_WORD_ACCESS
1769# define UNALIGNED_WORD_ACCESS 0
1770#endif
1771
1772/* This hash function is quite simplified MurmurHash3
1773 * Simplification is legal, cause most of magic still happens in finalizator.
1774 * And finalizator is almost the same as in MurmurHash3 */
1775#define BIG_CONSTANT(x,y) ((st_index_t)(x)<<32|(st_index_t)(y))
1776#define ROTL(x,n) ((x)<<(n)|(x)>>(SIZEOF_ST_INDEX_T*CHAR_BIT-(n)))
1777
1778#if ST_INDEX_BITS <= 32
1779#define C1 (st_index_t)0xcc9e2d51
1780#define C2 (st_index_t)0x1b873593
1781#else
1782#define C1 BIG_CONSTANT(0x87c37b91,0x114253d5);
1783#define C2 BIG_CONSTANT(0x4cf5ad43,0x2745937f);
1784#endif
1785NO_SANITIZE("unsigned-integer-overflow", static inline st_index_t murmur_step(st_index_t h, st_index_t k));
1786NO_SANITIZE("unsigned-integer-overflow", static inline st_index_t murmur_finish(st_index_t h));
1787NO_SANITIZE("unsigned-integer-overflow", extern st_index_t st_hash(const void *ptr, size_t len, st_index_t h));
1788
1789static inline st_index_t
1790murmur_step(st_index_t h, st_index_t k)
1791{
1792#if ST_INDEX_BITS <= 32
1793#define r1 (17)
1794#define r2 (11)
1795#else
1796#define r1 (33)
1797#define r2 (24)
1798#endif
1799 k *= C1;
1800 h ^= ROTL(k, r1);
1801 h *= C2;
1802 h = ROTL(h, r2);
1803 return h;
1804}
1805#undef r1
1806#undef r2
1807
1808static inline st_index_t
1809murmur_finish(st_index_t h)
1810{
1811#if ST_INDEX_BITS <= 32
1812#define r1 (16)
1813#define r2 (13)
1814#define r3 (16)
1815 const st_index_t c1 = 0x85ebca6b;
1816 const st_index_t c2 = 0xc2b2ae35;
1817#else
1818/* values are taken from Mix13 on http://zimbry.blogspot.ru/2011/09/better-bit-mixing-improving-on.html */
1819#define r1 (30)
1820#define r2 (27)
1821#define r3 (31)
1822 const st_index_t c1 = BIG_CONSTANT(0xbf58476d,0x1ce4e5b9);
1823 const st_index_t c2 = BIG_CONSTANT(0x94d049bb,0x133111eb);
1824#endif
1825#if ST_INDEX_BITS > 64
1826 h ^= h >> 64;
1827 h *= c2;
1828 h ^= h >> 65;
1829#endif
1830 h ^= h >> r1;
1831 h *= c1;
1832 h ^= h >> r2;
1833 h *= c2;
1834 h ^= h >> r3;
1835 return h;
1836}
1837#undef r1
1838#undef r2
1839#undef r3
1840
1841st_index_t
1842st_hash(const void *ptr, size_t len, st_index_t h)
1843{
1844 const char *data = ptr;
1845 st_index_t t = 0;
1846 size_t l = len;
1847
1848#define data_at(n) (st_index_t)((unsigned char)data[(n)])
1849#define UNALIGNED_ADD_4 UNALIGNED_ADD(2); UNALIGNED_ADD(1); UNALIGNED_ADD(0)
1850#if SIZEOF_ST_INDEX_T > 4
1851#define UNALIGNED_ADD_8 UNALIGNED_ADD(6); UNALIGNED_ADD(5); UNALIGNED_ADD(4); UNALIGNED_ADD(3); UNALIGNED_ADD_4
1852#if SIZEOF_ST_INDEX_T > 8
1853#define UNALIGNED_ADD_16 UNALIGNED_ADD(14); UNALIGNED_ADD(13); UNALIGNED_ADD(12); UNALIGNED_ADD(11); \
1854 UNALIGNED_ADD(10); UNALIGNED_ADD(9); UNALIGNED_ADD(8); UNALIGNED_ADD(7); UNALIGNED_ADD_8
1855#define UNALIGNED_ADD_ALL UNALIGNED_ADD_16
1856#endif
1857#define UNALIGNED_ADD_ALL UNALIGNED_ADD_8
1858#else
1859#define UNALIGNED_ADD_ALL UNALIGNED_ADD_4
1860#endif
1861#undef SKIP_TAIL
1862 if (len >= sizeof(st_index_t)) {
1863#if !UNALIGNED_WORD_ACCESS
1864 int align = (int)((st_data_t)data % sizeof(st_index_t));
1865 if (align) {
1866 st_index_t d = 0;
1867 int sl, sr, pack;
1868
1869 switch (align) {
1870#ifdef WORDS_BIGENDIAN
1871# define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \
1872 t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 2)
1873#else
1874# define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \
1875 t |= data_at(n) << CHAR_BIT*(n)
1876#endif
1877 UNALIGNED_ADD_ALL;
1878#undef UNALIGNED_ADD
1879 }
1880
1881#ifdef WORDS_BIGENDIAN
1882 t >>= (CHAR_BIT * align) - CHAR_BIT;
1883#else
1884 t <<= (CHAR_BIT * align);
1885#endif
1886
1887 data += sizeof(st_index_t)-align;
1888 len -= sizeof(st_index_t)-align;
1889
1890 sl = CHAR_BIT * (SIZEOF_ST_INDEX_T-align);
1891 sr = CHAR_BIT * align;
1892
1893 while (len >= sizeof(st_index_t)) {
1894 d = *(st_index_t *)data;
1895#ifdef WORDS_BIGENDIAN
1896 t = (t << sr) | (d >> sl);
1897#else
1898 t = (t >> sr) | (d << sl);
1899#endif
1900 h = murmur_step(h, t);
1901 t = d;
1902 data += sizeof(st_index_t);
1903 len -= sizeof(st_index_t);
1904 }
1905
1906 pack = len < (size_t)align ? (int)len : align;
1907 d = 0;
1908 switch (pack) {
1909#ifdef WORDS_BIGENDIAN
1910# define UNALIGNED_ADD(n) case (n) + 1: \
1911 d |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
1912#else
1913# define UNALIGNED_ADD(n) case (n) + 1: \
1914 d |= data_at(n) << CHAR_BIT*(n)
1915#endif
1916 UNALIGNED_ADD_ALL;
1917#undef UNALIGNED_ADD
1918 }
1919#ifdef WORDS_BIGENDIAN
1920 t = (t << sr) | (d >> sl);
1921#else
1922 t = (t >> sr) | (d << sl);
1923#endif
1924
1925 if (len < (size_t)align) goto skip_tail;
1926# define SKIP_TAIL 1
1927 h = murmur_step(h, t);
1928 data += pack;
1929 len -= pack;
1930 }
1931 else
1932#endif
1933#ifdef HAVE_BUILTIN___BUILTIN_ASSUME_ALIGNED
1934#define aligned_data __builtin_assume_aligned(data, sizeof(st_index_t))
1935#else
1936#define aligned_data data
1937#endif
1938 {
1939 do {
1940 h = murmur_step(h, *(st_index_t *)aligned_data);
1941 data += sizeof(st_index_t);
1942 len -= sizeof(st_index_t);
1943 } while (len >= sizeof(st_index_t));
1944 }
1945 }
1946
1947 t = 0;
1948 switch (len) {
1949#if UNALIGNED_WORD_ACCESS && SIZEOF_ST_INDEX_T <= 8 && CHAR_BIT == 8
1950 /* in this case byteorder doesn't really matter */
1951#if SIZEOF_ST_INDEX_T > 4
1952 case 7: t |= data_at(6) << 48;
1953 case 6: t |= data_at(5) << 40;
1954 case 5: t |= data_at(4) << 32;
1955 case 4:
1956 t |= (st_index_t)*(uint32_t*)aligned_data;
1957 goto skip_tail;
1958# define SKIP_TAIL 1
1959#endif
1960 case 3: t |= data_at(2) << 16;
1961 case 2: t |= data_at(1) << 8;
1962 case 1: t |= data_at(0);
1963#else
1964#ifdef WORDS_BIGENDIAN
1965# define UNALIGNED_ADD(n) case (n) + 1: \
1966 t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
1967#else
1968# define UNALIGNED_ADD(n) case (n) + 1: \
1969 t |= data_at(n) << CHAR_BIT*(n)
1970#endif
1971 UNALIGNED_ADD_ALL;
1972#undef UNALIGNED_ADD
1973#endif
1974#ifdef SKIP_TAIL
1975 skip_tail:
1976#endif
1977 h ^= t; h -= ROTL(t, 7);
1978 h *= C2;
1979 }
1980 h ^= l;
1981#undef aligned_data
1982
1983 return murmur_finish(h);
1984}
1985
1986st_index_t
1987st_hash_uint32(st_index_t h, uint32_t i)
1988{
1989 return murmur_step(h, i);
1990}
1991
1992NO_SANITIZE("unsigned-integer-overflow", extern st_index_t st_hash_uint(st_index_t h, st_index_t i));
1993st_index_t
1994st_hash_uint(st_index_t h, st_index_t i)
1995{
1996 i += h;
1997/* no matter if it is BigEndian or LittleEndian,
1998 * we hash just integers */
1999#if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8
2000 h = murmur_step(h, i >> 8*8);
2001#endif
2002 h = murmur_step(h, i);
2003 return h;
2004}
2005
2006st_index_t
2007st_hash_end(st_index_t h)
2008{
2009 h = murmur_finish(h);
2010 return h;
2011}
2012
2013#undef st_hash_start
2014st_index_t
2015rb_st_hash_start(st_index_t h)
2016{
2017 return h;
2018}
2019
2020static st_index_t
2021strhash(st_data_t arg)
2022{
2023 register const char *string = (const char *)arg;
2024 return st_hash(string, strlen(string), FNV1_32A_INIT);
2025}
2026
2027int
2028st_locale_insensitive_strcasecmp(const char *s1, const char *s2)
2029{
2030 char c1, c2;
2031
2032 while (1) {
2033 c1 = *s1++;
2034 c2 = *s2++;
2035 if (c1 == '\0' || c2 == '\0') {
2036 if (c1 != '\0') return 1;
2037 if (c2 != '\0') return -1;
2038 return 0;
2039 }
2040 if (('A' <= c1) && (c1 <= 'Z')) c1 += 'a' - 'A';
2041 if (('A' <= c2) && (c2 <= 'Z')) c2 += 'a' - 'A';
2042 if (c1 != c2) {
2043 if (c1 > c2)
2044 return 1;
2045 else
2046 return -1;
2047 }
2048 }
2049}
2050
2051int
2052st_locale_insensitive_strncasecmp(const char *s1, const char *s2, size_t n)
2053{
2054 char c1, c2;
2055 size_t i;
2056
2057 for (i = 0; i < n; i++) {
2058 c1 = *s1++;
2059 c2 = *s2++;
2060 if (c1 == '\0' || c2 == '\0') {
2061 if (c1 != '\0') return 1;
2062 if (c2 != '\0') return -1;
2063 return 0;
2064 }
2065 if (('A' <= c1) && (c1 <= 'Z')) c1 += 'a' - 'A';
2066 if (('A' <= c2) && (c2 <= 'Z')) c2 += 'a' - 'A';
2067 if (c1 != c2) {
2068 if (c1 > c2)
2069 return 1;
2070 else
2071 return -1;
2072 }
2073 }
2074 return 0;
2075}
2076
2077static int
2078st_strcmp(st_data_t lhs, st_data_t rhs)
2079{
2080 const char *s1 = (char *)lhs;
2081 const char *s2 = (char *)rhs;
2082 return strcmp(s1, s2);
2083}
2084
2085static int
2086st_locale_insensitive_strcasecmp_i(st_data_t lhs, st_data_t rhs)
2087{
2088 const char *s1 = (char *)lhs;
2089 const char *s2 = (char *)rhs;
2090 return st_locale_insensitive_strcasecmp(s1, s2);
2091}
2092
2093NO_SANITIZE("unsigned-integer-overflow", PUREFUNC(static st_index_t strcasehash(st_data_t)));
2094static st_index_t
2095strcasehash(st_data_t arg)
2096{
2097 register const char *string = (const char *)arg;
2098 register st_index_t hval = FNV1_32A_INIT;
2099
2100 /*
2101 * FNV-1a hash each octet in the buffer
2102 */
2103 while (*string) {
2104 unsigned int c = (unsigned char)*string++;
2105 if ((unsigned int)(c - 'A') <= ('Z' - 'A')) c += 'a' - 'A';
2106 hval ^= c;
2107
2108 /* multiply by the 32 bit FNV magic prime mod 2^32 */
2109 hval *= FNV_32_PRIME;
2110 }
2111 return hval;
2112}
2113
2114int
2115st_numcmp(st_data_t x, st_data_t y)
2116{
2117 return x != y;
2118}
2119
2120st_index_t
2121st_numhash(st_data_t n)
2122{
2123 enum {s1 = 11, s2 = 3};
2124 return (st_index_t)((n>>s1|(n<<s2)) ^ (n>>s2));
2125}
2126
2127#ifdef RUBY
2128/* Expand TAB to be suitable for holding SIZ entries in total.
2129 Pre-existing entries remain not deleted inside of TAB, but its bins
2130 are cleared to expect future reconstruction. See rehash below. */
2131static void
2132st_expand_table(st_table *tab, st_index_t siz)
2133{
2134 st_table *tmp;
2135 st_index_t n;
2136
2137 if (siz <= get_allocated_entries(tab))
2138 return; /* enough room already */
2139
2140 tmp = st_init_table_with_size(tab->type, siz);
2141 n = get_allocated_entries(tab);
2142 MEMCPY(tmp->entries, tab->entries, st_table_entry, n);
2143 free(tab->entries);
2144 free(tab->bins);
2145 free(tmp->bins);
2146 tab->entry_power = tmp->entry_power;
2147 tab->bin_power = tmp->bin_power;
2148 tab->size_ind = tmp->size_ind;
2149 tab->entries = tmp->entries;
2150 tab->bins = NULL;
2151 tab->rebuilds_num++;
2152 free(tmp);
2153}
2154
2155/* Rehash using linear search. Return TRUE if we found that the table
2156 was rebuilt. */
2157static int
2158st_rehash_linear(st_table *tab)
2159{
2160 int eq_p, rebuilt_p;
2161 st_index_t i, j;
2162 st_table_entry *p, *q;
2163
2164 free(tab->bins);
2165 tab->bins = NULL;
2166
2167 for (i = tab->entries_start; i < tab->entries_bound; i++) {
2168 p = &tab->entries[i];
2169 if (DELETED_ENTRY_P(p))
2170 continue;
2171 for (j = i + 1; j < tab->entries_bound; j++) {
2172 q = &tab->entries[j];
2173 if (DELETED_ENTRY_P(q))
2174 continue;
2175 DO_PTR_EQUAL_CHECK(tab, p, q->hash, q->key, eq_p, rebuilt_p);
2176 if (EXPECT(rebuilt_p, 0))
2177 return TRUE;
2178 if (eq_p) {
2179 *p = *q;
2180 MARK_ENTRY_DELETED(q);
2181 tab->num_entries--;
2182 update_range_for_deleted(tab, j);
2183 }
2184 }
2185 }
2186 return FALSE;
2187}
2188
2189/* Rehash using index. Return TRUE if we found that the table was
2190 rebuilt. */
2191static int
2192st_rehash_indexed(st_table *tab)
2193{
2194 int eq_p, rebuilt_p;
2195 st_index_t i;
2196 st_index_t const n = bins_size(tab);
2197 unsigned int const size_ind = get_size_ind(tab);
2198 st_index_t *bins = realloc(tab->bins, n);
2199 tab->bins = bins;
2200 initialize_bins(tab);
2201 for (i = tab->entries_start; i < tab->entries_bound; i++) {
2202 st_table_entry *p = &tab->entries[i];
2203 st_index_t ind;
2204#ifdef QUADRATIC_PROBE
2205 st_index_t d = 1;
2206#else
2207 st_index_t perturb = p->hash;
2208#endif
2209
2210 if (DELETED_ENTRY_P(p))
2211 continue;
2212
2213 ind = hash_bin(p->hash, tab);
2214 for (;;) {
2215 st_index_t bin = get_bin(bins, size_ind, ind);
2216 if (EMPTY_OR_DELETED_BIN_P(bin)) {
2217 /* ok, new room */
2218 set_bin(bins, size_ind, ind, i + ENTRY_BASE);
2219 break;
2220 }
2221 else {
2222 st_table_entry *q = &tab->entries[bin - ENTRY_BASE];
2223 DO_PTR_EQUAL_CHECK(tab, q, p->hash, p->key, eq_p, rebuilt_p);
2224 if (EXPECT(rebuilt_p, 0))
2225 return TRUE;
2226 if (eq_p) {
2227 /* duplicated key; delete it */
2228 q->record = p->record;
2229 MARK_ENTRY_DELETED(p);
2230 tab->num_entries--;
2231 update_range_for_deleted(tab, bin);
2232 break;
2233 }
2234 else {
2235 /* hash collision; skip it */
2236#ifdef QUADRATIC_PROBE
2237 ind = hash_bin(ind + d, tab);
2238 d++;
2239#else
2240 ind = secondary_hash(ind, tab, &perturb);
2241#endif
2242 }
2243 }
2244 }
2245 }
2246 return FALSE;
2247}
2248
2249/* Reconstruct TAB's bins according to TAB's entries. This function
2250 permits conflicting keys inside of entries. No errors are reported
2251 then. All but one of them are discarded silently. */
2252static void
2253st_rehash(st_table *tab)
2254{
2255 int rebuilt_p;
2256
2257 do {
2258 if (tab->bin_power <= MAX_POWER2_FOR_TABLES_WITHOUT_BINS)
2259 rebuilt_p = st_rehash_linear(tab);
2260 else
2261 rebuilt_p = st_rehash_indexed(tab);
2262 } while (rebuilt_p);
2263}
2264
2265static st_data_t
2266st_stringify(VALUE key)
2267{
2268 return (rb_obj_class(key) == rb_cString && !RB_OBJ_FROZEN(key)) ?
2269 rb_hash_key_str(key) : key;
2270}
2271
2272static void
2273st_insert_single(st_table *tab, VALUE hash, VALUE key, VALUE val)
2274{
2275 st_data_t k = st_stringify(key);
2276 st_table_entry e;
2277 e.hash = do_hash(k, tab);
2278 e.key = k;
2279 e.record = val;
2280
2281 tab->entries[tab->entries_bound++] = e;
2282 tab->num_entries++;
2283 RB_OBJ_WRITTEN(hash, Qundef, k);
2284 RB_OBJ_WRITTEN(hash, Qundef, val);
2285}
2286
2287static void
2288st_insert_linear(st_table *tab, long argc, const VALUE *argv, VALUE hash)
2289{
2290 long i;
2291
2292 for (i = 0; i < argc; /* */) {
2293 st_data_t k = st_stringify(argv[i++]);
2294 st_data_t v = argv[i++];
2295 st_insert(tab, k, v);
2296 RB_OBJ_WRITTEN(hash, Qundef, k);
2297 RB_OBJ_WRITTEN(hash, Qundef, v);
2298 }
2299}
2300
2301static void
2302st_insert_generic(st_table *tab, long argc, const VALUE *argv, VALUE hash)
2303{
2304 long i;
2305
2306 /* push elems */
2307 for (i = 0; i < argc; /* */) {
2308 VALUE key = argv[i++];
2309 VALUE val = argv[i++];
2310 st_insert_single(tab, hash, key, val);
2311 }
2312
2313 /* reindex */
2314 st_rehash(tab);
2315}
2316
2317/* Mimics ruby's { foo => bar } syntax. This function is subpart
2318 of rb_hash_bulk_insert. */
2319void
2320rb_hash_bulk_insert_into_st_table(long argc, const VALUE *argv, VALUE hash)
2321{
2322 st_index_t n, size = argc / 2;
2323 st_table *tab = RHASH_ST_TABLE(hash);
2324
2325 tab = RHASH_TBL_RAW(hash);
2326 n = tab->entries_bound + size;
2327 st_expand_table(tab, n);
2328 if (UNLIKELY(tab->num_entries))
2329 st_insert_generic(tab, argc, argv, hash);
2330 else if (argc <= 2)
2331 st_insert_single(tab, hash, argv[0], argv[1]);
2332 else if (tab->bin_power <= MAX_POWER2_FOR_TABLES_WITHOUT_BINS)
2333 st_insert_linear(tab, argc, argv, hash);
2334 else
2335 st_insert_generic(tab, argc, argv, hash);
2336}
2337
2338void
2339rb_st_compact_table(st_table *tab)
2340{
2341 st_index_t num = tab->num_entries;
2342 if (REBUILD_THRESHOLD * num <= get_allocated_entries(tab)) {
2343 /* Compaction: */
2344 st_table *new_tab = st_init_table_with_size(tab->type, 2 * num);
2345 rebuild_table_with(new_tab, tab);
2346 rebuild_move_table(new_tab, tab);
2347 rebuild_cleanup(tab);
2348 }
2349}
2350
2351/*
2352 * set_table related code
2353 */
2354
2355struct set_table_entry {
2356 st_hash_t hash;
2357 st_data_t key;
2358};
2359
2360/* Return hash value of KEY for table TAB. */
2361static inline st_hash_t
2362set_do_hash(st_data_t key, set_table *tab)
2363{
2364 st_hash_t hash = (st_hash_t)(tab->type->hash)(key);
2365 return normalize_hash_value(hash);
2366}
2367
2368/* Return bin size index of table TAB. */
2369static inline unsigned int
2370set_get_size_ind(const set_table *tab)
2371{
2372 return tab->size_ind;
2373}
2374
2375/* Return the number of allocated bins of table TAB. */
2376static inline st_index_t
2377set_get_bins_num(const set_table *tab)
2378{
2379 return ((st_index_t) 1)<<tab->bin_power;
2380}
2381
2382/* Return mask for a bin index in table TAB. */
2383static inline st_index_t
2384set_bins_mask(const set_table *tab)
2385{
2386 return set_get_bins_num(tab) - 1;
2387}
2388
2389/* Return the index of table TAB bin corresponding to
2390 HASH_VALUE. */
2391static inline st_index_t
2392set_hash_bin(st_hash_t hash_value, set_table *tab)
2393{
2394 return hash_value & set_bins_mask(tab);
2395}
2396
2397/* Return the number of allocated entries of table TAB. */
2398static inline st_index_t
2399set_get_allocated_entries(const set_table *tab)
2400{
2401 return ((st_index_t) 1)<<tab->entry_power;
2402}
2403
2404static inline size_t
2405set_allocated_entries_size(const set_table *tab)
2406{
2407 return set_get_allocated_entries(tab) * sizeof(set_table_entry);
2408}
2409
2410static inline bool
2411set_has_bins(const set_table *tab)
2412{
2413 return tab->entry_power > MAX_POWER2_FOR_TABLES_WITHOUT_BINS;
2414}
2415
2416/* Return size of the allocated bins of table TAB. */
2417static inline st_index_t
2418set_bins_size(const set_table *tab)
2419{
2420 if (set_has_bins(tab)) {
2421 return features[tab->entry_power].bins_words * sizeof (st_index_t);
2422 }
2423
2424 return 0;
2425}
2426
2427static inline st_index_t *
2428set_bins_ptr(const set_table *tab)
2429{
2430 if (set_has_bins(tab)) {
2431 return (st_index_t *)(((char *)tab->entries) + set_allocated_entries_size(tab));
2432 }
2433
2434 return NULL;
2435}
2436
2437/* Mark all bins of table TAB as empty. */
2438static void
2439set_initialize_bins(set_table *tab)
2440{
2441 memset(set_bins_ptr(tab), 0, set_bins_size(tab));
2442}
2443
2444/* Make table TAB empty. */
2445static void
2446set_make_tab_empty(set_table *tab)
2447{
2448 tab->num_entries = 0;
2449 tab->entries_start = tab->entries_bound = 0;
2450 if (set_bins_ptr(tab) != NULL)
2451 set_initialize_bins(tab);
2452}
2453
2454static set_table *
2455set_init_existing_table_with_size(set_table *tab, const struct st_hash_type *type, st_index_t size)
2456{
2457 int n;
2458
2459#ifdef HASH_LOG
2460#if HASH_LOG+0 < 0
2461 {
2462 const char *e = getenv("ST_HASH_LOG");
2463 if (!e || !*e) init_st = 1;
2464 }
2465#endif
2466 if (init_st == 0) {
2467 init_st = 1;
2468 atexit(stat_col);
2469 }
2470#endif
2471
2472 n = get_power2(size);
2473
2474 tab->type = type;
2475 tab->entry_power = n;
2476 tab->bin_power = features[n].bin_power;
2477 tab->size_ind = features[n].size_ind;
2478
2479 size_t memsize = 0;
2480 if (set_has_bins(tab)) {
2481 memsize += set_bins_size(tab);
2482 }
2483 memsize += set_get_allocated_entries(tab) * sizeof(set_table_entry);
2484 tab->entries = (set_table_entry *)malloc(memsize);
2485 set_make_tab_empty(tab);
2486 tab->rebuilds_num = 0;
2487 return tab;
2488}
2489
2490/* Create and return table with TYPE which can hold at least SIZE
2491 entries. The real number of entries which the table can hold is
2492 the nearest power of two for SIZE. */
2493set_table *
2494set_init_table_with_size(set_table *tab, const struct st_hash_type *type, st_index_t size)
2495{
2496 if (tab == NULL) tab = malloc(sizeof(set_table));
2497
2498 set_init_existing_table_with_size(tab, type, size);
2499
2500 return tab;
2501}
2502
2503set_table *
2504set_init_numtable(void)
2505{
2506 return set_init_table_with_size(NULL, &type_numhash, 0);
2507}
2508
2509set_table *
2510set_init_numtable_with_size(st_index_t size)
2511{
2512 return set_init_table_with_size(NULL, &type_numhash, size);
2513}
2514
2515size_t
2516set_table_size(const struct set_table *tbl)
2517{
2518 return tbl->num_entries;
2519}
2520
2521/* Make table TAB empty. */
2522void
2523set_table_clear(set_table *tab)
2524{
2525 set_make_tab_empty(tab);
2526 tab->rebuilds_num++;
2527}
2528
2529/* Free table TAB space. This should only be used if you passed NULL to
2530 set_init_table_with_size/set_copy when creating the table. */
2531void
2532set_free_table(set_table *tab)
2533{
2534 free(tab->entries);
2535 free(tab);
2536}
2537
2538/* Return byte size of memory allocated for table TAB. */
2539size_t
2540set_memsize(const set_table *tab)
2541{
2542 return(sizeof(set_table)
2543 + (tab->entry_power <= MAX_POWER2_FOR_TABLES_WITHOUT_BINS ? 0 : set_bins_size(tab))
2544 + set_get_allocated_entries(tab) * sizeof(set_table_entry));
2545}
2546
2547static st_index_t
2548set_find_table_entry_ind(set_table *tab, st_hash_t hash_value, st_data_t key);
2549
2550static st_index_t
2551set_find_table_bin_ind(set_table *tab, st_hash_t hash_value, st_data_t key);
2552
2553static st_index_t
2554set_find_table_bin_ind_direct(set_table *table, st_hash_t hash_value, st_data_t key);
2555
2556static st_index_t
2557set_find_table_bin_ptr_and_reserve(set_table *tab, st_hash_t *hash_value,
2558 st_data_t key, st_index_t *bin_ind);
2559
2560static void set_rebuild_table_with(set_table *const new_tab, set_table *const tab);
2561static void set_rebuild_move_table(set_table *const new_tab, set_table *const tab);
2562static void set_rebuild_cleanup(set_table *const tab);
2563
2564/* Rebuild table TAB. Rebuilding removes all deleted bins and entries
2565 and can change size of the table entries and bins arrays.
2566 Rebuilding is implemented by creation of a new table or by
2567 compaction of the existing one. */
2568static void
2569set_rebuild_table(set_table *tab)
2570{
2571 if ((2 * tab->num_entries <= set_get_allocated_entries(tab)
2572 && REBUILD_THRESHOLD * tab->num_entries > set_get_allocated_entries(tab))
2573 || tab->num_entries < (1 << MINIMAL_POWER2)) {
2574 /* Compaction: */
2575 tab->num_entries = 0;
2576 if (set_has_bins(tab))
2577 set_initialize_bins(tab);
2578 set_rebuild_table_with(tab, tab);
2579 }
2580 else {
2581 set_table *new_tab;
2582 /* This allocation could trigger GC and compaction. If tab is the
2583 * gen_fields_tbl, then tab could have changed in size due to objects being
2584 * freed and/or moved. Do not store attributes of tab before this line. */
2585 new_tab = set_init_table_with_size(NULL, tab->type,
2586 2 * tab->num_entries - 1);
2587 set_rebuild_table_with(new_tab, tab);
2588 set_rebuild_move_table(new_tab, tab);
2589 }
2590 set_rebuild_cleanup(tab);
2591}
2592
2593static void
2594set_rebuild_table_with(set_table *const new_tab, set_table *const tab)
2595{
2596 st_index_t i, ni;
2597 unsigned int size_ind;
2598 set_table_entry *new_entries;
2599 set_table_entry *curr_entry_ptr;
2600 st_index_t *bins;
2601 st_index_t bin_ind;
2602
2603 new_entries = new_tab->entries;
2604
2605 ni = 0;
2606 bins = set_bins_ptr(new_tab);
2607 size_ind = set_get_size_ind(new_tab);
2608 st_index_t bound = tab->entries_bound;
2609 set_table_entry *entries = tab->entries;
2610
2611 for (i = tab->entries_start; i < bound; i++) {
2612 curr_entry_ptr = &entries[i];
2613 PREFETCH(entries + i + 1, 0);
2614 if (EXPECT(DELETED_ENTRY_P(curr_entry_ptr), 0))
2615 continue;
2616 if (&new_entries[ni] != curr_entry_ptr)
2617 new_entries[ni] = *curr_entry_ptr;
2618 if (EXPECT(bins != NULL, 1)) {
2619 bin_ind = set_find_table_bin_ind_direct(new_tab, curr_entry_ptr->hash,
2620 curr_entry_ptr->key);
2621 set_bin(bins, size_ind, bin_ind, ni + ENTRY_BASE);
2622 }
2623 new_tab->num_entries++;
2624 ni++;
2625 }
2626
2627 assert(new_tab->num_entries == tab->num_entries);
2628}
2629
2630static void
2631set_rebuild_move_table(set_table *const new_tab, set_table *const tab)
2632{
2633 tab->entry_power = new_tab->entry_power;
2634 tab->bin_power = new_tab->bin_power;
2635 tab->size_ind = new_tab->size_ind;
2636 free(tab->entries);
2637 tab->entries = new_tab->entries;
2638 free(new_tab);
2639}
2640
2641static void
2642set_rebuild_cleanup(set_table *const tab)
2643{
2644 tab->entries_start = 0;
2645 tab->entries_bound = tab->num_entries;
2646 tab->rebuilds_num++;
2647}
2648
2649/* Return the next secondary hash index for table TAB using previous
2650 index IND and PERTURB. Finally modulo of the function becomes a
2651 full *cycle linear congruential generator*, in other words it
2652 guarantees traversing all table bins in extreme case.
2653
2654 According the Hull-Dobell theorem a generator
2655 "Xnext = (a*Xprev + c) mod m" is a full cycle generator if and only if
2656 o m and c are relatively prime
2657 o a-1 is divisible by all prime factors of m
2658 o a-1 is divisible by 4 if m is divisible by 4.
2659
2660 For our case a is 5, c is 1, and m is a power of two. */
2661static inline st_index_t
2662set_secondary_hash(st_index_t ind, set_table *tab, st_index_t *perturb)
2663{
2664 *perturb >>= 11;
2665 ind = (ind << 2) + ind + *perturb + 1;
2666 return set_hash_bin(ind, tab);
2667}
2668
2669/* Find an entry with HASH_VALUE and KEY in TABLE using a linear
2670 search. Return the index of the found entry in array `entries`.
2671 If it is not found, return UNDEFINED_ENTRY_IND. If the table was
2672 rebuilt during the search, return REBUILT_TABLE_ENTRY_IND. */
2673static inline st_index_t
2674set_find_entry(set_table *tab, st_hash_t hash_value, st_data_t key)
2675{
2676 int eq_p, rebuilt_p;
2677 st_index_t i, bound;
2678 set_table_entry *entries;
2679
2680 bound = tab->entries_bound;
2681 entries = tab->entries;
2682 for (i = tab->entries_start; i < bound; i++) {
2683 DO_PTR_EQUAL_CHECK(tab, &entries[i], hash_value, key, eq_p, rebuilt_p);
2684 if (EXPECT(rebuilt_p, 0))
2685 return REBUILT_TABLE_ENTRY_IND;
2686 if (eq_p)
2687 return i;
2688 }
2689 return UNDEFINED_ENTRY_IND;
2690}
2691
2692/* Use the quadratic probing. The method has a better data locality
2693 but more collisions than the current approach. In average it
2694 results in a bit slower search. */
2695/*#define QUADRATIC_PROBE*/
2696
2697/* Return index of entry with HASH_VALUE and KEY in table TAB. If
2698 there is no such entry, return UNDEFINED_ENTRY_IND. If the table
2699 was rebuilt during the search, return REBUILT_TABLE_ENTRY_IND. */
2700static st_index_t
2701set_find_table_entry_ind(set_table *tab, st_hash_t hash_value, st_data_t key)
2702{
2703 int eq_p, rebuilt_p;
2704 st_index_t ind;
2705#ifdef QUADRATIC_PROBE
2706 st_index_t d;
2707#else
2708 st_index_t perturb;
2709#endif
2710 st_index_t bin;
2711 set_table_entry *entries = tab->entries;
2712
2713 ind = set_hash_bin(hash_value, tab);
2714#ifdef QUADRATIC_PROBE
2715 d = 1;
2716#else
2717 perturb = hash_value;
2718#endif
2719 for (;;) {
2720 bin = get_bin(set_bins_ptr(tab), set_get_size_ind(tab), ind);
2721 if (! EMPTY_OR_DELETED_BIN_P(bin)) {
2722 DO_PTR_EQUAL_CHECK(tab, &entries[bin - ENTRY_BASE], hash_value, key, eq_p, rebuilt_p);
2723 if (EXPECT(rebuilt_p, 0))
2724 return REBUILT_TABLE_ENTRY_IND;
2725 if (eq_p)
2726 break;
2727 }
2728 else if (EMPTY_BIN_P(bin))
2729 return UNDEFINED_ENTRY_IND;
2730#ifdef QUADRATIC_PROBE
2731 ind = set_hash_bin(ind + d, tab);
2732 d++;
2733#else
2734 ind = set_secondary_hash(ind, tab, &perturb);
2735#endif
2736 }
2737 return bin;
2738}
2739
2740/* Find and return index of table TAB bin corresponding to an entry
2741 with HASH_VALUE and KEY. If there is no such bin, return
2742 UNDEFINED_BIN_IND. If the table was rebuilt during the search,
2743 return REBUILT_TABLE_BIN_IND. */
2744static st_index_t
2745set_find_table_bin_ind(set_table *tab, st_hash_t hash_value, st_data_t key)
2746{
2747 int eq_p, rebuilt_p;
2748 st_index_t ind;
2749#ifdef QUADRATIC_PROBE
2750 st_index_t d;
2751#else
2752 st_index_t perturb;
2753#endif
2754 st_index_t bin;
2755 set_table_entry *entries = tab->entries;
2756
2757 ind = set_hash_bin(hash_value, tab);
2758#ifdef QUADRATIC_PROBE
2759 d = 1;
2760#else
2761 perturb = hash_value;
2762#endif
2763 for (;;) {
2764 bin = get_bin(set_bins_ptr(tab), set_get_size_ind(tab), ind);
2765 if (! EMPTY_OR_DELETED_BIN_P(bin)) {
2766 DO_PTR_EQUAL_CHECK(tab, &entries[bin - ENTRY_BASE], hash_value, key, eq_p, rebuilt_p);
2767 if (EXPECT(rebuilt_p, 0))
2768 return REBUILT_TABLE_BIN_IND;
2769 if (eq_p)
2770 break;
2771 }
2772 else if (EMPTY_BIN_P(bin))
2773 return UNDEFINED_BIN_IND;
2774#ifdef QUADRATIC_PROBE
2775 ind = set_hash_bin(ind + d, tab);
2776 d++;
2777#else
2778 ind = set_secondary_hash(ind, tab, &perturb);
2779#endif
2780 }
2781 return ind;
2782}
2783
2784/* Find and return index of table TAB bin corresponding to an entry
2785 with HASH_VALUE and KEY. The entry should be in the table
2786 already. */
2787static st_index_t
2788set_find_table_bin_ind_direct(set_table *tab, st_hash_t hash_value, st_data_t key)
2789{
2790 st_index_t ind;
2791#ifdef QUADRATIC_PROBE
2792 st_index_t d;
2793#else
2794 st_index_t perturb;
2795#endif
2796 st_index_t bin;
2797
2798 ind = set_hash_bin(hash_value, tab);
2799#ifdef QUADRATIC_PROBE
2800 d = 1;
2801#else
2802 perturb = hash_value;
2803#endif
2804 for (;;) {
2805 bin = get_bin(set_bins_ptr(tab), set_get_size_ind(tab), ind);
2806 if (EMPTY_OR_DELETED_BIN_P(bin))
2807 return ind;
2808#ifdef QUADRATIC_PROBE
2809 ind = set_hash_bin(ind + d, tab);
2810 d++;
2811#else
2812 ind = set_secondary_hash(ind, tab, &perturb);
2813#endif
2814 }
2815}
2816
2817/* Mark I-th bin of table TAB as empty, in other words not
2818 corresponding to any entry. */
2819#define MARK_SET_BIN_EMPTY(tab, i) (set_bin(set_bins_ptr(tab), set_get_size_ind(tab), i, EMPTY_BIN))
2820
2821/* Return index of table TAB bin for HASH_VALUE and KEY through
2822 BIN_IND and the pointed value as the function result. Reserve the
2823 bin for inclusion of the corresponding entry into the table if it
2824 is not there yet. We always find such bin as bins array length is
2825 bigger entries array. Although we can reuse a deleted bin, the
2826 result bin value is always empty if the table has no entry with
2827 KEY. Return the entries array index of the found entry or
2828 UNDEFINED_ENTRY_IND if it is not found. If the table was rebuilt
2829 during the search, return REBUILT_TABLE_ENTRY_IND. */
2830static st_index_t
2831set_find_table_bin_ptr_and_reserve(set_table *tab, st_hash_t *hash_value,
2832 st_data_t key, st_index_t *bin_ind)
2833{
2834 int eq_p, rebuilt_p;
2835 st_index_t ind;
2836 st_hash_t curr_hash_value = *hash_value;
2837#ifdef QUADRATIC_PROBE
2838 st_index_t d;
2839#else
2840 st_index_t perturb;
2841#endif
2842 st_index_t entry_index;
2843 st_index_t firset_deleted_bin_ind;
2844 set_table_entry *entries;
2845
2846 ind = set_hash_bin(curr_hash_value, tab);
2847#ifdef QUADRATIC_PROBE
2848 d = 1;
2849#else
2850 perturb = curr_hash_value;
2851#endif
2852 firset_deleted_bin_ind = UNDEFINED_BIN_IND;
2853 entries = tab->entries;
2854 for (;;) {
2855 entry_index = get_bin(set_bins_ptr(tab), set_get_size_ind(tab), ind);
2856 if (EMPTY_BIN_P(entry_index)) {
2857 tab->num_entries++;
2858 entry_index = UNDEFINED_ENTRY_IND;
2859 if (firset_deleted_bin_ind != UNDEFINED_BIN_IND) {
2860 /* We can reuse bin of a deleted entry. */
2861 ind = firset_deleted_bin_ind;
2862 MARK_SET_BIN_EMPTY(tab, ind);
2863 }
2864 break;
2865 }
2866 else if (! DELETED_BIN_P(entry_index)) {
2867 DO_PTR_EQUAL_CHECK(tab, &entries[entry_index - ENTRY_BASE], curr_hash_value, key, eq_p, rebuilt_p);
2868 if (EXPECT(rebuilt_p, 0))
2869 return REBUILT_TABLE_ENTRY_IND;
2870 if (eq_p)
2871 break;
2872 }
2873 else if (firset_deleted_bin_ind == UNDEFINED_BIN_IND)
2874 firset_deleted_bin_ind = ind;
2875#ifdef QUADRATIC_PROBE
2876 ind = set_hash_bin(ind + d, tab);
2877 d++;
2878#else
2879 ind = set_secondary_hash(ind, tab, &perturb);
2880#endif
2881 }
2882 *bin_ind = ind;
2883 return entry_index;
2884}
2885
2886/* Find an entry with KEY in table TAB. Return non-zero if we found
2887 it. */
2888int
2889set_table_lookup(set_table *tab, st_data_t key)
2890{
2891 st_index_t bin;
2892 st_hash_t hash = set_do_hash(key, tab);
2893
2894 retry:
2895 if (!set_has_bins(tab)) {
2896 bin = set_find_entry(tab, hash, key);
2897 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
2898 goto retry;
2899 if (bin == UNDEFINED_ENTRY_IND)
2900 return 0;
2901 }
2902 else {
2903 bin = set_find_table_entry_ind(tab, hash, key);
2904 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
2905 goto retry;
2906 if (bin == UNDEFINED_ENTRY_IND)
2907 return 0;
2908 bin -= ENTRY_BASE;
2909 }
2910 return 1;
2911}
2912
2913/* Check the table and rebuild it if it is necessary. */
2914static inline void
2915set_rebuild_table_if_necessary (set_table *tab)
2916{
2917 st_index_t bound = tab->entries_bound;
2918
2919 if (bound == set_get_allocated_entries(tab))
2920 set_rebuild_table(tab);
2921}
2922
2923/* Insert KEY into table TAB and return zero. If there is
2924 already entry with KEY in the table, return nonzero and update
2925 the value of the found entry. */
2926int
2927set_insert(set_table *tab, st_data_t key)
2928{
2929 set_table_entry *entry;
2930 st_index_t bin;
2931 st_index_t ind;
2932 st_hash_t hash_value;
2933 st_index_t bin_ind;
2934 int new_p;
2935
2936 hash_value = set_do_hash(key, tab);
2937 retry:
2938 set_rebuild_table_if_necessary(tab);
2939 if (!set_has_bins(tab)) {
2940 bin = set_find_entry(tab, hash_value, key);
2941 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
2942 goto retry;
2943 new_p = bin == UNDEFINED_ENTRY_IND;
2944 if (new_p)
2945 tab->num_entries++;
2946 bin_ind = UNDEFINED_BIN_IND;
2947 }
2948 else {
2949 bin = set_find_table_bin_ptr_and_reserve(tab, &hash_value,
2950 key, &bin_ind);
2951 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
2952 goto retry;
2953 new_p = bin == UNDEFINED_ENTRY_IND;
2954 bin -= ENTRY_BASE;
2955 }
2956 if (new_p) {
2957 ind = tab->entries_bound++;
2958 entry = &tab->entries[ind];
2959 entry->hash = hash_value;
2960 entry->key = key;
2961 if (bin_ind != UNDEFINED_BIN_IND)
2962 set_bin(set_bins_ptr(tab), set_get_size_ind(tab), bin_ind, ind + ENTRY_BASE);
2963 return 0;
2964 }
2965 return 1;
2966}
2967
2968/* Create a copy of old_tab into new_tab. */
2969static set_table *
2970set_replace(set_table *new_tab, set_table *old_tab)
2971{
2972 *new_tab = *old_tab;
2973 size_t memsize = set_allocated_entries_size(old_tab) + set_bins_size(old_tab);
2974 new_tab->entries = (set_table_entry *)malloc(memsize);
2975 MEMCPY(new_tab->entries, old_tab->entries, char, memsize);
2976 return new_tab;
2977}
2978
2979/* Create and return a copy of table OLD_TAB. */
2980set_table *
2981set_copy(set_table *new_tab, set_table *old_tab)
2982{
2983 if (new_tab == NULL) new_tab = (set_table *) malloc(sizeof(set_table));
2984
2985 if (set_replace(new_tab, old_tab) == NULL) {
2986 set_free_table(new_tab);
2987 return NULL;
2988 }
2989
2990 return new_tab;
2991}
2992
2993/* Update the entries start of table TAB after removing an entry
2994 with index N in the array entries. */
2995static inline void
2996set_update_range_for_deleted(set_table *tab, st_index_t n)
2997{
2998 /* Do not update entries_bound here. Otherwise, we can fill all
2999 bins by deleted entry value before rebuilding the table. */
3000 if (tab->entries_start == n) {
3001 st_index_t start = n + 1;
3002 st_index_t bound = tab->entries_bound;
3003 set_table_entry *entries = tab->entries;
3004 while (start < bound && DELETED_ENTRY_P(&entries[start])) start++;
3005 tab->entries_start = start;
3006 }
3007}
3008
3009/* Mark I-th bin of table TAB as corresponding to a deleted table
3010 entry. Update number of entries in the table and number of bins
3011 corresponding to deleted entries. */
3012#define MARK_SET_BIN_DELETED(tab, i) \
3013 do { \
3014 set_bin(set_bins_ptr(tab), set_get_size_ind(tab), i, DELETED_BIN); \
3015 } while (0)
3016
3017/* Delete entry with KEY from table TAB, and return non-zero. If
3018 there is no entry with KEY in the table, return zero. */
3019int
3020set_table_delete(set_table *tab, st_data_t *key)
3021{
3022 set_table_entry *entry;
3023 st_index_t bin;
3024 st_index_t bin_ind;
3025 st_hash_t hash;
3026
3027 hash = set_do_hash(*key, tab);
3028 retry:
3029 if (!set_has_bins(tab)) {
3030 bin = set_find_entry(tab, hash, *key);
3031 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
3032 goto retry;
3033 if (bin == UNDEFINED_ENTRY_IND) {
3034 return 0;
3035 }
3036 }
3037 else {
3038 bin_ind = set_find_table_bin_ind(tab, hash, *key);
3039 if (EXPECT(bin_ind == REBUILT_TABLE_BIN_IND, 0))
3040 goto retry;
3041 if (bin_ind == UNDEFINED_BIN_IND) {
3042 return 0;
3043 }
3044 bin = get_bin(set_bins_ptr(tab), set_get_size_ind(tab), bin_ind) - ENTRY_BASE;
3045 MARK_SET_BIN_DELETED(tab, bin_ind);
3046 }
3047 entry = &tab->entries[bin];
3048 *key = entry->key;
3049 MARK_ENTRY_DELETED(entry);
3050 tab->num_entries--;
3051 set_update_range_for_deleted(tab, bin);
3052 return 1;
3053}
3054
3055/* Traverse all entries in table TAB calling FUNC with current entry
3056 key and zero. If the call returns ST_STOP, stop
3057 traversing. If the call returns ST_DELETE, delete the current
3058 entry from the table. In case of ST_CHECK or ST_CONTINUE, continue
3059 traversing. The function returns zero unless an error is found.
3060 CHECK_P is flag of set_foreach_check call. The behavior is a bit
3061 different for ST_CHECK and when the current element is removed
3062 during traversing. */
3063static inline int
3064set_general_foreach(set_table *tab, set_foreach_check_callback_func *func,
3065 set_update_callback_func *replace, st_data_t arg,
3066 int check_p)
3067{
3068 st_index_t bin;
3069 st_index_t bin_ind;
3070 set_table_entry *entries, *curr_entry_ptr;
3071 enum st_retval retval;
3072 st_index_t i, rebuilds_num;
3073 st_hash_t hash;
3074 st_data_t key;
3075 int error_p, packed_p = !set_has_bins(tab);
3076
3077 entries = tab->entries;
3078 /* The bound can change inside the loop even without rebuilding
3079 the table, e.g. by an entry insertion. */
3080 for (i = tab->entries_start; i < tab->entries_bound; i++) {
3081 curr_entry_ptr = &entries[i];
3082 if (EXPECT(DELETED_ENTRY_P(curr_entry_ptr), 0))
3083 continue;
3084 key = curr_entry_ptr->key;
3085 rebuilds_num = tab->rebuilds_num;
3086 hash = curr_entry_ptr->hash;
3087 retval = (*func)(key, arg, 0);
3088
3089 if (retval == ST_REPLACE && replace) {
3090 retval = (*replace)(&key, arg, TRUE);
3091 curr_entry_ptr->key = key;
3092 }
3093
3094 if (rebuilds_num != tab->rebuilds_num) {
3095 retry:
3096 entries = tab->entries;
3097 packed_p = !set_has_bins(tab);
3098 if (packed_p) {
3099 i = set_find_entry(tab, hash, key);
3100 if (EXPECT(i == REBUILT_TABLE_ENTRY_IND, 0))
3101 goto retry;
3102 error_p = i == UNDEFINED_ENTRY_IND;
3103 }
3104 else {
3105 i = set_find_table_entry_ind(tab, hash, key);
3106 if (EXPECT(i == REBUILT_TABLE_ENTRY_IND, 0))
3107 goto retry;
3108 error_p = i == UNDEFINED_ENTRY_IND;
3109 i -= ENTRY_BASE;
3110 }
3111 if (error_p && check_p) {
3112 /* call func with error notice */
3113 retval = (*func)(0, arg, 1);
3114 return 1;
3115 }
3116 curr_entry_ptr = &entries[i];
3117 }
3118 switch (retval) {
3119 case ST_REPLACE:
3120 break;
3121 case ST_CONTINUE:
3122 break;
3123 case ST_CHECK:
3124 if (check_p)
3125 break;
3126 case ST_STOP:
3127 return 0;
3128 case ST_DELETE: {
3129 st_data_t key = curr_entry_ptr->key;
3130
3131 again:
3132 if (packed_p) {
3133 bin = set_find_entry(tab, hash, key);
3134 if (EXPECT(bin == REBUILT_TABLE_ENTRY_IND, 0))
3135 goto again;
3136 if (bin == UNDEFINED_ENTRY_IND)
3137 break;
3138 }
3139 else {
3140 bin_ind = set_find_table_bin_ind(tab, hash, key);
3141 if (EXPECT(bin_ind == REBUILT_TABLE_BIN_IND, 0))
3142 goto again;
3143 if (bin_ind == UNDEFINED_BIN_IND)
3144 break;
3145 bin = get_bin(set_bins_ptr(tab), set_get_size_ind(tab), bin_ind) - ENTRY_BASE;
3146 MARK_SET_BIN_DELETED(tab, bin_ind);
3147 }
3148 curr_entry_ptr = &entries[bin];
3149 MARK_ENTRY_DELETED(curr_entry_ptr);
3150 tab->num_entries--;
3151 set_update_range_for_deleted(tab, bin);
3152 break;
3153 }
3154 }
3155 }
3156 return 0;
3157}
3158
3159int
3160set_foreach_with_replace(set_table *tab, set_foreach_check_callback_func *func, set_update_callback_func *replace, st_data_t arg)
3161{
3162 return set_general_foreach(tab, func, replace, arg, TRUE);
3163}
3164
3165struct set_functor {
3166 set_foreach_callback_func *func;
3167 st_data_t arg;
3168};
3169
3170static int
3171set_apply_functor(st_data_t k, st_data_t d, int _)
3172{
3173 const struct set_functor *f = (void *)d;
3174 return f->func(k, f->arg);
3175}
3176
3177int
3178set_table_foreach(set_table *tab, set_foreach_callback_func *func, st_data_t arg)
3179{
3180 const struct set_functor f = { func, arg };
3181 return set_general_foreach(tab, set_apply_functor, NULL, (st_data_t)&f, FALSE);
3182}
3183
3184/* See comments for function set_delete_safe. */
3185int
3186set_foreach_check(set_table *tab, set_foreach_check_callback_func *func, st_data_t arg,
3187 st_data_t never ATTRIBUTE_UNUSED)
3188{
3189 return set_general_foreach(tab, func, NULL, arg, TRUE);
3190}
3191
3192/* Set up array KEYS by at most SIZE keys of head table TAB entries.
3193 Return the number of keys set up in array KEYS. */
3194inline st_index_t
3195set_keys(set_table *tab, st_data_t *keys, st_index_t size)
3196{
3197 st_index_t i, bound;
3198 st_data_t key, *keys_start, *keys_end;
3199 set_table_entry *curr_entry_ptr, *entries = tab->entries;
3200
3201 bound = tab->entries_bound;
3202 keys_start = keys;
3203 keys_end = keys + size;
3204 for (i = tab->entries_start; i < bound; i++) {
3205 if (keys == keys_end)
3206 break;
3207 curr_entry_ptr = &entries[i];
3208 key = curr_entry_ptr->key;
3209 if (! DELETED_ENTRY_P(curr_entry_ptr))
3210 *keys++ = key;
3211 }
3212
3213 return keys - keys_start;
3214}
3215
3216void
3217set_compact_table(set_table *tab)
3218{
3219 st_index_t num = tab->num_entries;
3220 if (REBUILD_THRESHOLD * num <= set_get_allocated_entries(tab)) {
3221 /* Compaction: */
3222 set_table *new_tab = set_init_table_with_size(NULL, tab->type, 2 * num);
3223 set_rebuild_table_with(new_tab, tab);
3224 set_rebuild_move_table(new_tab, tab);
3225 set_rebuild_cleanup(tab);
3226 }
3227}
3228
3229#endif
#define RUBY_ASSERT(...)
Asserts that the given expression is truthy if and only if RUBY_DEBUG is truthy.
Definition assert.h:219
#define Qundef
Old name of RUBY_Qundef.
VALUE rb_eRuntimeError
RuntimeError exception.
Definition error.c:1429
VALUE rb_obj_class(VALUE obj)
Queries the class of an object.
Definition object.c:264
VALUE rb_cString
String class.
Definition string.c:84
#define RB_OBJ_WRITTEN(old, oldv, young)
Identical to RB_OBJ_WRITE(), except it doesn't write any values, but only a WB declaration.
Definition gc.h:615
char * ptr
Pointer to the underlying memory region, of at least capa bytes.
Definition io.h:2
int len
Length of the buffer.
Definition io.h:8
#define MEMCPY(p1, p2, type, n)
Handy macro to call memcpy.
Definition memory.h:372
VALUE type(ANYARGS)
ANYARGS-ed function type.
#define _(args)
This was a transition path from K&R to ANSI.
Definition stdarg.h:35
set_table_entry * entries
Array of size 2^entry_power.
Definition set_table.h:28
Definition st.c:137
uintptr_t VALUE
Type that represents a Ruby object.
Definition value.h:40