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