Lines Matching refs:hash
45 #include "hash.h"
56 StringMem *string_memory; /* Memory used to allocate hash strings */
60 * Define a hash symbol-table entry.
65 Symbol symbol; /* The symbol stored in the hash-entry */
66 HashNode *next; /* The next hash-table entry in a bucket list */
70 * Each hash-table bucket contains a linked list of entries that
71 * hash to the same bucket.
74 HashNode *head; /* The head of the bucket hash-node list */
79 * A hash-table consists of 'size' hash buckets.
80 * Note that the HashTable typedef for this struct is contained in hash.h.
86 int size; /* The number of hash buckets */
87 HashBucket *bucket; /* An array of 'size' hash buckets */
93 static HashNode *_del_HashNode(HashTable *hash, HashNode *node);
94 static HashNode *_new_HashNode(HashTable *hash, const char *name, int code,
96 static HashNode *_find_HashNode(HashTable *hash, HashBucket *bucket,
98 static HashBucket *_find_HashBucket(HashTable *hash, const char *name);
103 * Allocate a free-list for use in allocating hash tables and their nodes.
110 * return HashMemory * The new free-list for use in allocating hash tables
182 * Create a new hash table.
187 * in hash.h. If you are going to allocate more
188 * than one hash table, then it will be more
190 * all of them than to force each hash table
192 * size int The size of the hash table. Best performance
208 * hash-table is destroyed, register a suitable
211 * return HashTable * The new hash table, or NULL on error.
216 HashTable *hash; /* The table to be returned */
237 hash = (HashTable *) _new_FreeListNode(mem->hash_memory);
238 if(!hash) {
249 hash->mem = mem;
250 hash->internal_mem = allocate_mem;
251 hash->case_sensitive = hcase==HONOUR_CASE;
252 hash->size = size;
253 hash->bucket = NULL;
254 hash->keycmp = hash->case_sensitive ? _ht_strcmp : _ht_lower_strcmp;
255 hash->app_data = app_data;
256 hash->del_fn = del_fn;
258 * Allocate the array of 'size' hash buckets.
260 hash->bucket = (HashBucket *) malloc(sizeof(HashBucket) * size);
261 if(!hash->bucket) {
263 return _del_HashTable(hash);
269 HashBucket *b = hash->bucket + i;
276 return hash;
280 * Delete a hash-table.
283 * hash HashTable * The hash table to be deleted.
285 * return HashTable * The deleted hash table (always NULL).
287 HashTable *_del_HashTable(HashTable *hash)
289 if(hash) {
293 if(hash->bucket) {
294 _clear_HashTable(hash);
295 free(hash->bucket);
296 hash->bucket = NULL;
301 if(hash->del_fn)
302 hash->del_fn(hash->app_data);
304 * If the hash table was allocated from an internal free-list, delete
305 * it and the hash table by deleting the free-list. Otherwise just
306 * return the hash-table to the external free-list.
308 if(hash->internal_mem)
309 _del_HashMemory(hash->mem, 1);
311 hash = (HashTable *) _del_FreeListNode(hash->mem->hash_memory, hash);
317 * Create and install a new entry in a hash table. If an entry with the
321 * hash HashTable * The hash table to insert the symbol into.
340 Symbol *_new_HashSymbol(HashTable *hash, const char *name, int code,
343 HashBucket *bucket; /* The hash-bucket associated with the name */
348 if(!hash || !name) {
353 * Get the hash bucket of the specified name.
355 bucket = _find_HashBucket(hash, name);
359 node = _find_HashNode(hash, bucket, name, NULL);
366 node->symbol.data = node->symbol.del_fn(hash->app_data, node->symbol.code,
373 node = _new_HashNode(hash, name, code, fn, data, del_fn);
378 * Install the node at the head of the hash-bucket list.
387 * Remove and delete a given hash-table entry.
390 * hash HashTable * The hash table to find the symbol in.
393 * return HashNode * The deleted hash node (always NULL).
395 Symbol *_del_HashSymbol(HashTable *hash, const char *name)
397 if(hash && name) {
398 HashBucket *bucket = _find_HashBucket(hash, name);
400 HashNode *node = _find_HashNode(hash, bucket, name, &prev);
420 (void) _del_HashNode(hash, node);
427 * Look up a symbol in the hash table.
430 * hash HashTable * The table to look up the string in.
433 * return Symbol * The located hash-table symbol, or NULL if not
436 Symbol *_find_HashSymbol(HashTable *hash, const char *name)
438 HashBucket *bucket; /* The hash-table bucket associated with name[] */
439 HashNode *node; /* The hash-table node of the requested symbol */
443 if(!hash)
451 * Hash the name to a hash-table bucket.
453 bucket = _find_HashBucket(hash, name);
457 node = _find_HashNode(hash, bucket, name, NULL);
464 * Private function used to allocate a hash-table node.
469 * hash HashTable * The table to allocate the node for.
478 static HashNode *_new_HashNode(HashTable *hash, const char *name, int code,
486 node = (HashNode *) _new_FreeListNode(hash->mem->node_memory);
504 node->symbol.name = _new_StringMemString(hash->mem->string_memory, len);
506 return _del_HashNode(hash, node);
511 if(hash->case_sensitive) {
524 * Private function used to delete a hash-table node.
529 * hash HashTable * The table for which the node was originally
535 static HashNode *_del_HashNode(HashTable *hash, HashNode *node)
538 node->symbol.name = _del_StringMemString(hash->mem->string_memory,
544 node->symbol.data = node->symbol.del_fn(hash->app_data,
551 node = (HashNode *) _del_FreeListNode(hash->mem->node_memory, node);
557 * Private function to locate the hash bucket associated with a given
560 * This uses a hash-function described in the dragon-book
565 * hash HashTable * The table to look up the string in.
568 * return HashBucket * The located hash-bucket.
570 static HashBucket *_find_HashBucket(HashTable *hash, const char *name)
574 if(hash->case_sensitive) {
581 return hash->bucket + (h % hash->size);
588 * hash HashTable * The hash-table being searched.
597 * return HashNode * The located hash-table node, or NULL if not
600 static HashNode *_find_HashNode(HashTable *hash, HashBucket *bucket,
609 node && hash->keycmp(node->symbol.name, name)!=0;
618 * When hash->case_sensitive is zero this function is called
619 * in place of strcmp(). In such cases the hash-table names are stored
625 * node_key const char * The lower-case hash-node key being compared
645 * This is a wrapper around strcmp for comparing hash-keys in a case
654 * node_key char * The lower-case hash-node key being compared against.
667 * Empty a hash-table by deleting all of its entries.
670 * hash HashTable * The hash table to clear.
675 int _clear_HashTable(HashTable *hash)
681 if(!hash)
686 for(i=0; i<hash->size; i++) {
687 HashBucket *bucket = hash->bucket + i;
689 * Delete the list of active hash nodes from the bucket.
694 (void) _del_HashNode(hash, node);
707 * Execute a given function on each entry of a hash table, returning
711 * hash HashTable * The table to traverse.
721 int _scan_HashTable(HashTable *hash, HASH_SCAN_FN(*scan_fn), void *context)
727 if(!hash || !scan_fn)
732 for(i=0; i<hash->size; i++) {
733 HashBucket *bucket = hash->bucket + i;