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