ENH: Initial import

3 files changed, 997 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;
+}
+
+
diff --git a/Utilities/cmtar/listhash/list.c.in b/Utilities/cmtar/listhash/list.c.in
new file mode 100644
index 0000000..71c5bf6
--- /dev/null
+++ b/Utilities/cmtar/listhash/list.c.in
@@ -0,0 +1,457 @@
+/* @configure_input@ */
+
+/*
+**  Copyright 1998-2002 University of Illinois Board of Trustees
+**  Copyright 1998-2002 Mark D. Roth
+**  All rights reserved.
+**
+**  @LISTHASH_PREFIX@_list.c - linked list 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 <string.h>
+# include <stdlib.h>
+#endif
+
+
+/*
+** @LISTHASH_PREFIX@_listptr_reset() - reset a list pointer
+*/
+void
+@LISTHASH_PREFIX@_listptr_reset(@LISTHASH_PREFIX@_listptr_t *lp)
+{
+  *lp = NULL;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_listptr_data() - retrieve the data pointed to by lp
+*/
+void *
+@LISTHASH_PREFIX@_listptr_data(@LISTHASH_PREFIX@_listptr_t *lp)
+{
+  return (*lp)->data;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_list_new() - create a new, empty list
+*/
+@LISTHASH_PREFIX@_list_t *
+@LISTHASH_PREFIX@_list_new(int flags, @LISTHASH_PREFIX@_cmpfunc_t cmpfunc)
+{
+  @LISTHASH_PREFIX@_list_t *newlist;
+
+#ifdef DS_DEBUG
+  printf("in @LISTHASH_PREFIX@_list_new(%d, 0x%lx)\n", flags, cmpfunc);
+#endif
+
+  if (flags != LIST_USERFUNC
+      && flags != LIST_STACK
+      && flags != LIST_QUEUE)
+  {
+    errno = EINVAL;
+    return NULL;
+  }
+
+  newlist = (@LISTHASH_PREFIX@_list_t *)calloc(1, sizeof(@LISTHASH_PREFIX@_list_t));
+  if (cmpfunc != NULL)
+    newlist->cmpfunc = cmpfunc;
+  else
+    newlist->cmpfunc = (@LISTHASH_PREFIX@_cmpfunc_t)strcmp;
+  newlist->flags = flags;
+
+  return newlist;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_list_iterate() - call a function for every element
+**              in a list
+*/
+int
+@LISTHASH_PREFIX@_list_iterate(@LISTHASH_PREFIX@_list_t *l,
+             @LISTHASH_PREFIX@_iterate_func_t plugin,
+             void *state)
+{
+  @LISTHASH_PREFIX@_listptr_t n;
+
+  if (l == NULL)
+    return -1;
+
+  for (n = l->first; n != NULL; n = n->next)
+  {
+    if ((*plugin)(n->data, state) == -1)
+      return -1;
+  }
+
+  return 0;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_list_empty() - empty the list
+*/
+void
+@LISTHASH_PREFIX@_list_empty(@LISTHASH_PREFIX@_list_t *l, @LISTHASH_PREFIX@_freefunc_t freefunc)
+{
+  @LISTHASH_PREFIX@_listptr_t n;
+
+  for (n = l->first; n != NULL; n = l->first)
+  {
+    l->first = n->next;
+    if (freefunc != NULL)
+      (*freefunc)(n->data);
+    free(n);
+  }
+
+  l->nents = 0;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_list_free() - remove and free() the whole list
+*/
+void
+@LISTHASH_PREFIX@_list_free(@LISTHASH_PREFIX@_list_t *l, @LISTHASH_PREFIX@_freefunc_t freefunc)
+{
+  @LISTHASH_PREFIX@_list_empty(l, freefunc);
+  free(l);
+}
+
+
+/*
+** @LISTHASH_PREFIX@_list_nents() - return number of elements in the list
+*/
+unsigned int
+@LISTHASH_PREFIX@_list_nents(@LISTHASH_PREFIX@_list_t *l)
+{
+  return l->nents;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_list_add() - adds an element to the list
+** returns:
+**  0      success
+**  -1 (and sets errno)  failure
+*/
+int
+@LISTHASH_PREFIX@_list_add(@LISTHASH_PREFIX@_list_t *l, void *data)
+{
+  @LISTHASH_PREFIX@_listptr_t n, m;
+
+#ifdef DS_DEBUG
+  printf("==> @LISTHASH_PREFIX@_list_add(\"%s\")\n", (char *)data);
+#endif
+
+  n = (@LISTHASH_PREFIX@_listptr_t)malloc(sizeof(struct @LISTHASH_PREFIX@_node));
+  if (n == NULL)
+    return -1;
+  n->data = data;
+  l->nents++;
+
+#ifdef DS_DEBUG
+  printf("    @LISTHASH_PREFIX@_list_add(): allocated data\n");
+#endif
+
+  /* if the list is empty */
+  if (l->first == NULL)
+  {
+    l->last = l->first = n;
+    n->next = n->prev = NULL;
+#ifdef DS_DEBUG
+    printf("<== @LISTHASH_PREFIX@_list_add(): list was empty; "
+           "added first element and returning 0\n");
+#endif
+    return 0;
+  }
+
+#ifdef DS_DEBUG
+  printf("    @LISTHASH_PREFIX@_list_add(): list not empty\n");
+#endif
+
+  if (l->flags == LIST_STACK)
+  {
+    n->prev = NULL;
+    n->next = l->first;
+    if (l->first != NULL)
+      l->first->prev = n;
+    l->first = n;
+#ifdef DS_DEBUG
+    printf("<== @LISTHASH_PREFIX@_list_add(): LIST_STACK set; "
+           "added in front\n");
+#endif
+    return 0;
+  }
+
+  if (l->flags == LIST_QUEUE)
+  {
+    n->prev = l->last;
+    n->next = NULL;
+    if (l->last != NULL)
+      l->last->next = n;
+    l->last = n;
+#ifdef DS_DEBUG
+    printf("<== @LISTHASH_PREFIX@_list_add(): LIST_QUEUE set; "
+           "added at end\n");
+#endif
+    return 0;
+  }
+
+  for (m = l->first; m != NULL; m = m->next)
+    if ((*(l->cmpfunc))(data, m->data) < 0)
+    {
+      /*
+      ** if we find one that's bigger,
+      ** insert data before it
+      */
+#ifdef DS_DEBUG
+      printf("    @LISTHASH_PREFIX@_list_add(): gotcha..."
+             "inserting data\n");
+#endif
+      if (m == l->first)
+      {
+        l->first = n;
+        n->prev = NULL;
+        m->prev = n;
+        n->next = m;
+#ifdef DS_DEBUG
+        printf("<== @LISTHASH_PREFIX@_list_add(): "
+               "added first, returning 0\n");
+#endif
+        return 0;
+      }
+      m->prev->next = n;
+      n->prev = m->prev;
+      m->prev = n;
+      n->next = m;
+#ifdef DS_DEBUG
+      printf("<== @LISTHASH_PREFIX@_list_add(): added middle,"
+             " returning 0\n");
+#endif
+      return 0;
+    }
+
+#ifdef DS_DEBUG
+  printf("    @LISTHASH_PREFIX@_list_add(): new data larger than current "
+         "list elements\n");
+#endif
+
+  /* if we get here, data is bigger than everything in the list */
+  l->last->next = n;
+  n->prev = l->last;
+  l->last = n;
+  n->next = NULL;
+#ifdef DS_DEBUG
+  printf("<== @LISTHASH_PREFIX@_list_add(): added end, returning 0\n");
+#endif
+  return 0;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_list_del() - remove the element pointed to by n
+**          from the list l
+*/
+void
+@LISTHASH_PREFIX@_list_del(@LISTHASH_PREFIX@_list_t *l, @LISTHASH_PREFIX@_listptr_t *n)
+{
+  @LISTHASH_PREFIX@_listptr_t m;
+
+#ifdef DS_DEBUG
+  printf("==> @LISTHASH_PREFIX@_list_del()\n");
+#endif
+
+  l->nents--;
+
+  m = (*n)->next;
+
+  if ((*n)->prev)
+    (*n)->prev->next = (*n)->next;
+  else
+    l->first = (*n)->next;
+  if ((*n)->next)
+    (*n)->next->prev = (*n)->prev;
+  else
+    l->last = (*n)->prev;
+
+  free(*n);
+  *n = m;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_list_next() - get the next element in the list
+** returns:
+**  1      success
+**  0      end of list
+*/
+int
+@LISTHASH_PREFIX@_list_next(@LISTHASH_PREFIX@_list_t *l,
+          @LISTHASH_PREFIX@_listptr_t *n)
+{
+  if (*n == NULL)
+    *n = l->first;
+  else
+    *n = (*n)->next;
+
+  return (*n != NULL ? 1 : 0);
+}
+
+
+/*
+** @LISTHASH_PREFIX@_list_prev() - get the previous element in the list
+** returns:
+**  1      success
+**  0      end of list
+*/
+int
+@LISTHASH_PREFIX@_list_prev(@LISTHASH_PREFIX@_list_t *l,
+          @LISTHASH_PREFIX@_listptr_t *n)
+{
+  if (*n == NULL)
+    *n = l->last;
+  else
+    *n = (*n)->prev;
+
+  return (*n != NULL ? 1 : 0);
+}
+
+
+/*
+** @LISTHASH_PREFIX@_str_match() - string matching function
+** returns:
+**  1      match
+**  0      no match
+*/
+int
+@LISTHASH_PREFIX@_str_match(char *check, char *data)
+{
+  return !strcmp(check, data);
+}
+
+
+/*
+** @LISTHASH_PREFIX@_list_add_str() - splits string str into delim-delimited
+**              elements and adds them to list l
+** returns:
+**  0      success
+**  -1 (and sets errno)  failure
+*/
+int
+@LISTHASH_PREFIX@_list_add_str(@LISTHASH_PREFIX@_list_t *l,
+             char *str, char *delim)
+{
+  char tmp[10240];
+  char *tokp, *nextp = tmp;
+
+  strlcpy(tmp, str, sizeof(tmp));
+  while ((tokp = strsep(&nextp, delim)) != NULL)
+  {
+    if (*tokp == '\0')
+      continue;
+    if (@LISTHASH_PREFIX@_list_add(l, strdup(tokp)))
+      return -1;
+  }
+
+  return 0;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_list_search() - find an entry in a list
+** returns:
+**  1      match found
+**  0      no match
+*/
+int
+@LISTHASH_PREFIX@_list_search(@LISTHASH_PREFIX@_list_t *l,
+            @LISTHASH_PREFIX@_listptr_t *n, void *data,
+            @LISTHASH_PREFIX@_matchfunc_t matchfunc)
+{
+#ifdef DS_DEBUG
+  printf("==> @LISTHASH_PREFIX@_list_search(l=0x%lx, n=0x%lx, \"%s\")\n",
+         l, n, (char *)data);
+#endif
+
+  if (matchfunc == NULL)
+    matchfunc = (@LISTHASH_PREFIX@_matchfunc_t)@LISTHASH_PREFIX@_str_match;
+
+  if (*n == NULL)
+    *n = l->first;
+  else
+    *n = (*n)->next;
+
+  for (; *n != NULL; *n = (*n)->next)
+  {
+#ifdef DS_DEBUG
+    printf("checking against \"%s\"\n", (char *)(*n)->data);
+#endif
+    if ((*(matchfunc))(data, (*n)->data) != 0)
+      return 1;
+  }
+
+#ifdef DS_DEBUG
+  printf("no matches found\n");
+#endif
+  return 0;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_list_dup() - copy an existing list
+*/
+@LISTHASH_PREFIX@_list_t *
+@LISTHASH_PREFIX@_list_dup(@LISTHASH_PREFIX@_list_t *l)
+{
+  @LISTHASH_PREFIX@_list_t *newlist;
+  @LISTHASH_PREFIX@_listptr_t n;
+
+  newlist = @LISTHASH_PREFIX@_list_new(l->flags, l->cmpfunc);
+  for (n = l->first; n != NULL; n = n->next)
+    @LISTHASH_PREFIX@_list_add(newlist, n->data);
+
+#ifdef DS_DEBUG
+  printf("returning from @LISTHASH_PREFIX@_list_dup()\n");
+#endif
+  return newlist;
+}
+
+
+/*
+** @LISTHASH_PREFIX@_list_merge() - merge two lists into a new list
+*/
+@LISTHASH_PREFIX@_list_t *
+@LISTHASH_PREFIX@_list_merge(@LISTHASH_PREFIX@_cmpfunc_t cmpfunc, int flags,
+           @LISTHASH_PREFIX@_list_t *list1,
+           @LISTHASH_PREFIX@_list_t *list2)
+{
+  @LISTHASH_PREFIX@_list_t *newlist;
+  @LISTHASH_PREFIX@_listptr_t n;
+
+  newlist = @LISTHASH_PREFIX@_list_new(flags, cmpfunc);
+
+  n = NULL;
+  while (@LISTHASH_PREFIX@_list_next(list1, &n) != 0)
+    @LISTHASH_PREFIX@_list_add(newlist, n->data);
+  n = NULL;
+  while (@LISTHASH_PREFIX@_list_next(list2, &n) != 0)
+    @LISTHASH_PREFIX@_list_add(newlist, n->data);
+
+  return newlist;
+}
+
+
diff --git a/Utilities/cmtar/listhash/listhash.h.in b/Utilities/cmtar/listhash/listhash.h.in
new file mode 100644
index 0000000..4ab5fdf
--- /dev/null
+++ b/Utilities/cmtar/listhash/listhash.h.in
@@ -0,0 +1,196 @@
+/* @configure_input@ */
+
+/*
+**  Copyright 1998-2002 University of Illinois Board of Trustees
+**  Copyright 1998-2002 Mark D. Roth
+**  All rights reserved.
+**
+**  @LISTHASH_PREFIX@_listhash.h - header file for listhash module
+**
+**  Mark D. Roth <roth@uiuc.edu>
+**  Campus Information Technologies and Educational Services
+**  University of Illinois at Urbana-Champaign
+*/
+
+#ifndef @LISTHASH_PREFIX@_LISTHASH_H
+#define @LISTHASH_PREFIX@_LISTHASH_H
+
+
+/***** list.c **********************************************************/
+
+/*
+** Comparison function (used to determine order of elements in a list)
+** returns less than, equal to, or greater than 0
+** if data1 is less than, equal to, or greater than data2
+*/
+typedef int (*@LISTHASH_PREFIX@_cmpfunc_t)(void *, void *);
+
+/*
+** Free function (for freeing allocated memory in each element)
+*/
+typedef void (*@LISTHASH_PREFIX@_freefunc_t)(void *);
+
+/*
+** Plugin function for @LISTHASH_PREFIX@_list_iterate()
+*/
+typedef int (*@LISTHASH_PREFIX@_iterate_func_t)(void *, void *);
+
+/*
+** Matching function (used to find elements in a list)
+** first argument is the data to search for
+** second argument is the list element it's being compared to
+** returns 0 if no match is found, non-zero otherwise
+*/
+typedef int (*@LISTHASH_PREFIX@_matchfunc_t)(void *, void *);
+
+
+struct @LISTHASH_PREFIX@_node
+{
+  void *data;
+  struct @LISTHASH_PREFIX@_node *next;
+  struct @LISTHASH_PREFIX@_node *prev;
+};
+typedef struct @LISTHASH_PREFIX@_node *@LISTHASH_PREFIX@_listptr_t;
+
+struct @LISTHASH_PREFIX@_list
+{
+  @LISTHASH_PREFIX@_listptr_t first;
+  @LISTHASH_PREFIX@_listptr_t last;
+  @LISTHASH_PREFIX@_cmpfunc_t cmpfunc;
+  int flags;
+  unsigned int nents;
+};
+typedef struct @LISTHASH_PREFIX@_list @LISTHASH_PREFIX@_list_t;
+
+
+/* values for flags */
+#define LIST_USERFUNC  0  /* use cmpfunc() to order */
+#define LIST_STACK  1  /* new elements go in front */
+#define LIST_QUEUE  2  /* new elements go at the end */
+
+
+/* reset a list pointer */
+void @LISTHASH_PREFIX@_listptr_reset(@LISTHASH_PREFIX@_listptr_t *);
+
+/* retrieve the data being pointed to */
+void *@LISTHASH_PREFIX@_listptr_data(@LISTHASH_PREFIX@_listptr_t *);
+
+/* creates a new, empty list */
+@LISTHASH_PREFIX@_list_t *@LISTHASH_PREFIX@_list_new(int, @LISTHASH_PREFIX@_cmpfunc_t);
+
+/* call a function for every element in a list */
+int @LISTHASH_PREFIX@_list_iterate(@LISTHASH_PREFIX@_list_t *,
+           @LISTHASH_PREFIX@_iterate_func_t, void *);
+
+/* empty the list */
+void @LISTHASH_PREFIX@_list_empty(@LISTHASH_PREFIX@_list_t *,
+          @LISTHASH_PREFIX@_freefunc_t);
+
+/* remove and free() the entire list */
+void @LISTHASH_PREFIX@_list_free(@LISTHASH_PREFIX@_list_t *,
+         @LISTHASH_PREFIX@_freefunc_t);
+
+/* add elements */
+int @LISTHASH_PREFIX@_list_add(@LISTHASH_PREFIX@_list_t *, void *);
+
+/* removes an element from the list - returns -1 on error */
+void @LISTHASH_PREFIX@_list_del(@LISTHASH_PREFIX@_list_t *,
+        @LISTHASH_PREFIX@_listptr_t *);
+
+/* returns 1 when valid data is returned, or 0 at end of list */
+int @LISTHASH_PREFIX@_list_next(@LISTHASH_PREFIX@_list_t *,
+        @LISTHASH_PREFIX@_listptr_t *);
+
+/* returns 1 when valid data is returned, or 0 at end of list */
+int @LISTHASH_PREFIX@_list_prev(@LISTHASH_PREFIX@_list_t *,
+        @LISTHASH_PREFIX@_listptr_t *);
+
+/* return 1 if the data matches a list entry, 0 otherwise */
+int @LISTHASH_PREFIX@_list_search(@LISTHASH_PREFIX@_list_t *,
+          @LISTHASH_PREFIX@_listptr_t *, void *,
+          @LISTHASH_PREFIX@_matchfunc_t);
+
+/* return number of elements from list */
+unsigned int @LISTHASH_PREFIX@_list_nents(@LISTHASH_PREFIX@_list_t *);
+
+/* adds elements from a string delimited by delim */
+int @LISTHASH_PREFIX@_list_add_str(@LISTHASH_PREFIX@_list_t *, char *, char *);
+
+/* string matching function */
+int @LISTHASH_PREFIX@_str_match(char *, char *);
+
+
+/***** hash.c **********************************************************/
+
+/*
+** Hashing function (determines which bucket the given key hashes into)
+** first argument is the key to hash
+** second argument is the total number of buckets
+** returns the bucket number
+*/
+typedef unsigned int (*@LISTHASH_PREFIX@_hashfunc_t)(void *, unsigned int);
+
+
+struct @LISTHASH_PREFIX@_hashptr
+{
+  int bucket;
+  @LISTHASH_PREFIX@_listptr_t node;
+};
+typedef struct @LISTHASH_PREFIX@_hashptr @LISTHASH_PREFIX@_hashptr_t;
+
+struct @LISTHASH_PREFIX@_hash
+{
+  int numbuckets;
+  @LISTHASH_PREFIX@_list_t **table;
+  @LISTHASH_PREFIX@_hashfunc_t hashfunc;
+  unsigned int nents;
+};
+typedef struct @LISTHASH_PREFIX@_hash @LISTHASH_PREFIX@_hash_t;
+
+
+/* reset a hash pointer */
+void @LISTHASH_PREFIX@_hashptr_reset(@LISTHASH_PREFIX@_hashptr_t *);
+
+/* retrieve the data being pointed to */
+void *@LISTHASH_PREFIX@_hashptr_data(@LISTHASH_PREFIX@_hashptr_t *);
+
+/* default hash function, optimized for 7-bit strings */
+unsigned int @LISTHASH_PREFIX@_str_hashfunc(char *, unsigned int);
+
+/* return number of elements from hash */
+unsigned int @LISTHASH_PREFIX@_hash_nents(@LISTHASH_PREFIX@_hash_t *);
+
+/* create a new hash */
+@LISTHASH_PREFIX@_hash_t *@LISTHASH_PREFIX@_hash_new(int, @LISTHASH_PREFIX@_hashfunc_t);
+
+/* empty the hash */
+void @LISTHASH_PREFIX@_hash_empty(@LISTHASH_PREFIX@_hash_t *,
+          @LISTHASH_PREFIX@_freefunc_t);
+
+/* delete all the @LISTHASH_PREFIX@_nodes of the hash and clean up */
+void @LISTHASH_PREFIX@_hash_free(@LISTHASH_PREFIX@_hash_t *,
+         @LISTHASH_PREFIX@_freefunc_t);
+
+/* returns 1 when valid data is returned, or 0 at end of list */
+int @LISTHASH_PREFIX@_hash_next(@LISTHASH_PREFIX@_hash_t *,
+        @LISTHASH_PREFIX@_hashptr_t *);
+
+/* return 1 if the data matches a list entry, 0 otherwise */
+int @LISTHASH_PREFIX@_hash_search(@LISTHASH_PREFIX@_hash_t *,
+          @LISTHASH_PREFIX@_hashptr_t *, void *,
+          @LISTHASH_PREFIX@_matchfunc_t);
+
+/* return 1 if the key matches a list entry, 0 otherwise */
+int @LISTHASH_PREFIX@_hash_getkey(@LISTHASH_PREFIX@_hash_t *,
+          @LISTHASH_PREFIX@_hashptr_t *, void *,
+          @LISTHASH_PREFIX@_matchfunc_t);
+
+/* inserting data */
+int @LISTHASH_PREFIX@_hash_add(@LISTHASH_PREFIX@_hash_t *, void *);
+
+/* delete an entry */
+int @LISTHASH_PREFIX@_hash_del(@LISTHASH_PREFIX@_hash_t *,
+             @LISTHASH_PREFIX@_hashptr_t *);
+
+#endif /* ! @LISTHASH_PREFIX@_LISTHASH_H */
+