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

   1 /* -*-c-*-
   2  *
   3  * $Id: hash.c,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.c,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 /*----- Header files ------------------------------------------------------*/
  39
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42 #include <string.h>
  43
  44 #include "alloc.h"
  45 #include "bits.h"
  46 #include "exc.h"
  47 #include "hash.h"
  48 #include "track.h"
  49
  50 /*----- Main code ---------------------------------------------------------*/
  51
  52 /* --- @hash_create@ --- *
  53  *
  54  * Arguments:   @hash_table *t@ = pointer to hashtable to initialize
  55  *              @size_t n@ = number of bins to allocate (zero initially)
  56  *
  57  * Returns:     ---
  58  *
  59  * Use:         Initializes a hashtable with a given number of bins.  The
  60  *              bins are initially empty.  The number of bins must be a power
  61  *              of two.  This is not checked.
  62  */
  63
  64 void hash_create(hash_table *t, size_t n)
  65 {
  66   hash_base **v;
  67   TRACK_CTX("hashtable creation");
  68   TRACK_PUSH;
  69   t->v = xmalloc(n * sizeof(hash_base *));
  70   t->mask = n - 1;
  71   for (v = t->v; n; v++, n--)
  72     *v = 0;
  73   TRACK_POP;
  74 }
  75
  76 /* --- @hash_destroy@ --- *
  77  *
  78  * Arguments:   @hash_table *t@ = pointer to hashtable to destroy
  79  *
  80  * Returns:     ---
  81  *
  82  * Use:         Frees a hashtable.  The items are not freed: they are the
  83  *              responsibility of the implementation.
  84  */
  85
  86 void hash_destroy(hash_table *t)
  87 {
  88   TRACK_CTX("hashtable destruction");
  89   TRACK_PUSH;
  90   free(t->v);
  91   TRACK_POP;
  92 }
  93
  94 /* --- @hash_bin@ --- *
  95  *
  96  * Arguments:   @hash_table *t@ = pointer to hashtable
  97  *              @uint32 hash@ = hash value to look up
  98  *
  99  * Returns:     Pointer to the bin's list head.
 100  *
 101  * Use:         Given a hash value return the address of the appropriate list
 102  *              head.  It is safe to remove the current entry from the table.
 103  */
 104
 105 hash_base **hash_bin(hash_table *t, uint32 hash)
 106 {
 107   return (HASH_BIN(t, hash));
 108 }
 109
 110 /* --- @hash_extend@ --- *
 111  *
 112  * Arguments:   @hash_table *t@ = pointer to hashtable to extend
 113  *
 114  * Returns:     Nonzero if extension was successful.
 115  *
 116  * Use:         Extends a hashtable.  The number of bins is doubled and the
 117  *              entries are redistributed.
 118  */
 119
 120 int hash_extend(hash_table *t)
 121 {
 122   hash_base **v;
 123   uint32 m = t->mask + 1;
 124   size_t i;
 125
 126   /* --- Push in a tracking context --- */
 127
 128   TRACK_CTX("hashtable extension");
 129   TRACK_PUSH;
 130
 131   /* --- Allocate a new hash bin vector --- */
 132
 133   if ((v = realloc(t->v, m * 2 * sizeof(hash_base *))) == 0) {
 134     TRACK_POP;
 135     return (0);
 136   }
 137   t->v = v;
 138   t->mask = (m * 2) - 1;
 139
 140   /* --- Wander through the table rehashing things --- */
 141
 142   for (i = 0; i < m; i++) {
 143     hash_base **p = v + i;
 144     hash_base **q = p + m;
 145
 146     while (*p) {
 147       if (!((*p)->hash & m))
 148         p = &(*p)->next;
 149       else {
 150         *q = *p;
 151         q = &(*q)->next;
 152         *p = (*p)->next;
 153       }
 154     }
 155     *p = 0;
 156     *q = 0;
 157   }
 158
 159   TRACK_POP;
 160   return (1);
 161 }
 162
 163 /* --- @hash_remove@ --- *
 164  *
 165  * Arguments:   @hash_table *t@ = pointer to hashtable
 166  *              @hash_base *p@ = pointer to item to remove
 167  *
 168  * Returns:     ---
 169  *
 170  * Use:         Removes an item from a hashtable.  The item itself is not
 171  *              freed, although it is removed from the data structure and is
 172  *              safe to free.
 173  */
 174
 175 void hash_remove(hash_table *t, hash_base *p)
 176 {
 177   hash_base **b = HASH_BIN(t, p->hash);
 178   while (*b) {
 179     if (*b == p) {
 180       *b = p->next;
 181       return;
 182     }
 183     b = &(*b)->next;
 184   }
 185   return;
 186 }
 187
 188 /* --- @hash_mkiter@ --- *
 189  *
 190  * Arguments:   @hash_iter *i@ = pointer to iterator to create
 191  *              @hash_table *t@ = pointer to hashtable to iterate
 192  *
 193  * Returns:     ---
 194  *
 195  * Use:         Initializes a hashtable iterator.
 196  */
 197
 198 void hash_mkiter(hash_iter *i, hash_table *t) { HASH_MKITER(i, t); }
 199
 200 /* --- @hash_next@ --- *
 201  *
 202  * Arguments:   @hash_iter *i@ = pointer to iterator
 203  *
 204  * Returns:     Pointer to the next hashtable entry found, or null.
 205  *
 206  * Use:         Returns the next entry from the hashtable.
 207  */
 208
 209 hash_base *hash_next(hash_iter *i)
 210 {
 211   hash_base *b;
 212   HASH_NEXT(i, b);
 213   return (b);
 214 }
 215
 216 /*----- That's all, folks -------------------------------------------------*/