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

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