diff options
Diffstat (limited to 'lib/hashtable.c')
| -rw-r--r-- | lib/hashtable.c | 232 |
1 files changed, 232 insertions, 0 deletions
diff --git a/lib/hashtable.c b/lib/hashtable.c new file mode 100644 index 0000000..85fbb04 --- /dev/null +++ b/lib/hashtable.c @@ -0,0 +1,232 @@ +/* + * hashtable.c: in core hash table routines. + * + * Copyright (C) 1994, 1995 Graeme W. Wilford. (Wilf.) + * Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2009 Colin Watson. + * + * This file is part of man-db. + * + * man-db is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * man-db is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with man-db; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + * + * All of these routines except hashtable_free() can be found in K&R II. + * + * Sat Aug 20 15:01:02 BST 1994 Wilf. (G.Wilford@ee.surrey.ac.uk) + */ + +/* which hash function do we want ? */ +/* #define PROLOGUE */ +#define KRII + +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif /* HAVE_CONFIG_H */ + +#include <string.h> +#include <stdlib.h> + +#include "manconfig.h" +#include "hashtable.h" + +#if defined(PROLOGUE) +#define HASHSIZE 2048 +#elif defined(KRII) +#define HASHSIZE 2001 +#else +#error hash function not defined +#endif + +/* Return hash value for string. */ +static unsigned int hash (const char *s, size_t len) +{ + unsigned int hashval = 0; + size_t i; + + for (i = 0; i < len && s[i]; ++i) +#if defined(KRII) + hashval = s[i] + 31 * hashval; + return hashval % HASHSIZE; +#elif defined(PROLOGUE) + hashval = (hashval << 1) + s[i]; + return hashval & (HASHSIZE - 1); +#endif +} + +void null_hashtable_free (void *defn ATTRIBUTE_UNUSED) +{ +} + +/* Create a hashtable. */ +struct hashtable *hashtable_create (hashtable_free_ptr free_defn) +{ + struct hashtable *ht = XMALLOC (struct hashtable); + ht->hashtab = XCALLOC (HASHSIZE, struct nlist *); + ht->unique = 0; + ht->identical = 0; + ht->free_defn = free_defn; + return ht; +} + +/* Return pointer to hash entry structure containing s, or NULL if it + * doesn't exist. + */ +struct nlist *hashtable_lookup_structure (const struct hashtable *ht, + const char *s, size_t len) +{ + struct nlist *np; + + for (np = ht->hashtab[hash (s, len)]; np; np = np->next) { + if (strncmp (s, np->name, len) == 0) + return np; + } + return NULL; +} + +/* Return pointer to definition of s, or NULL if it doesn't exist. */ +void *hashtable_lookup (const struct hashtable *ht, const char *s, size_t len) +{ + struct nlist *np = hashtable_lookup_structure (ht, s, len); + if (np) + return np->defn; + else + return NULL; +} + +/* Return structure containing definition (never NULL). */ +struct nlist *hashtable_install (struct hashtable *ht, + const char *name, size_t len, void *defn) +{ + struct nlist *np; + + np = hashtable_lookup_structure (ht, name, len); + if (np) { + if (np->defn) + ht->free_defn (np->defn); + } else { + unsigned int hashval; + + np = XMALLOC (struct nlist); + np->name = xstrndup (name, len); + hashval = hash (name, len); + + /* record uniqueness if debugging */ + if (debug_level) { + if (ht->hashtab[hashval]) + ht->identical++; + else + ht->unique++; + } + + /* point to last entry with this hash */ + np->next = ht->hashtab[hashval]; + + /* attach to hashtab array */ + ht->hashtab[hashval] = np; + } + + np->defn = defn; + + return np; +} + +/* Remove structure containing name from the hash tree. */ +void hashtable_remove (struct hashtable *ht, const char *name, size_t len) +{ + struct nlist *np, *prev; + unsigned int hashval = hash (name, len); + + for (np = ht->hashtab[hashval], prev = NULL; np; + prev = np, np = np->next) { + if (strncmp (name, np->name, len) == 0) { + if (prev) + prev->next = np->next; + else + ht->hashtab[hashval] = np->next; + if (np->defn) + ht->free_defn (np->defn); + free (np->name); + free (np); + return; + } + } +} + +struct hashtable_iter { + struct nlist **bucket; + struct nlist *np; +}; + +/* Iterate over hash. Do not modify hash while iterating. */ +struct nlist *hashtable_iterate (const struct hashtable *ht, + struct hashtable_iter **iterp) +{ + struct hashtable_iter *iter = *iterp; + + if (!iter) + *iterp = iter = XZALLOC (struct hashtable_iter); + + if (iter->np && iter->np->next) + return iter->np = iter->np->next; + + if (iter->bucket) + ++iter->bucket; + else + iter->bucket = ht->hashtab; + + while (iter->bucket < ht->hashtab + HASHSIZE) { + if (*iter->bucket) + return iter->np = *iter->bucket; + ++iter->bucket; + } + + free (iter); + *iterp = NULL; + return NULL; +} + +/* Free up the hash tree (garbage collection). Also call the free_defn() + * hook to free up values if necessary. + */ +void hashtable_free (struct hashtable *ht) +{ + int i; + + if (!ht) + return; + + debug ("hashtable_free: %d entries, %d (%d%%) unique\n", + ht->unique + ht->identical, + ht->unique, + ht->unique ? (ht->unique * 100) / (ht->unique + ht->identical) + : 0); + + for (i = 0; i < HASHSIZE; i++) { + struct nlist *np; + + np = ht->hashtab[i]; + while (np) { + struct nlist *next; + + if (np->defn) + ht->free_defn (np->defn); + free (np->name); + next = np->next; + free (np); + np = next; + } + } + + free (ht->hashtab); + free (ht); +} |