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