ENH: Initial import

1 files changed, 344 insertions, 0 deletions

diff --git a/Utilities/cmtar/listhash/hash.c.in b/Utilities/cmtar/listhash/hash.c.in
new file mode 100644
index 0000000..41a1618
--- /dev/null
+++ b/Utilities/cmtar/listhash/hash.c.in
@@ -0,0 +1,344 @@
+/* @configure_input@ */
+
+/*
+**  Copyright 1998-2002 University of Illinois Board of Trustees
+**  Copyright 1998-2002 Mark D. Roth
+**  All rights reserved. 
+**
+**  @LISTHASH_PREFIX@_hash.c - hash table routines
+**
+**  Mark D. Roth <roth@uiuc.edu>
+**  Campus Information Technologies and Educational Services
+**  University of Illinois at Urbana-Champaign
+*/
+
+#include <@LISTHASH_PREFIX@/config.h>
+#include <@LISTHASH_PREFIX@/compat.h>
+
+#include <@LISTHASH_PREFIX@/@LISTHASH_PREFIX@_listhash.h>
+
+#include <stdio.h>
+#include <errno.h>
+
+#ifdef STDC_HEADERS
+# include <stdlib.h>
+#endif
+
+
+/*
+** @LISTHASH_PREFIX@_hashptr_reset() - reset a hash pointer
+*/
+void
+@LISTHASH_PREFIX@_hashptr_reset(@LISTHASH_PREFIX@_hashptr_t *hp)
+{
+  @LISTHASH_PREFIX@_listptr_reset(&(hp->node));
+  hp->bucket = -1;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_hashptr_data() - retrieve the data being pointed to
+*/
+void *
+@LISTHASH_PREFIX@_hashptr_data(@LISTHASH_PREFIX@_hashptr_t *hp)
+{
+  return @LISTHASH_PREFIX@_listptr_data(&(hp->node));
+}
+
+
+/*
+** @LISTHASH_PREFIX@_str_hashfunc() - default hash function, optimized for
+**              7-bit strings
+*/
+unsigned int
+@LISTHASH_PREFIX@_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
+}
+
+
+/*
+** @LISTHASH_PREFIX@_hash_nents() - return number of elements from hash
+*/
+unsigned int
+@LISTHASH_PREFIX@_hash_nents(@LISTHASH_PREFIX@_hash_t *h)
+{
+  return h->nents;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_hash_new() - create a new hash
+*/
+@LISTHASH_PREFIX@_hash_t *
+@LISTHASH_PREFIX@_hash_new(int num, @LISTHASH_PREFIX@_hashfunc_t hashfunc)
+{
+  @LISTHASH_PREFIX@_hash_t *hash;
+
+  hash = (@LISTHASH_PREFIX@_hash_t *)calloc(1, sizeof(@LISTHASH_PREFIX@_hash_t));
+  if (hash == NULL)
+    return NULL;
+  hash->numbuckets = num;
+  if (hashfunc != NULL)
+    hash->hashfunc = hashfunc;
+  else
+    hash->hashfunc = (@LISTHASH_PREFIX@_hashfunc_t)@LISTHASH_PREFIX@_str_hashfunc;
+
+  hash->table = (@LISTHASH_PREFIX@_list_t **)calloc(num, sizeof(@LISTHASH_PREFIX@_list_t *));
+  if (hash->table == NULL)
+  {
+    free(hash);
+    return NULL;
+  }
+
+  return hash;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_hash_next() - get next element in hash
+** returns:
+**  1      data found
+**  0      end of list
+*/
+int
+@LISTHASH_PREFIX@_hash_next(@LISTHASH_PREFIX@_hash_t *h,
+          @LISTHASH_PREFIX@_hashptr_t *hp)
+{
+#ifdef DS_DEBUG
+  printf("==> @LISTHASH_PREFIX@_hash_next(h=0x%lx, hp={%d,0x%lx})\n",
+         h, hp->bucket, hp->node);
+#endif
+
+  if (hp->bucket >= 0 && hp->node != NULL &&
+      @LISTHASH_PREFIX@_list_next(h->table[hp->bucket], &(hp->node)) != 0)
+  {
+#ifdef DS_DEBUG
+    printf("    @LISTHASH_PREFIX@_hash_next(): found additional "
+           "data in current bucket (%d), returing 1\n",
+           hp->bucket);
+#endif
+    return 1;
+  }
+
+#ifdef DS_DEBUG
+  printf("    @LISTHASH_PREFIX@_hash_next(): done with bucket %d\n",
+         hp->bucket);
+#endif
+
+  for (hp->bucket++; hp->bucket < h->numbuckets; hp->bucket++)
+  {
+#ifdef DS_DEBUG
+    printf("    @LISTHASH_PREFIX@_hash_next(): "
+           "checking bucket %d\n", hp->bucket);
+#endif
+    hp->node = NULL;
+    if (h->table[hp->bucket] != NULL &&
+        @LISTHASH_PREFIX@_list_next(h->table[hp->bucket],
+                &(hp->node)) != 0)
+    {
+#ifdef DS_DEBUG
+      printf("    @LISTHASH_PREFIX@_hash_next(): "
+             "found data in bucket %d, returing 1\n",
+             hp->bucket);
+#endif
+      return 1;
+    }
+  }
+
+  if (hp->bucket == h->numbuckets)
+  {
+#ifdef DS_DEBUG
+    printf("    @LISTHASH_PREFIX@_hash_next(): hash pointer "
+           "wrapped to 0\n");
+#endif
+    hp->bucket = -1;
+    hp->node = NULL;
+  }
+
+#ifdef DS_DEBUG
+  printf("<== @LISTHASH_PREFIX@_hash_next(): no more data, "
+         "returning 0\n");
+#endif
+  return 0;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_hash_del() - delete an entry from the hash
+** returns:
+**  0      success
+**  -1 (and sets errno)  failure
+*/
+int
+@LISTHASH_PREFIX@_hash_del(@LISTHASH_PREFIX@_hash_t *h,
+         @LISTHASH_PREFIX@_hashptr_t *hp)
+{
+  if (hp->bucket < 0
+      || hp->bucket >= h->numbuckets
+      || h->table[hp->bucket] == NULL
+      || hp->node == NULL)
+  {
+    errno = EINVAL;
+    return -1;
+  }
+
+  @LISTHASH_PREFIX@_list_del(h->table[hp->bucket], &(hp->node));
+  h->nents--;
+  return 0;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_hash_empty() - empty the hash
+*/
+void
+@LISTHASH_PREFIX@_hash_empty(@LISTHASH_PREFIX@_hash_t *h, @LISTHASH_PREFIX@_freefunc_t freefunc)
+{
+  int i;
+
+  for (i = 0; i < h->numbuckets; i++)
+    if (h->table[i] != NULL)
+      @LISTHASH_PREFIX@_list_empty(h->table[i], freefunc);
+
+  h->nents = 0;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_hash_free() - delete all of the nodes in the hash
+*/
+void
+@LISTHASH_PREFIX@_hash_free(@LISTHASH_PREFIX@_hash_t *h, @LISTHASH_PREFIX@_freefunc_t freefunc)
+{
+  int i;
+
+  for (i = 0; i < h->numbuckets; i++)
+    if (h->table[i] != NULL)
+      @LISTHASH_PREFIX@_list_free(h->table[i], freefunc);
+
+  free(h->table);
+  free(h);
+}
+
+
+/*
+** @LISTHASH_PREFIX@_hash_search() - iterative search for an element in a hash
+** returns:
+**  1      match found
+**  0      no match
+*/
+int
+@LISTHASH_PREFIX@_hash_search(@LISTHASH_PREFIX@_hash_t *h,
+            @LISTHASH_PREFIX@_hashptr_t *hp, void *data,
+            @LISTHASH_PREFIX@_matchfunc_t matchfunc)
+{
+  while (@LISTHASH_PREFIX@_hash_next(h, hp) != 0)
+    if ((*matchfunc)(data, @LISTHASH_PREFIX@_listptr_data(&(hp->node))) != 0)
+      return 1;
+
+  return 0;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_hash_getkey() - hash-based search for an element in a hash
+** returns:
+**  1      match found
+**  0      no match
+*/
+int
+@LISTHASH_PREFIX@_hash_getkey(@LISTHASH_PREFIX@_hash_t *h,
+            @LISTHASH_PREFIX@_hashptr_t *hp, void *key,
+            @LISTHASH_PREFIX@_matchfunc_t matchfunc)
+{
+#ifdef DS_DEBUG
+  printf("==> @LISTHASH_PREFIX@_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("    @LISTHASH_PREFIX@_hash_getkey(): hp->bucket "
+           "set to %d\n", hp->bucket);
+#endif
+  }
+
+  if (h->table[hp->bucket] == NULL)
+  {
+#ifdef DS_DEBUG
+    printf("    @LISTHASH_PREFIX@_hash_getkey(): no list "
+           "for bucket %d, returning 0\n", hp->bucket);
+#endif
+    hp->bucket = -1;
+    return 0;
+  }
+
+#ifdef DS_DEBUG
+  printf("<== @LISTHASH_PREFIX@_hash_getkey(): "
+         "returning @LISTHASH_PREFIX@_list_search()\n");
+#endif
+  return @LISTHASH_PREFIX@_list_search(h->table[hp->bucket], &(hp->node),
+               key, matchfunc);
+}
+
+
+/*
+** @LISTHASH_PREFIX@_hash_add() - add an element to the hash
+** returns:
+**  0      success
+**  -1 (and sets errno)  failure
+*/
+int
+@LISTHASH_PREFIX@_hash_add(@LISTHASH_PREFIX@_hash_t *h, void *data)
+{
+  int bucket, i;
+
+#ifdef DS_DEBUG
+  printf("==> @LISTHASH_PREFIX@_hash_add(h=0x%lx, data=0x%lx)\n",
+         h, data);
+#endif
+
+  bucket = (*(h->hashfunc))(data, h->numbuckets);
+#ifdef DS_DEBUG
+  printf("    @LISTHASH_PREFIX@_hash_add(): inserting in bucket %d\n",
+         bucket);
+#endif
+  if (h->table[bucket] == NULL)
+  {
+#ifdef DS_DEBUG
+    printf("    @LISTHASH_PREFIX@_hash_add(): creating new list\n");
+#endif
+    h->table[bucket] = @LISTHASH_PREFIX@_list_new(LIST_QUEUE, NULL);
+  }
+
+#ifdef DS_DEBUG
+  printf("<== @LISTHASH_PREFIX@_hash_add(): "
+         "returning @LISTHASH_PREFIX@_list_add()\n");
+#endif
+  i = @LISTHASH_PREFIX@_list_add(h->table[bucket], data);
+  if (i == 0)
+    h->nents++;
+  return i;
+}
+
+