/* // Full copyright information is available in the file ../doc/CREDITS */ #include "defs.h" #include "quickhash.h" #define MALLOC_DELTA 0 #define HASHTAB_STARTING_SIZE 128 INTERNAL void double_hashtab_size(Hash * hash); INTERNAL void insert_key(Hash * hash, Int i); Hash * hash_new_with(cList *keys) { Hash *cnew; Int i, j; /* Construct a new hash */ cnew = EMALLOC(Hash, 1); cnew->keys = list_dup(keys); /* Calculate initial size of chain and hash table. */ cnew->hashtab_size = HASHTAB_STARTING_SIZE; while (cnew->hashtab_size < keys->len) cnew->hashtab_size = cnew->hashtab_size * 2 + MALLOC_DELTA; /* Initialize chain entries and hash table. */ cnew->links = EMALLOC(Int, cnew->hashtab_size); cnew->hashtab = EMALLOC(Int, cnew->hashtab_size); for (i = 0; i < cnew->hashtab_size; i++) { cnew->links[i] = -1; cnew->hashtab[i] = -1; } /* Insert the keys into the hash table, eliminating duplicates. */ i = j = 0; while (i < cnew->keys->len) { if (i != j) cnew->keys->el[j] = cnew->keys->el[i]; if (hash_find(cnew, &keys->el[i]) == F_FAILURE) insert_key(cnew, j++); else data_discard(&cnew->keys->el[i]); i++; } cnew->keys->len = j; cnew->refs = 1; return cnew; } Hash * hash_new(int size) { cList * keys; Hash * out; keys = list_new(size); out = hash_new_with(keys); list_discard(keys); return out; } Hash * hash_dup(Hash * hash) { hash->refs++; return hash; } void hash_discard(Hash * hash) { hash->refs--; if (!hash->refs) { list_discard(hash->keys); efree(hash->links); efree(hash->hashtab); efree(hash); } } Hash * hash_add(Hash * hash, cData * key) { Int pos; #if 0 hash = hash_prep(hash); #endif pos = hash_find(hash, key); if (pos != F_FAILURE) return hash; /* Add the key */ hash->keys = list_add(hash->keys, key); /* Check if we should resize the hash table. */ if (hash->keys->len > hash->hashtab_size) double_hashtab_size(hash); else insert_key(hash, hash->keys->len - 1); return hash; } INTERNAL void insert_key(Hash * hash, Int i) { Int ind; ind = data_hash(&hash->keys->el[i]) % hash->hashtab_size; hash->links[i] = hash->hashtab[ind]; hash->hashtab[ind] = i; } Int hash_find(Hash * hash, cData *key) { Int ind, i; ind = data_hash(key) % hash->hashtab_size; for (i = hash->hashtab[ind]; i != -1; i = hash->links[i]) { if (data_cmp(&hash->keys->el[i], key) == 0) return i; } return F_FAILURE; } INTERNAL void double_hashtab_size(Hash * hash) { Int i; hash->hashtab_size = hash->hashtab_size * 2 + MALLOC_DELTA; hash->links = EREALLOC(hash->links, Int, hash->hashtab_size); hash->hashtab = EREALLOC(hash->hashtab, Int, hash->hashtab_size); for (i = 0; i < hash->hashtab_size; i++) { hash->links[i] = -1; hash->hashtab[i] = -1; } for (i = 0; i < hash->keys->len; i++) insert_key(hash, i); }