メインページ | アルファベット順一覧 | 構成 | ファイル一覧 | 構成メンバ | ファイルメンバ | 関連ページ

# st.c

説明を見る。

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