Include `crc32.h' for @CRC32@ macro.

[mLib] / hash.c

/* -*-c-*-
 *
 * $Id: hash.c,v 1.3 2000/07/16 12:29:16 mdw Exp $
 *
 * General hashtable infrastructure
 *
 * (c) 1999 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of the mLib utilities library.
 *
 * mLib is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * mLib is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with mLib; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: hash.c,v $
 * Revision 1.3  2000/07/16 12:29:16  mdw
 * Change to arena `realloc' interface, to fix a design bug.
 *
 * Revision 1.2  2000/06/17 10:37:39  mdw
 * Add support for arena management.
 *
 * Revision 1.1  1999/08/02 14:45:48  mdw
 * Break low-level hashtable code out from sym.
 *
 */

/*----- Header files ------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "alloc.h"
#include "arena.h"
#include "bits.h"
#include "exc.h"
#include "hash.h"

/*----- Main code ---------------------------------------------------------*/

/* --- @hash_create@ --- *
 *
 * Arguments:	@hash_table *t@ = pointer to hashtable to initialize
 *		@size_t n@ = number of bins to allocate (zero initially)
 *
 * Returns:	---
 *
 * Use:		Initializes a hashtable with a given number of bins.  The
 *		bins are initially empty.  The number of bins must be a power
 *		of two.  This is not checked.
 */

void hash_create(hash_table *t, size_t n)
{
  hash_base **v;

  t->a = arena_global;
  t->v = x_alloc(t->a, n * sizeof(hash_base *));
  t->mask = n - 1;
  for (v = t->v; n; v++, n--)
    *v = 0;
}

/* --- @hash_destroy@ --- *
 *
 * Arguments:	@hash_table *t@ = pointer to hashtable to destroy
 *
 * Returns:	---
 *
 * Use:		Frees a hashtable.  The items are not freed: they are the
 *		responsibility of the implementation.
 */

void hash_destroy(hash_table *t)
{
  x_free(t->a, t->v);
}

/* --- @hash_bin@ --- *
 *
 * Arguments:	@hash_table *t@ = pointer to hashtable
 *		@uint32 hash@ = hash value to look up
 *
 * Returns:	Pointer to the bin's list head.
 *
 * Use:		Given a hash value return the address of the appropriate list
 *		head.  It is safe to remove the current entry from the table.
 */

hash_base **hash_bin(hash_table *t, uint32 hash)
{
  return (HASH_BIN(t, hash));
}

/* --- @hash_extend@ --- *
 *
 * Arguments:	@hash_table *t@ = pointer to hashtable to extend
 *
 * Returns:	Nonzero if extension was successful.
 *
 * Use:		Extends a hashtable.  The number of bins is doubled and the
 *		entries are redistributed.
 */

int hash_extend(hash_table *t)
{
  hash_base **v;
  uint32 m = t->mask + 1;
  size_t i;

  /* --- Allocate a new hash bin vector --- */

  if ((v = A_REALLOC(t->a, t->v,
		     2 * m * sizeof(hash_base *),
		     m * sizeof(hash_base *))) == 0) {
    return (0);
  }
  t->v = v;
  t->mask = (m * 2) - 1;

  /* --- Wander through the table rehashing things --- */

  for (i = 0; i < m; i++) {
    hash_base **p = v + i;
    hash_base **q = p + m;

    while (*p) {
      if (!((*p)->hash & m))
	p = &(*p)->next;
      else {
	*q = *p;
	q = &(*q)->next;
	*p = (*p)->next;
      }
    }
    *p = 0;
    *q = 0;
  }

  return (1);
}

/* --- @hash_remove@ --- *
 *
 * Arguments:	@hash_table *t@ = pointer to hashtable
 *		@hash_base *p@ = pointer to item to remove
 *
 * Returns:	---
 *
 * Use:		Removes an item from a hashtable.  The item itself is not
 *		freed, although it is removed from the data structure and is
 *		safe to free.
 */

void hash_remove(hash_table *t, hash_base *p)
{
  hash_base **b = HASH_BIN(t, p->hash);
  while (*b) {
    if (*b == p) {
      *b = p->next;
      return;
    }
    b = &(*b)->next;
  }
  return;
}

/* --- @hash_mkiter@ --- *
 *
 * Arguments:	@hash_iter *i@ = pointer to iterator to create
 *		@hash_table *t@ = pointer to hashtable to iterate
 *
 * Returns:	---
 *
 * Use:		Initializes a hashtable iterator.
 */

void hash_mkiter(hash_iter *i, hash_table *t) { HASH_MKITER(i, t); }

/* --- @hash_next@ --- *
 *
 * Arguments:	@hash_iter *i@ = pointer to iterator
 *
 * Returns:	Pointer to the next hashtable entry found, or null.
 *
 * Use:		Returns the next entry from the hashtable.
 */

hash_base *hash_next(hash_iter *i)
{
  hash_base *b;
  HASH_NEXT(i, b);
  return (b);
}

/*----- That's all, folks -------------------------------------------------*/