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 /** @brief One entry in a hash table */
  29 struct entry {
  30   struct entry *next;                   /* next entry same key */
  31   size_t h;                             /* hash of KEY */
  32   const char *key;                      /* key of this entry */
  33   void *value;                          /* value of this entry */
  34 };
  35
  36 /** @brief A hash table */
  37 struct hash {
  38   size_t nslots;                        /* number of slots */
  39   size_t nitems;                        /* total number of entries */
  40   struct entry **slots;                 /* table of slots */
  41   size_t valuesize;                     /* size of a value */
  42 };
  43
  44 /** @brief Hash function
  45  * @param key Key to hash
  46  * @return Hash code
  47  */
  48 static size_t hashfn(const char *key) {
  49   size_t i = 0;
  50
  51   while(*key)
  52     i = 33 * i + (unsigned char)*key++;
  53   return i;
  54 }
  55
  56 /** @brief Expand a hash table
  57  * @param h Hash table to expand
  58  */
  59 static void grow(hash *h) {
  60   size_t n, newnslots;
  61   struct entry **newslots, *e, *f;
  62
  63   /* Allocate a new, larger array */
  64   newnslots = 2 * h->nslots;
  65   newslots = xcalloc(newnslots, sizeof (struct entry *));
  66   /* Copy everything to it */
  67   for(n = 0; n < h->nslots; ++n) {
  68     for(e = h->slots[n]; e; e = f) {
  69       f = e->next;
  70       e->next = newslots[e->h & (newnslots - 1)];
  71       newslots[e->h & (newnslots - 1)] = e;
  72     }
  73   }
  74   h->slots = newslots;
  75   h->nslots = newnslots;
  76 }
  77
  78 /** @brief Create a new hash table
  79  * @param valuesize Size of value type
  80  * @return Hash table
  81  */
  82 hash *hash_new(size_t valuesize) {
  83   hash *h = xmalloc(sizeof *h);
  84
  85   h->nslots = 256;
  86   h->slots = xcalloc(h->nslots, sizeof (struct slot *));
  87   h->valuesize = valuesize;
  88   return h;
  89 }
  90
  91 /** @brief Add an element to a hash table
  92  * @param h Hash table
  93  * @param key Key
  94  * @param value New value (will be shallow-copied)
  95  * @param mode Add mode
  96  * @return 0 on success, -1 if the value could not be added
  97  *
  98  * Possible add modes are:
  99  * - @ref HASH_INSERT - key must not exist yet
 100  * - @ref HASH_REPLACE - key must already exist
 101  * - @ref HASH_INSERT_OR_REPLACE - key may or may not exist
 102  */
 103 int hash_add(hash *h, const char *key, const void *value, int mode) {
 104   size_t n = hashfn(key);
 105   struct entry *e;
 106
 107   for(e = h->slots[n & (h->nslots - 1)]; e; e = e->next)
 108     if(e->h == n || !strcmp(e->key, key))
 109       break;
 110   if(e) {
 111     /* This key is already present. */
 112     if(mode == HASH_INSERT) return -1;
 113     if(value) memcpy(e->value, value, h->valuesize);
 114     return 0;
 115   } else {
 116     /* This key is absent. */
 117     if(mode == HASH_REPLACE) return -1;
 118     if(h->nitems >= h->nslots)          /* bound mean chain length */
 119       grow(h);
 120     e = xmalloc(sizeof *e);
 121     e->next = h->slots[n & (h->nslots - 1)];
 122     e->h = n;
 123     e->key = xstrdup(key);
 124     e->value = xmalloc(h->valuesize);
 125     if(value) memcpy(e->value, value, h->valuesize);
 126     h->slots[n & (h->nslots - 1)] = e;
 127     ++h->nitems;
 128     return 0;
 129   }
 130 }
 131
 132 /** @brief Remove an element from a hash table
 133  * @param h Hash table
 134  * @param key Key to remove
 135  * @return 0 on success, -1 if the key wasn't found
 136  */
 137 int hash_remove(hash *h, const char *key) {
 138   size_t n = hashfn(key);
 139   struct entry *e, **ee;
 140
 141   for(ee = &h->slots[n & (h->nslots - 1)]; (e = *ee); ee = &e->next)
 142     if(e->h == n || !strcmp(e->key, key))
 143       break;
 144   if(e) {
 145     *ee = e->next;
 146     --h->nitems;
 147     return 0;
 148   } else
 149     return -1;
 150 }
 151
 152 /** @brief Find an item in a hash table
 153  * @param h Hash table
 154  * @param key Key to find
 155  * @return Pointer to value or NULL if not found
 156  *
 157  * The return value points inside the hash table and should not be modified.
 158  */
 159 void *hash_find(hash *h, const char *key) {
 160   size_t n = hashfn(key);
 161   struct entry *e;
 162
 163   for(e = h->slots[n & (h->nslots - 1)]; e; e = e->next)
 164     if(e->h == n || !strcmp(e->key, key))
 165       return e->value;
 166   return 0;
 167 }
 168
 169 /** @brief Visit every item in a hash table
 170  * @param h Hash Table
 171  * @param callback Function to call for each item
 172  * @param u Passed to @p callback
 173  * @return 0 on completion, else last return from @p callback
 174  *
 175  * @p callback should return 0 to continue or non-0 to stop.  The @p key and @p
 176  * value pointers passed to it point into the hash table and should not be
 177  * modified.
 178  *
 179  * It's safe to remove items from inside the callback including the visited
 180  * one.  It is not safe to add items from inside the callback.
 181  *
 182  * No particular ordering is used.
 183  */
 184 int hash_foreach(hash *h,
 185                  int (*callback)(const char *key, void *value, void *u),
 186                  void *u) {
 187   size_t n;
 188   int ret;
 189   struct entry *e, *f;
 190
 191   for(n = 0; n < h->nslots; ++n)
 192     for(e = h->slots[n]; e; e = f) {
 193       f = e->next;
 194       if((ret = callback(e->key, e->value, u)))
 195         return ret;
 196     }
 197   return 0;
 198 }
 199
 200 /** @brief Count the size of a hash table
 201  * @param h Hash table
 202  * @return Number of elements in hash table
 203  */
 204 size_t hash_count(hash *h) {
 205   return h->nitems;
 206 }
 207
 208 /** @brief Get all the keys of a hash table
 209  * @param h Hash table
 210  * @return NULL-terminated list of keys
 211  *
 212  * The keys point into the hash table itself and should not be modified.
 213  *
 214  * No particular ordering is used.
 215  */
 216 char **hash_keys(hash *h) {
 217   size_t n;
 218   char **vec = xcalloc(h->nitems + 1, sizeof (char *)), **vp = vec;
 219   struct entry *e;
 220
 221   for(n = 0; n < h->nslots; ++n)
 222     for(e = h->slots[n]; e; e = e->next)
 223       *vp++ = (char *)e->key;
 224   *vp = 0;
 225   return vec;
 226 }
 227
 228 /*
 229 Local Variables:
 230 c-basic-offset:2
 231 comment-column:40
 232 fill-column:79
 233 indent-tabs-mode:nil
 234 End:
 235 */