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

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