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

# st.c

This is a public domain general purpose hash table package written by Peter Moore @ UCB. [詳細]

`#include "st.h"`
`#include <malloc.h>`

st.cのインクルード依存関係図

ソースコードを見る。

## 構成
struct | st_table_entry
## マクロ定義
#define | ST_INCLUDED_C
#define | ST_DEFAULT_MAX_DENSITY 5
#define | ST_DEFAULT_INIT_TABLE_SIZE 11
#define | alloc(type) (type*)malloc((unsigned)sizeof(type))
#define | Calloc(n, s) (char*)calloc((n),(s))
#define | EQUAL(table, x, y) ((x)==(y) || (*table->type->compare)((x),(y)) == 0)
#define | do_hash(key, table) (unsigned int)(*(table)->type->hash)((key))
#define | do_hash_bin(key, table) (do_hash(key, table)%(table)->num_bins)
#define | MINSIZE 8
#define | PTR_NOT_EQUAL(table, ptr, hash_val, key) ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
#define | COLLISION
#define | FIND_ENTRY(table, ptr, hash_val, bin_pos)
#define | ADD_DIRECT(table, key, value, hash_val, bin_pos)
## 型定義
typedef st_table_entry | st_table_entry
## 関数
static int | numcmp ()
static int | numhash ()
int | strcmp ()
static int | strhash ()
static void | rehash ()
static int | new_size (int size)
st_table * | st_init_table_with_size (struct st_hash_type *type, int size)
st_table * | st_init_table (struct st_hash_type *type)
st_table * | st_init_numtable ()
st_table * | st_init_numtable_with_size (int size)
st_table * | st_init_strtable ()
st_table * | st_init_strtable_with_size (int size)
void | st_free_table (st_table *table)
int | st_lookup (st_table *table, register char *key, char **value)
int | st_insert (register st_table *table, char *key, char *value)
void | st_add_direct (st_table *table, char *key, char *value)
static void | rehash (register st_table *table)
st_table * | st_copy (st_table *old_table)
int | st_delete (register st_table *table, register char **key, char **value)
int | st_delete_safe (register st_table *table, register char **key, char **value, char *never)
static int | delete_never (char *key, char *value, char *never)
void | st_cleanup_safe (st_table *table, char *never)
void | st_foreach (st_table *table, int(*func)(), char *arg)
static int | strhash (register char *string)
static int | numcmp (long x, long y)
static int | numhash (long n)
## 変数
static struct st_hash_type | type_numhash
static struct st_hash_type | type_strhash
static long | primes []

## 説明

This is a public domain general purpose hash table package written by Peter Moore @ UCB.

st.c で定義されています。

## マクロ定義

#define ADD_DIRECT | ( | table,
|  | key,
|  | value,
|  | hash_val,
|  | bin_pos |  | ) |

| 値:
    do {\
        st_table_entry *entry;\
        if (table->num_entries/(table->num_bins) > ST_DEFAULT_MAX_DENSITY) {\
        rehash(table);\
            bin_pos = hash_val % table->num_bins;\
        }\
        \
        entry = alloc(st_table_entry);\
        \
        entry->hash = hash_val;\
        entry->key = key;\
        entry->record = value;\
        entry->next = table->bins[bin_pos];\
        table->bins[bin_pos] = entry;\
        table->num_entries++;\
    } while (0)
st.c の 266 行で定義されています。 参照元 st_add_direct(), と st_insert().

#define alloc | ( | type |  | ) | (type*)malloc((unsigned)sizeof(type))

| st.c の 67 行で定義されています。 参照元 st_copy(), と st_init_table_with_size().

#define Calloc | ( | n,
|  | s |  | ) | (char*)calloc((n),(s))

| st.c の 68 行で定義されています。 参照元 rehash(), st_copy(), と st_init_table_with_size().

#define COLLISION

| st.c の 230 行で定義されています。

#define do_hash | ( | key,
|  | table |  | ) | (unsigned int)(*(table)->type->hash)((key))

| st.c の 73 行で定義されています。 参照元 st_add_direct(), st_insert(), と st_lookup().

#define do_hash_bin | ( | key,
|  | table |  | ) | (do_hash(key, table)%(table)->num_bins)

| st.c の 74 行で定義されています。 参照元 st_delete(), と st_delete_safe().

#define EQUAL | ( | table,
|  | x,
|  | y |  | ) | ((x)==(y) || (*table->type->compare)((x),(y)) == 0)

| st.c の 71 行で定義されています。 参照元 st_delete(), と st_delete_safe().

#define FIND_ENTRY | ( | table,
|  | ptr,
|  | hash_val,
|  | bin_pos |  | ) |

| 値:
    do {\
        bin_pos = hash_val%(table)->num_bins;\
        ptr = (table)->bins[bin_pos];\
        if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
        COLLISION;\
        while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
            ptr = ptr->next;\
        }\
        ptr = ptr->next;\
        }\
    } while (0)
st.c の 233 行で定義されています。 参照元 st_insert(), と st_lookup().

#define MINSIZE 8

| st.c の 80 行で定義されています。 参照元 new_size().

#define PTR_NOT_EQUAL | ( | table,
|  | ptr,
|  | hash_val,
|  | key |  | ) | ((ptr) != 0 && (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))

| st.c の 224 行で定義されています。

#define ST_DEFAULT_INIT_TABLE_SIZE 11

| st.c の 36 行で定義されています。

#define ST_DEFAULT_MAX_DENSITY 5

| st.c の 35 行で定義されています。

#define ST_INCLUDED_C

| st.c の 8 行で定義されています。

## 型定義

typedef struct st_table_entry st_table_entry

| st.c の 26 行で定義されています。

## 関数

static int delete_never | ( | char * | key,
|  | char * | value,
|  | char * | never
| ) | `[static]`

| st.c の 459 行で定義されています。 参照先 ST_CONTINUE, と ST_DELETE. 参照元 st_cleanup_safe().
    00461 {
    00462     if (value == never) return ST_DELETE;
    00463     return ST_CONTINUE;
    00464 }

static int new_size | ( | int | size | ) | `[static]`

| st.c の 118 行で定義されています。 参照先 MINSIZE, と primes. 参照元 rehash(), と st_init_table_with_size().
    00118                       {
    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 }

static int numcmp | ( | long | x,
|  | long | y
| ) | `[static]`

| st.c の 545 行で定義されています。
    00547 {
    00548     return x != y;
    00549 }

static int numcmp | ( |  | ) | `[static]`

static int numhash | ( | long | n | ) | `[static]`

| st.c の 552 行で定義されています。
    00554 {
    00555     return n;
    00556 }

static int numhash | ( |  | ) | `[static]`

static void rehash | ( | register st_table * | table | ) | `[static]`

| st.c の 320 行で定義されています。 参照先 Calloc, st_table_entry::hash, new_size(), と st_table_entry::next.
    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 }

static void rehash | ( |  | ) | `[static]`

void st_add_direct | ( | st_table * | table,
|  | char * | key,
|  | char * | value
| ) |

| st.c の 307 行で定義されています。 参照先 ADD_DIRECT, do_hash, と st_table::num_bins.
    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 }

void st_cleanup_safe | ( | st_table * | table,
|  | char * | never
| ) |

| st.c の 467 行で定義されています。 参照先 delete_never(), st_table::num_entries, と st_foreach().
    00468 {
    00469     int num_entries = table->num_entries;
    00470
    00471     st_foreach(table, delete_never, never);
    00472     table->num_entries = num_entries;
    00473 }

st_table* st_copy | ( | st_table * | old_table | ) |

| st.c の 346 行で定義されています。 参照先 alloc, st_table::bins, Calloc, st_table_entry::next, と st_table::num_bins.
    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 }

int st_delete | ( | register st_table * | table,
|  | register char ** | key,
|  | char ** | value
| ) |

| st.c の 387 行で定義されています。 参照先 do_hash_bin, EQUAL, st_table_entry::key, st_table_entry::next, st_table_entry::record, と tmp.
    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 }

int st_delete_safe | ( | register st_table * | table,
|  | register char ** | key,
|  | char ** | value,
|  | char * | never
| ) |

| st.c の 429 行で定義されています。 参照先 do_hash_bin, EQUAL, st_table_entry::key, st_table_entry::next, と st_table_entry::record.
    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 }

void st_foreach | ( | st_table * | table,
|  | int(*)() | func,
|  | char * | arg
| ) |

| st.c の 476 行で定義されています。 参照先 st_table::bins, st_table_entry::key, st_table_entry::next, st_table::num_bins, st_table::num_entries, st_table_entry::record, ST_CONTINUE, ST_DELETE, ST_STOP, と tmp. 参照元 st_cleanup_safe().
    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 }

void st_free_table | ( | st_table * | table | ) |

| st.c の 206 行で定義されています。 参照先 st_table::bins, st_table_entry::next, と st_table::num_bins.
    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 }

st_table* st_init_numtable | ( |  | ) |

| st.c の 180 行で定義されています。 参照先 st_init_table().
    00181 {
    00182     return st_init_table(&type_numhash);
    00183 }

st_table* st_init_numtable_with_size | ( | int | size | ) |

| st.c の 186 行で定義されています。 参照先 st_init_table_with_size().
    00188 {
    00189     return st_init_table_with_size(&type_numhash, size);
    00190 }

st_table* st_init_strtable | ( |  | ) |

| st.c の 193 行で定義されています。 参照先 st_init_table().
    00194 {
    00195     return st_init_table(&type_strhash);
    00196 }

st_table* st_init_strtable_with_size | ( | int | size | ) |

| st.c の 199 行で定義されています。 参照先 st_init_table_with_size().
    00201 {
    00202     return st_init_table_with_size(&type_strhash, size);
    00203 }

st_table* st_init_table | ( | struct st_hash_type * | type | ) |

| st.c の 174 行で定義されています。 参照先 st_init_table_with_size(). 参照元 st_init_numtable(), と st_init_strtable().
    00175 {
    00176     return st_init_table_with_size(type, 0);
    00177 }

st_table* st_init_table_with_size | ( | struct st_hash_type * | type,
|  | int | size
| ) |

| st.c の 152 行で定義されています。 参照先 alloc, st_table::bins, Calloc, new_size(), st_table::num_bins, st_table::num_entries, と st_table::type. 参照元 st_init_numtable_with_size(), st_init_strtable_with_size(), と st_init_table().
    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 }

int st_insert | ( | register st_table * | table,
|  | char * | key,
|  | char * | value
| ) |

| st.c の 285 行で定義されています。 参照先 ADD_DIRECT, do_hash, FIND_ENTRY, と st_table_entry::record.
    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 }

int st_lookup | ( | st_table * | table,
|  | register char * | key,
|  | char ** | value
| ) |

| st.c の 246 行で定義されています。 参照先 do_hash, FIND_ENTRY, と st_table_entry::record.
    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 }

int strcmp | ( |  | ) |

| 参照元 dkcFindFileIsDot(), と dkcFindFileIsFolder().

static int strhash | ( | register char * | string | ) | `[static]`

| st.c の 510 行で定義されています。
    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 }

static int strhash | ( |  | ) | `[static]`

## 変数

long primes[]`[static]`

| st.c の 85 行で定義されています。 参照元 new_size().

struct st_hash_type type_numhash`[static]`

| 初期値:
     {
        numcmp,
        numhash,
    }
st.c の 49 行で定義されています。

struct st_hash_type type_strhash`[static]`

| 初期値:
     {
        strcmp,
        strhash,
    }
st.c の 56 行で定義されています。