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

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