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