Document crc-mktab a little.

[mLib] / hash.h

/* -*-c-*-
 *
 * $Id: hash.h,v 1.3 2000/06/17 10:37:39 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.h,v $
 * Revision 1.3  2000/06/17 10:37:39  mdw
 * Add support for arena management.
 *
 * Revision 1.2  1999/12/10 23:42:04  mdw
 * Change header file guard names.
 *
 * Revision 1.1  1999/08/02 14:45:48  mdw
 * Break low-level hashtable code out from sym.
 *
 */

#ifndef MLIB_HASH_H
#define MLIB_HASH_H

#ifdef __cplusplus
  extern "C" {
#endif

/*----- Notes -------------------------------------------------------------*
 *
 * This isn't a complete implementation of anything.  It's a collection of
 * useful types and functions which will help when building hashtables of
 * things.  The general-purpose hashtable is provided by the @sym@ functions.
 */

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

#include <stddef.h>

#ifndef MLIB_ARENA_H
#  include "arena.h"
#endif

#ifndef MLIB_BITS_H
#  include "bits.h"
#endif

/*----- Data structures ---------------------------------------------------*/

/* --- Hashtable basics --- *
 *
 * This contains the bare minimum to actually get anything useful done.  In
 * particular it doesn't maintain any weighting information: when to extend
 * the table is left up to the particular implementation.
 */

typedef struct hash_table {
  uint32 mask;				/* Bit mask of hash bits */
  struct hash_base **v;			/* Vector of hash bins */
  arena *a;				/* Allocation arena */
} hash_table;

/* --- A hashtable entry --- *
 *
 * This is the bare minimum of what needs to be remembered in each hashtable
 * entry.  Comparison of elements is left to the implementation, so I don't
 * need to know anything about how to represent hash keys here.
 */

typedef struct hash_base {
  struct hash_base *next;		/* Next entry in hash bin */
  uint32 hash;				/* Hash value for this entry */
} hash_base;

/* --- A hashtable iterator --- */

typedef struct hash_iter {
  hash_table *t;			/* Hashtable being iterated */
  hash_base *p;				/* Address of next item to return */
  size_t i;				/* Index of next hash bin to use */
} hash_iter;

/*----- Functions provided ------------------------------------------------*/

/* --- @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.
 */

extern void hash_create(hash_table */*t*/, size_t /*n*/);

/* --- @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.
 */

extern void hash_destroy(hash_table */*t*/);

/* --- @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.
 */

#define HASH_BIN(t, hash) ((t)->v + ((hash) & (t)->mask))

extern hash_base **hash_bin(hash_table */*t*/, uint32 /*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.
 */

extern int hash_extend(hash_table */*t*/);

/* --- @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.
 */

extern void hash_remove(hash_table */*t*/, hash_base */*p*/);

/* --- @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.
 */

#define HASH_MKITER(i_, t_) ((i_)->t = (t_), (i_)->p = 0, (i_)->i = 0)

extern void hash_mkiter(hash_iter */*i*/, hash_table */*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.
 */

#define HASH_NEXT(i_, b_) do {						\
  hash_iter *_i = (i_);							\
  hash_base *_p;							\
  hash_table *_t = _i->t;						\
  uint32 _m = _t->mask;							\
									\
  for (;;) {								\
    if (_i->p) {							\
      _p = _i->p;							\
      _i->p = _p->next;							\
      break;								\
    } else if (_i->i > _m) {						\
      _p = 0;								\
      break;								\
    } else								\
      _i->p = _t->v[_i->i++];						\
  }									\
  (b_) = _p;								\
} while (0)

extern hash_base *hash_next(hash_iter */*i*/);

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

#ifdef __cplusplus
  }
#endif

#endif