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