diff options
Diffstat (limited to 'src/hash.c')
| -rw-r--r-- | src/hash.c | 134 |
1 files changed, 68 insertions, 66 deletions
@@ -26,8 +26,8 @@ the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ #endif #include "hash.h" -unsigned long (*hashfunc)(char *) = NULL; -int (*matchfunc)(char *, char *) = NULL; +unsigned long (*hashfunc)(char *, int) = hash; +int (*matchfunc)(char *, char *) = match; int (*matchintfunc)(char *, char *, int, int) = NULL; /* Add match functions: These are just strcmp() and */ @@ -45,13 +45,17 @@ int matchnocase(char *st1, char *st2) else return 0; } -void InitializeHashTable(struct hashlist **tab) +void InitializeHashTable(struct hashtable *table, int hashsize) { int i; - for (i = 0; i < OBJHASHSIZE; i++) tab[i] = NULL; + table->hashsize = hashsize; + table->hashfirstindex = 0; + table->hashfirstptr = NULL; + table->hashtab = (struct hashlist **)malloc(hashsize * sizeof(struct hashlist *)); + for (i = 0; i < hashsize; i++) table->hashtab[i] = NULL; } -int RecurseHashTable(struct hashlist **hashtab, +int RecurseHashTable(struct hashtable *table, int (*func)(struct hashlist *elem)) /* returns the sum of the return values of (*func) */ { @@ -59,8 +63,8 @@ int RecurseHashTable(struct hashlist **hashtab, struct hashlist *p; sum = 0; - for (i = 0; i < OBJHASHSIZE; i++) - for (p = hashtab[i]; p != NULL; p = p->next) + for (i = 0; i < table->hashsize; i++) + for (p = table->hashtab[i]; p != NULL; p = p->next) sum += (*func)(p); return(sum); } @@ -69,15 +73,15 @@ int RecurseHashTable(struct hashlist **hashtab, * type int value to the function. */ -int RecurseHashTableValue(struct hashlist **hashtab, +int RecurseHashTableValue(struct hashtable *table, int (*func)(struct hashlist *elem, int), int value) { int i, sum; struct hashlist *p; sum = 0; - for (i = 0; i < OBJHASHSIZE; i++) - for (p = hashtab[i]; p != NULL; p = p->next) + for (i = 0; i < table->hashsize; i++) + for (p = table->hashtab[i]; p != NULL; p = p->next) sum += (*func)(p, value); return(sum); } @@ -88,7 +92,7 @@ int RecurseHashTableValue(struct hashlist **hashtab, * function through that structure. */ -struct nlist *RecurseHashTablePointer(struct hashlist **hashtab, +struct nlist *RecurseHashTablePointer(struct hashtable *table, struct nlist *(*func)(struct hashlist *elem, void *), void *pointer) { @@ -96,8 +100,8 @@ struct nlist *RecurseHashTablePointer(struct hashlist **hashtab, struct hashlist *p; struct nlist *tp; - for (i = 0; i < OBJHASHSIZE; i++) { - for (p = hashtab[i]; p != NULL; p = p->next) { + for (i = 0; i < table->hashsize; i++) { + for (p = table->hashtab[i]; p != NULL; p = p->next) { tp = (*func)(p, pointer); if (tp != NULL) return tp; } @@ -142,23 +146,23 @@ static unsigned char uppercase[] = { // have exactly the same hash result. Lousy for binning and even // lousier for generating class magic numbers. -unsigned long hashnocase(char *s) +unsigned long hashnocase(char *s, int hashsize) { unsigned long hashval; for (hashval = 0; *s != '\0'; ) hashval = uppercase[*s++] + (hashval << 6) + (hashval << 16) - hashval; - return (hashval % OBJHASHSIZE); + return (hashval % hashsize); } -unsigned long hash(char *s) +unsigned long hash(char *s, int hashsize) { unsigned long hashval; for (hashval = 0; *s != '\0'; ) hashval = (*s++) + (hashval << 6) + (hashval << 16) - hashval; - return (hashval % OBJHASHSIZE); + return (hashval % hashsize); } /*----------------------------------------------------------------------*/ @@ -166,14 +170,14 @@ unsigned long hash(char *s) /* return the 'ptr' field of the hash table entry, or NULL if not found */ /*----------------------------------------------------------------------*/ -void *HashLookup(char *s, struct hashlist **hashtab) +void *HashLookup(char *s, struct hashtable *table) { struct hashlist *np; unsigned long hashval; - hashval = (*hashfunc)(s); + hashval = (*hashfunc)(s, table->hashsize); - for (np = hashtab[hashval]; np != NULL; np = np->next) + for (np = table->hashtab[hashval]; np != NULL; np = np->next) if ((*matchfunc)(s, np->name)) return (np->ptr); /* correct match */ return (NULL); /* not found */ @@ -186,14 +190,14 @@ void *HashLookup(char *s, struct hashlist **hashtab) /* passed integer value i */ /*----------------------------------------------------------------------*/ -void *HashIntLookup(char *s, int i, struct hashlist **hashtab) +void *HashIntLookup(char *s, int i, struct hashtable *table) { struct hashlist *np; unsigned long hashval; - hashval = (*hashfunc)(s); + hashval = (*hashfunc)(s, table->hashsize); - for (np = hashtab[hashval]; np != NULL; np = np->next) { + for (np = table->hashtab[hashval]; np != NULL; np = np->next) { if (np->ptr == NULL) { if ((*matchintfunc)(s, np->name, i, -1)) return NULL; @@ -210,14 +214,13 @@ void *HashIntLookup(char *s, int i, struct hashlist **hashtab) /* return the hashlist entry, after (re)initializing its 'ptr' field */ /*----------------------------------------------------------------------*/ -struct hashlist *HashPtrInstall(char *name, void *ptr, - struct hashlist **hashtab) +struct hashlist *HashPtrInstall(char *name, void *ptr, struct hashtable *table) { struct hashlist *np; unsigned long hashval; - hashval = (*hashfunc)(name); - for (np = hashtab[hashval]; np != NULL; np = np->next) + hashval = (*hashfunc)(name, table->hashsize); + for (np = table->hashtab[hashval]; np != NULL; np = np->next) if ((*matchfunc)(name, np->name)) { np->ptr = ptr; return (np); /* match found in hash table */ @@ -229,8 +232,8 @@ struct hashlist *HashPtrInstall(char *name, void *ptr, if ((np->name = strdup(name)) == NULL) return (NULL); np->ptr = ptr; - np->next = hashtab[hashval]; - return(hashtab[hashval] = np); + np->next = table->hashtab[hashval]; + return(table->hashtab[hashval] = np); } /*----------------------------------------------------------------------*/ @@ -239,13 +242,13 @@ struct hashlist *HashPtrInstall(char *name, void *ptr, /*----------------------------------------------------------------------*/ struct hashlist *HashIntPtrInstall(char *name, int value, void *ptr, - struct hashlist **hashtab) + struct hashtable *table) { struct hashlist *np; unsigned long hashval; - hashval = (*hashfunc)(name); - for (np = hashtab[hashval]; np != NULL; np = np->next) + hashval = (*hashfunc)(name, table->hashsize); + for (np = table->hashtab[hashval]; np != NULL; np = np->next) if ((*matchintfunc)(name, np->name, value, (int)(*((int *)np->ptr)))) { np->ptr = ptr; return (np); /* match found in hash table */ @@ -256,27 +259,29 @@ struct hashlist *HashIntPtrInstall(char *name, int value, void *ptr, return (NULL); if ((np->name = strdup(name)) == NULL) return (NULL); np->ptr = ptr; - np->next = hashtab[hashval]; - return(hashtab[hashval] = np); + np->next = table->hashtab[hashval]; + return(table->hashtab[hashval] = np); } /*----------------------------------------------------------------------*/ /* destroy a hash table, freeing associated memory */ /*----------------------------------------------------------------------*/ -void HashKill(struct hashlist **hashtab) +void HashKill(struct hashtable *table) { struct hashlist *np, *p; int i; - for (i = 0; i < OBJHASHSIZE; i++) { - for (p = hashtab[i]; p != NULL; ) { + for (i = 0; i < table->hashsize; i++) { + for (p = table->hashtab[i]; p != NULL; ) { np = p->next; free(p->name); free(p); p = np; } } + free(table->hashtab); + table->hashtab = NULL; } /*----------------------------------------------------------------------*/ @@ -284,13 +289,13 @@ void HashKill(struct hashlist **hashtab) /* to the new hash entry. */ /*----------------------------------------------------------------------*/ -struct hashlist *HashInstall(char *name, struct hashlist **hashtab) +struct hashlist *HashInstall(char *name, struct hashtable *table) { struct hashlist *np; unsigned long hashval; - hashval = (*hashfunc)(name); - for (np = hashtab[hashval]; np != NULL; np = np->next) + hashval = (*hashfunc)(name, table->hashsize); + for (np = table->hashtab[hashval]; np != NULL; np = np->next) if ((*matchfunc)(name, np->name)) return (np); /* match found in hash table */ /* not in table, so install it */ @@ -298,27 +303,27 @@ struct hashlist *HashInstall(char *name, struct hashlist **hashtab) return (NULL); if ((np->name = strdup(name)) == NULL) return (NULL); np->ptr = NULL; - np->next = hashtab[hashval]; - return(hashtab[hashval] = np); + np->next = table->hashtab[hashval]; + return(table->hashtab[hashval] = np); } /*----------------------------------------------------------------------*/ /* frees a hash table entry, (but not the 'ptr' field) */ /*----------------------------------------------------------------------*/ -void HashDelete(char *name, struct hashlist **hashtab) +void HashDelete(char *name, struct hashtable *table) { unsigned long hashval; struct hashlist *np; struct hashlist *np2; - hashval = (*hashfunc)(name); - np = hashtab[hashval]; + hashval = (*hashfunc)(name, table->hashsize); + np = table->hashtab[hashval]; if (np == NULL) return; if ((*matchfunc)(name, np->name)) { /* it is the first element in the list */ - hashtab[hashval] = np->next; + table->hashtab[hashval] = np->next; free(np->name); free(np); return; @@ -341,19 +346,19 @@ void HashDelete(char *name, struct hashlist **hashtab) /* HashDelete with additional integer value matching */ /*----------------------------------------------------------------------*/ -void HashIntDelete(char *name, int value, struct hashlist **hashtab) +void HashIntDelete(char *name, int value, struct hashtable *table) { unsigned long hashval; struct hashlist *np; struct hashlist *np2; - hashval = (*hashfunc)(name); - np = hashtab[hashval]; + hashval = (*hashfunc)(name, table->hashsize); + np = table->hashtab[hashval]; if (np == NULL) return; if ((*matchintfunc)(name, np->name, value, (int)(*((int *)np->ptr)))) { /* it is the first element in the list */ - hashtab[hashval] = np->next; + table->hashtab[hashval] = np->next; free(np->name); free(np); return; @@ -375,31 +380,28 @@ void HashIntDelete(char *name, int value, struct hashlist **hashtab) /*----------------------------------------------------------------------*/ -static int hashfirstindex; /* was long */ -static struct hashlist *hashfirstptr; - -void *HashNext(struct hashlist **hashtab) +void *HashNext(struct hashtable *table) /* returns 'ptr' field of next element, NULL when done */ { - if (hashfirstptr != NULL && hashfirstptr->next != NULL) { - hashfirstptr = hashfirstptr->next; - return(hashfirstptr->ptr); + if (table->hashfirstptr != NULL && table->hashfirstptr->next != NULL) { + table->hashfirstptr = table->hashfirstptr->next; + return(table->hashfirstptr->ptr); } - while (hashfirstindex < OBJHASHSIZE) { - if ((hashfirstptr = hashtab[hashfirstindex++]) != NULL) { - return(hashfirstptr->ptr); + while (table->hashfirstindex < table->hashsize) { + if ((table->hashfirstptr = table->hashtab[table->hashfirstindex++]) != NULL) { + return(table->hashfirstptr->ptr); } } - hashfirstindex = 0; - hashfirstptr = NULL; + table->hashfirstindex = 0; + table->hashfirstptr = NULL; return(NULL); } -void *HashFirst(struct hashlist **hashtab) +void *HashFirst(struct hashtable *table) { - hashfirstindex = 0; - hashfirstptr = NULL; - return(HashNext(hashtab)); + table->hashfirstindex = 0; + table->hashfirstptr = NULL; + return(HashNext(table)); } |