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   /*
  53    * the hash table, just an array of item pointers
  54    */
  55   struct {
  56     int nel;
  57     ITEM **base;
  58   } tab;
  59
  60   int bloat;  /* tab.nel / items.nel */
  61   int inel;   /* initial number of elements */
  62
  63   /*
  64    * the array of records, maintained by these routines
  65    * essentially a microallocator
  66    */
  67   struct {
  68     int more; /* how many more ITEMs fit in lists[ list ] */
  69     char *next; /* where to put more ITEMs in lists[ list ] */
  70     int datalen;  /* length of records in this hash table */
  71     int size; /* sizeof( ITEM ) + aligned datalen */
  72     int nel;  /* total ITEMs held by all lists[] */
  73     int list; /* index into lists[] */
  74
  75     struct {
  76       int nel;  /* total ITEMs held by this list */
  77       char *base; /* base of ITEMs array */
  78     } lists[ MAX_LISTS ];
  79   } items;
  80
  81   const char *name; /* just for hashstats() */
  82 } ;
  83
  84 static void hashrehash( struct hash *hp );
  85 static void hashstat( struct hash *hp );
  86
  87 /*
  88  * hashitem() - find a record in the table, and optionally enter a new one
  89  */
  90
  91 int
  92 hashitem(
  93   register struct hash *hp,
  94   HASHDATA **data,
  95   int enter )
  96 {
  97   ITEM **base;
  98   register ITEM *i;
  99   unsigned char *b = (unsigned char *)(*data)->key;
 100   unsigned int keyval;
 101
 102   if( enter && !hp->items.more )
 103       hashrehash( hp );
 104
 105   if( !enter && !hp->items.nel )
 106       return 0;
 107
 108   keyval = *b;
 109
 110   while( *b )
 111     keyval = keyval * 2147059363 + *b++;
 112
 113   base = hp->tab.base + ( keyval % hp->tab.nel );
 114
 115   for( i = *base; i; i = i->hdr.next )
 116       if( keyval == i->hdr.keyval &&
 117     !strcmp( i->data.key, (*data)->key ) )
 118   {
 119     *data = &i->data;
 120     return !0;
 121   }
 122
 123   if( enter )
 124   {
 125     i = (ITEM *)hp->items.next;
 126     hp->items.next += hp->items.size;
 127     hp->items.more--;
 128     memcpy( (char *)&i->data, (char *)*data, hp->items.datalen );
 129     i->hdr.keyval = keyval;
 130     i->hdr.next = *base;
 131     *base = i;
 132     *data = &i->data;
 133   }
 134
 135   return 0;
 136 }
 137
 138 /*
 139  * hashrehash() - resize and rebuild hp->tab, the hash table
 140  */
 141
 142 static void hashrehash( register struct hash *hp )
 143 {
 144   int i = ++hp->items.list;
 145
 146   hp->items.more = i ? 2 * hp->items.nel : hp->inel;
 147   hp->items.next = (char *)malloc( hp->items.more * hp->items.size );
 148
 149   hp->items.lists[i].nel = hp->items.more;
 150   hp->items.lists[i].base = hp->items.next;
 151   hp->items.nel += hp->items.more;
 152
 153   if( hp->tab.base )
 154     free( (char *)hp->tab.base );
 155
 156   hp->tab.nel = hp->items.nel * hp->bloat;
 157   hp->tab.base = (ITEM **)malloc( hp->tab.nel * sizeof(ITEM **) );
 158
 159   memset( (char *)hp->tab.base, '\0', hp->tab.nel * sizeof( ITEM * ) );
 160
 161   for( i = 0; i < hp->items.list; i++ )
 162   {
 163     int nel = hp->items.lists[i].nel;
 164     char *next = hp->items.lists[i].base;
 165
 166     for( ; nel--; next += hp->items.size )
 167     {
 168       register ITEM *i = (ITEM *)next;
 169       ITEM **ip = hp->tab.base + i->hdr.keyval % hp->tab.nel;
 170
 171       i->hdr.next = *ip;
 172       *ip = i;
 173     }
 174   }
 175 }
 176
 177 /* --- */
 178
 179 # define ALIGNED(x) ( ( x + sizeof( ITEM ) - 1 ) & ~( sizeof( ITEM ) - 1 ) )
 180
 181 /*
 182  * hashinit() - initialize a hash table, returning a handle
 183  */
 184
 185 struct hash *
 186 hashinit(
 187   int datalen,
 188   const char *name )
 189 {
 190   struct hash *hp = (struct hash *)malloc( sizeof( *hp ) );
 191
 192   hp->bloat = 3;
 193   hp->tab.nel = 0;
 194   hp->tab.base = (ITEM **)0;
 195   hp->items.more = 0;
 196   hp->items.datalen = datalen;
 197   hp->items.size = sizeof( struct hashhdr ) + ALIGNED( datalen );
 198   hp->items.list = -1;
 199   hp->items.nel = 0;
 200   hp->inel = 11;
 201   hp->name = name;
 202
 203   return hp;
 204 }
 205
 206 /*
 207  * hashdone() - free a hash table, given its handle
 208  */
 209
 210 void
 211 hashdone( struct hash *hp )
 212 {
 213   int i;
 214
 215   if( !hp )
 216       return;
 217
 218   if( DEBUG_MEM )
 219       hashstat( hp );
 220
 221   if( hp->tab.base )
 222     free( (char *)hp->tab.base );
 223   for( i = 0; i <= hp->items.list; i++ )
 224     free( hp->items.lists[i].base );
 225   free( (char *)hp );
 226 }
 227
 228 /* ---- */
 229
 230 static void
 231 hashstat( struct hash *hp )
 232 {
 233   ITEM **tab = hp->tab.base;
 234   int nel = hp->tab.nel;
 235   int count = 0;
 236   int sets = 0;
 237   int run = ( tab[ nel - 1 ] != (ITEM *)0 );
 238   int i, here;
 239
 240   for( i = nel; i > 0; i-- )
 241   {
 242     if ((here = (*tab++ != (ITEM *)0)))
 243       count++;
 244     if( here && !run )
 245       sets++;
 246     run = here;
 247   }
 248
 249   printf( "%s table: %d+%d+%d (%dK+%dK) items+table+hash, %f density\n",
 250     hp->name,
 251     count,
 252     hp->items.nel,
 253     hp->tab.nel,
 254     hp->items.nel * hp->items.size / 1024,
 255     hp->tab.nel * sizeof( ITEM ** ) / 1024,
 256     (float)count / (float)sets );
 257 }