Back to index

php5  5.3.10
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 #include "config.h"
00006 #include <stdio.h>
00007 #include <stdlib.h>
00008 #include <string.h>
00009 
00010 #ifdef _WIN32
00011 #include <malloc.h>
00012 #endif
00013 
00014 #ifdef NOT_RUBY
00015 #include "regint.h"
00016 #else
00017 #ifdef RUBY_PLATFORM
00018 #define xmalloc ruby_xmalloc
00019 #define xcalloc ruby_xcalloc
00020 #define xrealloc ruby_xrealloc
00021 #define xfree ruby_xfree
00022 
00023 void *xmalloc(long);
00024 void *xcalloc(long, long);
00025 void *xrealloc(void *, long);
00026 void xfree(void *);
00027 #endif
00028 #endif
00029 
00030 #include "st.h"
00031 
00032 typedef struct st_table_entry st_table_entry;
00033 
00034 struct st_table_entry {
00035     unsigned int hash;
00036     st_data_t key;
00037     st_data_t record;
00038     st_table_entry *next;
00039 };
00040 
00041 #define ST_DEFAULT_MAX_DENSITY 5
00042 #define ST_DEFAULT_INIT_TABLE_SIZE 11
00043 
00044     /*
00045      * DEFAULT_MAX_DENSITY is the default for the largest we allow the
00046      * average number of items per bin before increasing the number of
00047      * bins
00048      *
00049      * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
00050      * allocated initially
00051      *
00052      */
00053 
00054 static int numcmp(long, long);
00055 static int numhash(long);
00056 static struct st_hash_type type_numhash = {
00057     numcmp,
00058     numhash,
00059 };
00060 
00061 /* extern int strcmp(const char *, const char *); */
00062 static int strhash(const char *);
00063 static struct st_hash_type type_strhash = {
00064     strcmp,
00065     strhash,
00066 };
00067 
00068 static void rehash(st_table *);
00069 
00070 #define alloc(type) (type*)xmalloc((unsigned)sizeof(type))
00071 #define Calloc(n,s) (char*)xcalloc((n),(s))
00072 
00073 #define EQUAL(table,x,y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0)
00074 
00075 #define do_hash(key,table) (unsigned int)(*(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 long 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 int
00120 new_size(size)
00121     int size;
00122 {
00123     int i;
00124 
00125 #if 0
00126     for (i=3; i<31; i++) {
00127        if ((1<<i) > size) return 1<<i;
00128     }
00129     return -1;
00130 #else
00131     int newsize;
00132 
00133     for (i = 0, newsize = MINSIZE;
00134         i < (int )(sizeof(primes)/sizeof(primes[0]));
00135         i++, newsize <<= 1)
00136     {
00137        if (newsize > size) return primes[i];
00138     }
00139     /* Ran out of polynomials */
00140     return -1;                     /* should raise exception */
00141 #endif
00142 }
00143 
00144 #ifdef HASH_LOG
00145 static int collision = 0;
00146 static int init_st = 0;
00147 
00148 static void
00149 stat_col()
00150 {
00151     FILE *f = fopen("/tmp/col", "w");
00152     fprintf(f, "collision: %d\n", collision);
00153     fclose(f);
00154 }
00155 #endif
00156 
00157 st_table*
00158 st_init_table_with_size(type, size)
00159     struct st_hash_type *type;
00160     int size;
00161 {
00162     st_table *tbl;
00163 
00164 #ifdef HASH_LOG
00165     if (init_st == 0) {
00166        init_st = 1;
00167        atexit(stat_col);
00168     }
00169 #endif
00170 
00171     size = new_size(size);  /* round up to prime number */
00172 
00173     tbl = alloc(st_table);
00174     tbl->type = type;
00175     tbl->num_entries = 0;
00176     tbl->num_bins = size;
00177     tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
00178 
00179     return tbl;
00180 }
00181 
00182 st_table*
00183 st_init_table(type)
00184     struct st_hash_type *type;
00185 {
00186     return st_init_table_with_size(type, 0);
00187 }
00188 
00189 st_table*
00190 st_init_numtable(void)
00191 {
00192     return st_init_table(&type_numhash);
00193 }
00194 
00195 st_table*
00196 st_init_numtable_with_size(size)
00197     int size;
00198 {
00199     return st_init_table_with_size(&type_numhash, size);
00200 }
00201 
00202 st_table*
00203 st_init_strtable(void)
00204 {
00205     return st_init_table(&type_strhash);
00206 }
00207 
00208 st_table*
00209 st_init_strtable_with_size(size)
00210     int size;
00211 {
00212     return st_init_table_with_size(&type_strhash, size);
00213 }
00214 
00215 void
00216 st_free_table(table)
00217     st_table *table;
00218 {
00219     register st_table_entry *ptr, *next;
00220     int i;
00221 
00222     for(i = 0; i < table->num_bins; i++) {
00223        ptr = table->bins[i];
00224        while (ptr != 0) {
00225            next = ptr->next;
00226            free(ptr);
00227            ptr = next;
00228        }
00229     }
00230     free(table->bins);
00231     free(table);
00232 }
00233 
00234 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) \
00235 ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
00236 
00237 #ifdef HASH_LOG
00238 #define COLLISION collision++
00239 #else
00240 #define COLLISION
00241 #endif
00242 
00243 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
00244     bin_pos = hash_val%(table)->num_bins;\
00245     ptr = (table)->bins[bin_pos];\
00246     if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
00247        COLLISION;\
00248        while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
00249            ptr = ptr->next;\
00250        }\
00251        ptr = ptr->next;\
00252     }\
00253 } while (0)
00254 
00255 int
00256 st_lookup(table, key, value)
00257     st_table *table;
00258     register st_data_t key;
00259     st_data_t *value;
00260 {
00261     unsigned int hash_val, bin_pos;
00262     register st_table_entry *ptr;
00263 
00264     hash_val = do_hash(key, table);
00265     FIND_ENTRY(table, ptr, hash_val, bin_pos);
00266 
00267     if (ptr == 0) {
00268        return 0;
00269     }
00270     else {
00271        if (value != 0)  *value = ptr->record;
00272        return 1;
00273     }
00274 }
00275 
00276 #define ADD_DIRECT(table, key, value, hash_val, bin_pos)\
00277 do {\
00278     st_table_entry *entry;\
00279     if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
00280        rehash(table);\
00281         bin_pos = hash_val % table->num_bins;\
00282     }\
00283     \
00284     entry = alloc(st_table_entry);\
00285     \
00286     entry->hash = hash_val;\
00287     entry->key = key;\
00288     entry->record = value;\
00289     entry->next = table->bins[bin_pos];\
00290     table->bins[bin_pos] = entry;\
00291     table->num_entries++;\
00292 } while (0)
00293 
00294 int
00295 st_insert(table, key, value)
00296     register st_table *table;
00297     register st_data_t key;
00298     st_data_t value;
00299 {
00300     unsigned int hash_val, bin_pos;
00301     register st_table_entry *ptr;
00302 
00303     hash_val = do_hash(key, table);
00304     FIND_ENTRY(table, ptr, hash_val, bin_pos);
00305 
00306     if (ptr == 0) {
00307        ADD_DIRECT(table, key, value, hash_val, bin_pos);
00308        return 0;
00309     }
00310     else {
00311        ptr->record = value;
00312        return 1;
00313     }
00314 }
00315 
00316 void
00317 st_add_direct(table, key, value)
00318     st_table *table;
00319     st_data_t key;
00320     st_data_t value;
00321 {
00322     unsigned int hash_val, bin_pos;
00323 
00324     hash_val = do_hash(key, table);
00325     bin_pos = hash_val % table->num_bins;
00326     ADD_DIRECT(table, key, value, hash_val, bin_pos);
00327 }
00328 
00329 static void
00330 rehash(table)
00331     register st_table *table;
00332 {
00333     register st_table_entry *ptr, *next, **new_bins;
00334     int i, old_num_bins = table->num_bins, new_num_bins;
00335     unsigned int hash_val;
00336 
00337     new_num_bins = new_size(old_num_bins+1);
00338     new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*));
00339 
00340     for(i = 0; i < old_num_bins; i++) {
00341        ptr = table->bins[i];
00342        while (ptr != 0) {
00343            next = ptr->next;
00344            hash_val = ptr->hash % new_num_bins;
00345            ptr->next = new_bins[hash_val];
00346            new_bins[hash_val] = ptr;
00347            ptr = next;
00348        }
00349     }
00350     free(table->bins);
00351     table->num_bins = new_num_bins;
00352     table->bins = new_bins;
00353 }
00354 
00355 st_table*
00356 st_copy(old_table)
00357     st_table *old_table;
00358 {
00359     st_table *new_table;
00360     st_table_entry *ptr, *entry;
00361     int i, num_bins = old_table->num_bins;
00362 
00363     new_table = alloc(st_table);
00364     if (new_table == 0) {
00365        return 0;
00366     }
00367 
00368     *new_table = *old_table;
00369     new_table->bins = (st_table_entry**)
00370        Calloc((unsigned)num_bins, sizeof(st_table_entry*));
00371 
00372     if (new_table->bins == 0) {
00373        free(new_table);
00374        return 0;
00375     }
00376 
00377     for(i = 0; i < num_bins; i++) {
00378        new_table->bins[i] = 0;
00379        ptr = old_table->bins[i];
00380        while (ptr != 0) {
00381            entry = alloc(st_table_entry);
00382            if (entry == 0) {
00383               free(new_table->bins);
00384               free(new_table);
00385               return 0;
00386            }
00387            *entry = *ptr;
00388            entry->next = new_table->bins[i];
00389            new_table->bins[i] = entry;
00390            ptr = ptr->next;
00391        }
00392     }
00393     return new_table;
00394 }
00395 
00396 int
00397 st_delete(table, key, value)
00398     register st_table *table;
00399     register st_data_t *key;
00400     st_data_t *value;
00401 {
00402     unsigned int hash_val;
00403     st_table_entry *tmp;
00404     register st_table_entry *ptr;
00405 
00406     hash_val = do_hash_bin(*key, table);
00407     ptr = table->bins[hash_val];
00408 
00409     if (ptr == 0) {
00410        if (value != 0) *value = 0;
00411        return 0;
00412     }
00413 
00414     if (EQUAL(table, *key, ptr->key)) {
00415        table->bins[hash_val] = ptr->next;
00416        table->num_entries--;
00417        if (value != 0) *value = ptr->record;
00418        *key = ptr->key;
00419        free(ptr);
00420        return 1;
00421     }
00422 
00423     for(; ptr->next != 0; ptr = ptr->next) {
00424        if (EQUAL(table, ptr->next->key, *key)) {
00425            tmp = ptr->next;
00426            ptr->next = ptr->next->next;
00427            table->num_entries--;
00428            if (value != 0) *value = tmp->record;
00429            *key = tmp->key;
00430            free(tmp);
00431            return 1;
00432        }
00433     }
00434 
00435     return 0;
00436 }
00437 
00438 int
00439 st_delete_safe(table, key, value, never)
00440     register st_table *table;
00441     register st_data_t *key;
00442     st_data_t *value;
00443     st_data_t never;
00444 {
00445     unsigned int hash_val;
00446     register st_table_entry *ptr;
00447 
00448     hash_val = do_hash_bin(*key, table);
00449     ptr = table->bins[hash_val];
00450 
00451     if (ptr == 0) {
00452        if (value != 0) *value = 0;
00453        return 0;
00454     }
00455 
00456     for(; ptr != 0; ptr = ptr->next) {
00457        if ((ptr->key != never) && EQUAL(table, ptr->key, *key)) {
00458            table->num_entries--;
00459            *key = ptr->key;
00460            if (value != 0) *value = ptr->record;
00461            ptr->key = ptr->record = never;
00462            return 1;
00463        }
00464     }
00465 
00466     return 0;
00467 }
00468 
00469 static int
00470 delete_never(key, value, never)
00471     st_data_t key, value, never;
00472 {
00473     if (value == never) return ST_DELETE;
00474     return ST_CONTINUE;
00475 }
00476 
00477 void
00478 st_cleanup_safe(table, never)
00479     st_table *table;
00480     st_data_t never;
00481 {
00482     int num_entries = table->num_entries;
00483 
00484     st_foreach(table, delete_never, never);
00485     table->num_entries = num_entries;
00486 }
00487 
00488 int
00489 st_foreach(table, func, arg)
00490     st_table *table;
00491     int (*func)();
00492     st_data_t arg;
00493 {
00494     st_table_entry *ptr, *last, *tmp;
00495     enum st_retval retval;
00496     int i;
00497 
00498     for(i = 0; i < table->num_bins; i++) {
00499        last = 0;
00500        for(ptr = table->bins[i]; ptr != 0;) {
00501            retval = (*func)(ptr->key, ptr->record, arg);
00502            switch (retval) {
00503            case ST_CHECK:   /* check if hash is modified during iteration */
00504                tmp = 0;
00505               if (i < table->num_bins) {
00506                   for (tmp = table->bins[i]; tmp; tmp=tmp->next) {
00507                      if (tmp == ptr) break;
00508                   }
00509               }
00510               if (!tmp) {
00511                   /* call func with error notice */
00512                   return 1;
00513               }
00514               /* fall through */
00515            case ST_CONTINUE:
00516               last = ptr;
00517               ptr = ptr->next;
00518               break;
00519            case ST_STOP:
00520                return 0;
00521            case ST_DELETE:
00522               tmp = ptr;
00523               if (last == 0) {
00524                   table->bins[i] = ptr->next;
00525               }
00526               else {
00527                   last->next = ptr->next;
00528               }
00529               ptr = ptr->next;
00530               free(tmp);
00531               table->num_entries--;
00532            }
00533        }
00534     }
00535     return 0;
00536 }
00537 
00538 static int
00539 strhash(string)
00540     register const char *string;
00541 {
00542     register int c;
00543 
00544 #ifdef HASH_ELFHASH
00545     register unsigned int h = 0, g;
00546 
00547     while ((c = *string++) != '\0') {
00548        h = ( h << 4 ) + c;
00549        if ( g = h & 0xF0000000 )
00550            h ^= g >> 24;
00551        h &= ~g;
00552     }
00553     return h;
00554 #elif HASH_PERL
00555     register int val = 0;
00556 
00557     while ((c = *string++) != '\0') {
00558        val += c;
00559        val += (val << 10);
00560        val ^= (val >> 6);
00561     }
00562     val += (val << 3);
00563     val ^= (val >> 11);
00564 
00565     return val + (val << 15);
00566 #else
00567     register int val = 0;
00568 
00569     while ((c = *string++) != '\0') {
00570        val = val*997 + c;
00571     }
00572 
00573     return val + (val>>5);
00574 #endif
00575 }
00576 
00577 static int
00578 numcmp(x, y)
00579     long x, y;
00580 {
00581     return x != y;
00582 }
00583 
00584 static int
00585 numhash(n)
00586     long n;
00587 {
00588     return n;
00589 }