tools/build/v2/engine/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 # include "jam.h"
   8 # include "hash.h"
   9 # include "compile.h"
  10 # include "object.h"
  11 # include <assert.h>
  12
  13 /*
  14  * hash.c - simple in-memory hashing routines
  15  *
  16  * External routines:
  17  *
  18  *     hashinit() - initialize a hash table, returning a handle
  19  *     hashitem() - find a record in the table, and optionally enter a new one
  20  *     hashdone() - free a hash table, given its handle
  21  *
  22  * Internal routines:
  23  *
  24  *     hashrehash() - resize and rebuild hp->tab, the hash table
  25  *
  26  * 4/29/93 - ensure ITEM's are aligned
  27  */
  28
  29 /* */
  30 #define HASH_DEBUG_PROFILE 1
  31 /* */
  32
  33 /* Header attached to all data items entered into a hash table. */
  34
  35 struct hashhdr
  36 {
  37     struct item  * next;
  38 };
  39
  40 typedef struct item
  41 {
  42     struct hashhdr  hdr;
  43 } ITEM ;
  44
  45 # define MAX_LISTS 32
  46
  47 struct hash
  48 {
  49     /*
  50      * the hash table, just an array of item pointers
  51      */
  52     struct {
  53         int nel;
  54         ITEM **base;
  55     } tab;
  56
  57     int bloat;  /* tab.nel / items.nel */
  58     int inel;   /* initial number of elements */
  59
  60     /*
  61      * the array of records, maintained by these routines
  62      * essentially a microallocator
  63      */
  64     struct {
  65         int more;   /* how many more ITEMs fit in lists[ list ] */
  66         ITEM *free; /* free list of items */
  67         char *next; /* where to put more ITEMs in lists[ list ] */
  68         int size;   /* sizeof( ITEM ) + aligned datalen */
  69         int nel;    /* total ITEMs held by all lists[] */
  70         int list;   /* index into lists[] */
  71
  72         struct {
  73             int nel;    /* total ITEMs held by this list */
  74             char *base; /* base of ITEMs array */
  75         } lists[ MAX_LISTS ];
  76     } items;
  77
  78     const char * name; /* just for hashstats() */
  79 };
  80
  81 static void hashrehash( struct hash *hp );
  82 static void hashstat( struct hash *hp );
  83
  84 static unsigned int hash_keyval( OBJECT * key )
  85 {
  86     return object_hash( key );
  87 }
  88
  89 #define hash_bucket(hp,keyval) ((hp)->tab.base + ( (keyval) % (hp)->tab.nel ))
  90
  91 #define hash_data_key(data) (*(OBJECT * *)(data))
  92 #define hash_item_data(item) ((HASHDATA *)((char *)item + sizeof(struct hashhdr)))
  93 #define hash_item_key(item) (hash_data_key(hash_item_data(item)))
  94
  95 /*  Find the hash item for the given data. Returns pointer to the
  96     item and if given a pointer to the item before the found item.
  97     If it's the first item in a bucket, there is no previous item,
  98     and zero is returned for the previous item instead.
  99 */
 100 static ITEM * hash_search(
 101     struct hash *hp,
 102     unsigned int keyval,
 103     OBJECT * keydata,
 104     ITEM * * previous )
 105 {
 106     ITEM * i = *hash_bucket(hp,keyval);
 107     ITEM * p = 0;
 108
 109     for ( ; i; i = i->hdr.next )
 110     {
 111         if ( object_equal( hash_item_key( i ), keydata ) )
 112         {
 113             if (previous)
 114             {
 115                 *previous = p;
 116             }
 117             return i;
 118         }
 119         p = i;
 120     }
 121
 122     return 0;
 123 }
 124
 125 /*
 126  * hash_insert() - insert a record in the table or return the existing one
 127  */
 128
 129 HASHDATA * hash_insert( struct hash * hp, OBJECT * key, int * found )
 130 {
 131     ITEM * i;
 132     unsigned int keyval = hash_keyval( key );
 133
 134     #ifdef HASH_DEBUG_PROFILE
 135     profile_frame prof[1];
 136     if ( DEBUG_PROFILE )
 137         profile_enter( 0, prof );
 138     #endif
 139
 140     if ( !hp->items.more )
 141         hashrehash( hp );
 142
 143     i = hash_search( hp, keyval, key, 0 );
 144     if ( i )
 145     {
 146         *found = 1;
 147     }
 148     else
 149     {
 150         ITEM * * base = hash_bucket( hp, keyval );
 151
 152         /* try to grab one from the free list */
 153         if ( hp->items.free )
 154         {
 155             i = hp->items.free;
 156             hp->items.free = i->hdr.next;
 157             assert( hash_item_key( i ) == 0 );
 158         }
 159         else
 160         {
 161             i = (ITEM *)hp->items.next;
 162             hp->items.next += hp->items.size;
 163         }
 164         hp->items.more--;
 165         i->hdr.next = *base;
 166         *base = i;
 167         *found = 0;
 168     }
 169
 170     #ifdef HASH_DEBUG_PROFILE
 171     if ( DEBUG_PROFILE )
 172         profile_exit( prof );
 173     #endif
 174
 175     return hash_item_data( i );
 176 }
 177
 178 /*
 179  * hash_find() - find a record in the table or NULL if none exists
 180  */
 181
 182 HASHDATA * hash_find( struct hash *hp, OBJECT *key )
 183 {
 184     ITEM *i;
 185     unsigned int keyval = hash_keyval(key);
 186
 187     #ifdef HASH_DEBUG_PROFILE
 188     profile_frame prof[1];
 189     if ( DEBUG_PROFILE )
 190         profile_enter( 0, prof );
 191     #endif
 192
 193     if ( !hp->items.nel )
 194     {
 195         #ifdef HASH_DEBUG_PROFILE
 196         if ( DEBUG_PROFILE )
 197             profile_exit( prof );
 198         #endif
 199         return 0;
 200     }
 201
 202     i = hash_search( hp, keyval, key, 0 );
 203
 204     #ifdef HASH_DEBUG_PROFILE
 205     if ( DEBUG_PROFILE )
 206         profile_exit( prof );
 207     #endif
 208
 209     if (i)
 210     {
 211         return hash_item_data( i );
 212     }
 213     else
 214     {
 215         return 0;
 216     }
 217 }
 218
 219 /*
 220  * hashrehash() - resize and rebuild hp->tab, the hash table
 221  */
 222
 223 static void hashrehash( register struct hash *hp )
 224 {
 225     int i = ++hp->items.list;
 226     hp->items.more = i ? 2 * hp->items.nel : hp->inel;
 227     hp->items.next = (char *)BJAM_MALLOC( hp->items.more * hp->items.size );
 228     hp->items.free = 0;
 229
 230     hp->items.lists[i].nel = hp->items.more;
 231     hp->items.lists[i].base = hp->items.next;
 232     hp->items.nel += hp->items.more;
 233
 234     if ( hp->tab.base )
 235         BJAM_FREE( (char *)hp->tab.base );
 236
 237     hp->tab.nel = hp->items.nel * hp->bloat;
 238     hp->tab.base = (ITEM **)BJAM_MALLOC( hp->tab.nel * sizeof(ITEM **) );
 239
 240     memset( (char *)hp->tab.base, '\0', hp->tab.nel * sizeof( ITEM * ) );
 241
 242     for ( i = 0; i < hp->items.list; ++i )
 243     {
 244         int nel = hp->items.lists[i].nel;
 245         char *next = hp->items.lists[i].base;
 246
 247         for ( ; nel--; next += hp->items.size )
 248         {
 249             register ITEM *i = (ITEM *)next;
 250             ITEM **ip = hp->tab.base + object_hash( hash_item_key( i ) ) % hp->tab.nel;
 251             /* code currently assumes rehashing only when there are no free items */
 252             assert( hash_item_key( i ) != 0 );
 253
 254             i->hdr.next = *ip;
 255             *ip = i;
 256         }
 257     }
 258 }
 259
 260 void hashenumerate( struct hash * hp, void (* f)( void *, void * ), void * data )
 261 {
 262     int i;
 263     for ( i = 0; i <= hp->items.list; ++i )
 264     {
 265         char * next = hp->items.lists[i].base;
 266         int nel = hp->items.lists[i].nel;
 267         if ( i == hp->items.list )
 268             nel -= hp->items.more;
 269
 270         for ( ; nel--; next += hp->items.size )
 271         {
 272             ITEM * i = (ITEM *)next;
 273             if ( hash_item_key( i ) != 0 )  /* DO not enumerate freed items. */
 274                 f( hash_item_data( i ), data );
 275         }
 276     }
 277 }
 278
 279 /* --- */
 280
 281 # define ALIGNED(x) ( ( x + sizeof( ITEM ) - 1 ) & ~( sizeof( ITEM ) - 1 ) )
 282
 283 /*
 284  * hashinit() - initialize a hash table, returning a handle
 285  */
 286
 287 struct hash *
 288 hashinit(
 289     int datalen,
 290     const char *name )
 291 {
 292     struct hash *hp = (struct hash *)BJAM_MALLOC( sizeof( *hp ) );
 293
 294     hp->bloat = 3;
 295     hp->tab.nel = 0;
 296     hp->tab.base = (ITEM **)0;
 297     hp->items.more = 0;
 298     hp->items.free = 0;
 299     hp->items.size = sizeof( struct hashhdr ) + ALIGNED( datalen );
 300     hp->items.list = -1;
 301     hp->items.nel = 0;
 302     hp->inel = 11 /* 47 */;
 303     hp->name = name;
 304
 305     return hp;
 306 }
 307
 308 void hashdone( struct hash * hp )
 309 {
 310     if ( !hp )
 311         return;
 312     if ( DEBUG_MEM || DEBUG_PROFILE )
 313         hashstat( hp );
 314     hash_free( hp );
 315 }
 316
 317 /*
 318  * hash_free() - free a hash table, given its handle
 319  */
 320
 321 void
 322 hash_free( struct hash * hp )
 323 {
 324     int i;
 325
 326     if ( !hp )
 327         return;
 328
 329     if ( hp->tab.base )
 330         BJAM_FREE( (char *)hp->tab.base );
 331     for ( i = 0; i <= hp->items.list; ++i )
 332         BJAM_FREE( hp->items.lists[i].base );
 333     BJAM_FREE( (char *)hp );
 334 }
 335
 336
 337 /* ---- */
 338
 339 static void hashstat( struct hash * hp )
 340 {
 341     struct hashstats stats[ 1 ];
 342     hashstats_init( stats );
 343     hashstats_add( stats, hp );
 344     hashstats_print( stats, hp->name );
 345 }
 346
 347 void hashstats_init( struct hashstats * stats )
 348 {
 349     stats->count = 0;
 350     stats->num_items = 0;
 351     stats->tab_size = 0;
 352     stats->item_size = 0;
 353     stats->sets = 0;
 354 }
 355
 356 void hashstats_add( struct hashstats * stats, struct hash * hp )
 357 {
 358     if ( hp )
 359     {
 360         ITEM * * tab = hp->tab.base;
 361         int nel = hp->tab.nel;
 362         int count = 0;
 363         int sets = 0;
 364         int i;
 365
 366         for ( i = 0; i < nel; ++i )
 367         {
 368             ITEM * item;
 369             int here = 0;
 370             for ( item = tab[ i ]; item != 0; item = item->hdr.next )
 371                 ++here;
 372
 373             count += here;
 374             if ( here > 0 )
 375                 ++sets;
 376         }
 377
 378         stats->count += count;
 379         stats->sets += sets;
 380         stats->num_items += hp->items.nel;
 381         stats->tab_size += hp->tab.nel;
 382         stats->item_size = hp->items.size;
 383     }
 384 }
 385
 386 void hashstats_print( struct hashstats * stats, const char * name )
 387 {
 388     printf( "%s table: %d+%d+%d (%dK+%luK) items+table+hash, %f density\n",
 389         name,
 390         stats->count,
 391         stats->num_items,
 392         stats->tab_size,
 393         stats->num_items * stats->item_size / 1024,
 394         (long unsigned)stats->tab_size * sizeof( ITEM ** ) / 1024,
 395         (float)stats->count / (float)stats->sets );
 396 }