/* -*-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
#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