src/hash.c

   1 /*
   2  * Copyright 1993, 1995 Christopher Seiwald.
   3  *
   4  * This file is part of Jam - see jam.c for Copyright information.
   5  */
   6
   7 /*
   8  * hash.c - simple in-memory hashing routines
   9  *
  10  * External routines:
  11  *
  12  *     hashinit() - initialize a hash table, returning a handle
  13  *     hashitem() - find a record in the table, and optionally enter a new one
  14  *     hashdone() - free a hash table, given its handle
  15  *
  16  * Internal routines:
  17  *
  18  *     hashrehash() - resize and rebuild hp->tab, the hash table
  19  *
  20  * 4/29/93 - ensure ITEM's are aligned
  21  * 11/04/02 (seiwald) - const-ing for string literals
  22  * 01/31/02 (seiwald) - keyval now unsigned (cray-ziness)
  23  */
  24 #include "jam.h"
  25 #include "hash.h"
  26
  27
  28 /* header attached to all data items entered into a hash table. */
  29 struct hashhdr {
  30   struct item *next;
  31   unsigned int keyval; /* for quick comparisons */
  32 };
  33
  34
  35 /* this structure overlays the one handed to hashenter() */
  36 /* it's actual size is given to hashinit() */
  37 struct hashdata {
  38   char *key;
  39   /* rest of user data */
  40 };
  41
  42
  43 typedef struct item {
  44   struct hashhdr hdr;
  45   struct hashdata data;
  46 } ITEM;
  47
  48
  49 #define MAX_LISTS  (32)
  50 struct hash {
  51   /* the hash table, just an array of item pointers */
  52   struct {
  53     int nel;
  54     ITEM **base;
  55   } tab;
  56   int bloat; /* tab.nel / items.nel */
  57   int inel; /* initial number of elements */
  58   /* the array of records, maintained by these routines essentially a microallocator */
  59   struct {
  60     int more; /* how many more ITEMs fit in lists[ list ] */
  61     char *next; /* where to put more ITEMs in lists[ list ] */
  62     int datalen; /* length of records in this hash table */
  63     int size; /* sizeof(ITEM) + aligned datalen */
  64     int nel; /* total ITEMs held by all lists[] */
  65     int list; /* index into lists[] */
  66     struct {
  67       int nel; /* total ITEMs held by this list */
  68       char *base; /* base of ITEMs array */
  69     } lists[MAX_LISTS];
  70   } items;
  71   const char *name; /* just for hashstats() */
  72 };
  73
  74
  75 static void hashrehash (struct hash *hp);
  76 static void hashstat (struct hash *hp);
  77
  78
  79 /*
  80  * hashitem() - find a record in the table, and optionally enter a new one
  81  */
  82 int hashitem (struct hash *hp, HASHDATA **data, int enter) {
  83   ITEM **base;
  84   ITEM *i;
  85   unsigned char *b = (unsigned char *)(*data)->key;
  86   unsigned int keyval;
  87   //
  88   if (enter && !hp->items.more) hashrehash(hp);
  89   if (!enter && !hp->items.nel) return 0;
  90   keyval = *b;
  91   while (*b) keyval = keyval*2147059363 + *b++;
  92   base = hp->tab.base+(keyval%hp->tab.nel);
  93   for (i = *base; i; i = i->hdr.next) {
  94     if (keyval == i->hdr.keyval && !strcmp(i->data.key, (*data)->key)) {
  95       *data = &i->data;
  96       return !0;
  97     }
  98   }
  99   if (enter) {
 100     i = (ITEM *)hp->items.next;
 101     hp->items.next += hp->items.size;
 102     --hp->items.more;
 103     memcpy((char *)&i->data, (char *)*data, hp->items.datalen);
 104     i->hdr.keyval = keyval;
 105     i->hdr.next = *base;
 106     *base = i;
 107     *data = &i->data;
 108   }
 109   return 0;
 110 }
 111
 112
 113 /*
 114  * hashrehash() - resize and rebuild hp->tab, the hash table
 115  */
 116 static void hashrehash (struct hash *hp) {
 117   int i = ++hp->items.list;
 118   //
 119   hp->items.more = i ? 2 * hp->items.nel : hp->inel;
 120   hp->items.next = (char *)malloc(hp->items.more * hp->items.size);
 121   //
 122   hp->items.lists[i].nel = hp->items.more;
 123   hp->items.lists[i].base = hp->items.next;
 124   hp->items.nel += hp->items.more;
 125   //
 126   if (hp->tab.base) free((char *)hp->tab.base);
 127   //
 128   hp->tab.nel = hp->items.nel * hp->bloat;
 129   hp->tab.base = (ITEM **)malloc(hp->tab.nel * sizeof(ITEM **));
 130   //
 131   memset((char *)hp->tab.base, '\0', hp->tab.nel * sizeof(ITEM *));
 132   //
 133   for (i = 0; i < hp->items.list; ++i) {
 134     int nel = hp->items.lists[i].nel;
 135     char *next = hp->items.lists[i].base;
 136     //
 137     for (; nel--; next += hp->items.size) {
 138       ITEM *i = (ITEM *)next;
 139       ITEM **ip = hp->tab.base+i->hdr.keyval%hp->tab.nel;
 140       i->hdr.next = *ip;
 141       *ip = i;
 142     }
 143   }
 144 }
 145
 146 /* --- */
 147
 148 #define ALIGNED(x)  ((x+sizeof(ITEM)-1)&(~(sizeof(ITEM)-1)))
 149
 150
 151 /*
 152  * hashinit() - initialize a hash table, returning a handle
 153  */
 154 struct hash *hashinit (int datalen, const char *name) {
 155   struct hash *hp = (struct hash *)malloc(sizeof(*hp));
 156   //
 157   hp->bloat = 3;
 158   hp->tab.nel = 0;
 159   hp->tab.base = (ITEM **)0;
 160   hp->items.more = 0;
 161   hp->items.datalen = datalen;
 162   hp->items.size = sizeof(struct hashhdr)+ALIGNED(datalen);
 163   hp->items.list = -1;
 164   hp->items.nel = 0;
 165   hp->inel = 11;
 166   hp->name = name;
 167   return hp;
 168 }
 169
 170
 171 /*
 172  * hashdone() - free a hash table, given its handle
 173  */
 174 void hashdone (struct hash *hp) {
 175   int i;
 176   //
 177   if (!hp) return;
 178   if (DEBUG_MEM) hashstat(hp);
 179   if (hp->tab.base) free((char *)hp->tab.base);
 180   for (i = 0; i <= hp->items.list; i++) free(hp->items.lists[i].base);
 181   free((char *)hp);
 182 }
 183
 184 /* ---- */
 185
 186
 187 static void hashstat (struct hash *hp) {
 188   ITEM **tab = hp->tab.base;
 189   int nel = hp->tab.nel;
 190   int count = 0;
 191   int sets = 0;
 192   int run = (tab[nel-1] != (ITEM *)0);
 193   int i, here;
 194   //
 195   for (i = nel; i > 0; --i) {
 196     if ((here = (*tab++ != (ITEM *)0))) ++count;
 197     if (here && !run) ++sets;
 198     run = here;
 199   }
 200   printf("%s table: %d+%d+%d (%dK+%dK) items+table+hash, %f density\n",
 201     hp->name,
 202     count,
 203     hp->items.nel,
 204     hp->tab.nel,
 205     hp->items.nel*hp->items.size/1024,
 206     (int)(hp->tab.nel*sizeof(ITEM **)/1024),
 207     (float)count/(float)sets
 208   );
 209 }