diff options
author | matz <matz@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 1999-01-20 04:59:39 +0000 |
---|---|---|
committer | matz <matz@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 1999-01-20 04:59:39 +0000 |
commit | 210367ec889f5910e270d6ea2c7ddb8a8d939e61 (patch) | |
tree | feb35473da45947378fbc02defe39bcd79ef600e /st.c | |
parent | 9c5b1986a36c7a700b4c76817e35aa874ba7907c (diff) | |
download | ruby-210367ec889f5910e270d6ea2c7ddb8a8d939e61.tar.gz |
This commit was generated by cvs2svn to compensate for changes in r372,
which included commits to RCS files with non-trunk default branches.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@373 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'st.c')
-rw-r--r-- | st.c | 280 |
1 files changed, 164 insertions, 116 deletions
@@ -6,6 +6,19 @@ static char sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible"; #include <stdio.h> #include "st.h" +#ifdef USE_CWGUSI +#include <stdlib.h> +#endif + +typedef struct st_table_entry st_table_entry; + +struct st_table_entry { + unsigned int hash; + char *key; + char *record; + st_table_entry *next; +}; + #define ST_DEFAULT_MAX_DENSITY 5 #define ST_DEFAULT_INIT_TABLE_SIZE 11 @@ -37,14 +50,70 @@ void *xcalloc(); void *xrealloc(); static void rehash(); -#define max(a,b) ((a) > (b) ? (a) : (b)) -#define nil(type) ((type*)0) #define alloc(type) (type*)xmalloc((unsigned)sizeof(type)) #define Calloc(n,s) (char*)xcalloc((n),(s)) #define EQUAL(table, x, y) ((*table->type->compare)(x, y) == 0) -#define do_hash(key, table) (*(table)->type->hash)((key), (table)->num_bins) +#define do_hash(key, table) (unsigned int)(*(table)->type->hash)((key)) +#define do_hash_bin(key, table) (do_hash(key, table)%(table)->num_bins) + +/* + * MINSIZE is the minimum size of a dictionary. + */ + +#define MINSIZE 8 + +/* +Table of prime numbers 2^n+a, 2<=n<=30. +*/ +static long primes[] = { + 8 + 3, + 16 + 3, + 32 + 5, + 64 + 3, + 128 + 3, + 256 + 29, + 512 + 17, + 1024 + 9, + 2048 + 5, + 4096 + 83, + 8192 + 27, + 16384 + 43, + 32768 + 3, + 65536 + 45, + 131072 + 9, + 262144 + 39, + 524288 + 39, + 1048576 + 9, + 2097152 + 5, + 4194304 + 3, + 8388608 + 33, + 16777216 + 27, + 33554432 + 9, + 67108864 + 71, + 134217728 + 39, + 268435456 + 9, + 536870912 + 5, + 1073741824 + 83, + 0 +}; + +static int +new_size(size) + int size; +{ + int i, newsize; + + for (i = 0, newsize = MINSIZE; + i < sizeof(primes)/sizeof(primes[0]); + i++, newsize <<= 1) + { + if (newsize > size) return primes[i]; + } + /* Ran out of polynomials */ + return -1; /* should raise exception */ +} st_table* st_init_table_with_size(type, size) @@ -53,17 +122,14 @@ st_init_table_with_size(type, size) { st_table *tbl; - if (size == 0) size = ST_DEFAULT_INIT_TABLE_SIZE; - else size /= ST_DEFAULT_MAX_DENSITY*0.87; - - if (size < ST_DEFAULT_INIT_TABLE_SIZE) - size = ST_DEFAULT_INIT_TABLE_SIZE; + size = new_size(size); /* round up to prime number */ tbl = alloc(st_table); tbl->type = type; tbl->num_entries = 0; tbl->num_bins = size; tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*)); + return tbl; } @@ -81,11 +147,25 @@ st_init_numtable() } st_table* +st_init_numtable_with_size(size) + int size; +{ + return st_init_table_with_size(&type_numhash, size); +} + +st_table* st_init_strtable() { return st_init_table(&type_strhash); } +st_table* +st_init_strtable_with_size(size) + int size; +{ + return st_init_table_with_size(&type_strhash, size); +} + void st_free_table(table) st_table *table; @@ -95,23 +175,24 @@ st_free_table(table) for(i = 0; i < table->num_bins ; i++) { ptr = table->bins[i]; - while (ptr != nil(st_table_entry)) { + while (ptr != 0) { next = ptr->next; - free((char*)ptr); + free(ptr); ptr = next; } } - free((char*)table->bins); - free((char*)table); + free(table->bins); + free(table); } -#define PTR_NOT_EQUAL(table, ptr, key) \ -(ptr != nil(st_table_entry) && !EQUAL(table, key, (ptr)->key)) +#define PTR_NOT_EQUAL(table, ptr, hash_val, key) \ +((ptr) != 0 && ptr->hash != (hash_val) && !EQUAL((table), (key), (ptr)->key)) -#define FIND_ENTRY(table, ptr, hash_val) \ -ptr = (table)->bins[hash_val];\ -if (PTR_NOT_EQUAL(table, ptr, key)) {\ - while (PTR_NOT_EQUAL(table, ptr->next, key)) {\ +#define FIND_ENTRY(table, ptr, hash_val, bin_pos) \ +bin_pos = hash_val%(table)->num_bins;\ +ptr = (table)->bins[bin_pos];\ +if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\ + while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\ ptr = ptr->next;\ }\ ptr = ptr->next;\ @@ -123,34 +204,35 @@ st_lookup(table, key, value) register char *key; char **value; { - int hash_val; + unsigned int hash_val, bin_pos; register st_table_entry *ptr; hash_val = do_hash(key, table); + FIND_ENTRY(table, ptr, hash_val, bin_pos); - FIND_ENTRY(table, ptr, hash_val); - - if (ptr == nil(st_table_entry)) { + if (ptr == 0) { return 0; } else { - if (value != nil(char*)) *value = ptr->record; + if (value != 0) *value = ptr->record; return 1; } } -#define ADD_DIRECT(table, key, value, hash_val, tbl)\ +#define ADD_DIRECT(table, key, value, hash_val, bin_pos)\ {\ + st_table_entry *tbl;\ if (table->num_entries/table->num_bins > ST_DEFAULT_MAX_DENSITY) {\ rehash(table);\ - hash_val = do_hash(key, table);\ + bin_pos = hash_val % table->num_bins;\ }\ \ tbl = alloc(st_table_entry);\ \ + tbl->hash = hash_val;\ tbl->key = key;\ tbl->record = value;\ - tbl->next = table->bins[hash_val];\ - table->bins[hash_val] = tbl;\ + tbl->next = table->bins[bin_pos];\ + table->bins[bin_pos] = tbl;\ table->num_entries++;\ } @@ -160,16 +242,14 @@ st_insert(table, key, value) register char *key; char *value; { - int hash_val; - st_table_entry *tbl; + unsigned int hash_val, bin_pos; register st_table_entry *ptr; hash_val = do_hash(key, table); + FIND_ENTRY(table, ptr, hash_val, bin_pos); - FIND_ENTRY(table, ptr, hash_val); - - if (ptr == nil(st_table_entry)) { - ADD_DIRECT(table,key,value,hash_val,tbl); + if (ptr == 0) { + ADD_DIRECT(table, key, value, hash_val, bin_pos); return 0; } else { ptr->record = value; @@ -183,65 +263,37 @@ st_add_direct(table, key, value) char *key; char *value; { - int hash_val; - st_table_entry *tbl; - - hash_val = do_hash(key, table); - ADD_DIRECT(table, key, value, hash_val, tbl); -} - -int -st_find_or_add(table, key, slot) - st_table *table; - char *key; - char ***slot; -{ - int hash_val; - st_table_entry *tbl, *ptr; + unsigned int hash_val, bin_pos; hash_val = do_hash(key, table); - - FIND_ENTRY(table, ptr, hash_val); - - if (ptr == nil(st_table_entry)) { - ADD_DIRECT(table, key, (char*)0, hash_val, tbl) - if (slot != nil(char**)) *slot = &tbl->record; - return 0; - } else { - if (slot != nil(char**)) *slot = &ptr->record; - return 1; - } + bin_pos = hash_val % table->num_bins; + ADD_DIRECT(table, key, value, hash_val, bin_pos); } static void rehash(table) register st_table *table; { - register st_table_entry *ptr, *next, **old_bins = table->bins; - int i, old_num_bins = table->num_bins, hash_val; - - table->num_bins = 1.79*old_num_bins; - - if (table->num_bins%2 == 0) { - table->num_bins += 1; - } + register st_table_entry *ptr, *next, **new_bins; + int i, old_num_bins = table->num_bins, new_num_bins; + unsigned int hash_val; - table->num_entries = 0; - table->bins = (st_table_entry **) - Calloc((unsigned)table->num_bins, sizeof(st_table_entry*)); + new_num_bins = new_size(old_num_bins); + new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*)); for(i = 0; i < old_num_bins ; i++) { - ptr = old_bins[i]; - while (ptr != nil(st_table_entry)) { + ptr = table->bins[i]; + while (ptr != 0) { next = ptr->next; - hash_val = do_hash(ptr->key, table); - ptr->next = table->bins[hash_val]; - table->bins[hash_val] = ptr; - table->num_entries++; + hash_val = ptr->hash % new_num_bins; + ptr->next = new_bins[hash_val]; + new_bins[hash_val] = ptr; ptr = next; } } - free((char*)old_bins); + free(table->bins); + table->num_bins = new_num_bins; + table->bins = new_bins; } st_table* @@ -253,28 +305,28 @@ st_copy(old_table) int i, num_bins = old_table->num_bins; new_table = alloc(st_table); - if (new_table == nil(st_table)) { - return nil(st_table); + if (new_table == 0) { + return 0; } *new_table = *old_table; new_table->bins = (st_table_entry**) Calloc((unsigned)num_bins, sizeof(st_table_entry*)); - if (new_table->bins == nil(st_table_entry*)) { - free((char*)new_table); - return nil(st_table); + if (new_table->bins == 0) { + free(new_table); + return 0; } for(i = 0; i < num_bins ; i++) { - new_table->bins[i] = nil(st_table_entry); + new_table->bins[i] = 0; ptr = old_table->bins[i]; - while (ptr != nil(st_table_entry)) { + while (ptr != 0) { tbl = alloc(st_table_entry); - if (tbl == nil(st_table_entry)) { - free((char*)new_table->bins); - free((char*)new_table); - return nil(st_table); + if (tbl == 0) { + free(new_table->bins); + free(new_table); + return 0; } *tbl = *ptr; tbl->next = new_table->bins[i]; @@ -291,36 +343,35 @@ st_delete(table, key, value) register char **key; char **value; { - int hash_val; + unsigned int hash_val; st_table_entry *tmp; register st_table_entry *ptr; - hash_val = do_hash(*key, table); - + hash_val = do_hash_bin(*key, table); ptr = table->bins[hash_val]; - if (ptr == nil(st_table_entry)) { - if (value != nil(char*)) *value = nil(char); + if (ptr == 0) { + if (value != 0) *value = 0; return 0; } if (EQUAL(table, *key, ptr->key)) { table->bins[hash_val] = ptr->next; table->num_entries--; - if (value != nil(char*)) *value = ptr->record; + if (value != 0) *value = ptr->record; *key = ptr->key; - free((char*)ptr); + free(ptr); return 1; } - for(; ptr->next != nil(st_table_entry); ptr = ptr->next) { + for(; ptr->next != 0; ptr = ptr->next) { if (EQUAL(table, ptr->next->key, *key)) { tmp = ptr->next; ptr->next = ptr->next->next; table->num_entries--; - if (value != nil(char*)) *value = tmp->record; + if (value != 0) *value = tmp->record; *key = tmp->key; - free((char*)tmp); + free(tmp); return 1; } } @@ -335,31 +386,30 @@ st_delete_safe(table, key, value, never) char **value; char *never; { - int hash_val; + unsigned int hash_val; register st_table_entry *ptr; - hash_val = do_hash(*key, table); - + hash_val = do_hash_bin(*key, table); ptr = table->bins[hash_val]; - if (ptr == nil(st_table_entry)) { - if (value != nil(char*)) *value = nil(char); + if (ptr == 0) { + if (value != 0) *value = 0; return 0; } if (EQUAL(table, *key, ptr->key)) { table->num_entries--; *key = ptr->key; - if (value != nil(char*)) *value = ptr->record; + if (value != 0) *value = ptr->record; ptr->key = ptr->record = never; return 1; } - for(; ptr->next != nil(st_table_entry); ptr = ptr->next) { + for(; ptr->next != 0; ptr = ptr->next) { if (EQUAL(table, ptr->next->key, *key)) { table->num_entries--; *key = ptr->key; - if (value != nil(char*)) *value = ptr->record; + if (value != 0) *value = ptr->record; ptr->key = ptr->record = never; return 1; } @@ -379,8 +429,8 @@ st_foreach(table, func, arg) int i; for(i = 0; i < table->num_bins; i++) { - last = nil(st_table_entry); - for(ptr = table->bins[i]; ptr != nil(st_table_entry);) { + last = 0; + for(ptr = table->bins[i]; ptr != 0;) { retval = (*func)(ptr->key, ptr->record, arg); switch (retval) { case ST_CONTINUE: @@ -391,13 +441,13 @@ st_foreach(table, func, arg) return; case ST_DELETE: tmp = ptr; - if (last == nil(st_table_entry)) { + if (last == 0) { table->bins[i] = ptr->next; } else { last->next = ptr->next; } ptr = ptr->next; - free((char*)tmp); + free(tmp); table->num_entries--; } } @@ -405,9 +455,8 @@ st_foreach(table, func, arg) } static int -strhash(string, modulus) +strhash(string) register char *string; - int modulus; { register int val = 0; register int c; @@ -416,7 +465,7 @@ strhash(string, modulus) val = val*997 + c; } - return ((val < 0) ? -val : val)%modulus; + return val; } static int @@ -427,9 +476,8 @@ numcmp(x, y) } static int -numhash(n, modulus) +numhash(n) int n; - int modulus; { - return n % modulus; + return n; } |