Ruby  2.0.0p247(2013-06-27revision41674)
st.c
Go to the documentation of this file.
1 /* This is a public domain general purpose hash table package written by Peter Moore @ UCB. */
2 
3 /* static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; */
4 
5 #ifdef NOT_RUBY
6 #include "regint.h"
7 #include "st.h"
8 #else
9 #include "ruby/ruby.h"
10 #endif
11 
12 #include <stdio.h>
13 #ifdef HAVE_STDLIB_H
14 #include <stdlib.h>
15 #endif
16 #include <string.h>
17 
19 
26 };
27 
28 typedef struct st_packed_entry {
32 
33 #define STATIC_ASSERT(name, expr) typedef int static_assert_##name##_check[(expr) ? 1 : -1];
34 
35 #define ST_DEFAULT_MAX_DENSITY 5
36 #define ST_DEFAULT_INIT_TABLE_SIZE 11
37 #define ST_DEFAULT_SECOND_TABLE_SIZE 19
38 #define ST_DEFAULT_PACKED_TABLE_SIZE 18
39 #define PACKED_UNIT (int)(sizeof(st_packed_entry) / sizeof(st_table_entry*))
40 #define MAX_PACKED_HASH (int)(ST_DEFAULT_PACKED_TABLE_SIZE * sizeof(st_table_entry*) / sizeof(st_packed_entry))
41 
44 
45  /*
46  * DEFAULT_MAX_DENSITY is the default for the largest we allow the
47  * average number of items per bin before increasing the number of
48  * bins
49  *
50  * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
51  * allocated initially
52  *
53  */
54 
55 #define type_numhash st_hashtype_num
56 const struct st_hash_type st_hashtype_num = {
57  st_numcmp,
58  st_numhash,
59 };
60 
61 /* extern int strcmp(const char *, const char *); */
63 static const struct st_hash_type type_strhash = {
64  strcmp,
65  strhash,
66 };
67 
69 static const struct st_hash_type type_strcasehash = {
72 };
73 
74 static void rehash(st_table *);
75 
76 #ifdef RUBY
77 #define malloc xmalloc
78 #define calloc xcalloc
79 #define realloc xrealloc
80 #define free(x) xfree(x)
81 #endif
82 
83 #define numberof(array) (int)(sizeof(array) / sizeof((array)[0]))
84 
85 #define EQUAL(table,x,y) ((x)==(y) || (*(table)->type->compare)((x),(y)) == 0)
86 
87 #define do_hash(key,table) (st_index_t)(*(table)->type->hash)((key))
88 #define do_hash_bin(key,table) (do_hash((key), (table))%(table)->num_bins)
89 
90 /* preparation for possible allocation improvements */
91 #define st_alloc_entry() (st_table_entry *)malloc(sizeof(st_table_entry))
92 #define st_free_entry(entry) free(entry)
93 #define st_alloc_table() (st_table *)malloc(sizeof(st_table))
94 #define st_dealloc_table(table) free(table)
95 #define st_alloc_bins(size) (st_table_entry **)calloc(size, sizeof(st_table_entry *))
96 #define st_free_bins(bins, size) free(bins)
97 static inline st_table_entry**
99 {
100  bins = (st_table_entry **)realloc(bins, newsize * sizeof(st_table_entry *));
101  MEMZERO(bins, st_table_entry*, newsize);
102  return bins;
103 }
104 
105 /* Shortage */
106 #define bins as.big.bins
107 #define head as.big.head
108 #define tail as.big.tail
109 #define real_entries as.packed.real_entries
110 
111 /* preparation for possible packing improvements */
112 #define PACKED_BINS(table) ((table)->as.packed.entries)
113 #define PACKED_ENT(table, i) PACKED_BINS(table)[i]
114 #define PKEY(table, i) PACKED_ENT((table), (i)).key
115 #define PVAL(table, i) PACKED_ENT((table), (i)).val
116 #define PHASH(table, i) PACKED_ENT((table), (i)).hash
117 #define PKEY_SET(table, i, v) (PKEY((table), (i)) = (v))
118 #define PVAL_SET(table, i, v) (PVAL((table), (i)) = (v))
119 #define PHASH_SET(table, i, v) (PHASH((table), (i)) = (v))
120 
121 /* this function depends much on packed layout, so that it placed here */
122 static inline void
124 {
125  table->real_entries--;
126  table->num_entries--;
127  if (i < table->real_entries) {
128  MEMMOVE(&PACKED_ENT(table, i), &PACKED_ENT(table, i+1),
129  st_packed_entry, table->real_entries - i);
130  }
131 }
132 
133 static inline void
135 {
136  table->num_entries--;
137  PKEY_SET(table, i, never);
138  PVAL_SET(table, i, never);
139  PHASH_SET(table, i, 0);
140 }
141 
142 /*
143  * MINSIZE is the minimum size of a dictionary.
144  */
145 
146 #define MINSIZE 8
147 
148 /*
149 Table of prime numbers 2^n+a, 2<=n<=30.
150 */
151 static const unsigned int primes[] = {
154  32 + 5,
155  64 + 3,
156  128 + 3,
157  256 + 27,
158  512 + 9,
159  1024 + 9,
160  2048 + 5,
161  4096 + 3,
162  8192 + 27,
163  16384 + 43,
164  32768 + 3,
165  65536 + 45,
166  131072 + 29,
167  262144 + 3,
168  524288 + 21,
169  1048576 + 7,
170  2097152 + 17,
171  4194304 + 15,
172  8388608 + 9,
173  16777216 + 43,
174  33554432 + 35,
175  67108864 + 15,
176  134217728 + 29,
177  268435456 + 3,
178  536870912 + 11,
179  1073741824 + 85,
180  0
181 };
182 
183 static st_index_t
185 {
186  int i;
187 
188 #if 0
189  for (i=3; i<31; i++) {
190  if ((1<<i) > size) return 1<<i;
191  }
192  return -1;
193 #else
194  st_index_t newsize;
195 
196  for (i = 0, newsize = MINSIZE; i < numberof(primes); i++, newsize <<= 1) {
197  if (newsize > size) return primes[i];
198  }
199  /* Ran out of polynomials */
200 #ifndef NOT_RUBY
201  rb_raise(rb_eRuntimeError, "st_table too big");
202 #endif
203  return -1; /* should raise exception */
204 #endif
205 }
206 
207 #ifdef HASH_LOG
208 #ifdef HAVE_UNISTD_H
209 #include <unistd.h>
210 #endif
211 static struct {
212  int all, total, num, str, strcase;
213 } collision;
214 static int init_st = 0;
215 
216 static void
217 stat_col(void)
218 {
219  char fname[10+sizeof(long)*3];
220  FILE *f = fopen((snprintf(fname, sizeof(fname), "/tmp/col%ld", (long)getpid()), fname), "w");
221  fprintf(f, "collision: %d / %d (%6.2f)\n", collision.all, collision.total,
222  ((double)collision.all / (collision.total)) * 100);
223  fprintf(f, "num: %d, str: %d, strcase: %d\n", collision.num, collision.str, collision.strcase);
224  fclose(f);
225 }
226 #endif
227 
228 st_table*
230 {
231  st_table *tbl;
232 
233 #ifdef HASH_LOG
234 # if HASH_LOG+0 < 0
235  {
236  const char *e = getenv("ST_HASH_LOG");
237  if (!e || !*e) init_st = 1;
238  }
239 # endif
240  if (init_st == 0) {
241  init_st = 1;
242  atexit(stat_col);
243  }
244 #endif
245 
246 
247  tbl = st_alloc_table();
248  tbl->type = type;
249  tbl->num_entries = 0;
250  tbl->entries_packed = size <= MAX_PACKED_HASH;
251  if (tbl->entries_packed) {
253  }
254  else {
255  size = new_size(size); /* round up to prime number */
256  }
257  tbl->num_bins = size;
258  tbl->bins = st_alloc_bins(size);
259  tbl->head = 0;
260  tbl->tail = 0;
261 
262  return tbl;
263 }
264 
265 st_table*
267 {
268  return st_init_table_with_size(type, 0);
269 }
270 
271 st_table*
273 {
274  return st_init_table(&type_numhash);
275 }
276 
277 st_table*
279 {
280  return st_init_table_with_size(&type_numhash, size);
281 }
282 
283 st_table*
285 {
286  return st_init_table(&type_strhash);
287 }
288 
289 st_table*
291 {
292  return st_init_table_with_size(&type_strhash, size);
293 }
294 
295 st_table*
297 {
298  return st_init_table(&type_strcasehash);
299 }
300 
301 st_table*
303 {
304  return st_init_table_with_size(&type_strcasehash, size);
305 }
306 
307 void
309 {
310  register st_table_entry *ptr, *next;
311  st_index_t i;
312 
313  if (table->entries_packed) {
314  table->num_entries = 0;
315  table->real_entries = 0;
316  return;
317  }
318 
319  for (i = 0; i < table->num_bins; i++) {
320  ptr = table->bins[i];
321  table->bins[i] = 0;
322  while (ptr != 0) {
323  next = ptr->next;
324  st_free_entry(ptr);
325  ptr = next;
326  }
327  }
328  table->num_entries = 0;
329  table->head = 0;
330  table->tail = 0;
331 }
332 
333 void
335 {
336  st_clear(table);
337  st_free_bins(table->bins, table->num_bins);
338  st_dealloc_table(table);
339 }
340 
341 size_t
343 {
344  if (table->entries_packed) {
345  return table->num_bins * sizeof (void *) + sizeof(st_table);
346  }
347  else {
348  return table->num_entries * sizeof(struct st_table_entry) + table->num_bins * sizeof (void *) + sizeof(st_table);
349  }
350 }
351 
352 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
353 ((ptr) != 0 && ((ptr)->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
354 
355 #ifdef HASH_LOG
356 static void
357 count_collision(const struct st_hash_type *type)
358 {
359  collision.all++;
360  if (type == &type_numhash) {
361  collision.num++;
362  }
363  else if (type == &type_strhash) {
364  collision.strcase++;
365  }
366  else if (type == &type_strcasehash) {
367  collision.str++;
368  }
369 }
370 #define COLLISION (collision_check ? count_collision(table->type) : (void)0)
371 #define FOUND_ENTRY (collision_check ? collision.total++ : (void)0)
372 #else
373 #define COLLISION
374 #define FOUND_ENTRY
375 #endif
376 
377 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) \
378  ((ptr) = find_entry((table), key, (hash_val), ((bin_pos) = (hash_val)%(table)->num_bins)))
379 
380 static st_table_entry *
382 {
383  register st_table_entry *ptr = table->bins[bin_pos];
384  FOUND_ENTRY;
385  if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {
386  COLLISION;
387  while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {
388  ptr = ptr->next;
389  }
390  ptr = ptr->next;
391  }
392  return ptr;
393 }
394 
395 static inline st_index_t
397 {
398  st_index_t i = 0;
399  while (i < table->real_entries &&
400  (PHASH(table, i) != hash_val || !EQUAL(table, key, PKEY(table, i)))) {
401  i++;
402  }
403  return i;
404 }
405 
406 #define collision_check 0
407 
408 int
410 {
411  st_index_t hash_val;
412  register st_table_entry *ptr;
413 
414  hash_val = do_hash(key, table);
415 
416  if (table->entries_packed) {
417  st_index_t i = find_packed_index(table, hash_val, key);
418  if (i < table->real_entries) {
419  if (value != 0) *value = PVAL(table, i);
420  return 1;
421  }
422  return 0;
423  }
424 
425  ptr = find_entry(table, key, hash_val, hash_val % table->num_bins);
426 
427  if (ptr == 0) {
428  return 0;
429  }
430  else {
431  if (value != 0) *value = ptr->record;
432  return 1;
433  }
434 }
435 
436 int
438 {
439  st_index_t hash_val;
440  register st_table_entry *ptr;
441 
442  hash_val = do_hash(key, table);
443 
444  if (table->entries_packed) {
445  st_index_t i = find_packed_index(table, hash_val, key);
446  if (i < table->real_entries) {
447  if (result != 0) *result = PKEY(table, i);
448  return 1;
449  }
450  return 0;
451  }
452 
453  ptr = find_entry(table, key, hash_val, hash_val % table->num_bins);
454 
455  if (ptr == 0) {
456  return 0;
457  }
458  else {
459  if (result != 0) *result = ptr->key;
460  return 1;
461  }
462 }
463 
464 #undef collision_check
465 #define collision_check 1
466 
467 static inline st_table_entry *
469  st_index_t hash_val, register st_index_t bin_pos)
470 {
471  register st_table_entry *entry = st_alloc_entry();
472 
473  entry->next = table->bins[bin_pos];
474  table->bins[bin_pos] = entry;
475  entry->hash = hash_val;
476  entry->key = key;
477  entry->record = value;
478 
479  return entry;
480 }
481 
482 static inline void
484  st_index_t hash_val, register st_index_t bin_pos)
485 {
486  register st_table_entry *entry;
487  if (table->num_entries > ST_DEFAULT_MAX_DENSITY * table->num_bins) {
488  rehash(table);
489  bin_pos = hash_val % table->num_bins;
490  }
491 
492  entry = new_entry(table, key, value, hash_val, bin_pos);
493 
494  if (table->head != 0) {
495  entry->fore = 0;
496  (entry->back = table->tail)->fore = entry;
497  table->tail = entry;
498  }
499  else {
500  table->head = table->tail = entry;
501  entry->fore = entry->back = 0;
502  }
503  table->num_entries++;
504 }
505 
506 static void
508 {
509  st_index_t i;
510  st_packed_entry packed_bins[MAX_PACKED_HASH];
511  register st_table_entry *entry, *preventry = 0, **chain;
512  st_table tmp_table = *table;
513 
514  MEMCPY(packed_bins, PACKED_BINS(table), st_packed_entry, MAX_PACKED_HASH);
515  table->as.packed.entries = packed_bins;
516  tmp_table.entries_packed = 0;
517 #if ST_DEFAULT_INIT_TABLE_SIZE == ST_DEFAULT_PACKED_TABLE_SIZE
518  MEMZERO(tmp_table.bins, st_table_entry*, tmp_table.num_bins);
519 #else
520  tmp_table.bins = st_realloc_bins(tmp_table.bins, ST_DEFAULT_INIT_TABLE_SIZE, tmp_table.num_bins);
522 #endif
523  i = 0;
524  chain = &tmp_table.head;
525  do {
526  st_data_t key = packed_bins[i].key;
527  st_data_t val = packed_bins[i].val;
528  st_index_t hash = packed_bins[i].hash;
529  entry = new_entry(&tmp_table, key, val, hash,
531  *chain = entry;
532  entry->back = preventry;
533  preventry = entry;
534  chain = &entry->fore;
535  } while (++i < MAX_PACKED_HASH);
536  *chain = NULL;
537  tmp_table.tail = entry;
538  *table = tmp_table;
539 }
540 
541 static void
543 {
544  if (table->real_entries < MAX_PACKED_HASH) {
545  st_index_t i = table->real_entries++;
546  PKEY_SET(table, i, key);
547  PVAL_SET(table, i, value);
548  PHASH_SET(table, i, hash_val);
549  table->num_entries++;
550  }
551  else {
552  unpack_entries(table);
553  add_direct(table, key, value, hash_val, hash_val % table->num_bins);
554  }
555 }
556 
557 
558 int
560 {
561  st_index_t hash_val;
562  register st_index_t bin_pos;
563  register st_table_entry *ptr;
564 
565  hash_val = do_hash(key, table);
566 
567  if (table->entries_packed) {
568  st_index_t i = find_packed_index(table, hash_val, key);
569  if (i < table->real_entries) {
570  PVAL_SET(table, i, value);
571  return 1;
572  }
573  add_packed_direct(table, key, value, hash_val);
574  return 0;
575  }
576 
577  FIND_ENTRY(table, ptr, hash_val, bin_pos);
578 
579  if (ptr == 0) {
580  add_direct(table, key, value, hash_val, bin_pos);
581  return 0;
582  }
583  else {
584  ptr->record = value;
585  return 1;
586  }
587 }
588 
589 int
592 {
593  st_index_t hash_val;
594  register st_index_t bin_pos;
595  register st_table_entry *ptr;
596 
597  hash_val = do_hash(key, table);
598 
599  if (table->entries_packed) {
600  st_index_t i = find_packed_index(table, hash_val, key);
601  if (i < table->real_entries) {
602  PVAL_SET(table, i, value);
603  return 1;
604  }
605  key = (*func)(key);
606  add_packed_direct(table, key, value, hash_val);
607  return 0;
608  }
609 
610  FIND_ENTRY(table, ptr, hash_val, bin_pos);
611 
612  if (ptr == 0) {
613  key = (*func)(key);
614  add_direct(table, key, value, hash_val, bin_pos);
615  return 0;
616  }
617  else {
618  ptr->record = value;
619  return 1;
620  }
621 }
622 
623 void
625 {
626  st_index_t hash_val;
627 
628  hash_val = do_hash(key, table);
629  if (table->entries_packed) {
630  add_packed_direct(table, key, value, hash_val);
631  return;
632  }
633 
634  add_direct(table, key, value, hash_val, hash_val % table->num_bins);
635 }
636 
637 static void
638 rehash(register st_table *table)
639 {
640  register st_table_entry *ptr, **new_bins;
641  st_index_t new_num_bins, hash_val;
642 
643  new_num_bins = new_size(table->num_bins+1);
644  new_bins = st_realloc_bins(table->bins, new_num_bins, table->num_bins);
645  table->num_bins = new_num_bins;
646  table->bins = new_bins;
647 
648  if ((ptr = table->head) != 0) {
649  do {
650  hash_val = ptr->hash % new_num_bins;
651  ptr->next = new_bins[hash_val];
652  new_bins[hash_val] = ptr;
653  } while ((ptr = ptr->fore) != 0);
654  }
655 }
656 
657 st_table*
658 st_copy(st_table *old_table)
659 {
660  st_table *new_table;
661  st_table_entry *ptr, *entry, *prev, **tailp;
662  st_index_t num_bins = old_table->num_bins;
663  st_index_t hash_val;
664 
665  new_table = st_alloc_table();
666  if (new_table == 0) {
667  return 0;
668  }
669 
670  *new_table = *old_table;
671  new_table->bins = st_alloc_bins(num_bins);
672 
673  if (new_table->bins == 0) {
674  st_dealloc_table(new_table);
675  return 0;
676  }
677 
678  if (old_table->entries_packed) {
679  MEMCPY(new_table->bins, old_table->bins, st_table_entry*, old_table->num_bins);
680  return new_table;
681  }
682 
683  if ((ptr = old_table->head) != 0) {
684  prev = 0;
685  tailp = &new_table->head;
686  do {
687  entry = st_alloc_entry();
688  if (entry == 0) {
689  st_free_table(new_table);
690  return 0;
691  }
692  *entry = *ptr;
693  hash_val = entry->hash % num_bins;
694  entry->next = new_table->bins[hash_val];
695  new_table->bins[hash_val] = entry;
696  entry->back = prev;
697  *tailp = prev = entry;
698  tailp = &entry->fore;
699  } while ((ptr = ptr->fore) != 0);
700  new_table->tail = prev;
701  }
702 
703  return new_table;
704 }
705 
706 static inline void
708 {
709  if (ptr->fore == 0 && ptr->back == 0) {
710  table->head = 0;
711  table->tail = 0;
712  }
713  else {
714  st_table_entry *fore = ptr->fore, *back = ptr->back;
715  if (fore) fore->back = back;
716  if (back) back->fore = fore;
717  if (ptr == table->head) table->head = fore;
718  if (ptr == table->tail) table->tail = back;
719  }
720  table->num_entries--;
721 }
722 
723 int
724 st_delete(register st_table *table, register st_data_t *key, st_data_t *value)
725 {
726  st_index_t hash_val;
727  st_table_entry **prev;
728  register st_table_entry *ptr;
729 
730  hash_val = do_hash(*key, table);
731 
732  if (table->entries_packed) {
733  st_index_t i = find_packed_index(table, hash_val, *key);
734  if (i < table->real_entries) {
735  if (value != 0) *value = PVAL(table, i);
736  *key = PKEY(table, i);
737  remove_packed_entry(table, i);
738  return 1;
739  }
740  if (value != 0) *value = 0;
741  return 0;
742  }
743 
744  prev = &table->bins[hash_val % table->num_bins];
745  for (;(ptr = *prev) != 0; prev = &ptr->next) {
746  if (EQUAL(table, *key, ptr->key)) {
747  *prev = ptr->next;
748  remove_entry(table, ptr);
749  if (value != 0) *value = ptr->record;
750  *key = ptr->key;
751  st_free_entry(ptr);
752  return 1;
753  }
754  }
755 
756  if (value != 0) *value = 0;
757  return 0;
758 }
759 
760 int
761 st_delete_safe(register st_table *table, register st_data_t *key, st_data_t *value, st_data_t never)
762 {
763  st_index_t hash_val;
764  register st_table_entry *ptr;
765 
766  hash_val = do_hash(*key, table);
767 
768  if (table->entries_packed) {
769  st_index_t i = find_packed_index(table, hash_val, *key);
770  if (i < table->real_entries) {
771  if (value != 0) *value = PVAL(table, i);
772  *key = PKEY(table, i);
773  remove_safe_packed_entry(table, i, never);
774  return 1;
775  }
776  if (value != 0) *value = 0;
777  return 0;
778  }
779 
780  ptr = table->bins[hash_val % table->num_bins];
781 
782  for (; ptr != 0; ptr = ptr->next) {
783  if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
784  remove_entry(table, ptr);
785  *key = ptr->key;
786  if (value != 0) *value = ptr->record;
787  ptr->key = ptr->record = never;
788  return 1;
789  }
790  }
791 
792  if (value != 0) *value = 0;
793  return 0;
794 }
795 
796 void
798 {
799  st_table_entry *ptr, **last, *tmp;
800  st_index_t i;
801 
802  if (table->entries_packed) {
803  st_index_t i = 0, j = 0;
804  while (PKEY(table, i) != never) {
805  if (i++ == table->real_entries) return;
806  }
807  for (j = i; ++i < table->real_entries;) {
808  if (PKEY(table, i) == never) continue;
809  PACKED_ENT(table, j) = PACKED_ENT(table, i);
810  j++;
811  }
812  table->real_entries = j;
813  /* table->num_entries really should be equal j at this moment, but let set it anyway */
814  table->num_entries = j;
815  return;
816  }
817 
818  for (i = 0; i < table->num_bins; i++) {
819  ptr = *(last = &table->bins[i]);
820  while (ptr != 0) {
821  if (ptr->key == never) {
822  tmp = ptr;
823  *last = ptr = ptr->next;
824  st_free_entry(tmp);
825  }
826  else {
827  ptr = *(last = &ptr->next);
828  }
829  }
830  }
831 }
832 
833 int
835 {
836  st_index_t hash_val, bin_pos;
837  register st_table_entry *ptr, **last, *tmp;
838  st_data_t value = 0;
839  int retval, existing = 0;
840 
841  hash_val = do_hash(key, table);
842 
843  if (table->entries_packed) {
844  st_index_t i = find_packed_index(table, hash_val, key);
845  if (i < table->real_entries) {
846  key = PKEY(table, i);
847  value = PVAL(table, i);
848  existing = 1;
849  }
850  {
851  retval = (*func)(&key, &value, arg, existing);
852  if (!table->entries_packed) {
853  FIND_ENTRY(table, ptr, hash_val, bin_pos);
854  goto unpacked;
855  }
856  switch (retval) {
857  case ST_CONTINUE:
858  if (!existing) {
859  add_packed_direct(table, key, value, hash_val);
860  break;
861  }
862  PVAL_SET(table, i, value);
863  break;
864  case ST_DELETE:
865  if (!existing) break;
866  remove_packed_entry(table, i);
867  }
868  }
869  return existing;
870  }
871 
872  FIND_ENTRY(table, ptr, hash_val, bin_pos);
873 
874  if (ptr != 0) {
875  key = ptr->key;
876  value = ptr->record;
877  existing = 1;
878  }
879  {
880  retval = (*func)(&key, &value, arg, existing);
881  unpacked:
882  switch (retval) {
883  case ST_CONTINUE:
884  if (!existing) {
885  add_direct(table, key, value, hash_val, hash_val % table->num_bins);
886  break;
887  }
888  ptr->record = value;
889  break;
890  case ST_DELETE:
891  if (!existing) break;
892  last = &table->bins[bin_pos];
893  for (; (tmp = *last) != 0; last = &tmp->next) {
894  if (ptr == tmp) {
895  tmp = ptr->fore;
896  *last = ptr->next;
897  remove_entry(table, ptr);
898  st_free_entry(ptr);
899  break;
900  }
901  }
902  break;
903  }
904  return existing;
905  }
906 }
907 
908 int
910 {
911  st_table_entry *ptr, **last, *tmp;
912  enum st_retval retval;
913  st_index_t i;
914 
915  if (table->entries_packed) {
916  for (i = 0; i < table->real_entries; i++) {
917  st_data_t key, val;
919  key = PKEY(table, i);
920  val = PVAL(table, i);
921  hash = PHASH(table, i);
922  if (key == never) continue;
923  retval = (*func)(key, val, arg);
924  if (!table->entries_packed) {
925  FIND_ENTRY(table, ptr, hash, i);
926  if (retval == ST_CHECK) {
927  if (!ptr) goto deleted;
928  goto unpacked_continue;
929  }
930  goto unpacked;
931  }
932  switch (retval) {
933  case ST_CHECK: /* check if hash is modified during iteration */
934  if (PHASH(table, i) == 0 && PKEY(table, i) == never) {
935  break;
936  }
937  i = find_packed_index(table, hash, key);
938  if (i == table->real_entries) {
939  goto deleted;
940  }
941  /* fall through */
942  case ST_CONTINUE:
943  break;
944  case ST_STOP:
945  return 0;
946  case ST_DELETE:
947  remove_safe_packed_entry(table, i, never);
948  break;
949  }
950  }
951  return 0;
952  }
953  else {
954  ptr = table->head;
955  }
956 
957  if (ptr != 0) {
958  do {
959  if (ptr->key == never)
960  goto unpacked_continue;
961  i = ptr->hash % table->num_bins;
962  retval = (*func)(ptr->key, ptr->record, arg);
963  unpacked:
964  switch (retval) {
965  case ST_CHECK: /* check if hash is modified during iteration */
966  for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) {
967  if (!tmp) {
968  deleted:
969  /* call func with error notice */
970  retval = (*func)(0, 0, arg, 1);
971  return 1;
972  }
973  }
974  /* fall through */
975  case ST_CONTINUE:
976  unpacked_continue:
977  ptr = ptr->fore;
978  break;
979  case ST_STOP:
980  return 0;
981  case ST_DELETE:
982  last = &table->bins[ptr->hash % table->num_bins];
983  for (; (tmp = *last) != 0; last = &tmp->next) {
984  if (ptr == tmp) {
985  tmp = ptr->fore;
986  remove_entry(table, ptr);
987  ptr->key = ptr->record = never;
988  ptr->hash = 0;
989  ptr = tmp;
990  break;
991  }
992  }
993  }
994  } while (ptr && table->head);
995  }
996  return 0;
997 }
998 
999 int
1001 {
1002  st_table_entry *ptr, **last, *tmp;
1003  enum st_retval retval;
1004  st_index_t i;
1005 
1006  if (table->entries_packed) {
1007  for (i = 0; i < table->real_entries; i++) {
1008  st_data_t key, val, hash;
1009  key = PKEY(table, i);
1010  val = PVAL(table, i);
1011  hash = PHASH(table, i);
1012  retval = (*func)(key, val, arg);
1013  if (!table->entries_packed) {
1014  FIND_ENTRY(table, ptr, hash, i);
1015  if (!ptr) return 0;
1016  goto unpacked;
1017  }
1018  switch (retval) {
1019  case ST_CONTINUE:
1020  break;
1021  case ST_CHECK:
1022  case ST_STOP:
1023  return 0;
1024  case ST_DELETE:
1025  remove_packed_entry(table, i);
1026  i--;
1027  break;
1028  }
1029  }
1030  return 0;
1031  }
1032  else {
1033  ptr = table->head;
1034  }
1035 
1036  if (ptr != 0) {
1037  do {
1038  i = ptr->hash % table->num_bins;
1039  retval = (*func)(ptr->key, ptr->record, arg);
1040  unpacked:
1041  switch (retval) {
1042  case ST_CONTINUE:
1043  ptr = ptr->fore;
1044  break;
1045  case ST_CHECK:
1046  case ST_STOP:
1047  return 0;
1048  case ST_DELETE:
1049  last = &table->bins[ptr->hash % table->num_bins];
1050  for (; (tmp = *last) != 0; last = &tmp->next) {
1051  if (ptr == tmp) {
1052  tmp = ptr->fore;
1053  *last = ptr->next;
1054  remove_entry(table, ptr);
1055  st_free_entry(ptr);
1056  ptr = tmp;
1057  break;
1058  }
1059  }
1060  }
1061  } while (ptr && table->head);
1062  }
1063  return 0;
1064 }
1065 
1066 #if 0 /* unused right now */
1067 int
1069 {
1070  st_table_entry *ptr, **last, *tmp;
1071  enum st_retval retval;
1072  int i;
1073 
1074  if (table->entries_packed) {
1075  for (i = table->num_entries-1; 0 <= i; i--) {
1076  int j;
1077  st_data_t key, val;
1078  key = PKEY(table, i);
1079  val = PVAL(table, i);
1080  retval = (*func)(key, val, arg);
1081  switch (retval) {
1082  case ST_CHECK: /* check if hash is modified during iteration */
1083  for (j = 0; j < table->num_entries; j++) {
1084  if (PKEY(table, j) == key)
1085  break;
1086  }
1087  if (j == table->num_entries) {
1088  /* call func with error notice */
1089  retval = (*func)(0, 0, arg, 1);
1090  return 1;
1091  }
1092  /* fall through */
1093  case ST_CONTINUE:
1094  break;
1095  case ST_STOP:
1096  return 0;
1097  case ST_DELETE:
1098  remove_packed_entry(table, i);
1099  break;
1100  }
1101  }
1102  return 0;
1103  }
1104 
1105  if ((ptr = table->head) != 0) {
1106  ptr = ptr->back;
1107  do {
1108  retval = (*func)(ptr->key, ptr->record, arg, 0);
1109  switch (retval) {
1110  case ST_CHECK: /* check if hash is modified during iteration */
1111  i = ptr->hash % table->num_bins;
1112  for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) {
1113  if (!tmp) {
1114  /* call func with error notice */
1115  retval = (*func)(0, 0, arg, 1);
1116  return 1;
1117  }
1118  }
1119  /* fall through */
1120  case ST_CONTINUE:
1121  ptr = ptr->back;
1122  break;
1123  case ST_STOP:
1124  return 0;
1125  case ST_DELETE:
1126  last = &table->bins[ptr->hash % table->num_bins];
1127  for (; (tmp = *last) != 0; last = &tmp->next) {
1128  if (ptr == tmp) {
1129  tmp = ptr->back;
1130  *last = ptr->next;
1131  remove_entry(table, ptr);
1132  st_free_entry(ptr);
1133  ptr = tmp;
1134  break;
1135  }
1136  }
1137  ptr = ptr->next;
1138  free(tmp);
1139  table->num_entries--;
1140  }
1141  } while (ptr && table->head);
1142  }
1143  return 0;
1144 }
1145 #endif
1146 
1147 /*
1148  * hash_32 - 32 bit Fowler/Noll/Vo FNV-1a hash code
1149  *
1150  * @(#) $Hash32: Revision: 1.1 $
1151  * @(#) $Hash32: Id: hash_32a.c,v 1.1 2003/10/03 20:38:53 chongo Exp $
1152  * @(#) $Hash32: Source: /usr/local/src/cmd/fnv/RCS/hash_32a.c,v $
1153  *
1154  ***
1155  *
1156  * Fowler/Noll/Vo hash
1157  *
1158  * The basis of this hash algorithm was taken from an idea sent
1159  * as reviewer comments to the IEEE POSIX P1003.2 committee by:
1160  *
1161  * Phong Vo (http://www.research.att.com/info/kpv/)
1162  * Glenn Fowler (http://www.research.att.com/~gsf/)
1163  *
1164  * In a subsequent ballot round:
1165  *
1166  * Landon Curt Noll (http://www.isthe.com/chongo/)
1167  *
1168  * improved on their algorithm. Some people tried this hash
1169  * and found that it worked rather well. In an EMail message
1170  * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
1171  *
1172  * FNV hashes are designed to be fast while maintaining a low
1173  * collision rate. The FNV speed allows one to quickly hash lots
1174  * of data while maintaining a reasonable collision rate. See:
1175  *
1176  * http://www.isthe.com/chongo/tech/comp/fnv/index.html
1177  *
1178  * for more details as well as other forms of the FNV hash.
1179  ***
1180  *
1181  * To use the recommended 32 bit FNV-1a hash, pass FNV1_32A_INIT as the
1182  * Fnv32_t hashval argument to fnv_32a_buf() or fnv_32a_str().
1183  *
1184  ***
1185  *
1186  * Please do not copyright this code. This code is in the public domain.
1187  *
1188  * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
1189  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
1190  * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
1191  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
1192  * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
1193  * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
1194  * PERFORMANCE OF THIS SOFTWARE.
1195  *
1196  * By:
1197  * chongo <Landon Curt Noll> /\oo/\
1198  * http://www.isthe.com/chongo/
1199  *
1200  * Share and Enjoy! :-)
1201  */
1202 
1203 /*
1204  * 32 bit FNV-1 and FNV-1a non-zero initial basis
1205  *
1206  * The FNV-1 initial basis is the FNV-0 hash of the following 32 octets:
1207  *
1208  * chongo <Landon Curt Noll> /\../\
1209  *
1210  * NOTE: The \'s above are not back-slashing escape characters.
1211  * They are literal ASCII backslash 0x5c characters.
1212  *
1213  * NOTE: The FNV-1a initial basis is the same value as FNV-1 by definition.
1214  */
1215 #define FNV1_32A_INIT 0x811c9dc5
1216 
1217 /*
1218  * 32 bit magic FNV-1a prime
1219  */
1220 #define FNV_32_PRIME 0x01000193
1221 
1222 #ifdef ST_USE_FNV1
1223 static st_index_t
1224 strhash(st_data_t arg)
1225 {
1226  register const char *string = (const char *)arg;
1227  register st_index_t hval = FNV1_32A_INIT;
1228 
1229  /*
1230  * FNV-1a hash each octet in the buffer
1231  */
1232  while (*string) {
1233  /* xor the bottom with the current octet */
1234  hval ^= (unsigned int)*string++;
1235 
1236  /* multiply by the 32 bit FNV magic prime mod 2^32 */
1237  hval *= FNV_32_PRIME;
1238  }
1239  return hval;
1240 }
1241 #else
1242 
1243 #ifndef UNALIGNED_WORD_ACCESS
1244 # if defined(__i386) || defined(__i386__) || defined(_M_IX86) || \
1245  defined(__x86_64) || defined(__x86_64__) || defined(_M_AMD86) || \
1246  defined(__mc68020__)
1247 # define UNALIGNED_WORD_ACCESS 1
1248 # endif
1249 #endif
1250 #ifndef UNALIGNED_WORD_ACCESS
1251 # define UNALIGNED_WORD_ACCESS 0
1252 #endif
1253 
1254 /* MurmurHash described in http://murmurhash.googlepages.com/ */
1255 #ifndef MURMUR
1256 #define MURMUR 2
1257 #endif
1258 
1259 #define MurmurMagic_1 (st_index_t)0xc6a4a793
1260 #define MurmurMagic_2 (st_index_t)0x5bd1e995
1261 #if MURMUR == 1
1262 #define MurmurMagic MurmurMagic_1
1263 #elif MURMUR == 2
1264 #if SIZEOF_ST_INDEX_T > 4
1265 #define MurmurMagic ((MurmurMagic_1 << 32) | MurmurMagic_2)
1266 #else
1267 #define MurmurMagic MurmurMagic_2
1268 #endif
1269 #endif
1270 
1271 static inline st_index_t
1273 {
1274  const st_index_t m = MurmurMagic;
1275 #if MURMUR == 1
1276  h += k;
1277  h *= m;
1278  h ^= h >> r;
1279 #elif MURMUR == 2
1280  k *= m;
1281  k ^= k >> r;
1282  k *= m;
1283 
1284  h *= m;
1285  h ^= k;
1286 #endif
1287  return h;
1288 }
1289 
1290 static inline st_index_t
1292 {
1293 #if MURMUR == 1
1294  h = murmur(h, 0, 10);
1295  h = murmur(h, 0, 17);
1296 #elif MURMUR == 2
1297  h ^= h >> 13;
1298  h *= MurmurMagic;
1299  h ^= h >> 15;
1300 #endif
1301  return h;
1302 }
1303 
1304 #define murmur_step(h, k) murmur((h), (k), 16)
1305 
1306 #if MURMUR == 1
1307 #define murmur1(h) murmur_step((h), 16)
1308 #else
1309 #define murmur1(h) murmur_step((h), 24)
1310 #endif
1311 
1312 st_index_t
1313 st_hash(const void *ptr, size_t len, st_index_t h)
1314 {
1315  const char *data = ptr;
1316  st_index_t t = 0;
1317 
1318  h += 0xdeadbeef;
1319 
1320 #define data_at(n) (st_index_t)((unsigned char)data[(n)])
1321 #define UNALIGNED_ADD_4 UNALIGNED_ADD(2); UNALIGNED_ADD(1); UNALIGNED_ADD(0)
1322 #if SIZEOF_ST_INDEX_T > 4
1323 #define UNALIGNED_ADD_8 UNALIGNED_ADD(6); UNALIGNED_ADD(5); UNALIGNED_ADD(4); UNALIGNED_ADD(3); UNALIGNED_ADD_4
1324 #if SIZEOF_ST_INDEX_T > 8
1325 #define UNALIGNED_ADD_16 UNALIGNED_ADD(14); UNALIGNED_ADD(13); UNALIGNED_ADD(12); UNALIGNED_ADD(11); \
1326  UNALIGNED_ADD(10); UNALIGNED_ADD(9); UNALIGNED_ADD(8); UNALIGNED_ADD(7); UNALIGNED_ADD_8
1327 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_16
1328 #endif
1329 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_8
1330 #else
1331 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_4
1332 #endif
1333  if (len >= sizeof(st_index_t)) {
1334 #if !UNALIGNED_WORD_ACCESS
1335  int align = (int)((st_data_t)data % sizeof(st_index_t));
1336  if (align) {
1337  st_index_t d = 0;
1338  int sl, sr, pack;
1339 
1340  switch (align) {
1341 #ifdef WORDS_BIGENDIAN
1342 # define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \
1343  t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 2)
1344 #else
1345 # define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \
1346  t |= data_at(n) << CHAR_BIT*(n)
1347 #endif
1349 #undef UNALIGNED_ADD
1350  }
1351 
1352 #ifdef WORDS_BIGENDIAN
1353  t >>= (CHAR_BIT * align) - CHAR_BIT;
1354 #else
1355  t <<= (CHAR_BIT * align);
1356 #endif
1357 
1358  data += sizeof(st_index_t)-align;
1359  len -= sizeof(st_index_t)-align;
1360 
1361  sl = CHAR_BIT * (SIZEOF_ST_INDEX_T-align);
1362  sr = CHAR_BIT * align;
1363 
1364  while (len >= sizeof(st_index_t)) {
1365  d = *(st_index_t *)data;
1366 #ifdef WORDS_BIGENDIAN
1367  t = (t << sr) | (d >> sl);
1368 #else
1369  t = (t >> sr) | (d << sl);
1370 #endif
1371  h = murmur_step(h, t);
1372  t = d;
1373  data += sizeof(st_index_t);
1374  len -= sizeof(st_index_t);
1375  }
1376 
1377  pack = len < (size_t)align ? (int)len : align;
1378  d = 0;
1379  switch (pack) {
1380 #ifdef WORDS_BIGENDIAN
1381 # define UNALIGNED_ADD(n) case (n) + 1: \
1382  d |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
1383 #else
1384 # define UNALIGNED_ADD(n) case (n) + 1: \
1385  d |= data_at(n) << CHAR_BIT*(n)
1386 #endif
1388 #undef UNALIGNED_ADD
1389  }
1390 #ifdef WORDS_BIGENDIAN
1391  t = (t << sr) | (d >> sl);
1392 #else
1393  t = (t >> sr) | (d << sl);
1394 #endif
1395 
1396 #if MURMUR == 2
1397  if (len < (size_t)align) goto skip_tail;
1398 #endif
1399  h = murmur_step(h, t);
1400  data += pack;
1401  len -= pack;
1402  }
1403  else
1404 #endif
1405  {
1406  do {
1407  h = murmur_step(h, *(st_index_t *)data);
1408  data += sizeof(st_index_t);
1409  len -= sizeof(st_index_t);
1410  } while (len >= sizeof(st_index_t));
1411  }
1412  }
1413 
1414  t = 0;
1415  switch (len) {
1416 #ifdef WORDS_BIGENDIAN
1417 # define UNALIGNED_ADD(n) case (n) + 1: \
1418  t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
1419 #else
1420 # define UNALIGNED_ADD(n) case (n) + 1: \
1421  t |= data_at(n) << CHAR_BIT*(n)
1422 #endif
1424 #undef UNALIGNED_ADD
1425 #if MURMUR == 1
1426  h = murmur_step(h, t);
1427 #elif MURMUR == 2
1428 # if !UNALIGNED_WORD_ACCESS
1429  skip_tail:
1430 # endif
1431  h ^= t;
1432  h *= MurmurMagic;
1433 #endif
1434  }
1435 
1436  return murmur_finish(h);
1437 }
1438 
1439 st_index_t
1441 {
1442  return murmur_step(h + i, 16);
1443 }
1444 
1445 st_index_t
1447 {
1448  st_index_t v = 0;
1449  h += i;
1450 #ifdef WORDS_BIGENDIAN
1451 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8
1452  v = murmur1(v + (h >> 12*8));
1453 #endif
1454 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8
1455  v = murmur1(v + (h >> 8*8));
1456 #endif
1457 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8
1458  v = murmur1(v + (h >> 4*8));
1459 #endif
1460 #endif
1461  v = murmur1(v + h);
1462 #ifndef WORDS_BIGENDIAN
1463 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8
1464  v = murmur1(v + (h >> 4*8));
1465 #endif
1466 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8
1467  v = murmur1(v + (h >> 8*8));
1468 #endif
1469 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8
1470  v = murmur1(v + (h >> 12*8));
1471 #endif
1472 #endif
1473  return v;
1474 }
1475 
1476 st_index_t
1478 {
1479  h = murmur_step(h, 10);
1480  h = murmur_step(h, 17);
1481  return h;
1482 }
1483 
1484 #undef st_hash_start
1485 st_index_t
1487 {
1488  return h;
1489 }
1490 
1491 static st_index_t
1493 {
1494  register const char *string = (const char *)arg;
1495  return st_hash(string, strlen(string), FNV1_32A_INIT);
1496 }
1497 #endif
1498 
1499 int
1500 st_strcasecmp(const char *s1, const char *s2)
1501 {
1502  unsigned int c1, c2;
1503 
1504  while (1) {
1505  c1 = (unsigned char)*s1++;
1506  c2 = (unsigned char)*s2++;
1507  if (c1 == '\0' || c2 == '\0') {
1508  if (c1 != '\0') return 1;
1509  if (c2 != '\0') return -1;
1510  return 0;
1511  }
1512  if ((unsigned int)(c1 - 'A') <= ('Z' - 'A')) c1 += 'a' - 'A';
1513  if ((unsigned int)(c2 - 'A') <= ('Z' - 'A')) c2 += 'a' - 'A';
1514  if (c1 != c2) {
1515  if (c1 > c2)
1516  return 1;
1517  else
1518  return -1;
1519  }
1520  }
1521 }
1522 
1523 int
1524 st_strncasecmp(const char *s1, const char *s2, size_t n)
1525 {
1526  unsigned int c1, c2;
1527 
1528  while (n--) {
1529  c1 = (unsigned char)*s1++;
1530  c2 = (unsigned char)*s2++;
1531  if (c1 == '\0' || c2 == '\0') {
1532  if (c1 != '\0') return 1;
1533  if (c2 != '\0') return -1;
1534  return 0;
1535  }
1536  if ((unsigned int)(c1 - 'A') <= ('Z' - 'A')) c1 += 'a' - 'A';
1537  if ((unsigned int)(c2 - 'A') <= ('Z' - 'A')) c2 += 'a' - 'A';
1538  if (c1 != c2) {
1539  if (c1 > c2)
1540  return 1;
1541  else
1542  return -1;
1543  }
1544  }
1545  return 0;
1546 }
1547 
1548 static st_index_t
1550 {
1551  register const char *string = (const char *)arg;
1552  register st_index_t hval = FNV1_32A_INIT;
1553 
1554  /*
1555  * FNV-1a hash each octet in the buffer
1556  */
1557  while (*string) {
1558  unsigned int c = (unsigned char)*string++;
1559  if ((unsigned int)(c - 'A') <= ('Z' - 'A')) c += 'a' - 'A';
1560  hval ^= c;
1561 
1562  /* multiply by the 32 bit FNV magic prime mod 2^32 */
1563  hval *= FNV_32_PRIME;
1564  }
1565  return hval;
1566 }
1567 
1568 int
1570 {
1571  return x != y;
1572 }
1573 
1574 st_index_t
1576 {
1577  return (st_index_t)n;
1578 }
VALUE data
Definition: tcltklib.c:3368
#define PKEY(table, i)
Definition: st.c:114
volatile VALUE tmp
Definition: tcltklib.c:10209
static st_index_t new_size(st_index_t size)
Definition: st.c:184
ssize_t n
Definition: bigdecimal.c:5655
st_index_t hash
Definition: st.c:21
#define MurmurMagic
Definition: st.c:1267
VP_EXPORT int
Definition: bigdecimal.c:5050
st_table * st_init_table_with_size(const struct st_hash_type *, st_index_t)
Definition: st.c:229
#define PVAL_SET(table, i, v)
Definition: st.c:118
size_t strlen(const char *)
#define st_hash_start(h)
int st_lookup(st_table *, st_data_t, st_data_t *)
void st_add_direct(st_table *, st_data_t, st_data_t)
Definition: st.c:624
static st_table_entry * new_entry(st_table *table, st_data_t key, st_data_t value, st_index_t hash_val, register st_index_t bin_pos)
Definition: st.c:468
static st_index_t find_packed_index(st_table *table, st_index_t hash_val, st_data_t key)
Definition: st.c:396
st_table * st_init_numtable(void)
Definition: st.c:272
#define FNV_32_PRIME
Definition: st.c:1220
static int VALUE table
Definition: tcltklib.c:10138
SSL_METHOD *(* func)(void)
Definition: ossl_ssl.c:108
#define MINSIZE
Definition: st.c:146
ssize_t i
Definition: bigdecimal.c:5655
#define PACKED_UNIT
Definition: st.c:39
st_index_t num_bins
Definition: ripper.y:79
int st_update_callback_func(st_data_t *key, st_data_t *value, st_data_t arg, int existing)
Definition: ripper.y:124
st_table * st_init_strcasetable(void)
Definition: st.c:296
int st_numcmp(st_data_t, st_data_t)
Definition: st.c:1569
int st_insert2(st_table *, st_data_t, st_data_t, st_data_t(*)(st_data_t))
st_table_entry * next
Definition: st.c:24
struct st_hash_type * type
Definition: ripper.y:78
#define MEMMOVE(p1, p2, type, n)
void rb_raise(VALUE exc, const char *fmt,...)
Definition: error.c:1780
size_t st_memsize(const st_table *)
Definition: st.c:342
st_table * st_init_strtable(void)
Definition: st.c:284
#define st_free_entry(entry)
Definition: st.c:92
st_data_t record
Definition: st.c:23
r
Definition: bigdecimal.c:1196
#define st_dealloc_table(table)
Definition: st.c:94
static void add_packed_direct(st_table *table, st_data_t key, st_data_t value, st_index_t hash_val)
Definition: st.c:542
unsigned int last
Definition: nkf.c:4310
#define murmur1(h)
Definition: st.c:1309
st_index_t st_hash(const void *ptr, size_t len, st_index_t h)
Definition: st.c:1313
st_retval
Definition: ripper.y:108
VALUE tbl
Definition: tkutil.c:1280
#define ST_DEFAULT_MAX_DENSITY
Definition: st.c:35
#define MAX_PACKED_HASH
Definition: st.c:40
static void unpack_entries(register st_table *table)
Definition: st.c:507
#define SIZEOF_ST_INDEX_T
unsigned int entries_packed
Definition: ripper.y:80
d
Definition: strlcat.c:58
#define MEMZERO(p, type, n)
int st_strcasecmp(const char *s1, const char *s2)
Definition: st.c:1500
int st_update(st_table *table, st_data_t key, st_update_callback_func *func, st_data_t arg)
Definition: st.c:834
unsigned long st_data_t
Definition: ripper.y:35
int st_delete(st_table *, st_data_t *, st_data_t *)
#define FIND_ENTRY(table, ptr, hash_val, bin_pos)
Definition: st.c:377
st_data_t key
Definition: st.c:30
VALUE hash
Definition: tkutil.c:267
#define st_alloc_table()
Definition: st.c:93
BDIGIT m
Definition: bigdecimal.c:5085
static struct st_hash_type type_strcasehash
Definition: st.c:69
#define val
Definition: tcltklib.c:1949
VALUE rb_eRuntimeError
Definition: error.c:510
#define st_alloc_bins(size)
Definition: st.c:95
#define UNALIGNED_ADD_ALL
static VALUE char * str
Definition: tcltklib.c:3547
Definition: st.c:20
static st_index_t murmur_finish(st_index_t h)
Definition: st.c:1291
#define murmur_step(h, k)
Definition: st.c:1304
#define PVAL(table, i)
Definition: st.c:115
static st_index_t murmur(st_index_t h, st_index_t k, int r)
Definition: st.c:1272
st_index_t st_numhash(st_data_t)
Definition: st.c:1575
int st_strncasecmp(const char *s1, const char *s2, size_t n)
Definition: st.c:1524
static void add_direct(st_table *table, st_data_t key, st_data_t value, st_index_t hash_val, register st_index_t bin_pos)
Definition: st.c:483
static const unsigned int primes[]
Definition: st.c:151
#define ANYARGS
static st_index_t strhash(st_data_t)
Definition: st.c:1492
#define PHASH_SET(table, i, v)
Definition: st.c:119
#define PHASH(table, i)
Definition: st.c:116
#define realloc
Definition: ripper.c:333
static st_table_entry * find_entry(st_table *table, st_data_t key, st_index_t hash_val, st_index_t bin_pos)
Definition: st.c:381
static struct st_hash_type type_strhash
Definition: st.c:63
static st_table_entry ** st_realloc_bins(st_table_entry **bins, st_index_t newsize, st_index_t oldsize)
Definition: st.c:98
#define STATIC_ASSERT(name, expr)
Definition: enum.c:18
st_table_entry * back
Definition: st.c:25
struct st_table_entry * head
Definition: ripper.y:97
union st_table::@74 as
static int VALUE key
Definition: tkutil.c:265
static void rehash(st_table *)
st_table_entry * fore
Definition: st.c:25
register int hval
Definition: lex.c:89
int st_foreach(st_table *, int(*)(ANYARGS), st_data_t)
Definition: st.c:1000
q result
Definition: tcltklib.c:7070
st_data_t val
Definition: st.c:30
volatile VALUE value
Definition: tcltklib.c:9442
#define real_entries
Definition: st.c:109
st_index_t st_hash_uint(st_index_t h, st_index_t i)
Definition: st.c:1446
Definition: st.c:28
int st_get_key(st_table *, st_data_t, st_data_t *)
VALUE retval
Definition: tcltklib.c:7830
static void remove_safe_packed_entry(st_table *table, st_index_t i, st_data_t never)
Definition: st.c:134
int type
Definition: tcltklib.c:111
st_table * st_init_strcasetable_with_size(st_index_t)
Definition: st.c:302
#define PTR_NOT_EQUAL(table, ptr, hash_val, key)
Definition: st.c:352
struct st_table_entry ** bins
Definition: ripper.y:96
#define FNV1_32A_INIT
Definition: st.c:1215
#define ST_DEFAULT_SECOND_TABLE_SIZE
Definition: st.c:37
st_data_t key
Definition: st.c:22
char * getenv()
#define st_free_bins(bins, size)
Definition: st.c:96
#define free(x)
Definition: dln.c:50
return ptr
Definition: tcltklib.c:784
VpDivd * c
Definition: bigdecimal.c:1205
#define CHAR_BIT
Definition: ruby.h:208
int st_reverse_foreach(st_table *, int(*)(ANYARGS), st_data_t)
unsigned int uint32_t
Definition: sha2.h:101
#define MEMCPY(p1, p2, type, n)
st_index_t hash
Definition: st.c:29
arg
Definition: ripper.y:1312
int size
Definition: encoding.c:52
#define f
static void remove_packed_entry(st_table *table, st_index_t i)
Definition: st.c:123
#define type_numhash
#define do_hash(key, table)
Definition: st.c:87
struct st_hash_type st_hashtype_num
int t
Definition: ripper.c:13760
#define EQUAL(table, x, y)
Definition: st.c:85
#define ST_DEFAULT_PACKED_TABLE_SIZE
Definition: st.c:38
st_data_t st_index_t
Definition: ripper.y:63
st_index_t real_entries
Definition: ripper.y:101
int st_insert(st_table *, st_data_t, st_data_t)
int st_foreach_check(st_table *, int(*)(ANYARGS), st_data_t, st_data_t)
Definition: st.c:909
void st_clear(st_table *)
Definition: st.c:308
st_table * st_init_table(const struct st_hash_type *)
Definition: st.c:266
st_index_t st_hash_uint32(st_index_t h, uint32_t i)
Definition: st.c:1440
#define ST_DEFAULT_INIT_TABLE_SIZE
Definition: st.c:36
#define PACKED_BINS(table)
Definition: st.c:112
BDIGIT e
Definition: bigdecimal.c:5085
#define st_alloc_entry()
Definition: st.c:91
st_table * st_copy(st_table *)
Definition: st.c:658
st_table * st_init_strtable_with_size(st_index_t)
Definition: st.c:290
struct st_packed_entry st_packed_entry
#define snprintf
st_table * st_init_numtable_with_size(st_index_t)
Definition: st.c:278
#define bins
Definition: st.c:106
static st_index_t strcasehash(st_data_t)
Definition: st.c:1549
BDIGIT v
Definition: bigdecimal.c:5656
int st_delete_safe(st_table *, st_data_t *, st_data_t *, st_data_t)
#define FOUND_ENTRY
Definition: st.c:374
#define NULL
Definition: _sdbm.c:103
st_index_t st_hash_end(st_index_t h)
Definition: st.c:1477
void st_cleanup_safe(st_table *, st_data_t)
Definition: st.c:797
struct st_table_entry * tail
Definition: ripper.y:97
st_index_t num_entries
Definition: ripper.y:93
static void remove_entry(st_table *table, st_table_entry *ptr)
Definition: st.c:707
#define COLLISION
Definition: st.c:373
struct st_table::@74::@76 packed
void st_free_table(st_table *)
Definition: st.c:334
#define PACKED_ENT(table, i)
Definition: st.c:113
#define numberof(array)
Definition: st.c:83
#define PKEY_SET(table, i, v)
Definition: st.c:117
size_t len
Definition: tcltklib.c:3568