1 files changed, 387 insertions, 0 deletions

diff --git a/tools/build/src/engine/hash.c b/tools/build/src/engine/hash.c
new file mode 100644
index 000000000..36f836668
--- /dev/null
+++ b/tools/build/src/engine/hash.c
@@ -0,0 +1,387 @@
+/*
+ * Copyright 1993, 1995 Christopher Seiwald.
+ *
+ * This file is part of Jam - see jam.c for Copyright information.
+ */
+
+/*
+ * hash.c - simple in-memory hashing routines
+ *
+ * External routines:
+ *     hashinit() - initialize a hash table, returning a handle
+ *     hashitem() - find a record in the table, and optionally enter a new one
+ *     hashdone() - free a hash table, given its handle
+ *
+ * Internal routines:
+ *     hashrehash() - resize and rebuild hp->tab, the hash table
+ */
+
+#include "jam.h"
+#include "hash.h"
+
+#include "compile.h"
+
+#include <assert.h>
+
+/* */
+#define HASH_DEBUG_PROFILE 1
+/* */
+
+/* Header attached to all hash table data items. */
+
+typedef struct item ITEM;
+struct item
+{
+    ITEM * next;
+};
+
+#define MAX_LISTS 32
+
+struct hash
+{
+    /*
+     * the hash table, just an array of item pointers
+     */
+    struct
+    {
+        int nel;
+        ITEM * * base;
+    } tab;
+
+    int bloat;  /* tab.nel / items.nel */
+    int inel;   /* initial number of elements */
+
+    /*
+     * the array of records, maintained by these routines - essentially a
+     * microallocator
+     */
+    struct
+    {
+        int more;     /* how many more ITEMs fit in lists[ list ] */
+        ITEM * free;  /* free list of items */
+        char * next;  /* where to put more ITEMs in lists[ list ] */
+        int size;     /* sizeof( ITEM ) + aligned datalen */
+        int nel;      /* total ITEMs held by all lists[] */
+        int list;     /* index into lists[] */
+
+        struct
+        {
+            int nel;      /* total ITEMs held by this list */
+            char * base;  /* base of ITEMs array */
+        } lists[ MAX_LISTS ];
+    } items;
+
+    char const * name;  /* just for hashstats() */
+};
+
+static void hashrehash( struct hash * );
+static void hashstat( struct hash * );
+
+static unsigned int hash_keyval( OBJECT * key )
+{
+    return object_hash( key );
+}
+
+#define hash_bucket(hp, keyval) ((hp)->tab.base + ((keyval) % (hp)->tab.nel))
+
+#define hash_data_key(data) (*(OBJECT * *)(data))
+#define hash_item_data(item) ((HASHDATA *)((char *)item + sizeof(ITEM)))
+#define hash_item_key(item) (hash_data_key(hash_item_data(item)))
+
+
+#define ALIGNED(x) ((x + sizeof(ITEM) - 1) & ~(sizeof(ITEM) - 1))
+
+/*
+ * hashinit() - initialize a hash table, returning a handle
+ */
+
+struct hash * hashinit( int datalen, char const * name )
+{
+    struct hash * hp = (struct hash *)BJAM_MALLOC( sizeof( *hp ) );
+
+    hp->bloat = 3;
+    hp->tab.nel = 0;
+    hp->tab.base = 0;
+    hp->items.more = 0;
+    hp->items.free = 0;
+    hp->items.size = sizeof( ITEM ) + ALIGNED( datalen );
+    hp->items.list = -1;
+    hp->items.nel = 0;
+    hp->inel = 11;  /* 47 */
+    hp->name = name;
+
+    return hp;
+}
+
+
+/*
+ * hash_search() - Find the hash item for the given data.
+ *
+ * Returns a pointer to a hashed item with the given key. If given a 'previous'
+ * pointer, makes it point to the item prior to the found item in the same
+ * bucket or to 0 if our item is the first item in its bucket.
+ */
+
+static ITEM * hash_search( struct hash * hp, unsigned int keyval,
+    OBJECT * keydata, ITEM * * previous )
+{
+    ITEM * i = *hash_bucket( hp, keyval );
+    ITEM * p = 0;
+    for ( ; i; i = i->next )
+    {
+        if ( object_equal( hash_item_key( i ), keydata ) )
+        {
+            if ( previous )
+                *previous = p;
+            return i;
+        }
+        p = i;
+    }
+    return 0;
+}
+
+
+/*
+ * hash_insert() - insert a record in the table or return the existing one
+ */
+
+HASHDATA * hash_insert( struct hash * hp, OBJECT * key, int * found )
+{
+    ITEM * i;
+    unsigned int keyval = hash_keyval( key );
+
+    #ifdef HASH_DEBUG_PROFILE
+    profile_frame prof[ 1 ];
+    if ( DEBUG_PROFILE )
+        profile_enter( 0, prof );
+    #endif
+
+    if ( !hp->items.more )
+        hashrehash( hp );
+
+    i = hash_search( hp, keyval, key, 0 );
+    if ( i )
+        *found = 1;
+    else
+    {
+        ITEM * * base = hash_bucket( hp, keyval );
+
+        /* Try to grab one from the free list. */
+        if ( hp->items.free )
+        {
+            i = hp->items.free;
+            hp->items.free = i->next;
+            assert( !hash_item_key( i ) );
+        }
+        else
+        {
+            i = (ITEM *)hp->items.next;
+            hp->items.next += hp->items.size;
+        }
+        --hp->items.more;
+        i->next = *base;
+        *base = i;
+        *found = 0;
+    }
+
+    #ifdef HASH_DEBUG_PROFILE
+    if ( DEBUG_PROFILE )
+        profile_exit( prof );
+    #endif
+
+    return hash_item_data( i );
+}
+
+
+/*
+ * hash_find() - find a record in the table or NULL if none exists
+ */
+
+HASHDATA * hash_find( struct hash * hp, OBJECT * key )
+{
+    ITEM * i;
+    unsigned int keyval = hash_keyval( key );
+
+    #ifdef HASH_DEBUG_PROFILE
+    profile_frame prof[ 1 ];
+    if ( DEBUG_PROFILE )
+        profile_enter( 0, prof );
+    #endif
+
+    if ( !hp->items.nel )
+    {
+        #ifdef HASH_DEBUG_PROFILE
+        if ( DEBUG_PROFILE )
+            profile_exit( prof );
+        #endif
+        return 0;
+    }
+
+    i = hash_search( hp, keyval, key, 0 );
+
+    #ifdef HASH_DEBUG_PROFILE
+    if ( DEBUG_PROFILE )
+        profile_exit( prof );
+    #endif
+
+    return i ? hash_item_data( i ) : 0;
+}
+
+
+/*
+ * hashrehash() - resize and rebuild hp->tab, the hash table
+ */
+
+static void hashrehash( struct hash * hp )
+{
+    int i = ++hp->items.list;
+    hp->items.more = i ? 2 * hp->items.nel : hp->inel;
+    hp->items.next = (char *)BJAM_MALLOC( hp->items.more * hp->items.size );
+    hp->items.free = 0;
+
+    hp->items.lists[ i ].nel = hp->items.more;
+    hp->items.lists[ i ].base = hp->items.next;
+    hp->items.nel += hp->items.more;
+
+    if ( hp->tab.base )
+        BJAM_FREE( (char *)hp->tab.base );
+
+    hp->tab.nel = hp->items.nel * hp->bloat;
+    hp->tab.base = (ITEM * *)BJAM_MALLOC( hp->tab.nel * sizeof( ITEM * * ) );
+
+    memset( (char *)hp->tab.base, '\0', hp->tab.nel * sizeof( ITEM * ) );
+
+    for ( i = 0; i < hp->items.list; ++i )
+    {
+        int nel = hp->items.lists[ i ].nel;
+        char * next = hp->items.lists[ i ].base;
+
+        for ( ; nel--; next += hp->items.size )
+        {
+            ITEM * i = (ITEM *)next;
+            ITEM * * ip = hp->tab.base + object_hash( hash_item_key( i ) ) %
+                hp->tab.nel;
+            /* code currently assumes rehashing only when there are no free
+             * items
+             */
+            assert( hash_item_key( i ) );
+
+            i->next = *ip;
+            *ip = i;
+        }
+    }
+}
+
+
+void hashenumerate( struct hash * hp, void (* f)( void *, void * ), void * data
+    )
+{
+    int i;
+    for ( i = 0; i <= hp->items.list; ++i )
+    {
+        char * next = hp->items.lists[ i ].base;
+        int nel = hp->items.lists[ i ].nel;
+        if ( i == hp->items.list )
+            nel -= hp->items.more;
+
+        for ( ; nel--; next += hp->items.size )
+        {
+            ITEM * const i = (ITEM *)next;
+            if ( hash_item_key( i ) != 0 )  /* Do not enumerate freed items. */
+                f( hash_item_data( i ), data );
+        }
+    }
+}
+
+
+/*
+ * hash_free() - free a hash table, given its handle
+ */
+
+void hash_free( struct hash * hp )
+{
+    int i;
+    if ( !hp )
+        return;
+    if ( hp->tab.base )
+        BJAM_FREE( (char *)hp->tab.base );
+    for ( i = 0; i <= hp->items.list; ++i )
+        BJAM_FREE( hp->items.lists[ i ].base );
+    BJAM_FREE( (char *)hp );
+}
+
+
+static void hashstat( struct hash * hp )
+{
+    struct hashstats stats[ 1 ];
+    hashstats_init( stats );
+    hashstats_add( stats, hp );
+    hashstats_print( stats, hp->name );
+}
+
+
+void hashstats_init( struct hashstats * stats )
+{
+    stats->count = 0;
+    stats->num_items = 0;
+    stats->tab_size = 0;
+    stats->item_size = 0;
+    stats->sets = 0;
+    stats->num_hashes = 0;
+}
+
+
+void hashstats_add( struct hashstats * stats, struct hash * hp )
+{
+    if ( hp )
+    {
+        ITEM * * tab = hp->tab.base;
+        int nel = hp->tab.nel;
+        int count = 0;
+        int sets = 0;
+        int i;
+
+        for ( i = 0; i < nel; ++i )
+        {
+            ITEM * item;
+            int here = 0;
+            for ( item = tab[ i ]; item; item = item->next )
+                ++here;
+
+            count += here;
+            if ( here > 0 )
+                ++sets;
+        }
+
+        stats->count += count;
+        stats->sets += sets;
+        stats->num_items += hp->items.nel;
+        stats->tab_size += hp->tab.nel;
+        stats->item_size = hp->items.size;
+        ++stats->num_hashes;
+    }
+}
+
+
+void hashstats_print( struct hashstats * stats, char const * name )
+{
+    printf( "%s table: %d+%d+%d (%dK+%luK+%luK) items+table+hash, %f density\n",
+        name,
+        stats->count,
+        stats->num_items,
+        stats->tab_size,
+        stats->num_items * stats->item_size / 1024,
+        (long unsigned)stats->tab_size * sizeof( ITEM * * ) / 1024,
+        (long unsigned)stats->num_hashes * sizeof( struct hash ) / 1024,
+        (float)stats->count / (float)stats->sets );
+}
+
+
+void hashdone( struct hash * hp )
+{
+    if ( !hp )
+        return;
+    if ( DEBUG_MEM || DEBUG_PROFILE )
+        hashstat( hp );
+    hash_free( hp );
+}