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 static size_t hashfn(const char *key) {
  43   size_t i = 0;
  44
  45   while(*key)
  46     i = 33 * i + (unsigned char)*key++;
  47   return i;
  48 }
  49
  50 static void grow(hash *h) {
  51   size_t n, newnslots;
  52   struct entry **newslots, *e, *f;
  53
  54   /* Allocate a new, larger array */
  55   newnslots = 2 * h->nslots;
  56   newslots = xcalloc(newnslots, sizeof (struct entry *));
  57   /* Copy everything to it */
  58   for(n = 0; n < h->nslots; ++n) {
  59     for(e = h->slots[n]; e; e = f) {
  60       f = e->next;
  61       e->next = newslots[e->h & (newnslots - 1)];
  62       newslots[e->h & (newnslots - 1)] = e;
  63     }
  64   }
  65   h->slots = newslots;
  66   h->nslots = newnslots;
  67 }
  68
  69 hash *hash_new(size_t valuesize) {
  70   hash *h = xmalloc(sizeof *h);
  71
  72   h->nslots = 256;
  73   h->slots = xcalloc(h->nslots, sizeof (struct slot *));
  74   h->valuesize = valuesize;
  75   return h;
  76 }
  77
  78 int hash_add(hash *h, const char *key, const void *value, int mode) {
  79   size_t n = hashfn(key);
  80   struct entry *e;
  81
  82   for(e = h->slots[n & (h->nslots - 1)]; e; e = e->next)
  83     if(e->h == n || !strcmp(e->key, key))
  84       break;
  85   if(e) {
  86     /* This key is already present. */
  87     if(mode == HASH_INSERT) return -1;
  88     if(value) memcpy(e->value, value, h->valuesize);
  89     return 0;
  90   } else {
  91     /* This key is absent. */
  92     if(mode == HASH_REPLACE) return -1;
  93     if(h->nitems >= h->nslots)          /* bound mean chain length */
  94       grow(h);
  95     e = xmalloc(sizeof *e);
  96     e->next = h->slots[n & (h->nslots - 1)];
  97     e->h = n;
  98     e->key = xstrdup(key);
  99     e->value = xmalloc(h->valuesize);
 100     if(value) memcpy(e->value, value, h->valuesize);
 101     h->slots[n & (h->nslots - 1)] = e;
 102     ++h->nitems;
 103     return 0;
 104   }
 105 }
 106
 107 int hash_remove(hash *h, const char *key) {
 108   size_t n = hashfn(key);
 109   struct entry *e, **ee;
 110
 111   for(ee = &h->slots[n & (h->nslots - 1)]; (e = *ee); ee = &e->next)
 112     if(e->h == n || !strcmp(e->key, key))
 113       break;
 114   if(e) {
 115     *ee = e->next;
 116     --h->nitems;
 117     return 0;
 118   } else
 119     return -1;
 120 }
 121
 122 void *hash_find(hash *h, const char *key) {
 123   size_t n = hashfn(key);
 124   struct entry *e;
 125
 126   for(e = h->slots[n & (h->nslots - 1)]; e; e = e->next)
 127     if(e->h == n || !strcmp(e->key, key))
 128       return e->value;
 129   return 0;
 130 }
 131
 132 int hash_foreach(hash *h,
 133                  int (*callback)(const char *key, void *value, void *u),
 134                  void *u) {
 135   size_t n;
 136   int ret;
 137   struct entry *e, *f;
 138
 139   for(n = 0; n < h->nslots; ++n)
 140     for(e = h->slots[n]; e; e = f) {
 141       f = e->next;
 142       if((ret = callback(e->key, e->value, u)))
 143         return ret;
 144     }
 145   return 0;
 146 }
 147
 148 size_t hash_count(hash *h) {
 149   return h->nitems;
 150 }
 151
 152 char **hash_keys(hash *h) {
 153   size_t n;
 154   char **vec = xcalloc(h->nitems + 1, sizeof (char *)), **vp = vec;
 155   struct entry *e;
 156
 157   for(n = 0; n < h->nslots; ++n)
 158     for(e = h->slots[n]; e; e = e->next)
 159       *vp++ = (char *)e->key;
 160   *vp = 0;
 161   return vec;
 162 }
 163
 164 /*
 165 Local Variables:
 166 c-basic-offset:2
 167 comment-column:40
 168 fill-column:79
 169 indent-tabs-mode:nil
 170 End:
 171 */