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 #define ALIGNED(x)  ((x+sizeof(ITEM)-1)&(~(sizeof(ITEM)-1)))
  76
  77
  78 static void hashstat (struct hash *hp) {
  79   ITEM **tab = hp->tab.base;
  80   int nel = hp->tab.nel;
  81   int count = 0;
  82   int sets = 0;
  83   int run = (tab[nel-1] != (ITEM *)0);
  84   int i, here;
  85   //
  86   for (i = nel; i > 0; --i) {
  87     if ((here = (*tab++ != (ITEM *)0))) ++count;
  88     if (here && !run) ++sets;
  89     run = here;
  90   }
  91 #ifdef __NEATCC__
  92   printf("%s table: %d+%d+%d (%dK+%dK) items+table+hash, density: count=%d; sets=%d\n",
  93     hp->name,
  94     count,
  95     hp->items.nel,
  96     hp->tab.nel,
  97     hp->items.nel*hp->items.size/1024,
  98     (int)(hp->tab.nel*sizeof(ITEM **)/1024),
  99     count, sets
 100   );
 101 #else
 102   printf("%s table: %d+%d+%d (%dK+%dK) items+table+hash, %f density\n",
 103     hp->name,
 104     count,
 105     hp->items.nel,
 106     hp->tab.nel,
 107     hp->items.nel*hp->items.size/1024,
 108     (int)(hp->tab.nel*sizeof(ITEM **)/1024),
 109     (float)count/(float)sets
 110   );
 111 #endif
 112 }
 113
 114
 115 /*
 116  * hashrehash() - resize and rebuild hp->tab, the hash table
 117  */
 118 static void hashrehash (struct hash *hp) {
 119   int i = ++hp->items.list;
 120   //
 121   hp->items.more = i ? 2*hp->items.nel : hp->inel;
 122   hp->items.next = (char *)malloc(hp->items.more*hp->items.size);
 123   //
 124   hp->items.lists[i].nel = hp->items.more;
 125   hp->items.lists[i].base = hp->items.next;
 126   hp->items.nel += hp->items.more;
 127   //
 128   if (hp->tab.base) free((char *)hp->tab.base);
 129   //
 130   hp->tab.nel = hp->items.nel*hp->bloat;
 131   hp->tab.base = (ITEM **)malloc(hp->tab.nel*sizeof(ITEM **));
 132   //
 133   memset((char *)hp->tab.base, '\0', hp->tab.nel*sizeof(ITEM *));
 134   //
 135   for (i = 0; i < hp->items.list; ++i) {
 136     int nel = hp->items.lists[i].nel;
 137     char *next = hp->items.lists[i].base;
 138     //
 139     for (; nel--; next += hp->items.size) {
 140       ITEM *i = (ITEM *)next;
 141       ITEM **ip = hp->tab.base+i->hdr.keyval%hp->tab.nel;
 142       i->hdr.next = *ip;
 143       *ip = i;
 144     }
 145   }
 146 }
 147
 148
 149 int hashiterate (struct hash *hp, HashIteratorCB itercb, void *udata) {
 150   ITEM **tab = hp->tab.base;
 151   int i;
 152   //
 153   for (i = hp->tab.nel; i > 0; --i, ++tab) {
 154     if (*tab != NULL) {
 155       int res = itercb(&((*tab)->data), udata);
 156       //
 157       if (res) return res;
 158     }
 159   }
 160   return 0;
 161 }
 162
 163
 164 /*
 165  * hashitem() - find a record in the table, and optionally enter a new one
 166  */
 167 int hashitem (struct hash *hp, HASHDATA **data, int enter) {
 168   ITEM **base;
 169   ITEM *i;
 170   unsigned char *b = (unsigned char *)(*data)->key;
 171   unsigned int keyval;
 172   //
 173   if (enter && !hp->items.more) hashrehash(hp);
 174   if (!enter && !hp->items.nel) return 0;
 175   keyval = *b;
 176   while (*b) keyval = keyval*2147059363 + *b++;
 177   base = hp->tab.base+(keyval%hp->tab.nel);
 178   for (i = *base; i; i = i->hdr.next) {
 179     if (keyval == i->hdr.keyval && !strcmp(i->data.key, (*data)->key)) {
 180       *data = &i->data;
 181       return !0;
 182     }
 183   }
 184   if (enter) {
 185     i = (ITEM *)hp->items.next;
 186     hp->items.next += hp->items.size;
 187     --hp->items.more;
 188     memcpy((char *)&i->data, (char *)*data, hp->items.datalen);
 189     i->hdr.keyval = keyval;
 190     i->hdr.next = *base;
 191     *base = i;
 192     *data = &i->data;
 193   }
 194   return 0;
 195 }
 196
 197
 198 /*
 199  * hashinit() - initialize a hash table, returning a handle
 200  */
 201 struct hash *hashinit (int datalen, const char *name) {
 202   struct hash *hp = (struct hash *)malloc(sizeof(*hp));
 203   //
 204   hp->bloat = 3;
 205   hp->tab.nel = 0;
 206   hp->tab.base = (ITEM **)0;
 207   hp->items.more = 0;
 208   hp->items.datalen = datalen;
 209   hp->items.size = sizeof(struct hashhdr)+ALIGNED(datalen);
 210   hp->items.list = -1;
 211   hp->items.nel = 0;
 212   hp->inel = 11;
 213   hp->name = name;
 214   return hp;
 215 }
 216
 217
 218 /*
 219  * hashdone() - free a hash table, given its handle
 220  */
 221 void hashdone (struct hash *hp) {
 222   int i;
 223   //
 224   if (!hp) return;
 225   if (DEBUG_MEM) hashstat(hp);
 226   if (hp->tab.base) free((char *)hp->tab.base);
 227   for (i = 0; i <= hp->items.list; i++) free(hp->items.lists[i].base);
 228   free((char *)hp);
 229 }