chiark - git - mdw - disorder/blob - lib/hash.c

   1 /*
   2  * This file is part of DisOrder
   3  * Copyright (C) 2005-2008 Richard Kettlewell
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, either version 3 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17  */
  18 /** @file lib/hash.c
  19  * @brief A simple hash table
  20  */
  21 #include "common.h"
  22
  23 #include "hash.h"
  24 #include "mem.h"
  25 #include "log.h"
  26 #include "kvp.h"
  27
  28 struct entry {
  29   struct entry *next;                   /* next entry same key */
  30   size_t h;                             /* hash of KEY */
  31   const char *key;                      /* key of this entry */
  32   void *value;                          /* value of this entry */
  33 };
  34
  35 struct hash {
  36   size_t nslots;                        /* number of slots */
  37   size_t nitems;                        /* total number of entries */
  38   struct entry **slots;                 /* table of slots */
  39   size_t valuesize;                     /* size of a value */
  40 };
  41
  42 /** @brief Hash function
  43  * @param key Key to hash
  44  * @return Hash code
  45  */
  46 static size_t hashfn(const char *key) {
  47   size_t i = 0;
  48
  49   while(*key)
  50     i = 33 * i + (unsigned char)*key++;
  51   return i;
  52 }
  53
  54 /** @brief Expand a hash table
  55  * @param h Hash table to expand
  56  */
  57 static void grow(hash *h) {
  58   size_t n, newnslots;
  59   struct entry **newslots, *e, *f;
  60
  61   /* Allocate a new, larger array */
  62   newnslots = 2 * h->nslots;
  63   newslots = xcalloc(newnslots, sizeof (struct entry *));
  64   /* Copy everything to it */
  65   for(n = 0; n < h->nslots; ++n) {
  66     for(e = h->slots[n]; e; e = f) {
  67       f = e->next;
  68       e->next = newslots[e->h & (newnslots - 1)];
  69       newslots[e->h & (newnslots - 1)] = e;
  70     }
  71   }
  72   h->slots = newslots;
  73   h->nslots = newnslots;
  74 }
  75
  76 /** @brief Create a new hash table
  77  * @param valuesize Size of value type
  78  * @return Hash table
  79  */
  80 hash *hash_new(size_t valuesize) {
  81   hash *h = xmalloc(sizeof *h);
  82
  83   h->nslots = 256;
  84   h->slots = xcalloc(h->nslots, sizeof (struct slot *));
  85   h->valuesize = valuesize;
  86   return h;
  87 }
  88
  89 /** @brief Add an element to a hash table
  90  * @param h Hash table
  91  * @param key Key
  92  * @param value New value (will be shallow-copied)
  93  * @param mode Add mode
  94  * @return 0 on success, -1 if the value could not be added
  95  *
  96  * Possible add modes are:
  97  * - @ref HASH_INSERT - key must not exist yet
  98  * - @ref HASH_REPLACE - key must already exist
  99  * - @ref HASH_INSERT_OR_REPLACE - key may or may not exist
 100  */
 101 int hash_add(hash *h, const char *key, const void *value, int mode) {
 102   size_t n = hashfn(key);
 103   struct entry *e;
 104
 105   for(e = h->slots[n & (h->nslots - 1)]; e; e = e->next)
 106     if(e->h == n || !strcmp(e->key, key))
 107       break;
 108   if(e) {
 109     /* This key is already present. */
 110     if(mode == HASH_INSERT) return -1;
 111     if(value) memcpy(e->value, value, h->valuesize);
 112     return 0;
 113   } else {
 114     /* This key is absent. */
 115     if(mode == HASH_REPLACE) return -1;
 116     if(h->nitems >= h->nslots)          /* bound mean chain length */
 117       grow(h);
 118     e = xmalloc(sizeof *e);
 119     e->next = h->slots[n & (h->nslots - 1)];
 120     e->h = n;
 121     e->key = xstrdup(key);
 122     e->value = xmalloc(h->valuesize);
 123     if(value) memcpy(e->value, value, h->valuesize);
 124     h->slots[n & (h->nslots - 1)] = e;
 125     ++h->nitems;
 126     return 0;
 127   }
 128 }
 129
 130 /** @brief Remove an element from a hash table
 131  * @param h Hash table
 132  * @param key Key to remove
 133  * @return 0 on success, -1 if the key wasn't found
 134  */
 135 int hash_remove(hash *h, const char *key) {
 136   size_t n = hashfn(key);
 137   struct entry *e, **ee;
 138
 139   for(ee = &h->slots[n & (h->nslots - 1)]; (e = *ee); ee = &e->next)
 140     if(e->h == n || !strcmp(e->key, key))
 141       break;
 142   if(e) {
 143     *ee = e->next;
 144     --h->nitems;
 145     return 0;
 146   } else
 147     return -1;
 148 }
 149
 150 /** @brief Find an item in a hash table
 151  * @param h Hash table
 152  * @param key Key to find
 153  * @return Pointer to value or NULL if not found
 154  *
 155  * The return value points inside the hash table and should not be modified.
 156  */
 157 void *hash_find(hash *h, const char *key) {
 158   size_t n = hashfn(key);
 159   struct entry *e;
 160
 161   for(e = h->slots[n & (h->nslots - 1)]; e; e = e->next)
 162     if(e->h == n || !strcmp(e->key, key))
 163       return e->value;
 164   return 0;
 165 }
 166
 167 /** @brief Visit every item in a hash table
 168  * @param h Hash Table
 169  * @param callback Function to call for each item
 170  * @param u Passed to @p callback
 171  * @return 0 on completion, else last return from @p callback
 172  *
 173  * @p callback should return 0 to continue or non-0 to stop.  The @p key and @p
 174  * value pointers passed to it point into the hash table and should not be
 175  * modified.
 176  *
 177  * It's safe to remove items from inside the callback including the visited
 178  * one.  It is not safe to add items from inside the callback.
 179  *
 180  * No particular ordering is used.
 181  */
 182 int hash_foreach(hash *h,
 183                  int (*callback)(const char *key, void *value, void *u),
 184                  void *u) {
 185   size_t n;
 186   int ret;
 187   struct entry *e, *f;
 188
 189   for(n = 0; n < h->nslots; ++n)
 190     for(e = h->slots[n]; e; e = f) {
 191       f = e->next;
 192       if((ret = callback(e->key, e->value, u)))
 193         return ret;
 194     }
 195   return 0;
 196 }
 197
 198 /** @brief Count the size of a hash table
 199  * @param h Hash table
 200  * @return Number of elements in hash table
 201  */
 202 size_t hash_count(hash *h) {
 203   return h->nitems;
 204 }
 205
 206 /** @brief Get all the keys of a hash table
 207  * @param h Hash table
 208  * @return NULL-terminated list of keys
 209  *
 210  * The keys point into the hash table itself and should not be modified.
 211  *
 212  * No particular ordering is used.
 213  */
 214 char **hash_keys(hash *h) {
 215   size_t n;
 216   char **vec = xcalloc(h->nitems + 1, sizeof (char *)), **vp = vec;
 217   struct entry *e;
 218
 219   for(n = 0; n < h->nslots; ++n)
 220     for(e = h->slots[n]; e; e = e->next)
 221       *vp++ = (char *)e->key;
 222   *vp = 0;
 223   return vec;
 224 }
 225
 226 /*
 227 Local Variables:
 228 c-basic-offset:2
 229 comment-column:40
 230 fill-column:79
 231 indent-tabs-mode:nil
 232 End:
 233 */