src/hash.c

   1 /*
   2  * Copyright 1993, 1995 Christopher Seiwald.
   3  * This file is part of Jam - see jam.c for Copyright information.
   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, version 3 of the License ONLY.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16  */
  17 /*
  18  * hash.c - simple in-memory hashing routines
  19  *
  20  * External routines:
  21  *
  22  *     hashinit() - initialize a hash table, returning a handle
  23  *     hashitem() - find a record in the table, and optionally enter a new one
  24  *     hashdone() - free a hash table, given its handle
  25  *
  26  * Internal routines:
  27  *
  28  *     hashrehash() - resize and rebuild hp->tab, the hash table
  29  */
  30 #include <stdint.h>
  31
  32 #include "jam.h"
  33 #include "hash.h"
  34
  35
  36 static uint32_t hash_joaat (const void *key, size_t nbytes) {
  37   uint32_t hash = 0;
  38   const uint8_t *k = (const uint8_t *)key;
  39   while (nbytes-- > 0) {
  40     hash += *k++;
  41     hash += (hash<<10);
  42     hash ^= (hash>>6);
  43   }
  44   hash += (hash<<3);
  45   hash ^= (hash>>11);
  46   hash += (hash<<15);
  47   return hash;
  48 }
  49
  50
  51 /* header attached to all data items entered into a hash table. */
  52 struct hashhdr {
  53   struct item *next;
  54   uint32_t keyval; /* for quick comparisons */
  55 };
  56
  57
  58 /* this structure overlays the one handed to hashenter() */
  59 /* it's actual size is given to hashinit() */
  60 struct hashdata {
  61   const char *key;
  62   /* rest of user data */
  63 };
  64
  65
  66 typedef struct item {
  67   struct hashhdr hdr;
  68   struct hashdata data;
  69 } ITEM;
  70
  71
  72 #define MAX_LISTS  (32)
  73 struct hash {
  74   /* the hash table, just an array of item pointers */
  75   struct {
  76     int nel;
  77     ITEM **base;
  78   } tab;
  79   int bloat; /* tab.nel / items.nel */
  80   int inel; /* initial number of elements */
  81   /* the array of records, maintained by these routines essentially a microallocator */
  82   struct {
  83     int more; /* how many more ITEMs fit in lists[ list ] */
  84     char *next; /* where to put more ITEMs in lists[ list ] */
  85     int datalen; /* length of records in this hash table */
  86     int size; /* sizeof(ITEM) + aligned datalen */
  87     int nel; /* total ITEMs held by all lists[] */
  88     int list; /* index into lists[] */
  89     struct {
  90       int nel; /* total ITEMs held by this list */
  91       char *base; /* base of ITEMs array */
  92     } lists[MAX_LISTS];
  93   } items;
  94   char *name; /* just for hashstats() */
  95 };
  96
  97
  98 #define ALIGNED(x)  ((x+sizeof(ITEM)-1)&(~(sizeof(ITEM)-1)))
  99
 100
 101 static void hashstat (struct hash *hp) {
 102   ITEM **tab = hp->tab.base;
 103   int nel = hp->tab.nel, count = 0, sets = 0;
 104   int run = (tab[nel-1] != NULL);
 105   int i, here;
 106   for (i = nel; i > 0; --i) {
 107     if ((here = (*tab++ != NULL))) ++count;
 108     if (here && !run) ++sets;
 109     run = here;
 110   }
 111   printf("%s table: %d+%d+%d (%dK+%dK) items+table+hash, %f density\n",
 112     hp->name,
 113     count,
 114     hp->items.nel,
 115     hp->tab.nel,
 116     hp->items.nel*hp->items.size/1024,
 117     (int)(hp->tab.nel*sizeof(ITEM **)/1024),
 118     (float)count/(float)sets
 119   );
 120 }
 121
 122
 123 /*
 124  * hashrehash() - resize and rebuild hp->tab, the hash table
 125  */
 126 static void hashrehash (struct hash *hp) {
 127   int i = ++hp->items.list;
 128   hp->items.more = (i ? 2*hp->items.nel : hp->inel);
 129   hp->items.next = malloc(hp->items.more*hp->items.size);
 130   hp->items.lists[i].nel = hp->items.more;
 131   hp->items.lists[i].base = hp->items.next;
 132   hp->items.nel += hp->items.more;
 133   if (hp->tab.base) free(hp->tab.base);
 134   hp->tab.nel = hp->items.nel*hp->bloat;
 135   hp->tab.base = malloc(hp->tab.nel*sizeof(ITEM **));
 136   memset(hp->tab.base, '\0', hp->tab.nel*sizeof(ITEM *));
 137   for (i = 0; i < hp->items.list; ++i) {
 138     int nel = hp->items.lists[i].nel;
 139     char *next = hp->items.lists[i].base;
 140     for (; nel--; next += hp->items.size) {
 141       ITEM *xxi = (ITEM *)next;
 142       ITEM **ip = hp->tab.base+xxi->hdr.keyval%hp->tab.nel;
 143       xxi->hdr.next = *ip;
 144       *ip = xxi;
 145     }
 146   }
 147 }
 148
 149
 150 /*
 151  * hashiterate() - iterate thru all hash entries
 152  * return !0 from itercb() to stop
 153  * returns result of itercb() or 0 */
 154 int hashiterate (struct hash *hp, hash_iterator_cb itercb, void *udata) {
 155   ITEM **tab = hp->tab.base;
 156   for (int i = hp->tab.nel; i > 0; --i, ++tab) {
 157     if (*tab != NULL) {
 158       int res = itercb(&((*tab)->data), udata);
 159       if (res) return res;
 160     }
 161   }
 162   return 0;
 163 }
 164
 165
 166 /*
 167  * hashitem() - find a record in the table, and optionally enter a new one
 168  */
 169 int hashitem (struct hash *hp, HASHDATA **data, int enter) {
 170   ITEM **base, *i;
 171   uint32_t keyval;
 172   if (enter && !hp->items.more) hashrehash(hp);
 173   if (!enter && !hp->items.nel) return 0;
 174   keyval = hash_joaat((*data)->key, strlen((*data)->key));
 175   base = hp->tab.base+(keyval%hp->tab.nel);
 176   for (i = *base; i != NULL; i = i->hdr.next) {
 177     if (keyval == i->hdr.keyval && strcmp(i->data.key, (*data)->key) == 0) {
 178       *data = &i->data;
 179       return !0;
 180     }
 181   }
 182   if (enter) {
 183     i = (ITEM *)hp->items.next;
 184     hp->items.next += hp->items.size;
 185     --hp->items.more;
 186     memcpy(&i->data, *data, hp->items.datalen);
 187     i->hdr.keyval = keyval;
 188     i->hdr.next = *base;
 189     *base = i;
 190     *data = &i->data;
 191   }
 192   return 0;
 193 }
 194
 195
 196 /*
 197  * hashinit() - initialize a hash table, returning a handle
 198  */
 199 struct hash *hashinit (int datalen, const char *name) {
 200   struct hash *hp = malloc(sizeof(*hp));
 201   hp->bloat = 3;
 202   hp->tab.nel = 0;
 203   hp->tab.base = NULL;
 204   hp->items.more = 0;
 205   hp->items.datalen = datalen;
 206   hp->items.size = sizeof(struct hashhdr)+ALIGNED(datalen);
 207   hp->items.list = -1;
 208   hp->items.nel = 0;
 209   hp->inel = 11;
 210   hp->name = strdup(name != NULL ? name : "");
 211   return hp;
 212 }
 213
 214
 215 /*
 216  * hashdone() - free a hash table, given its handle
 217  */
 218 void hashdone (struct hash *hp) {
 219   if (hp != NULL) {
 220     if (DEBUG_MEM) hashstat(hp);
 221     if (hp->tab.base) free((char *)hp->tab.base);
 222     for (int i = 0; i <= hp->items.list; i++) free(hp->items.lists[i].base);
 223     free(hp->name);
 224     free(hp);
 225   }
 226 }