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