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