diff options
Diffstat (limited to 'libtar/libtar_hash.c')
| -rw-r--r-- | libtar/libtar_hash.c | 344 |
1 files changed, 344 insertions, 0 deletions
diff --git a/libtar/libtar_hash.c b/libtar/libtar_hash.c new file mode 100644 index 000000000..796ebbee6 --- /dev/null +++ b/libtar/libtar_hash.c @@ -0,0 +1,344 @@ +/* listhash/libtar_hash.c. Generated from hash.c.in by configure. */ + +/* +** Copyright 1998-2002 University of Illinois Board of Trustees +** Copyright 1998-2002 Mark D. Roth +** All rights reserved. +** +** libtar_hash.c - hash table routines +** +** Mark D. Roth <roth@uiuc.edu> +** Campus Information Technologies and Educational Services +** University of Illinois at Urbana-Champaign +*/ + +#include <config.h> +#include <compat.h> + +#include <libtar_listhash.h> + +#include <stdio.h> +#include <errno.h> + +#ifdef STDC_HEADERS +# include <stdlib.h> +#endif + + +/* +** libtar_hashptr_reset() - reset a hash pointer +*/ +void +libtar_hashptr_reset(libtar_hashptr_t *hp) +{ + libtar_listptr_reset(&(hp->node)); + hp->bucket = -1; +} + + +/* +** libtar_hashptr_data() - retrieve the data being pointed to +*/ +void * +libtar_hashptr_data(libtar_hashptr_t *hp) +{ + return libtar_listptr_data(&(hp->node)); +} + + +/* +** libtar_str_hashfunc() - default hash function, optimized for +** 7-bit strings +*/ +unsigned int +libtar_str_hashfunc(char *key, unsigned int num_buckets) +{ +#if 0 + register unsigned result = 0; + register int i; + + if (key == NULL) + return 0; + + for (i = 0; *key != '\0' && i < 32; i++) + result = result * 33U + *key++; + + return (result % num_buckets); +#else + if (key == NULL) + return 0; + + return (key[0] % num_buckets); +#endif +} + + +/* +** libtar_hash_nents() - return number of elements from hash +*/ +unsigned int +libtar_hash_nents(libtar_hash_t *h) +{ + return h->nents; +} + + +/* +** libtar_hash_new() - create a new hash +*/ +libtar_hash_t * +libtar_hash_new(int num, libtar_hashfunc_t hashfunc) +{ + libtar_hash_t *hash; + + hash = (libtar_hash_t *)calloc(1, sizeof(libtar_hash_t)); + if (hash == NULL) + return NULL; + hash->numbuckets = num; + if (hashfunc != NULL) + hash->hashfunc = hashfunc; + else + hash->hashfunc = (libtar_hashfunc_t)libtar_str_hashfunc; + + hash->table = (libtar_list_t **)calloc(num, sizeof(libtar_list_t *)); + if (hash->table == NULL) + { + free(hash); + return NULL; + } + + return hash; +} + + +/* +** libtar_hash_next() - get next element in hash +** returns: +** 1 data found +** 0 end of list +*/ +int +libtar_hash_next(libtar_hash_t *h, + libtar_hashptr_t *hp) +{ +#ifdef DS_DEBUG + printf("==> libtar_hash_next(h=0x%lx, hp={%d,0x%lx})\n", + h, hp->bucket, hp->node); +#endif + + if (hp->bucket >= 0 && hp->node != NULL && + libtar_list_next(h->table[hp->bucket], &(hp->node)) != 0) + { +#ifdef DS_DEBUG + printf(" libtar_hash_next(): found additional " + "data in current bucket (%d), returing 1\n", + hp->bucket); +#endif + return 1; + } + +#ifdef DS_DEBUG + printf(" libtar_hash_next(): done with bucket %d\n", + hp->bucket); +#endif + + for (hp->bucket++; hp->bucket < h->numbuckets; hp->bucket++) + { +#ifdef DS_DEBUG + printf(" libtar_hash_next(): " + "checking bucket %d\n", hp->bucket); +#endif + hp->node = NULL; + if (h->table[hp->bucket] != NULL && + libtar_list_next(h->table[hp->bucket], + &(hp->node)) != 0) + { +#ifdef DS_DEBUG + printf(" libtar_hash_next(): " + "found data in bucket %d, returing 1\n", + hp->bucket); +#endif + return 1; + } + } + + if (hp->bucket == h->numbuckets) + { +#ifdef DS_DEBUG + printf(" libtar_hash_next(): hash pointer " + "wrapped to 0\n"); +#endif + hp->bucket = -1; + hp->node = NULL; + } + +#ifdef DS_DEBUG + printf("<== libtar_hash_next(): no more data, " + "returning 0\n"); +#endif + return 0; +} + + +/* +** libtar_hash_del() - delete an entry from the hash +** returns: +** 0 success +** -1 (and sets errno) failure +*/ +int +libtar_hash_del(libtar_hash_t *h, + libtar_hashptr_t *hp) +{ + if (hp->bucket < 0 + || hp->bucket >= h->numbuckets + || h->table[hp->bucket] == NULL + || hp->node == NULL) + { + errno = EINVAL; + return -1; + } + + libtar_list_del(h->table[hp->bucket], &(hp->node)); + h->nents--; + return 0; +} + + +/* +** libtar_hash_empty() - empty the hash +*/ +void +libtar_hash_empty(libtar_hash_t *h, libtar_freefunc_t freefunc) +{ + int i; + + for (i = 0; i < h->numbuckets; i++) + if (h->table[i] != NULL) + libtar_list_empty(h->table[i], freefunc); + + h->nents = 0; +} + + +/* +** libtar_hash_free() - delete all of the nodes in the hash +*/ +void +libtar_hash_free(libtar_hash_t *h, libtar_freefunc_t freefunc) +{ + int i; + + for (i = 0; i < h->numbuckets; i++) + if (h->table[i] != NULL) + libtar_list_free(h->table[i], freefunc); + + free(h->table); + free(h); +} + + +/* +** libtar_hash_search() - iterative search for an element in a hash +** returns: +** 1 match found +** 0 no match +*/ +int +libtar_hash_search(libtar_hash_t *h, + libtar_hashptr_t *hp, void *data, + libtar_matchfunc_t matchfunc) +{ + while (libtar_hash_next(h, hp) != 0) + if ((*matchfunc)(data, libtar_listptr_data(&(hp->node))) != 0) + return 1; + + return 0; +} + + +/* +** libtar_hash_getkey() - hash-based search for an element in a hash +** returns: +** 1 match found +** 0 no match +*/ +int +libtar_hash_getkey(libtar_hash_t *h, + libtar_hashptr_t *hp, void *key, + libtar_matchfunc_t matchfunc) +{ +#ifdef DS_DEBUG + printf("==> libtar_hash_getkey(h=0x%lx, hp={%d,0x%lx}, " + "key=0x%lx, matchfunc=0x%lx)\n", + h, hp->bucket, hp->node, key, matchfunc); +#endif + + if (hp->bucket == -1) + { + hp->bucket = (*(h->hashfunc))(key, h->numbuckets); +#ifdef DS_DEBUG + printf(" libtar_hash_getkey(): hp->bucket " + "set to %d\n", hp->bucket); +#endif + } + + if (h->table[hp->bucket] == NULL) + { +#ifdef DS_DEBUG + printf(" libtar_hash_getkey(): no list " + "for bucket %d, returning 0\n", hp->bucket); +#endif + hp->bucket = -1; + return 0; + } + +#ifdef DS_DEBUG + printf("<== libtar_hash_getkey(): " + "returning libtar_list_search()\n"); +#endif + return libtar_list_search(h->table[hp->bucket], &(hp->node), + key, matchfunc); +} + + +/* +** libtar_hash_add() - add an element to the hash +** returns: +** 0 success +** -1 (and sets errno) failure +*/ +int +libtar_hash_add(libtar_hash_t *h, void *data) +{ + int bucket, i; + +#ifdef DS_DEBUG + printf("==> libtar_hash_add(h=0x%lx, data=0x%lx)\n", + h, data); +#endif + + bucket = (*(h->hashfunc))(data, h->numbuckets); +#ifdef DS_DEBUG + printf(" libtar_hash_add(): inserting in bucket %d\n", + bucket); +#endif + if (h->table[bucket] == NULL) + { +#ifdef DS_DEBUG + printf(" libtar_hash_add(): creating new list\n"); +#endif + h->table[bucket] = libtar_list_new(LIST_QUEUE, NULL); + } + +#ifdef DS_DEBUG + printf("<== libtar_hash_add(): " + "returning libtar_list_add()\n"); +#endif + i = libtar_list_add(h->table[bucket], data); + if (i == 0) + h->nents++; + return i; +} + + |