[mLib] / hash.h

/* -*-c-*-
 *
 * $Id: hash.h,v 1.2 1999/12/10 23:42:04 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.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_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 */
} 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