chiark - git - mdw - mLib/blob - hash.h

   1 /* -*-c-*-
   2  *
   3  * $Id: hash.h,v 1.3 2000/06/17 10:37:39 mdw Exp $
   4  *
   5  * General hashtable infrastructure
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of the mLib utilities library.
  13  *
  14  * mLib is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * mLib is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with mLib; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: hash.h,v $
  33  * Revision 1.3  2000/06/17 10:37:39  mdw
  34  * Add support for arena management.
  35  *
  36  * Revision 1.2  1999/12/10 23:42:04  mdw
  37  * Change header file guard names.
  38  *
  39  * Revision 1.1  1999/08/02 14:45:48  mdw
  40  * Break low-level hashtable code out from sym.
  41  *
  42  */
  43
  44 #ifndef MLIB_HASH_H
  45 #define MLIB_HASH_H
  46
  47 #ifdef __cplusplus
  48   extern "C" {
  49 #endif
  50
  51 /*----- Notes -------------------------------------------------------------*
  52  *
  53  * This isn't a complete implementation of anything.  It's a collection of
  54  * useful types and functions which will help when building hashtables of
  55  * things.  The general-purpose hashtable is provided by the @sym@ functions.
  56  */
  57
  58 /*----- Header files ------------------------------------------------------*/
  59
  60 #include <stddef.h>
  61
  62 #ifndef MLIB_ARENA_H
  63 #  include "arena.h"
  64 #endif
  65
  66 #ifndef MLIB_BITS_H
  67 #  include "bits.h"
  68 #endif
  69
  70 /*----- Data structures ---------------------------------------------------*/
  71
  72 /* --- Hashtable basics --- *
  73  *
  74  * This contains the bare minimum to actually get anything useful done.  In
  75  * particular it doesn't maintain any weighting information: when to extend
  76  * the table is left up to the particular implementation.
  77  */
  78
  79 typedef struct hash_table {
  80   uint32 mask;                          /* Bit mask of hash bits */
  81   struct hash_base **v;                 /* Vector of hash bins */
  82   arena *a;                             /* Allocation arena */
  83 } hash_table;
  84
  85 /* --- A hashtable entry --- *
  86  *
  87  * This is the bare minimum of what needs to be remembered in each hashtable
  88  * entry.  Comparison of elements is left to the implementation, so I don't
  89  * need to know anything about how to represent hash keys here.
  90  */
  91
  92 typedef struct hash_base {
  93   struct hash_base *next;               /* Next entry in hash bin */
  94   uint32 hash;                          /* Hash value for this entry */
  95 } hash_base;
  96
  97 /* --- A hashtable iterator --- */
  98
  99 typedef struct hash_iter {
 100   hash_table *t;                        /* Hashtable being iterated */
 101   hash_base *p;                         /* Address of next item to return */
 102   size_t i;                             /* Index of next hash bin to use */
 103 } hash_iter;
 104
 105 /*----- Functions provided ------------------------------------------------*/
 106
 107 /* --- @hash_create@ --- *
 108  *
 109  * Arguments:   @hash_table *t@ = pointer to hashtable to initialize
 110  *              @size_t n@ = number of bins to allocate (zero initially)
 111  *
 112  * Returns:     ---
 113  *
 114  * Use:         Initializes a hashtable with a given number of bins.  The
 115  *              bins are initially empty.  The number of bins must be a power
 116  *              of two.  This is not checked.
 117  */
 118
 119 extern void hash_create(hash_table */*t*/, size_t /*n*/);
 120
 121 /* --- @hash_destroy@ --- *
 122  *
 123  * Arguments:   @hash_table *t@ = pointer to hashtable to destroy
 124  *
 125  * Returns:     ---
 126  *
 127  * Use:         Frees a hashtable.  The items are not freed: they are the
 128  *              responsibility of the implementation.
 129  */
 130
 131 extern void hash_destroy(hash_table */*t*/);
 132
 133 /* --- @hash_bin@ --- *
 134  *
 135  * Arguments:   @hash_table *t@ = pointer to hashtable
 136  *              @uint32 hash@ = hash value to look up
 137  *
 138  * Returns:     Pointer to the bin's list head.
 139  *
 140  * Use:         Given a hash value return the address of the appropriate list
 141  *              head.  It is safe to remove the current entry from the table.
 142  */
 143
 144 #define HASH_BIN(t, hash) ((t)->v + ((hash) & (t)->mask))
 145
 146 extern hash_base **hash_bin(hash_table */*t*/, uint32 /*hash*/);
 147
 148 /* --- @hash_extend@ --- *
 149  *
 150  * Arguments:   @hash_table *t@ = pointer to hashtable to extend
 151  *
 152  * Returns:     Nonzero if extension was successful.
 153  *
 154  * Use:         Extends a hashtable.  The number of bins is doubled and the
 155  *              entries are redistributed.
 156  */
 157
 158 extern int hash_extend(hash_table */*t*/);
 159
 160 /* --- @hash_remove@ --- *
 161  *
 162  * Arguments:   @hash_table *t@ = pointer to hashtable
 163  *              @hash_base *p@ = pointer to item to remove
 164  *
 165  * Returns:     ---
 166  *
 167  * Use:         Removes an item from a hashtable.  The item itself is not
 168  *              freed, although it is removed from the data structure and is
 169  *              safe to free.
 170  */
 171
 172 extern void hash_remove(hash_table */*t*/, hash_base */*p*/);
 173
 174 /* --- @hash_mkiter@ --- *
 175  *
 176  * Arguments:   @hash_iter *i@ = pointer to iterator to create
 177  *              @hash_table *t@ = pointer to hashtable to iterate
 178  *
 179  * Returns:     ---
 180  *
 181  * Use:         Initializes a hashtable iterator.
 182  */
 183
 184 #define HASH_MKITER(i_, t_) ((i_)->t = (t_), (i_)->p = 0, (i_)->i = 0)
 185
 186 extern void hash_mkiter(hash_iter */*i*/, hash_table */*t*/);
 187
 188 /* --- @hash_next@ --- *
 189  *
 190  * Arguments:   @hash_iter *i@ = pointer to iterator
 191  *
 192  * Returns:     Pointer to the next hashtable entry found, or null.
 193  *
 194  * Use:         Returns the next entry from the hashtable.
 195  */
 196
 197 #define HASH_NEXT(i_, b_) do {                                          \
 198   hash_iter *_i = (i_);                                                 \
 199   hash_base *_p;                                                        \
 200   hash_table *_t = _i->t;                                               \
 201   uint32 _m = _t->mask;                                                 \
 202                                                                         \
 203   for (;;) {                                                            \
 204     if (_i->p) {                                                        \
 205       _p = _i->p;                                                       \
 206       _i->p = _p->next;                                                 \
 207       break;                                                            \
 208     } else if (_i->i > _m) {                                            \
 209       _p = 0;                                                           \
 210       break;                                                            \
 211     } else                                                              \
 212       _i->p = _t->v[_i->i++];                                           \
 213   }                                                                     \
 214   (b_) = _p;                                                            \
 215 } while (0)
 216
 217 extern hash_base *hash_next(hash_iter */*i*/);
 218
 219 /*----- That's all, folks -------------------------------------------------*/
 220
 221 #ifdef __cplusplus
 222   }
 223 #endif
 224
 225 #endif