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

   1 /* -*-c-*-
   2  *
   3  * $Id: hash.h,v 1.1 1999/08/02 14:45:48 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.1  1999/08/02 14:45:48  mdw
  34  * Break low-level hashtable code out from sym.
  35  *
  36  */
  37
  38 #ifndef HASH_H
  39 #define HASH_H
  40
  41 #ifdef __cplusplus
  42   extern "C" {
  43 #endif
  44
  45 /*----- Notes -------------------------------------------------------------*
  46  *
  47  * This isn't a complete implementation of anything.  It's a collection of
  48  * useful types and functions which will help when building hashtables of
  49  * things.  The general-purpose hashtable is provided by the @sym@ functions.
  50  */
  51
  52 /*----- Header files ------------------------------------------------------*/
  53
  54 #include <stddef.h>
  55
  56 #ifndef BITS_H
  57 #  include "bits.h"
  58 #endif
  59
  60 /*----- Data structures ---------------------------------------------------*/
  61
  62 /* --- Hashtable basics --- *
  63  *
  64  * This contains the bare minimum to actually get anything useful done.  In
  65  * particular it doesn't maintain any weighting information: when to extend
  66  * the table is left up to the particular implementation.
  67  */
  68
  69 typedef struct hash_table {
  70   uint32 mask;                          /* Bit mask of hash bits */
  71   struct hash_base **v;                 /* Vector of hash bins */
  72 } hash_table;
  73
  74 /* --- A hashtable entry --- *
  75  *
  76  * This is the bare minimum of what needs to be remembered in each hashtable
  77  * entry.  Comparison of elements is left to the implementation, so I don't
  78  * need to know anything about how to represent hash keys here.
  79  */
  80
  81 typedef struct hash_base {
  82   struct hash_base *next;               /* Next entry in hash bin */
  83   uint32 hash;                          /* Hash value for this entry */
  84 } hash_base;
  85
  86 /* --- A hashtable iterator --- */
  87
  88 typedef struct hash_iter {
  89   hash_table *t;                        /* Hashtable being iterated */
  90   hash_base *p;                         /* Address of next item to return */
  91   size_t i;                             /* Index of next hash bin to use */
  92 } hash_iter;
  93
  94 /*----- Functions provided ------------------------------------------------*/
  95
  96 /* --- @hash_create@ --- *
  97  *
  98  * Arguments:   @hash_table *t@ = pointer to hashtable to initialize
  99  *              @size_t n@ = number of bins to allocate (zero initially)
 100  *
 101  * Returns:     ---
 102  *
 103  * Use:         Initializes a hashtable with a given number of bins.  The
 104  *              bins are initially empty.  The number of bins must be a power
 105  *              of two.  This is not checked.
 106  */
 107
 108 extern void hash_create(hash_table */*t*/, size_t /*n*/);
 109
 110 /* --- @hash_destroy@ --- *
 111  *
 112  * Arguments:   @hash_table *t@ = pointer to hashtable to destroy
 113  *
 114  * Returns:     ---
 115  *
 116  * Use:         Frees a hashtable.  The items are not freed: they are the
 117  *              responsibility of the implementation.
 118  */
 119
 120 extern void hash_destroy(hash_table */*t*/);
 121
 122 /* --- @hash_bin@ --- *
 123  *
 124  * Arguments:   @hash_table *t@ = pointer to hashtable
 125  *              @uint32 hash@ = hash value to look up
 126  *
 127  * Returns:     Pointer to the bin's list head.
 128  *
 129  * Use:         Given a hash value return the address of the appropriate list
 130  *              head.  It is safe to remove the current entry from the table.
 131  */
 132
 133 #define HASH_BIN(t, hash) ((t)->v + ((hash) & (t)->mask))
 134
 135 extern hash_base **hash_bin(hash_table */*t*/, uint32 /*hash*/);
 136
 137 /* --- @hash_extend@ --- *
 138  *
 139  * Arguments:   @hash_table *t@ = pointer to hashtable to extend
 140  *
 141  * Returns:     Nonzero if extension was successful.
 142  *
 143  * Use:         Extends a hashtable.  The number of bins is doubled and the
 144  *              entries are redistributed.
 145  */
 146
 147 extern int hash_extend(hash_table */*t*/);
 148
 149 /* --- @hash_remove@ --- *
 150  *
 151  * Arguments:   @hash_table *t@ = pointer to hashtable
 152  *              @hash_base *p@ = pointer to item to remove
 153  *
 154  * Returns:     ---
 155  *
 156  * Use:         Removes an item from a hashtable.  The item itself is not
 157  *              freed, although it is removed from the data structure and is
 158  *              safe to free.
 159  */
 160
 161 extern void hash_remove(hash_table */*t*/, hash_base */*p*/);
 162
 163 /* --- @hash_mkiter@ --- *
 164  *
 165  * Arguments:   @hash_iter *i@ = pointer to iterator to create
 166  *              @hash_table *t@ = pointer to hashtable to iterate
 167  *
 168  * Returns:     ---
 169  *
 170  * Use:         Initializes a hashtable iterator.
 171  */
 172
 173 #define HASH_MKITER(i_, t_) ((i_)->t = (t_), (i_)->p = 0, (i_)->i = 0)
 174
 175 extern void hash_mkiter(hash_iter */*i*/, hash_table */*t*/);
 176
 177 /* --- @hash_next@ --- *
 178  *
 179  * Arguments:   @hash_iter *i@ = pointer to iterator
 180  *
 181  * Returns:     Pointer to the next hashtable entry found, or null.
 182  *
 183  * Use:         Returns the next entry from the hashtable.
 184  */
 185
 186 #define HASH_NEXT(i_, b_) do {                                          \
 187   hash_iter *_i = (i_);                                                 \
 188   hash_base *_p;                                                        \
 189   hash_table *_t = _i->t;                                               \
 190   uint32 _m = _t->mask;                                                 \
 191                                                                         \
 192   for (;;) {                                                            \
 193     if (_i->p) {                                                        \
 194       _p = _i->p;                                                       \
 195       _i->p = _p->next;                                                 \
 196       break;                                                            \
 197     } else if (_i->i > _m) {                                            \
 198       _p = 0;                                                           \
 199       break;                                                            \
 200     } else                                                              \
 201       _i->p = _t->v[_i->i++];                                           \
 202   }                                                                     \
 203   (b_) = _p;                                                            \
 204 } while (0)
 205
 206 extern hash_base *hash_next(hash_iter */*i*/);
 207
 208 /*----- That's all, folks -------------------------------------------------*/
 209
 210 #ifdef __cplusplus
 211   }
 212 #endif
 213
 214 #endif