Ruby 1.9.3p327(2012-11-10revision37606)
st.c
Go to the documentation of this file.
00001 /* This is a public domain general purpose hash table package written by Peter Moore @ UCB. */
00002 
00003 /* static       char    sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; */
00004 
00005 #ifdef NOT_RUBY
00006 #include "regint.h"
00007 #include "st.h"
00008 #else
00009 #include "ruby/ruby.h"
00010 #endif
00011 
00012 #include <stdio.h>
00013 #ifdef HAVE_STDLIB_H
00014 #include <stdlib.h>
00015 #endif
00016 #include <string.h>
00017 
00018 typedef struct st_table_entry st_table_entry;
00019 
00020 struct st_table_entry {
00021     st_index_t hash;
00022     st_data_t key;
00023     st_data_t record;
00024     st_table_entry *next;
00025     st_table_entry *fore, *back;
00026 };
00027 
00028 #define ST_DEFAULT_MAX_DENSITY 5
00029 #define ST_DEFAULT_INIT_TABLE_SIZE 11
00030 
00031     /*
00032      * DEFAULT_MAX_DENSITY is the default for the largest we allow the
00033      * average number of items per bin before increasing the number of
00034      * bins
00035      *
00036      * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
00037      * allocated initially
00038      *
00039      */
00040 
00041 static const struct st_hash_type type_numhash = {
00042     st_numcmp,
00043     st_numhash,
00044 };
00045 
00046 /* extern int strcmp(const char *, const char *); */
00047 static st_index_t strhash(st_data_t);
00048 static const struct st_hash_type type_strhash = {
00049     strcmp,
00050     strhash,
00051 };
00052 
00053 static st_index_t strcasehash(st_data_t);
00054 static const struct st_hash_type type_strcasehash = {
00055     st_strcasecmp,
00056     strcasehash,
00057 };
00058 
00059 static void rehash(st_table *);
00060 
00061 #ifdef RUBY
00062 #define malloc xmalloc
00063 #define calloc xcalloc
00064 #define free(x) xfree(x)
00065 #endif
00066 
00067 #define numberof(array) (int)(sizeof(array) / sizeof((array)[0]))
00068 
00069 #define alloc(type) (type*)malloc((size_t)sizeof(type))
00070 #define Calloc(n,s) (char*)calloc((n),(s))
00071 
00072 #define EQUAL(table,x,y) ((x)==(y) || (*(table)->type->compare)((x),(y)) == 0)
00073 
00074 /* remove cast to unsigned int in the future */
00075 #define do_hash(key,table) (unsigned int)(st_index_t)(*(table)->type->hash)((key))
00076 #define do_hash_bin(key,table) (do_hash((key), (table))%(table)->num_bins)
00077 
00078 /*
00079  * MINSIZE is the minimum size of a dictionary.
00080  */
00081 
00082 #define MINSIZE 8
00083 
00084 /*
00085 Table of prime numbers 2^n+a, 2<=n<=30.
00086 */
00087 static const unsigned int primes[] = {
00088         8 + 3,
00089         16 + 3,
00090         32 + 5,
00091         64 + 3,
00092         128 + 3,
00093         256 + 27,
00094         512 + 9,
00095         1024 + 9,
00096         2048 + 5,
00097         4096 + 3,
00098         8192 + 27,
00099         16384 + 43,
00100         32768 + 3,
00101         65536 + 45,
00102         131072 + 29,
00103         262144 + 3,
00104         524288 + 21,
00105         1048576 + 7,
00106         2097152 + 17,
00107         4194304 + 15,
00108         8388608 + 9,
00109         16777216 + 43,
00110         33554432 + 35,
00111         67108864 + 15,
00112         134217728 + 29,
00113         268435456 + 3,
00114         536870912 + 11,
00115         1073741824 + 85,
00116         0
00117 };
00118 
00119 static st_index_t
00120 new_size(st_index_t size)
00121 {
00122     int i;
00123 
00124 #if 0
00125     for (i=3; i<31; i++) {
00126         if ((1<<i) > size) return 1<<i;
00127     }
00128     return -1;
00129 #else
00130     st_index_t newsize;
00131 
00132     for (i = 0, newsize = MINSIZE; i < numberof(primes); i++, newsize <<= 1) {
00133         if (newsize > size) return primes[i];
00134     }
00135     /* Ran out of polynomials */
00136 #ifndef NOT_RUBY
00137     rb_raise(rb_eRuntimeError, "st_table too big");
00138 #endif
00139     return -1;                  /* should raise exception */
00140 #endif
00141 }
00142 
00143 #ifdef HASH_LOG
00144 #ifdef HAVE_UNISTD_H
00145 #include <unistd.h>
00146 #endif
00147 static struct {
00148     int all, total, num, str, strcase;
00149 }  collision;
00150 static int init_st = 0;
00151 
00152 static void
00153 stat_col(void)
00154 {
00155     char fname[10+sizeof(long)*3];
00156     FILE *f = fopen((snprintf(fname, sizeof(fname), "/tmp/col%ld", (long)getpid()), fname), "w");
00157     fprintf(f, "collision: %d / %d (%6.2f)\n", collision.all, collision.total,
00158             ((double)collision.all / (collision.total)) * 100);
00159     fprintf(f, "num: %d, str: %d, strcase: %d\n", collision.num, collision.str, collision.strcase);
00160     fclose(f);
00161 }
00162 #endif
00163 
00164 #define MAX_PACKED_NUMHASH (ST_DEFAULT_INIT_TABLE_SIZE/2)
00165 
00166 st_table*
00167 st_init_table_with_size(const struct st_hash_type *type, st_index_t size)
00168 {
00169     st_table *tbl;
00170 
00171 #ifdef HASH_LOG
00172 # if HASH_LOG+0 < 0
00173     {
00174         const char *e = getenv("ST_HASH_LOG");
00175         if (!e || !*e) init_st = 1;
00176     }
00177 # endif
00178     if (init_st == 0) {
00179         init_st = 1;
00180         atexit(stat_col);
00181     }
00182 #endif
00183 
00184     size = new_size(size);      /* round up to prime number */
00185 
00186     tbl = alloc(st_table);
00187     tbl->type = type;
00188     tbl->num_entries = 0;
00189     tbl->entries_packed = type == &type_numhash && size/2 <= MAX_PACKED_NUMHASH;
00190     tbl->num_bins = size;
00191     tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
00192     tbl->head = 0;
00193     tbl->tail = 0;
00194 
00195     return tbl;
00196 }
00197 
00198 st_table*
00199 st_init_table(const struct st_hash_type *type)
00200 {
00201     return st_init_table_with_size(type, 0);
00202 }
00203 
00204 st_table*
00205 st_init_numtable(void)
00206 {
00207     return st_init_table(&type_numhash);
00208 }
00209 
00210 st_table*
00211 st_init_numtable_with_size(st_index_t size)
00212 {
00213     return st_init_table_with_size(&type_numhash, size);
00214 }
00215 
00216 st_table*
00217 st_init_strtable(void)
00218 {
00219     return st_init_table(&type_strhash);
00220 }
00221 
00222 st_table*
00223 st_init_strtable_with_size(st_index_t size)
00224 {
00225     return st_init_table_with_size(&type_strhash, size);
00226 }
00227 
00228 st_table*
00229 st_init_strcasetable(void)
00230 {
00231     return st_init_table(&type_strcasehash);
00232 }
00233 
00234 st_table*
00235 st_init_strcasetable_with_size(st_index_t size)
00236 {
00237     return st_init_table_with_size(&type_strcasehash, size);
00238 }
00239 
00240 void
00241 st_clear(st_table *table)
00242 {
00243     register st_table_entry *ptr, *next;
00244     st_index_t i;
00245 
00246     if (table->entries_packed) {
00247         table->num_entries = 0;
00248         return;
00249     }
00250 
00251     for(i = 0; i < table->num_bins; i++) {
00252         ptr = table->bins[i];
00253         table->bins[i] = 0;
00254         while (ptr != 0) {
00255             next = ptr->next;
00256             free(ptr);
00257             ptr = next;
00258         }
00259     }
00260     table->num_entries = 0;
00261     table->head = 0;
00262     table->tail = 0;
00263 }
00264 
00265 void
00266 st_free_table(st_table *table)
00267 {
00268     st_clear(table);
00269     free(table->bins);
00270     free(table);
00271 }
00272 
00273 size_t
00274 st_memsize(const st_table *table)
00275 {
00276     if (table->entries_packed) {
00277         return table->num_bins * sizeof (void *) + sizeof(st_table);
00278     }
00279     else {
00280         return table->num_entries * sizeof(struct st_table_entry) + table->num_bins * sizeof (void *) + sizeof(st_table);
00281     }
00282 }
00283 
00284 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
00285 ((ptr) != 0 && ((ptr)->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
00286 
00287 #ifdef HASH_LOG
00288 static void
00289 count_collision(const struct st_hash_type *type)
00290 {
00291     collision.all++;
00292     if (type == &type_numhash) {
00293         collision.num++;
00294     }
00295     else if (type == &type_strhash) {
00296         collision.strcase++;
00297     }
00298     else if (type == &type_strcasehash) {
00299         collision.str++;
00300     }
00301 }
00302 #define COLLISION (collision_check ? count_collision(table->type) : (void)0)
00303 #define FOUND_ENTRY (collision_check ? collision.total++ : (void)0)
00304 #else
00305 #define COLLISION
00306 #define FOUND_ENTRY
00307 #endif
00308 
00309 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
00310     (bin_pos) = (hash_val)%(table)->num_bins;\
00311     (ptr) = (table)->bins[(bin_pos)];\
00312     FOUND_ENTRY;\
00313     if (PTR_NOT_EQUAL((table), (ptr), (hash_val), key)) {\
00314         COLLISION;\
00315         while (PTR_NOT_EQUAL((table), (ptr)->next, (hash_val), key)) {\
00316             (ptr) = (ptr)->next;\
00317         }\
00318         (ptr) = (ptr)->next;\
00319     }\
00320 } while (0)
00321 
00322 #define collision_check 0
00323 
00324 int
00325 st_lookup(st_table *table, register st_data_t key, st_data_t *value)
00326 {
00327     st_index_t hash_val, bin_pos;
00328     register st_table_entry *ptr;
00329 
00330     if (table->entries_packed) {
00331         st_index_t i;
00332         for (i = 0; i < table->num_entries; i++) {
00333             if ((st_data_t)table->bins[i*2] == key) {
00334                 if (value !=0) *value = (st_data_t)table->bins[i*2+1];
00335                 return 1;
00336             }
00337         }
00338         return 0;
00339     }
00340 
00341     hash_val = do_hash(key, table);
00342     FIND_ENTRY(table, ptr, hash_val, bin_pos);
00343 
00344     if (ptr == 0) {
00345         return 0;
00346     }
00347     else {
00348         if (value != 0)  *value = ptr->record;
00349         return 1;
00350     }
00351 }
00352 
00353 int
00354 st_get_key(st_table *table, register st_data_t key, st_data_t *result)
00355 {
00356     st_index_t hash_val, bin_pos;
00357     register st_table_entry *ptr;
00358 
00359     if (table->entries_packed) {
00360         st_index_t i;
00361         for (i = 0; i < table->num_entries; i++) {
00362             if ((st_data_t)table->bins[i*2] == key) {
00363                 if (result !=0) *result = (st_data_t)table->bins[i*2];
00364                 return 1;
00365             }
00366         }
00367         return 0;
00368     }
00369 
00370     hash_val = do_hash(key, table);
00371     FIND_ENTRY(table, ptr, hash_val, bin_pos);
00372 
00373     if (ptr == 0) {
00374         return 0;
00375     }
00376     else {
00377         if (result != 0)  *result = ptr->key;
00378         return 1;
00379     }
00380 }
00381 
00382 #undef collision_check
00383 #define collision_check 1
00384 
00385 #define MORE_PACKABLE_P(table) \
00386     ((st_index_t)((table)->num_entries+1) * 2 <= (table)->num_bins && \
00387      (table)->num_entries+1 <= MAX_PACKED_NUMHASH)
00388 
00389 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
00390 do {\
00391     st_table_entry *entry;\
00392     if ((table)->num_entries > ST_DEFAULT_MAX_DENSITY * (table)->num_bins) {\
00393         rehash(table);\
00394         (bin_pos) = (hash_val) % (table)->num_bins;\
00395     }\
00396     \
00397     entry = alloc(st_table_entry);\
00398     \
00399     entry->hash = (hash_val);\
00400     entry->key = (key);\
00401     entry->record = (value);\
00402     entry->next = (table)->bins[(bin_pos)];\
00403     if ((table)->head != 0) {\
00404         entry->fore = 0;\
00405         (entry->back = (table)->tail)->fore = entry;\
00406         (table)->tail = entry;\
00407     }\
00408     else {\
00409         (table)->head = (table)->tail = entry;\
00410         entry->fore = entry->back = 0;\
00411     }\
00412     (table)->bins[(bin_pos)] = entry;\
00413     (table)->num_entries++;\
00414 } while (0)
00415 
00416 static void
00417 unpack_entries(register st_table *table)
00418 {
00419     st_index_t i;
00420     struct st_table_entry *packed_bins[MAX_PACKED_NUMHASH*2];
00421     st_table tmp_table = *table;
00422 
00423     memcpy(packed_bins, table->bins, sizeof(struct st_table_entry *) * table->num_entries*2);
00424     table->bins = packed_bins;
00425     tmp_table.entries_packed = 0;
00426     tmp_table.num_entries = 0;
00427     memset(tmp_table.bins, 0, sizeof(struct st_table_entry *) * tmp_table.num_bins);
00428     for (i = 0; i < table->num_entries; i++) {
00429         st_insert(&tmp_table, (st_data_t)packed_bins[i*2], (st_data_t)packed_bins[i*2+1]);
00430     }
00431     *table = tmp_table;
00432 }
00433 
00434 int
00435 st_insert(register st_table *table, register st_data_t key, st_data_t value)
00436 {
00437     st_index_t hash_val, bin_pos;
00438     register st_table_entry *ptr;
00439 
00440     if (table->entries_packed) {
00441         st_index_t i;
00442         for (i = 0; i < table->num_entries; i++) {
00443             if ((st_data_t)table->bins[i*2] == key) {
00444                 table->bins[i*2+1] = (struct st_table_entry*)value;
00445                 return 1;
00446             }
00447         }
00448         if (MORE_PACKABLE_P(table)) {
00449             i = table->num_entries++;
00450             table->bins[i*2] = (struct st_table_entry*)key;
00451             table->bins[i*2+1] = (struct st_table_entry*)value;
00452             return 0;
00453         }
00454         else {
00455             unpack_entries(table);
00456         }
00457     }
00458 
00459     hash_val = do_hash(key, table);
00460     FIND_ENTRY(table, ptr, hash_val, bin_pos);
00461 
00462     if (ptr == 0) {
00463         ADD_DIRECT(table, key, value, hash_val, bin_pos);
00464         return 0;
00465     }
00466     else {
00467         ptr->record = value;
00468         return 1;
00469     }
00470 }
00471 
00472 int
00473 st_insert2(register st_table *table, register st_data_t key, st_data_t value,
00474            st_data_t (*func)(st_data_t))
00475 {
00476     st_index_t hash_val, bin_pos;
00477     register st_table_entry *ptr;
00478 
00479     if (table->entries_packed) {
00480         st_index_t i;
00481         for (i = 0; i < table->num_entries; i++) {
00482             if ((st_data_t)table->bins[i*2] == key) {
00483                 table->bins[i*2+1] = (struct st_table_entry*)value;
00484                 return 1;
00485             }
00486         }
00487         if (MORE_PACKABLE_P(table)) {
00488             i = table->num_entries++;
00489             table->bins[i*2] = (struct st_table_entry*)key;
00490             table->bins[i*2+1] = (struct st_table_entry*)value;
00491             return 0;
00492         }
00493         else {
00494             unpack_entries(table);
00495         }
00496     }
00497 
00498     hash_val = do_hash(key, table);
00499     FIND_ENTRY(table, ptr, hash_val, bin_pos);
00500 
00501     if (ptr == 0) {
00502         key = (*func)(key);
00503         ADD_DIRECT(table, key, value, hash_val, bin_pos);
00504         return 0;
00505     }
00506     else {
00507         ptr->record = value;
00508         return 1;
00509     }
00510 }
00511 
00512 void
00513 st_add_direct(st_table *table, st_data_t key, st_data_t value)
00514 {
00515     st_index_t hash_val, bin_pos;
00516 
00517     if (table->entries_packed) {
00518         int i;
00519         if (MORE_PACKABLE_P(table)) {
00520             i = table->num_entries++;
00521             table->bins[i*2] = (struct st_table_entry*)key;
00522             table->bins[i*2+1] = (struct st_table_entry*)value;
00523             return;
00524         }
00525         else {
00526             unpack_entries(table);
00527         }
00528     }
00529 
00530     hash_val = do_hash(key, table);
00531     bin_pos = hash_val % table->num_bins;
00532     ADD_DIRECT(table, key, value, hash_val, bin_pos);
00533 }
00534 
00535 static void
00536 rehash(register st_table *table)
00537 {
00538     register st_table_entry *ptr, **new_bins;
00539     st_index_t i, new_num_bins, hash_val;
00540 
00541     new_num_bins = new_size(table->num_bins+1);
00542     new_bins = (st_table_entry**)
00543         xrealloc(table->bins, new_num_bins * sizeof(st_table_entry*));
00544     for (i = 0; i < new_num_bins; ++i) new_bins[i] = 0;
00545     table->num_bins = new_num_bins;
00546     table->bins = new_bins;
00547 
00548     if ((ptr = table->head) != 0) {
00549         do {
00550             hash_val = ptr->hash % new_num_bins;
00551             ptr->next = new_bins[hash_val];
00552             new_bins[hash_val] = ptr;
00553         } while ((ptr = ptr->fore) != 0);
00554     }
00555 }
00556 
00557 st_table*
00558 st_copy(st_table *old_table)
00559 {
00560     st_table *new_table;
00561     st_table_entry *ptr, *entry, *prev, **tail;
00562     st_index_t num_bins = old_table->num_bins;
00563     st_index_t hash_val;
00564 
00565     new_table = alloc(st_table);
00566     if (new_table == 0) {
00567         return 0;
00568     }
00569 
00570     *new_table = *old_table;
00571     new_table->bins = (st_table_entry**)
00572         Calloc((unsigned)num_bins, sizeof(st_table_entry*));
00573 
00574     if (new_table->bins == 0) {
00575         free(new_table);
00576         return 0;
00577     }
00578 
00579     if (old_table->entries_packed) {
00580         memcpy(new_table->bins, old_table->bins, sizeof(struct st_table_entry *) * old_table->num_bins);
00581         return new_table;
00582     }
00583 
00584     if ((ptr = old_table->head) != 0) {
00585         prev = 0;
00586         tail = &new_table->head;
00587         do {
00588             entry = alloc(st_table_entry);
00589             if (entry == 0) {
00590                 st_free_table(new_table);
00591                 return 0;
00592             }
00593             *entry = *ptr;
00594             hash_val = entry->hash % num_bins;
00595             entry->next = new_table->bins[hash_val];
00596             new_table->bins[hash_val] = entry;
00597             entry->back = prev;
00598             *tail = prev = entry;
00599             tail = &entry->fore;
00600         } while ((ptr = ptr->fore) != 0);
00601         new_table->tail = prev;
00602     }
00603 
00604     return new_table;
00605 }
00606 
00607 #define REMOVE_ENTRY(table, ptr) do                                     \
00608     {                                                                   \
00609         if ((ptr)->fore == 0 && (ptr)->back == 0) {                     \
00610             (table)->head = 0;                                          \
00611             (table)->tail = 0;                                          \
00612         }                                                               \
00613         else {                                                          \
00614             st_table_entry *fore = (ptr)->fore, *back = (ptr)->back;    \
00615             if (fore) fore->back = back;                                \
00616             if (back) back->fore = fore;                                \
00617             if ((ptr) == (table)->head) (table)->head = fore;           \
00618             if ((ptr) == (table)->tail) (table)->tail = back;           \
00619         }                                                               \
00620         (table)->num_entries--;                                         \
00621     } while (0)
00622 
00623 int
00624 st_delete(register st_table *table, register st_data_t *key, st_data_t *value)
00625 {
00626     st_index_t hash_val;
00627     st_table_entry **prev;
00628     register st_table_entry *ptr;
00629 
00630     if (table->entries_packed) {
00631         st_index_t i;
00632         for (i = 0; i < table->num_entries; i++) {
00633             if ((st_data_t)table->bins[i*2] == *key) {
00634                 if (value != 0) *value = (st_data_t)table->bins[i*2+1];
00635                 table->num_entries--;
00636                 memmove(&table->bins[i*2], &table->bins[(i+1)*2],
00637                         sizeof(struct st_table_entry*) * 2*(table->num_entries-i));
00638                 return 1;
00639             }
00640         }
00641         if (value != 0) *value = 0;
00642         return 0;
00643     }
00644 
00645     hash_val = do_hash_bin(*key, table);
00646 
00647     for (prev = &table->bins[hash_val]; (ptr = *prev) != 0; prev = &ptr->next) {
00648         if (EQUAL(table, *key, ptr->key)) {
00649             *prev = ptr->next;
00650             REMOVE_ENTRY(table, ptr);
00651             if (value != 0) *value = ptr->record;
00652             *key = ptr->key;
00653             free(ptr);
00654             return 1;
00655         }
00656     }
00657 
00658     if (value != 0) *value = 0;
00659     return 0;
00660 }
00661 
00662 int
00663 st_delete_safe(register st_table *table, register st_data_t *key, st_data_t *value, st_data_t never)
00664 {
00665     st_index_t hash_val;
00666     register st_table_entry *ptr;
00667 
00668     if (table->entries_packed) {
00669         st_index_t i;
00670         for (i = 0; i < table->num_entries; i++) {
00671             if ((st_data_t)table->bins[i*2] == *key) {
00672                 if (value != 0) *value = (st_data_t)table->bins[i*2+1];
00673                 table->bins[i*2] = (void *)never;
00674                 return 1;
00675             }
00676         }
00677         if (value != 0) *value = 0;
00678         return 0;
00679     }
00680 
00681     hash_val = do_hash_bin(*key, table);
00682     ptr = table->bins[hash_val];
00683 
00684     for (; ptr != 0; ptr = ptr->next) {
00685         if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
00686             REMOVE_ENTRY(table, ptr);
00687             *key = ptr->key;
00688             if (value != 0) *value = ptr->record;
00689             ptr->key = ptr->record = never;
00690             return 1;
00691         }
00692     }
00693 
00694     if (value != 0) *value = 0;
00695     return 0;
00696 }
00697 
00698 void
00699 st_cleanup_safe(st_table *table, st_data_t never)
00700 {
00701     st_table_entry *ptr, **last, *tmp;
00702     st_index_t i;
00703 
00704     if (table->entries_packed) {
00705         st_index_t i = 0, j = 0;
00706         while ((st_data_t)table->bins[i*2] != never) {
00707             if (i++ == table->num_entries) return;
00708         }
00709         for (j = i; ++i < table->num_entries;) {
00710             if ((st_data_t)table->bins[i*2] == never) continue;
00711             table->bins[j*2] = table->bins[i*2];
00712             table->bins[j*2+1] = table->bins[i*2+1];
00713             j++;
00714         }
00715         table->num_entries = j;
00716         return;
00717     }
00718 
00719     for (i = 0; i < table->num_bins; i++) {
00720         ptr = *(last = &table->bins[i]);
00721         while (ptr != 0) {
00722             if (ptr->key == never) {
00723                 tmp = ptr;
00724                 *last = ptr = ptr->next;
00725                 free(tmp);
00726             }
00727             else {
00728                 ptr = *(last = &ptr->next);
00729             }
00730         }
00731     }
00732 }
00733 
00734 int
00735 st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
00736 {
00737     st_table_entry *ptr, **last, *tmp;
00738     enum st_retval retval;
00739     st_index_t i;
00740 
00741     if (table->entries_packed) {
00742         for (i = 0; i < table->num_entries; i++) {
00743             st_index_t j;
00744             st_data_t key, val;
00745             key = (st_data_t)table->bins[i*2];
00746             val = (st_data_t)table->bins[i*2+1];
00747             retval = (*func)(key, val, arg);
00748             if (!table->entries_packed) {
00749                 FIND_ENTRY(table, ptr, key, i);
00750                 if (retval == ST_CHECK) {
00751                     if (!ptr) goto deleted;
00752                     goto unpacked_continue;
00753                 }
00754                 goto unpacked;
00755             }
00756             switch (retval) {
00757               case ST_CHECK:    /* check if hash is modified during iteration */
00758                 for (j = 0; j < table->num_entries; j++) {
00759                     if ((st_data_t)table->bins[j*2] == key)
00760                         break;
00761                 }
00762                 if (j == table->num_entries) {
00763                     goto deleted;
00764                 }
00765                 /* fall through */
00766               case ST_CONTINUE:
00767                 break;
00768               case ST_STOP:
00769                 return 0;
00770               case ST_DELETE:
00771                 table->num_entries--;
00772                 memmove(&table->bins[i*2], &table->bins[(i+1)*2],
00773                         sizeof(struct st_table_entry*) * 2*(table->num_entries-i));
00774                 i--;
00775                 break;
00776             }
00777         }
00778         return 0;
00779     }
00780     else {
00781         ptr = table->head;
00782     }
00783 
00784     if (ptr != 0) {
00785         do {
00786             i = ptr->hash % table->num_bins;
00787             retval = (*func)(ptr->key, ptr->record, arg);
00788           unpacked:
00789             switch (retval) {
00790               case ST_CHECK:    /* check if hash is modified during iteration */
00791                 for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) {
00792                     if (!tmp) {
00793                       deleted:
00794                         /* call func with error notice */
00795                         retval = (*func)(0, 0, arg, 1);
00796                         return 1;
00797                     }
00798                 }
00799                 /* fall through */
00800               case ST_CONTINUE:
00801               unpacked_continue:
00802                 ptr = ptr->fore;
00803                 break;
00804               case ST_STOP:
00805                 return 0;
00806               case ST_DELETE:
00807                 last = &table->bins[ptr->hash % table->num_bins];
00808                 for (; (tmp = *last) != 0; last = &tmp->next) {
00809                     if (ptr == tmp) {
00810                         tmp = ptr->fore;
00811                         *last = ptr->next;
00812                         REMOVE_ENTRY(table, ptr);
00813                         free(ptr);
00814                         if (ptr == tmp) return 0;
00815                         ptr = tmp;
00816                         break;
00817                     }
00818                 }
00819             }
00820         } while (ptr && table->head);
00821     }
00822     return 0;
00823 }
00824 
00825 #if 0  /* unused right now */
00826 int
00827 st_reverse_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
00828 {
00829     st_table_entry *ptr, **last, *tmp;
00830     enum st_retval retval;
00831     int i;
00832 
00833     if (table->entries_packed) {
00834         for (i = table->num_entries-1; 0 <= i; i--) {
00835             int j;
00836             st_data_t key, val;
00837             key = (st_data_t)table->bins[i*2];
00838             val = (st_data_t)table->bins[i*2+1];
00839             retval = (*func)(key, val, arg);
00840             switch (retval) {
00841               case ST_CHECK:    /* check if hash is modified during iteration */
00842                 for (j = 0; j < table->num_entries; j++) {
00843                     if ((st_data_t)table->bins[j*2] == key)
00844                         break;
00845                 }
00846                 if (j == table->num_entries) {
00847                     /* call func with error notice */
00848                     retval = (*func)(0, 0, arg, 1);
00849                     return 1;
00850                 }
00851                 /* fall through */
00852               case ST_CONTINUE:
00853                 break;
00854               case ST_STOP:
00855                 return 0;
00856               case ST_DELETE:
00857                 table->num_entries--;
00858                 memmove(&table->bins[i*2], &table->bins[(i+1)*2],
00859                         sizeof(struct st_table_entry*) * 2*(table->num_entries-i));
00860                 break;
00861             }
00862         }
00863         return 0;
00864     }
00865 
00866     if ((ptr = table->head) != 0) {
00867         ptr = ptr->back;
00868         do {
00869             retval = (*func)(ptr->key, ptr->record, arg, 0);
00870             switch (retval) {
00871               case ST_CHECK:    /* check if hash is modified during iteration */
00872                 i = ptr->hash % table->num_bins;
00873                 for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) {
00874                     if (!tmp) {
00875                         /* call func with error notice */
00876                         retval = (*func)(0, 0, arg, 1);
00877                         return 1;
00878                     }
00879                 }
00880                 /* fall through */
00881               case ST_CONTINUE:
00882                 ptr = ptr->back;
00883                 break;
00884               case ST_STOP:
00885                 return 0;
00886               case ST_DELETE:
00887                 last = &table->bins[ptr->hash % table->num_bins];
00888                 for (; (tmp = *last) != 0; last = &tmp->next) {
00889                     if (ptr == tmp) {
00890                         tmp = ptr->back;
00891                         *last = ptr->next;
00892                         REMOVE_ENTRY(table, ptr);
00893                         free(ptr);
00894                         ptr = tmp;
00895                         break;
00896                     }
00897                 }
00898                 ptr = ptr->next;
00899                 free(tmp);
00900                 table->num_entries--;
00901             }
00902         } while (ptr && table->head);
00903     }
00904     return 0;
00905 }
00906 #endif
00907 
00908 /*
00909  * hash_32 - 32 bit Fowler/Noll/Vo FNV-1a hash code
00910  *
00911  * @(#) $Hash32: Revision: 1.1 $
00912  * @(#) $Hash32: Id: hash_32a.c,v 1.1 2003/10/03 20:38:53 chongo Exp $
00913  * @(#) $Hash32: Source: /usr/local/src/cmd/fnv/RCS/hash_32a.c,v $
00914  *
00915  ***
00916  *
00917  * Fowler/Noll/Vo hash
00918  *
00919  * The basis of this hash algorithm was taken from an idea sent
00920  * as reviewer comments to the IEEE POSIX P1003.2 committee by:
00921  *
00922  *      Phong Vo (http://www.research.att.com/info/kpv/)
00923  *      Glenn Fowler (http://www.research.att.com/~gsf/)
00924  *
00925  * In a subsequent ballot round:
00926  *
00927  *      Landon Curt Noll (http://www.isthe.com/chongo/)
00928  *
00929  * improved on their algorithm.  Some people tried this hash
00930  * and found that it worked rather well.  In an EMail message
00931  * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
00932  *
00933  * FNV hashes are designed to be fast while maintaining a low
00934  * collision rate. The FNV speed allows one to quickly hash lots
00935  * of data while maintaining a reasonable collision rate.  See:
00936  *
00937  *      http://www.isthe.com/chongo/tech/comp/fnv/index.html
00938  *
00939  * for more details as well as other forms of the FNV hash.
00940  ***
00941  *
00942  * To use the recommended 32 bit FNV-1a hash, pass FNV1_32A_INIT as the
00943  * Fnv32_t hashval argument to fnv_32a_buf() or fnv_32a_str().
00944  *
00945  ***
00946  *
00947  * Please do not copyright this code.  This code is in the public domain.
00948  *
00949  * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
00950  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
00951  * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
00952  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
00953  * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
00954  * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
00955  * PERFORMANCE OF THIS SOFTWARE.
00956  *
00957  * By:
00958  *      chongo <Landon Curt Noll> /\oo/\
00959  *      http://www.isthe.com/chongo/
00960  *
00961  * Share and Enjoy!     :-)
00962  */
00963 
00964 /*
00965  * 32 bit FNV-1 and FNV-1a non-zero initial basis
00966  *
00967  * The FNV-1 initial basis is the FNV-0 hash of the following 32 octets:
00968  *
00969  *              chongo <Landon Curt Noll> /\../\
00970  *
00971  * NOTE: The \'s above are not back-slashing escape characters.
00972  * They are literal ASCII  backslash 0x5c characters.
00973  *
00974  * NOTE: The FNV-1a initial basis is the same value as FNV-1 by definition.
00975  */
00976 #define FNV1_32A_INIT 0x811c9dc5
00977 
00978 /*
00979  * 32 bit magic FNV-1a prime
00980  */
00981 #define FNV_32_PRIME 0x01000193
00982 
00983 #ifdef ST_USE_FNV1
00984 static st_index_t
00985 strhash(st_data_t arg)
00986 {
00987     register const char *string = (const char *)arg;
00988     register st_index_t hval = FNV1_32A_INIT;
00989 
00990     /*
00991      * FNV-1a hash each octet in the buffer
00992      */
00993     while (*string) {
00994         /* xor the bottom with the current octet */
00995         hval ^= (unsigned int)*string++;
00996 
00997         /* multiply by the 32 bit FNV magic prime mod 2^32 */
00998         hval *= FNV_32_PRIME;
00999     }
01000     return hval;
01001 }
01002 #else
01003 
01004 #ifndef UNALIGNED_WORD_ACCESS
01005 # if defined(__i386) || defined(__i386__) || defined(_M_IX86) || \
01006      defined(__x86_64) || defined(__x86_64__) || defined(_M_AMD86) || \
01007      defined(__mc68020__)
01008 #   define UNALIGNED_WORD_ACCESS 1
01009 # endif
01010 #endif
01011 #ifndef UNALIGNED_WORD_ACCESS
01012 # define UNALIGNED_WORD_ACCESS 0
01013 #endif
01014 
01015 /* MurmurHash described in http://murmurhash.googlepages.com/ */
01016 #ifndef MURMUR
01017 #define MURMUR 2
01018 #endif
01019 
01020 #define MurmurMagic_1 (st_index_t)0xc6a4a793
01021 #define MurmurMagic_2 (st_index_t)0x5bd1e995
01022 #if MURMUR == 1
01023 #define MurmurMagic MurmurMagic_1
01024 #elif MURMUR == 2
01025 #if SIZEOF_ST_INDEX_T > 4
01026 #define MurmurMagic ((MurmurMagic_1 << 32) | MurmurMagic_2)
01027 #else
01028 #define MurmurMagic MurmurMagic_2
01029 #endif
01030 #endif
01031 
01032 static inline st_index_t
01033 murmur(st_index_t h, st_index_t k, int r)
01034 {
01035     const st_index_t m = MurmurMagic;
01036 #if MURMUR == 1
01037     h += k;
01038     h *= m;
01039     h ^= h >> r;
01040 #elif MURMUR == 2
01041     k *= m;
01042     k ^= k >> r;
01043     k *= m;
01044 
01045     h *= m;
01046     h ^= k;
01047 #endif
01048     return h;
01049 }
01050 
01051 static inline st_index_t
01052 murmur_finish(st_index_t h)
01053 {
01054 #if MURMUR == 1
01055     h = murmur(h, 0, 10);
01056     h = murmur(h, 0, 17);
01057 #elif MURMUR == 2
01058     h ^= h >> 13;
01059     h *= MurmurMagic;
01060     h ^= h >> 15;
01061 #endif
01062     return h;
01063 }
01064 
01065 #define murmur_step(h, k) murmur((h), (k), 16)
01066 
01067 #if MURMUR == 1
01068 #define murmur1(h) murmur_step((h), 16)
01069 #else
01070 #define murmur1(h) murmur_step((h), 24)
01071 #endif
01072 
01073 st_index_t
01074 st_hash(const void *ptr, size_t len, st_index_t h)
01075 {
01076     const char *data = ptr;
01077     st_index_t t = 0;
01078 
01079     h += 0xdeadbeef;
01080 
01081 #define data_at(n) (st_index_t)((unsigned char)data[(n)])
01082 #define UNALIGNED_ADD_4 UNALIGNED_ADD(2); UNALIGNED_ADD(1); UNALIGNED_ADD(0)
01083 #if SIZEOF_ST_INDEX_T > 4
01084 #define UNALIGNED_ADD_8 UNALIGNED_ADD(6); UNALIGNED_ADD(5); UNALIGNED_ADD(4); UNALIGNED_ADD(3); UNALIGNED_ADD_4
01085 #if SIZEOF_ST_INDEX_T > 8
01086 #define UNALIGNED_ADD_16 UNALIGNED_ADD(14); UNALIGNED_ADD(13); UNALIGNED_ADD(12); UNALIGNED_ADD(11); \
01087     UNALIGNED_ADD(10); UNALIGNED_ADD(9); UNALIGNED_ADD(8); UNALIGNED_ADD(7); UNALIGNED_ADD_8
01088 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_16
01089 #endif
01090 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_8
01091 #else
01092 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_4
01093 #endif
01094     if (len >= sizeof(st_index_t)) {
01095 #if !UNALIGNED_WORD_ACCESS
01096         int align = (int)((st_data_t)data % sizeof(st_index_t));
01097         if (align) {
01098             st_index_t d = 0;
01099             int sl, sr, pack;
01100 
01101             switch (align) {
01102 #ifdef WORDS_BIGENDIAN
01103 # define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \
01104                 t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 2)
01105 #else
01106 # define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1:     \
01107                 t |= data_at(n) << CHAR_BIT*(n)
01108 #endif
01109                 UNALIGNED_ADD_ALL;
01110 #undef UNALIGNED_ADD
01111             }
01112 
01113 #ifdef WORDS_BIGENDIAN
01114             t >>= (CHAR_BIT * align) - CHAR_BIT;
01115 #else
01116             t <<= (CHAR_BIT * align);
01117 #endif
01118 
01119             data += sizeof(st_index_t)-align;
01120             len -= sizeof(st_index_t)-align;
01121 
01122             sl = CHAR_BIT * (SIZEOF_ST_INDEX_T-align);
01123             sr = CHAR_BIT * align;
01124 
01125             while (len >= sizeof(st_index_t)) {
01126                 d = *(st_index_t *)data;
01127 #ifdef WORDS_BIGENDIAN
01128                 t = (t << sr) | (d >> sl);
01129 #else
01130                 t = (t >> sr) | (d << sl);
01131 #endif
01132                 h = murmur_step(h, t);
01133                 t = d;
01134                 data += sizeof(st_index_t);
01135                 len -= sizeof(st_index_t);
01136             }
01137 
01138             pack = len < (size_t)align ? (int)len : align;
01139             d = 0;
01140             switch (pack) {
01141 #ifdef WORDS_BIGENDIAN
01142 # define UNALIGNED_ADD(n) case (n) + 1: \
01143                 d |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
01144 #else
01145 # define UNALIGNED_ADD(n) case (n) + 1: \
01146                 d |= data_at(n) << CHAR_BIT*(n)
01147 #endif
01148                 UNALIGNED_ADD_ALL;
01149 #undef UNALIGNED_ADD
01150             }
01151 #ifdef WORDS_BIGENDIAN
01152             t = (t << sr) | (d >> sl);
01153 #else
01154             t = (t >> sr) | (d << sl);
01155 #endif
01156 
01157 #if MURMUR == 2
01158             if (len < (size_t)align) goto skip_tail;
01159 #endif
01160             h = murmur_step(h, t);
01161             data += pack;
01162             len -= pack;
01163         }
01164         else
01165 #endif
01166         {
01167             do {
01168                 h = murmur_step(h, *(st_index_t *)data);
01169                 data += sizeof(st_index_t);
01170                 len -= sizeof(st_index_t);
01171             } while (len >= sizeof(st_index_t));
01172         }
01173     }
01174 
01175     t = 0;
01176     switch (len) {
01177 #ifdef WORDS_BIGENDIAN
01178 # define UNALIGNED_ADD(n) case (n) + 1: \
01179         t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
01180 #else
01181 # define UNALIGNED_ADD(n) case (n) + 1: \
01182         t |= data_at(n) << CHAR_BIT*(n)
01183 #endif
01184         UNALIGNED_ADD_ALL;
01185 #undef UNALIGNED_ADD
01186 #if MURMUR == 1
01187         h = murmur_step(h, t);
01188 #elif MURMUR == 2
01189 # if !UNALIGNED_WORD_ACCESS
01190       skip_tail:
01191 # endif
01192         h ^= t;
01193         h *= MurmurMagic;
01194 #endif
01195     }
01196 
01197     return murmur_finish(h);
01198 }
01199 
01200 st_index_t
01201 st_hash_uint32(st_index_t h, uint32_t i)
01202 {
01203     return murmur_step(h + i, 16);
01204 }
01205 
01206 st_index_t
01207 st_hash_uint(st_index_t h, st_index_t i)
01208 {
01209     st_index_t v = 0;
01210     h += i;
01211 #ifdef WORDS_BIGENDIAN
01212 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8
01213     v = murmur1(v + (h >> 12*8));
01214 #endif
01215 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8
01216     v = murmur1(v + (h >> 8*8));
01217 #endif
01218 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8
01219     v = murmur1(v + (h >> 4*8));
01220 #endif
01221 #endif
01222     v = murmur1(v + h);
01223 #ifndef WORDS_BIGENDIAN
01224 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8
01225     v = murmur1(v + (h >> 4*8));
01226 #endif
01227 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8
01228     v = murmur1(v + (h >> 8*8));
01229 #endif
01230 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8
01231     v = murmur1(v + (h >> 12*8));
01232 #endif
01233 #endif
01234     return v;
01235 }
01236 
01237 st_index_t
01238 st_hash_end(st_index_t h)
01239 {
01240     h = murmur_step(h, 10);
01241     h = murmur_step(h, 17);
01242     return h;
01243 }
01244 
01245 #undef st_hash_start
01246 st_index_t
01247 st_hash_start(st_index_t h)
01248 {
01249     return h;
01250 }
01251 
01252 static st_index_t
01253 strhash(st_data_t arg)
01254 {
01255     register const char *string = (const char *)arg;
01256     return st_hash(string, strlen(string), FNV1_32A_INIT);
01257 }
01258 #endif
01259 
01260 int
01261 st_strcasecmp(const char *s1, const char *s2)
01262 {
01263     unsigned int c1, c2;
01264 
01265     while (1) {
01266         c1 = (unsigned char)*s1++;
01267         c2 = (unsigned char)*s2++;
01268         if (c1 == '\0' || c2 == '\0') {
01269             if (c1 != '\0') return 1;
01270             if (c2 != '\0') return -1;
01271             return 0;
01272         }
01273         if ((unsigned int)(c1 - 'A') <= ('Z' - 'A')) c1 += 'a' - 'A';
01274         if ((unsigned int)(c2 - 'A') <= ('Z' - 'A')) c2 += 'a' - 'A';
01275         if (c1 != c2) {
01276             if (c1 > c2)
01277                 return 1;
01278             else
01279                 return -1;
01280         }
01281     }
01282 }
01283 
01284 int
01285 st_strncasecmp(const char *s1, const char *s2, size_t n)
01286 {
01287     unsigned int c1, c2;
01288 
01289     while (n--) {
01290         c1 = (unsigned char)*s1++;
01291         c2 = (unsigned char)*s2++;
01292         if (c1 == '\0' || c2 == '\0') {
01293             if (c1 != '\0') return 1;
01294             if (c2 != '\0') return -1;
01295             return 0;
01296         }
01297         if ((unsigned int)(c1 - 'A') <= ('Z' - 'A')) c1 += 'a' - 'A';
01298         if ((unsigned int)(c2 - 'A') <= ('Z' - 'A')) c2 += 'a' - 'A';
01299         if (c1 != c2) {
01300             if (c1 > c2)
01301                 return 1;
01302             else
01303                 return -1;
01304         }
01305     }
01306     return 0;
01307 }
01308 
01309 static st_index_t
01310 strcasehash(st_data_t arg)
01311 {
01312     register const char *string = (const char *)arg;
01313     register st_index_t hval = FNV1_32A_INIT;
01314 
01315     /*
01316      * FNV-1a hash each octet in the buffer
01317      */
01318     while (*string) {
01319         unsigned int c = (unsigned char)*string++;
01320         if ((unsigned int)(c - 'A') <= ('Z' - 'A')) c += 'a' - 'A';
01321         hval ^= c;
01322 
01323         /* multiply by the 32 bit FNV magic prime mod 2^32 */
01324         hval *= FNV_32_PRIME;
01325     }
01326     return hval;
01327 }
01328 
01329 int
01330 st_numcmp(st_data_t x, st_data_t y)
01331 {
01332     return x != y;
01333 }
01334 
01335 st_index_t
01336 st_numhash(st_data_t n)
01337 {
01338     return (st_index_t)n;
01339 }
01340