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