path: root/Utilities/cmtar/listhash/hash.c.in

/* @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;
}