diff options
Diffstat (limited to 'libtecla-1.4.1/hash.c')
| -rw-r--r-- | libtecla-1.4.1/hash.c | 748 |
1 files changed, 0 insertions, 748 deletions
diff --git a/libtecla-1.4.1/hash.c b/libtecla-1.4.1/hash.c deleted file mode 100644 index 89f8245..0000000 --- a/libtecla-1.4.1/hash.c +++ /dev/null @@ -1,748 +0,0 @@ -/* - * Copyright (c) 2000, 2001 by Martin C. Shepherd. - * - * All rights reserved. - * - * Permission is hereby granted, free of charge, to any person obtaining a - * copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, and/or sell copies of the Software, and to permit persons - * to whom the Software is furnished to do so, provided that the above - * copyright notice(s) and this permission notice appear in all copies of - * the Software and that both the above copyright notice(s) and this - * permission notice appear in supporting documentation. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS - * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT - * OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR - * HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL - * INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING - * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, - * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION - * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. - * - * Except as contained in this notice, the name of a copyright holder - * shall not be used in advertising or otherwise to promote the sale, use - * or other dealings in this Software without prior written authorization - * of the copyright holder. - */ - -#include <stdlib.h> -#include <stdio.h> -#include <string.h> -#include <ctype.h> - -#include "hash.h" -#include "strngmem.h" -#include "freelist.h" - -/* - * The following container object contains free-lists to be used - * for allocation of HashTable containers and nodes. - */ -struct HashMemory { - FreeList *hash_memory; /* HashTable free-list */ - FreeList *node_memory; /* HashNode free-list */ - StringMem *string_memory; /* Memory used to allocate hash strings */ -}; - -/* - * Define a hash symbol-table entry. - * See symbol.h for the definition of the Symbol container type. - */ -typedef struct HashNode HashNode; -struct HashNode { - Symbol symbol; /* The symbol stored in the hash-entry */ - HashNode *next; /* The next hash-table entry in a bucket list */ -}; - -/* - * Each hash-table bucket contains a linked list of entries that - * hash to the same bucket. - */ -typedef struct { - HashNode *head; /* The head of the bucket hash-node list */ - int count; /* The number of entries in the list */ -} HashBucket; - -/* - * Set the max length of the error-reporting string. There is no point - * in this being longer than the width of a typical terminal window. - * In composing error messages, I have assumed that this number is - * at least 80, so you don't decrease it below this number. - */ -#define ERRLEN 200 - -/* - * A hash-table consists of 'size' hash buckets. - * Note that the HashTable typedef for this struct is contained in hash.h. - */ -struct HashTable { - char errmsg[ERRLEN+1];/* Error-report buffer */ - HashMemory *mem; /* HashTable free-list */ - int internal_mem; /* True if 'mem' was allocated by _new_HashTable() */ - int case_sensitive; /* True if case is significant in lookup keys */ - int size; /* The number of hash buckets */ - HashBucket *bucket; /* An array of 'size' hash buckets */ - int (*keycmp)(const char *, const char *); /* Key comparison function */ - void *app_data; /* Application-provided data */ - HASH_DEL_FN(*del_fn); /* Application-provided 'app_data' destructor */ -}; - -static HashNode *_del_HashNode(HashTable *hash, HashNode *node); -static HashNode *_new_HashNode(HashTable *hash, const char *name, int code, - void (*fn)(void), void *data, SYM_DEL_FN(*del_fn)); -static HashNode *_find_HashNode(HashTable *hash, HashBucket *bucket, - const char *name, HashNode **prev); -static HashBucket *_find_HashBucket(HashTable *hash, const char *name); -static int _ht_lower_strcmp(const char *node_key, const char *look_key); -static int _ht_strcmp(const char *node_key, const char *look_key); - -/*....................................................................... - * Allocate a free-list for use in allocating hash tables and their nodes. - * - * Input: - * list_count int The number of HashTable containers per free-list - * block. - * node_count int The number of HashTable nodes per free-list block. - * Output: - * return HashMemory * The new free-list for use in allocating hash tables - * and their nodes. - */ -HashMemory *_new_HashMemory(int hash_count, int node_count) -{ - HashMemory *mem; -/* - * Allocate the free-list container. - */ - mem = (HashMemory *) malloc(sizeof(HashMemory)); - if(!mem) { - fprintf(stderr, "_new_HashMemory: Insufficient memory.\n"); - return NULL; - }; -/* - * Initialize the container at least up to the point at which it can - * safely be passed to _del_HashMemory(). - */ - mem->hash_memory = NULL; - mem->node_memory = NULL; - mem->string_memory = NULL; -/* - * Allocate the two free-lists. - */ - mem->hash_memory = _new_FreeList("_new_HashMemory", sizeof(HashTable), - hash_count); - if(!mem->hash_memory) - return _del_HashMemory(mem, 1); - mem->node_memory = _new_FreeList("_new_HashMemory", sizeof(HashNode), - node_count); - if(!mem->node_memory) - return _del_HashMemory(mem, 1); - mem->string_memory = _new_StringMem("_new_HashMemory", 64); - if(!mem->string_memory) - return _del_HashMemory(mem, 1); -/* - * Return the free-list container. - */ - return mem; -} - -/*....................................................................... - * Delete a HashTable free-list. An error will be displayed if the list is - * still in use and the deletion will be aborted. - * - * Input: - * mem HashMemory * The free-list container to be deleted. - * force int If force==0 then _del_HashMemory() will complain - * and refuse to delete the free-list if any - * of nodes have not been returned to the free-list. - * If force!=0 then _del_HashMemory() will not check - * whether any nodes are still in use and will - * always delete the list. - * Output: - * return HashMemory * Always NULL (even if the memory could not be - * deleted). - */ -HashMemory *_del_HashMemory(HashMemory *mem, int force) -{ - const char *caller = "_del_HashMemory"; - if(mem) { - if(!force && (_busy_FreeListNodes(mem->hash_memory) > 0 || - _busy_FreeListNodes(mem->node_memory) > 0)) { - fprintf(stderr, "%s: Free-list in use.\n", caller); - return NULL; - }; - mem->hash_memory = _del_FreeList(caller, mem->hash_memory, force); - mem->node_memory = _del_FreeList(caller, mem->node_memory, force); - mem->string_memory = _del_StringMem(caller, mem->string_memory, force); - free(mem); - }; - return NULL; -} - -/*....................................................................... - * Create a new hash table. - * - * Input: - * mem HashMemory * An optional free-list for use in allocating - * HashTable containers and nodes. See explanation - * in hash.h. If you are going to allocate more - * than one hash table, then it will be more - * efficient to allocate a single free-list for - * all of them than to force each hash table - * to allocate its own private free-list. - * size int The size of the hash table. Best performance - * will be acheived if this is a prime number. - * hcase HashCase Specify how symbol case is considered when - * looking up symbols, from: - * IGNORE_CASE - Upper and lower case versions - * of a letter are treated as - * being identical. - * HONOUR_CASE - Upper and lower case versions - * of a letter are treated as - * being distinct. - * characters in a lookup name is significant. - * app_data void * Optional application data to be registered - * to the table. This is presented to user - * provided SYM_DEL_FN() symbol destructors along - * with the symbol data. - * del_fn() HASH_DEL_FN(*) If you want app_data to be free'd when the - * hash-table is destroyed, register a suitable - * destructor function here. - * Output: - * return HashTable * The new hash table, or NULL on error. - */ -HashTable *_new_HashTable(HashMemory *mem, int size, HashCase hcase, - void *app_data, HASH_DEL_FN(*del_fn)) -{ - HashTable *hash; /* The table to be returned */ - int allocate_mem = !mem; /* True if mem should be internally allocated */ - int i; -/* - * Check arguments. - */ - if(size <= 0) { - fprintf(stderr, "_new_HashTable: Illegal table size (%d).\n", size); - return NULL; - }; -/* - * Allocate an internal free-list? - */ - if(allocate_mem) { - mem = _new_HashMemory(1, 100); - if(!mem) - return NULL; - }; -/* - * Allocate the container. - */ - hash = (HashTable *) _new_FreeListNode(mem->hash_memory); - if(!hash) { - fprintf(stderr, "_new_HashTable: Insufficient memory.\n"); - if(allocate_mem) - mem = _del_HashMemory(mem, 1); - return NULL; - }; -/* - * Before attempting any operation that might fail, initialize - * the container at least up to the point at which it can safely - * be passed to _del_HashTable(). - */ - hash->errmsg[0] = '\0'; - hash->mem = mem; - hash->internal_mem = allocate_mem; - hash->case_sensitive = hcase==HONOUR_CASE; - hash->size = size; - hash->bucket = NULL; - hash->keycmp = hash->case_sensitive ? _ht_strcmp : _ht_lower_strcmp; - hash->app_data = app_data; - hash->del_fn = del_fn; -/* - * Allocate the array of 'size' hash buckets. - */ - hash->bucket = (HashBucket *) malloc(sizeof(HashBucket) * size); - if(!hash->bucket) { - fprintf(stderr, "_new_HashTable: Insufficient memory for %d buckets.\n", - size); - return _del_HashTable(hash); - }; -/* - * Initialize the bucket array. - */ - for(i=0; i<size; i++) { - HashBucket *b = hash->bucket + i; - b->head = NULL; - b->count = 0; - }; -/* - * The table is ready for use - albeit currently empty. - */ - return hash; -} - -/*....................................................................... - * Delete a hash-table. - * - * Input: - * hash HashTable * The hash table to be deleted. - * Output: - * return HashTable * The deleted hash table (always NULL). - */ -HashTable *_del_HashTable(HashTable *hash) -{ - if(hash) { -/* - * Clear and delete the bucket array. - */ - if(hash->bucket) { - _clear_HashTable(hash); - free(hash->bucket); - hash->bucket = NULL; - }; -/* - * Delete application data. - */ - if(hash->del_fn) - hash->del_fn(hash->app_data); -/* - * If the hash table was allocated from an internal free-list, delete - * it and the hash table by deleting the free-list. Otherwise just - * return the hash-table to the external free-list. - */ - if(hash->internal_mem) - _del_HashMemory(hash->mem, 1); - else - hash = (HashTable *) _del_FreeListNode(hash->mem->hash_memory, hash); - }; - return NULL; -} - -/*....................................................................... - * Create and install a new entry in a hash table. If an entry with the - * same name already exists, replace its contents with the new data. - * - * Input: - * hash HashTable * The hash table to insert the symbol into. - * name const char * The name to tag the entry with. - * code int An application-specific code to be stored in - * the entry. - * fn void (*)(void) An application-specific function to be stored - * in the entry. - * data void * An application-specific pointer to data to be - * associated with the entry, or NULL if not - * relevant. - * del_fn SYM_DEL_FN(*) An optional destructor function. When the - * symbol is deleted this function will be called - * with the 'code' and 'data' arguments given - * above. Any application data that was registered - * to the table via the app_data argument of - * _new_HashTable() will also be passed. - * Output: - * return HashNode * The new entry, or NULL if there was insufficient - * memory or the arguments were invalid. - */ -Symbol *_new_HashSymbol(HashTable *hash, const char *name, int code, - void (*fn)(void), void *data, SYM_DEL_FN(*del_fn)) -{ - HashBucket *bucket; /* The hash-bucket associated with the name */ - HashNode *node; /* The new node */ -/* - * Check arguments. - */ - if(!hash || !name) - return NULL; -/* - * Get the hash bucket of the specified name. - */ - bucket = _find_HashBucket(hash, name); -/* - * See if a node with the same name already exists. - */ - node = _find_HashNode(hash, bucket, name, NULL); -/* - * If found, delete its contents by calling the user-supplied - * destructor function, if provided. - */ - if(node) { - if(node->symbol.data && node->symbol.del_fn) { - node->symbol.data = node->symbol.del_fn(hash->app_data, node->symbol.code, - node->symbol.data); - }; -/* - * Allocate a new node if necessary. - */ - } else { - node = _new_HashNode(hash, name, code, fn, data, del_fn); - if(!node) - return NULL; - }; -/* - * Install the node at the head of the hash-bucket list. - */ - node->next = bucket->head; - bucket->head = node; - bucket->count++; - return &node->symbol; -} - -/*....................................................................... - * Remove and delete a given hash-table entry. - * - * Input: - * hash HashTable * The hash table to find the symbol in. - * name const char * The name of the entry. - * Output: - * return HashNode * The deleted hash node (always NULL). - */ -Symbol *_del_HashSymbol(HashTable *hash, const char *name) -{ - if(hash && name) { - HashBucket *bucket = _find_HashBucket(hash, name); - HashNode *prev; /* The node preceding the located node */ - HashNode *node = _find_HashNode(hash, bucket, name, &prev); -/* - * Node found? - */ - if(node) { -/* - * Remove the node from the bucket list. - */ - if(prev) { - prev->next = node->next; - } else { - bucket->head = node->next; - }; -/* - * Record the loss of a node. - */ - bucket->count--; -/* - * Delete the node. - */ - (void) _del_HashNode(hash, node); - }; - }; - return NULL; -} - -/*....................................................................... - * Look up a symbol in the hash table. - * - * Input: - * hash HashTable * The table to look up the string in. - * name const char * The name of the symbol to look up. - * Output: - * return Symbol * The located hash-table symbol, or NULL if not - * found. - */ -Symbol *_find_HashSymbol(HashTable *hash, const char *name) -{ - HashBucket *bucket; /* The hash-table bucket associated with name[] */ - HashNode *node; /* The hash-table node of the requested symbol */ -/* - * Check arguments. - */ - if(!hash) - return NULL; -/* - * Nothing to lookup? - */ - if(!name) - return NULL; -/* - * Hash the name to a hash-table bucket. - */ - bucket = _find_HashBucket(hash, name); -/* - * Find the bucket entry that exactly matches the name. - */ - node = _find_HashNode(hash, bucket, name, NULL); - if(!node) - return NULL; - return &node->symbol; -} - -/*....................................................................... - * Private function used to allocate a hash-table node. - * The caller is responsible for checking that the specified symbol - * is unique and for installing the returned entry in the table. - * - * Input: - * hash HashTable * The table to allocate the node for. - * name const char * The name of the new entry. - * code int A user-supplied context code. - * fn void (*)(void) A user-supplied function pointer. - * data void * A user-supplied data pointer. - * del_fn SYM_DEL_FN(*) An optional 'data' destructor function. - * Output: - * return HashNode * The new node, or NULL on error. - */ -static HashNode *_new_HashNode(HashTable *hash, const char *name, int code, - void (*fn)(void), void *data, SYM_DEL_FN(*del_fn)) -{ - HashNode *node; /* The new node */ -/* - * Allocate the new node from the free list. - */ - node = (HashNode *) _new_FreeListNode(hash->mem->node_memory); - if(!node) - return NULL; -/* - * Before attempting any operation that might fail, initialize the - * contents of 'node' at least up to the point at which it can be - * safely passed to _del_HashNode(). - */ - node->symbol.name = NULL; - node->symbol.code = code; - node->symbol.fn = fn; - node->symbol.data = data; - node->symbol.del_fn = del_fn; - node->next = NULL; -/* - * Allocate a copy of 'name'. - */ - node->symbol.name = _new_StringMemString(hash->mem->string_memory, - strlen(name) + 1); - if(!node->symbol.name) - return _del_HashNode(hash, node); -/* - * If character-case is insignificant in the current table, convert the - * name to lower case while copying it. - */ - if(hash->case_sensitive) { - strcpy(node->symbol.name, name); - } else { - const char *src = name; - char *dst = node->symbol.name; - for( ; *src; src++,dst++) - *dst = tolower(*src); - *dst = '\0'; - }; - return node; -} - -/*....................................................................... - * Private function used to delete a hash-table node. - * The node must have been removed from its list before calling this - * function. - * - * Input: - * hash HashTable * The table for which the node was originally - * allocated. - * node HashNode * The node to be deleted. - * Output: - * return HashNode * The deleted node (always NULL). - */ -static HashNode *_del_HashNode(HashTable *hash, HashNode *node) -{ - if(node) { - node->symbol.name = _del_StringMemString(hash->mem->string_memory, - node->symbol.name); -/* - * Call the user-supplied data-destructor if provided. - */ - if(node->symbol.data && node->symbol.del_fn) - node->symbol.data = node->symbol.del_fn(hash->app_data, - node->symbol.code, - node->symbol.data); -/* - * Return the node to the free-list. - */ - node->next = NULL; - node = (HashNode *) _del_FreeListNode(hash->mem->node_memory, node); - }; - return NULL; -} - -/*....................................................................... - * Private function to locate the hash bucket associated with a given - * name. - * - * This uses a hash-function described in the dragon-book - * ("Compilers - Principles, Techniques and Tools", by Aho, Sethi and - * Ullman; pub. Adison Wesley) page 435. - * - * Input: - * hash HashTable * The table to look up the string in. - * name const char * The name of the symbol to look up. - * Output: - * return HashBucket * The located hash-bucket. - */ -static HashBucket *_find_HashBucket(HashTable *hash, const char *name) -{ - unsigned const char *kp; - unsigned long h = 0L; - if(hash->case_sensitive) { - for(kp=(unsigned const char *) name; *kp; kp++) - h = 65599UL * h + *kp; /* 65599 is a prime close to 2^16 */ - } else { - for(kp=(unsigned const char *) name; *kp; kp++) - h = 65599UL * h + tolower((int)*kp); /* 65599 is a prime close to 2^16 */ - }; - return hash->bucket + (h % hash->size); -} - -/*....................................................................... - * Search for a given name in the entries of a given bucket. - * - * Input: - * hash HashTable * The hash-table being searched. - * bucket HashBucket * The bucket to search (use _find_HashBucket()). - * name const char * The name to search for. - * Output: - * prev HashNode ** If prev!=NULL then the pointer to the node - * preceding the located node in the list will - * be recorded in *prev. This will be NULL either - * if the name is not found or the located node is - * at the head of the list of entries. - * return HashNode * The located hash-table node, or NULL if not - * found. - */ -static HashNode *_find_HashNode(HashTable *hash, HashBucket *bucket, - const char *name, HashNode **prev) -{ - HashNode *last; /* The previously searched node */ - HashNode *node; /* The node that is being searched */ -/* - * Search the list for a node containing the specified name. - */ - for(last=NULL, node=bucket->head; - node && hash->keycmp(node->symbol.name, name)!=0; - last = node, node=node->next) - ; - if(prev) - *prev = node ? last : NULL; - return node; -} - -/*....................................................................... - * When hash->case_sensitive is zero this function is called - * in place of strcmp(). In such cases the hash-table names are stored - * as lower-case versions of the original strings so this function - * performs the comparison against lower-case copies of the characters - * of the string being compared. - * - * Input: - * node_key const char * The lower-case hash-node key being compared - * against. - * look_key const char * The lookup key. - * Output: - * return int <0 if node_key < look_key. - * 0 if node_key == look_key. - * >0 if node_key > look_key. - */ -static int _ht_lower_strcmp(const char *node_key, const char *look_key) -{ - int cn; /* The latest character from node_key[] */ - int cl; /* The latest character from look_key[] */ - do { - cn = *node_key++; - cl = *look_key++; - } while(cn && cn==tolower(cl)); - return cn - tolower(cl); -} - -/*....................................................................... - * This is a wrapper around strcmp for comparing hash-keys in a case - * sensitive manner. The reason for having this wrapper, instead of using - * strcmp() directly, is to make some C++ compilers happy. The problem - * is that when the library is compiled with a C++ compiler, the - * declaration of the comparison function is a C++ declaration, whereas - * strcmp() is a pure C function and thus although it appears to have the - * same declaration, the compiler disagrees. - * - * Input: - * node_key char * The lower-case hash-node key being compared against. - * look_key char * The lookup key. - * Output: - * return int <0 if node_key < look_key. - * 0 if node_key == look_key. - * >0 if node_key > look_key. - */ -static int _ht_strcmp(const char *node_key, const char *look_key) -{ - return strcmp(node_key, look_key); -} - -/*....................................................................... - * Empty a hash-table by deleting all of its entries. - * - * Input: - * hash HashTable * The hash table to clear. - * Output: - * return int 0 - OK. - * 1 - Invalid arguments. - */ -int _clear_HashTable(HashTable *hash) -{ - int i; -/* - * Check the arguments. - */ - if(!hash) - return 1; -/* - * Clear the contents of the bucket array. - */ - for(i=0; i<hash->size; i++) { - HashBucket *bucket = hash->bucket + i; -/* - * Delete the list of active hash nodes from the bucket. - */ - HashNode *node = bucket->head; - while(node) { - HashNode *next = node->next; - (void) _del_HashNode(hash, node); - node = next; - }; -/* - * Mark the bucket as empty. - */ - bucket->head = NULL; - bucket->count = 0; - }; - return 0; -} - -/*....................................................................... - * Execute a given function on each entry of a hash table, returning - * before completion if the the specified function returns non-zero. - * - * Input: - * hash HashTable * The table to traverse. - * scan_fn HASH_SCAN_FN(*) The function to call. - * context void * Optional caller-specific context data - * to be passed to scan_fn(). - * Output: - * return int 0 - OK. - * 1 - Either the arguments were invalid, or - * scan_fn() returned non-zero at some - * point. - */ -int _scan_HashTable(HashTable *hash, HASH_SCAN_FN(*scan_fn), void *context) -{ - int i; -/* - * Check the arguments. - */ - if(!hash || !scan_fn) - return 1; -/* - * Iterate through the buckets of the table. - */ - for(i=0; i<hash->size; i++) { - HashBucket *bucket = hash->bucket + i; - HashNode *node; -/* - * Iterate through the list of symbols that fall into bucket i, - * passing each one to the caller-specified function. - */ - for(node=bucket->head; node; node=node->next) { - if(scan_fn(&node->symbol, context)) - return 1; - }; - }; - return 0; -} |