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

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