summaryrefslogtreecommitdiffstats
path: root/libtar/libtar_hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'libtar/libtar_hash.c')
-rw-r--r--libtar/libtar_hash.c344
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;
+}
+
+