Ruby 1.9.2p136(2010-12-25revision30365)

- Main Page
- Modules
- Data Structures
- Files

- File List
- Globals

# 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             switch (retval) {
    00749               case ST_CHECK:    /* check if hash is modified during iteration */
    00750                 for (j = 0; j < table->num_entries; j++) {
    00751                     if ((st_data_t)table->bins[j*2] == key)
    00752                         break;
    00753                 }
    00754                 if (j == table->num_entries) {
    00755                     /* call func with error notice */
    00756                     retval = (*func)(0, 0, arg, 1);
    00757                     return 1;
    00758                 }
    00759                 /* fall through */
    00760               case ST_CONTINUE:
    00761                 break;
    00762               case ST_STOP:
    00763                 return 0;
    00764               case ST_DELETE:
    00765                 table->num_entries--;
    00766                 memmove(&table->bins[i*2], &table->bins[(i+1)*2],
    00767                         sizeof(struct st_table_entry*) * 2*(table->num_entries-i));
    00768                 i--;
    00769                 break;
    00770             }
    00771         }
    00772         return 0;
    00773     }
    00774
    00775     if ((ptr = table->head) != 0) {
    00776         do {
    00777             i = ptr->hash % table->num_bins;
    00778             retval = (*func)(ptr->key, ptr->record, arg);
    00779             switch (retval) {
    00780               case ST_CHECK:    /* check if hash is modified during iteration */
    00781                 for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) {
    00782                     if (!tmp) {
    00783                         /* call func with error notice */
    00784                         retval = (*func)(0, 0, arg, 1);
    00785                         return 1;
    00786                     }
    00787                 }
    00788                 /* fall through */
    00789               case ST_CONTINUE:
    00790                 ptr = ptr->fore;
    00791                 break;
    00792               case ST_STOP:
    00793                 return 0;
    00794               case ST_DELETE:
    00795                 last = &table->bins[ptr->hash % table->num_bins];
    00796                 for (; (tmp = *last) != 0; last = &tmp->next) {
    00797                     if (ptr == tmp) {
    00798                         tmp = ptr->fore;
    00799                         *last = ptr->next;
    00800                         REMOVE_ENTRY(table, ptr);
    00801                         free(ptr);
    00802                         if (ptr == tmp) return 0;
    00803                         ptr = tmp;
    00804                         break;
    00805                     }
    00806                 }
    00807             }
    00808         } while (ptr && table->head);
    00809     }
    00810     return 0;
    00811 }
    00812
    00813 #if 0  /* unused right now */
    00814 int
    00815 st_reverse_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
    00816 {
    00817     st_table_entry *ptr, **last, *tmp;
    00818     enum st_retval retval;
    00819     int i;
    00820
    00821     if (table->entries_packed) {
    00822         for (i = table->num_entries-1; 0 <= i; i--) {
    00823             int j;
    00824             st_data_t key, val;
    00825             key = (st_data_t)table->bins[i*2];
    00826             val = (st_data_t)table->bins[i*2+1];
    00827             retval = (*func)(key, val, arg);
    00828             switch (retval) {
    00829               case ST_CHECK:    /* check if hash is modified during iteration */
    00830                 for (j = 0; j < table->num_entries; j++) {
    00831                     if ((st_data_t)table->bins[j*2] == key)
    00832                         break;
    00833                 }
    00834                 if (j == table->num_entries) {
    00835                     /* call func with error notice */
    00836                     retval = (*func)(0, 0, arg, 1);
    00837                     return 1;
    00838                 }
    00839                 /* fall through */
    00840               case ST_CONTINUE:
    00841                 break;
    00842               case ST_STOP:
    00843                 return 0;
    00844               case ST_DELETE:
    00845                 table->num_entries--;
    00846                 memmove(&table->bins[i*2], &table->bins[(i+1)*2],
    00847                         sizeof(struct st_table_entry*) * 2*(table->num_entries-i));
    00848                 break;
    00849             }
    00850         }
    00851         return 0;
    00852     }
    00853
    00854     if ((ptr = table->head) != 0) {
    00855         ptr = ptr->back;
    00856         do {
    00857             retval = (*func)(ptr->key, ptr->record, arg, 0);
    00858             switch (retval) {
    00859               case ST_CHECK:    /* check if hash is modified during iteration */
    00860                 i = ptr->hash % table->num_bins;
    00861                 for (tmp = table->bins[i]; tmp != ptr; tmp = tmp->next) {
    00862                     if (!tmp) {
    00863                         /* call func with error notice */
    00864                         retval = (*func)(0, 0, arg, 1);
    00865                         return 1;
    00866                     }
    00867                 }
    00868                 /* fall through */
    00869               case ST_CONTINUE:
    00870                 ptr = ptr->back;
    00871                 break;
    00872               case ST_STOP:
    00873                 return 0;
    00874               case ST_DELETE:
    00875                 last = &table->bins[ptr->hash % table->num_bins];
    00876                 for (; (tmp = *last) != 0; last = &tmp->next) {
    00877                     if (ptr == tmp) {
    00878                         tmp = ptr->back;
    00879                         *last = ptr->next;
    00880                         REMOVE_ENTRY(table, ptr);
    00881                         free(ptr);
    00882                         ptr = tmp;
    00883                         break;
    00884                     }
    00885                 }
    00886                 ptr = ptr->next;
    00887                 free(tmp);
    00888                 table->num_entries--;
    00889             }
    00890         } while (ptr && table->head);
    00891     }
    00892     return 0;
    00893 }
    00894 #endif
    00895
    00896 /*
    00897  * hash_32 - 32 bit Fowler/Noll/Vo FNV-1a hash code
    00898  *
    00899  * @(#) $Hash32: Revision: 1.1 $
    00900  * @(#) $Hash32: Id: hash_32a.c,v 1.1 2003/10/03 20:38:53 chongo Exp $
    00901  * @(#) $Hash32: Source: /usr/local/src/cmd/fnv/RCS/hash_32a.c,v $
    00902  *
    00903  ***
    00904  *
    00905  * Fowler/Noll/Vo hash
    00906  *
    00907  * The basis of this hash algorithm was taken from an idea sent
    00908  * as reviewer comments to the IEEE POSIX P1003.2 committee by:
    00909  *
    00910  *      Phong Vo (http://www.research.att.com/info/kpv/)
    00911  *      Glenn Fowler (http://www.research.att.com/~gsf/)
    00912  *
    00913  * In a subsequent ballot round:
    00914  *
    00915  *      Landon Curt Noll (http://www.isthe.com/chongo/)
    00916  *
    00917  * improved on their algorithm.  Some people tried this hash
    00918  * and found that it worked rather well.  In an EMail message
    00919  * to Landon, they named it the ``Fowler/Noll/Vo'' or FNV hash.
    00920  *
    00921  * FNV hashes are designed to be fast while maintaining a low
    00922  * collision rate. The FNV speed allows one to quickly hash lots
    00923  * of data while maintaining a reasonable collision rate.  See:
    00924  *
    00925  *      http://www.isthe.com/chongo/tech/comp/fnv/index.html
    00926  *
    00927  * for more details as well as other forms of the FNV hash.
    00928  ***
    00929  *
    00930  * To use the recommended 32 bit FNV-1a hash, pass FNV1_32A_INIT as the
    00931  * Fnv32_t hashval argument to fnv_32a_buf() or fnv_32a_str().
    00932  *
    00933  ***
    00934  *
    00935  * Please do not copyright this code.  This code is in the public domain.
    00936  *
    00937  * LANDON CURT NOLL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
    00938  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO
    00939  * EVENT SHALL LANDON CURT NOLL BE LIABLE FOR ANY SPECIAL, INDIRECT OR
    00940  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
    00941  * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
    00942  * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
    00943  * PERFORMANCE OF THIS SOFTWARE.
    00944  *
    00945  * By:
    00946  *      chongo <Landon Curt Noll> /\oo/\
    00947  *      http://www.isthe.com/chongo/
    00948  *
    00949  * Share and Enjoy!     :-)
    00950  */
    00951
    00952 /*
    00953  * 32 bit FNV-1 and FNV-1a non-zero initial basis
    00954  *
    00955  * The FNV-1 initial basis is the FNV-0 hash of the following 32 octets:
    00956  *
    00957  *              chongo <Landon Curt Noll> /\../\
    00958  *
    00959  * NOTE: The \'s above are not back-slashing escape characters.
    00960  * They are literal ASCII  backslash 0x5c characters.
    00961  *
    00962  * NOTE: The FNV-1a initial basis is the same value as FNV-1 by definition.
    00963  */
    00964 #define FNV1_32A_INIT 0x811c9dc5
    00965
    00966 /*
    00967  * 32 bit magic FNV-1a prime
    00968  */
    00969 #define FNV_32_PRIME 0x01000193
    00970
    00971 #ifdef ST_USE_FNV1
    00972 static st_index_t
    00973 strhash(st_data_t arg)
    00974 {
    00975     register const char *string = (const char *)arg;
    00976     register st_index_t hval = FNV1_32A_INIT;
    00977
    00978     /*
    00979      * FNV-1a hash each octet in the buffer
    00980      */
    00981     while (*string) {
    00982         /* xor the bottom with the current octet */
    00983         hval ^= (unsigned int)*string++;
    00984
    00985         /* multiply by the 32 bit FNV magic prime mod 2^32 */
    00986         hval *= FNV_32_PRIME;
    00987     }
    00988     return hval;
    00989 }
    00990 #else
    00991
    00992 #ifndef UNALIGNED_WORD_ACCESS
    00993 # if defined __i386__ || defined _M_IX86
    00994 #   define UNALIGNED_WORD_ACCESS 1
    00995 # endif
    00996 #endif
    00997 #ifndef UNALIGNED_WORD_ACCESS
    00998 # define UNALIGNED_WORD_ACCESS 0
    00999 #endif
    01000
    01001 /* MurmurHash described in http://murmurhash.googlepages.com/ */
    01002 #ifndef MURMUR
    01003 #define MURMUR 2
    01004 #endif
    01005
    01006 #if MURMUR == 1
    01007 #define MurmurMagic 0xc6a4a793
    01008 #elif MURMUR == 2
    01009 #if SIZEOF_ST_INDEX_T > 4
    01010 #define MurmurMagic 0xc6a4a7935bd1e995
    01011 #else
    01012 #define MurmurMagic 0x5bd1e995
    01013 #endif
    01014 #endif
    01015
    01016 static inline st_index_t
    01017 murmur(st_index_t h, st_index_t k, int r)
    01018 {
    01019     const st_index_t m = MurmurMagic;
    01020 #if MURMUR == 1
    01021     h += k;
    01022     h *= m;
    01023     h ^= h >> r;
    01024 #elif MURMUR == 2
    01025     k *= m;
    01026     k ^= k >> r;
    01027     k *= m;
    01028
    01029     h *= m;
    01030     h ^= k;
    01031 #endif
    01032     return h;
    01033 }
    01034
    01035 static inline st_index_t
    01036 murmur_finish(st_index_t h)
    01037 {
    01038 #if MURMUR == 1
    01039     h = murmur(h, 0, 10);
    01040     h = murmur(h, 0, 17);
    01041 #elif MURMUR == 2
    01042     h ^= h >> 13;
    01043     h *= MurmurMagic;
    01044     h ^= h >> 15;
    01045 #endif
    01046     return h;
    01047 }
    01048
    01049 #define murmur_step(h, k) murmur(h, k, 16)
    01050
    01051 #if MURMUR == 1
    01052 #define murmur1(h) murmur_step(h, 16)
    01053 #else
    01054 #define murmur1(h) murmur_step(h, 24)
    01055 #endif
    01056
    01057 st_index_t
    01058 st_hash(const void *ptr, size_t len, st_index_t h)
    01059 {
    01060     const char *data = ptr;
    01061     st_index_t t = 0;
    01062
    01063     h += 0xdeadbeef;
    01064
    01065 #define data_at(n) (st_index_t)((unsigned char)data[n])
    01066 #define UNALIGNED_ADD_4 UNALIGNED_ADD(2); UNALIGNED_ADD(1); UNALIGNED_ADD(0)
    01067 #if SIZEOF_ST_INDEX_T > 4
    01068 #define UNALIGNED_ADD_8 UNALIGNED_ADD(6); UNALIGNED_ADD(5); UNALIGNED_ADD(4); UNALIGNED_ADD(3); UNALIGNED_ADD_4
    01069 #if SIZEOF_ST_INDEX_T > 8
    01070 #define UNALIGNED_ADD_16 UNALIGNED_ADD(14); UNALIGNED_ADD(13); UNALIGNED_ADD(12); UNALIGNED_ADD(11); \
    01071     UNALIGNED_ADD(10); UNALIGNED_ADD(9); UNALIGNED_ADD(8); UNALIGNED_ADD(7); UNALIGNED_ADD_8
    01072 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_16
    01073 #endif
    01074 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_8
    01075 #else
    01076 #define UNALIGNED_ADD_ALL UNALIGNED_ADD_4
    01077 #endif
    01078     if (len >= sizeof(st_index_t)) {
    01079 #if !UNALIGNED_WORD_ACCESS
    01080         int align = (int)((st_data_t)data % sizeof(st_index_t));
    01081         if (align) {
    01082             st_index_t d = 0;
    01083             int sl, sr, pack;
    01084
    01085             switch (align) {
    01086 #ifdef WORDS_BIGENDIAN
    01087 # define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1: \
    01088                 t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 2)
    01089 #else
    01090 # define UNALIGNED_ADD(n) case SIZEOF_ST_INDEX_T - (n) - 1:     \
    01091                 t |= data_at(n) << CHAR_BIT*(n)
    01092 #endif
    01093                 UNALIGNED_ADD_ALL;
    01094 #undef UNALIGNED_ADD
    01095             }
    01096
    01097 #ifdef WORDS_BIGENDIAN
    01098             t >>= (CHAR_BIT * align) - CHAR_BIT;
    01099 #else
    01100             t <<= (CHAR_BIT * align);
    01101 #endif
    01102
    01103             data += sizeof(st_index_t)-align;
    01104             len -= sizeof(st_index_t)-align;
    01105
    01106             sl = CHAR_BIT * (SIZEOF_ST_INDEX_T-align);
    01107             sr = CHAR_BIT * align;
    01108
    01109             while (len >= sizeof(st_index_t)) {
    01110                 d = *(st_index_t *)data;
    01111 #ifdef WORDS_BIGENDIAN
    01112                 t = (t << sr) | (d >> sl);
    01113 #else
    01114                 t = (t >> sr) | (d << sl);
    01115 #endif
    01116                 h = murmur_step(h, t);
    01117                 t = d;
    01118                 data += sizeof(st_index_t);
    01119                 len -= sizeof(st_index_t);
    01120             }
    01121
    01122             pack = len < (size_t)align ? (int)len : align;
    01123             d = 0;
    01124             switch (pack) {
    01125 #ifdef WORDS_BIGENDIAN
    01126 # define UNALIGNED_ADD(n) case (n) + 1: \
    01127                 d |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
    01128 #else
    01129 # define UNALIGNED_ADD(n) case (n) + 1: \
    01130                 d |= data_at(n) << CHAR_BIT*(n)
    01131 #endif
    01132                 UNALIGNED_ADD_ALL;
    01133 #undef UNALIGNED_ADD
    01134             }
    01135 #ifdef WORDS_BIGENDIAN
    01136             t = (t << sr) | (d >> sl);
    01137 #else
    01138             t = (t >> sr) | (d << sl);
    01139 #endif
    01140
    01141 #if MURMUR == 2
    01142             if (len < (size_t)align) goto skip_tail;
    01143 #endif
    01144             h = murmur_step(h, t);
    01145             data += pack;
    01146             len -= pack;
    01147         }
    01148         else
    01149 #endif
    01150         {
    01151             do {
    01152                 h = murmur_step(h, *(st_index_t *)data);
    01153                 data += sizeof(st_index_t);
    01154                 len -= sizeof(st_index_t);
    01155             } while (len >= sizeof(st_index_t));
    01156         }
    01157     }
    01158
    01159     t = 0;
    01160     switch (len) {
    01161 #ifdef WORDS_BIGENDIAN
    01162 # define UNALIGNED_ADD(n) case (n) + 1: \
    01163         t |= data_at(n) << CHAR_BIT*(SIZEOF_ST_INDEX_T - (n) - 1)
    01164 #else
    01165 # define UNALIGNED_ADD(n) case (n) + 1: \
    01166         t |= data_at(n) << CHAR_BIT*(n)
    01167 #endif
    01168         UNALIGNED_ADD_ALL;
    01169 #undef UNALIGNED_ADD
    01170 #if MURMUR == 1
    01171         h = murmur_step(h, t);
    01172 #elif MURMUR == 2
    01173 # if !UNALIGNED_WORD_ACCESS
    01174       skip_tail:
    01175 # endif
    01176         h ^= t;
    01177         h *= MurmurMagic;
    01178 #endif
    01179     }
    01180
    01181     return murmur_finish(h);
    01182 }
    01183
    01184 st_index_t
    01185 st_hash_uint32(st_index_t h, uint32_t i)
    01186 {
    01187     return murmur_step(h + i, 16);
    01188 }
    01189
    01190 st_index_t
    01191 st_hash_uint(st_index_t h, st_index_t i)
    01192 {
    01193     st_index_t v = 0;
    01194     h += i;
    01195 #ifdef WORDS_BIGENDIAN
    01196 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8
    01197     v = murmur1(v + (h >> 12*8));
    01198 #endif
    01199 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8
    01200     v = murmur1(v + (h >> 8*8));
    01201 #endif
    01202 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8
    01203     v = murmur1(v + (h >> 4*8));
    01204 #endif
    01205 #endif
    01206     v = murmur1(v + h);
    01207 #ifndef WORDS_BIGENDIAN
    01208 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8
    01209     v = murmur1(v + (h >> 4*8));
    01210 #endif
    01211 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8
    01212     v = murmur1(v + (h >> 8*8));
    01213 #endif
    01214 #if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8
    01215     v = murmur1(v + (h >> 12*8));
    01216 #endif
    01217 #endif
    01218     return v;
    01219 }
    01220
    01221 st_index_t
    01222 st_hash_end(st_index_t h)
    01223 {
    01224     h = murmur_step(h, 10);
    01225     h = murmur_step(h, 17);
    01226     return h;
    01227 }
    01228
    01229 #undef st_hash_start
    01230 st_index_t
    01231 st_hash_start(st_index_t h)
    01232 {
    01233     return h;
    01234 }
    01235
    01236 static st_index_t
    01237 strhash(st_data_t arg)
    01238 {
    01239     register const char *string = (const char *)arg;
    01240     return st_hash(string, strlen(string), FNV1_32A_INIT);
    01241 }
    01242 #endif
    01243
    01244 int
    01245 st_strcasecmp(const char *s1, const char *s2)
    01246 {
    01247     unsigned int c1, c2;
    01248
    01249     while (1) {
    01250         c1 = (unsigned char)*s1++;
    01251         c2 = (unsigned char)*s2++;
    01252         if (c1 == '\0' || c2 == '\0') {
    01253             if (c1 != '\0') return 1;
    01254             if (c2 != '\0') return -1;
    01255             return 0;
    01256         }
    01257         if ((unsigned int)(c1 - 'A') <= ('Z' - 'A')) c1 += 'a' - 'A';
    01258         if ((unsigned int)(c2 - 'A') <= ('Z' - 'A')) c2 += 'a' - 'A';
    01259         if (c1 != c2) {
    01260             if (c1 > c2)
    01261                 return 1;
    01262             else
    01263                 return -1;
    01264         }
    01265     }
    01266 }
    01267
    01268 int
    01269 st_strncasecmp(const char *s1, const char *s2, size_t n)
    01270 {
    01271     unsigned int c1, c2;
    01272
    01273     while (n--) {
    01274         c1 = (unsigned char)*s1++;
    01275         c2 = (unsigned char)*s2++;
    01276         if (c1 == '\0' || c2 == '\0') {
    01277             if (c1 != '\0') return 1;
    01278             if (c2 != '\0') return -1;
    01279             return 0;
    01280         }
    01281         if ((unsigned int)(c1 - 'A') <= ('Z' - 'A')) c1 += 'a' - 'A';
    01282         if ((unsigned int)(c2 - 'A') <= ('Z' - 'A')) c2 += 'a' - 'A';
    01283         if (c1 != c2) {
    01284             if (c1 > c2)
    01285                 return 1;
    01286             else
    01287                 return -1;
    01288         }
    01289     }
    01290     return 0;
    01291 }
    01292
    01293 static st_index_t
    01294 strcasehash(st_data_t arg)
    01295 {
    01296     register const char *string = (const char *)arg;
    01297     register st_index_t hval = FNV1_32A_INIT;
    01298
    01299     /*
    01300      * FNV-1a hash each octet in the buffer
    01301      */
    01302     while (*string) {
    01303         unsigned int c = (unsigned char)*string++;
    01304         if ((unsigned int)(c - 'A') <= ('Z' - 'A')) c += 'a' - 'A';
    01305         hval ^= c;
    01306
    01307         /* multiply by the 32 bit FNV magic prime mod 2^32 */
    01308         hval *= FNV_32_PRIME;
    01309     }
    01310     return hval;
    01311 }
    01312
    01313 int
    01314 st_numcmp(st_data_t x, st_data_t y)
    01315 {
    01316     return x != y;
    01317 }
    01318
    01319 st_index_t
    01320 st_numhash(st_data_t n)
    01321 {
    01322     return (st_index_t)n;
    01323 }
    01324