hash.cpp

/*
 * 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 "output.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
    {
        int32_t nel;
        ITEM * * base;
    } tab;

    int32_t bloat;  /* tab.nel / items.nel */
    int32_t inel;   /* initial number of elements */

    /*
     * the array of records, maintained by these routines - essentially a
     * microallocator
     */
    struct
    {
        int32_t 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 ] */
        int32_t size;     /* sizeof( ITEM ) + aligned datalen */
        int32_t nel;      /* total ITEMs held by all lists[] */
        int32_t list;     /* index into lists[] */

        struct
        {
            int32_t 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 uint32_t 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( int32_t 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, uint32_t 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, int32_t * found )
{
    ITEM * i;
    uint32_t keyval = hash_keyval( key );

    #ifdef HASH_DEBUG_PROFILE
    profile_frame prof[ 1 ];
    if ( is_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 ( is_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;
    uint32_t keyval = hash_keyval( key );

    #ifdef HASH_DEBUG_PROFILE
    profile_frame prof[ 1 ];
    if ( is_debug_profile() )
        profile_enter( 0, prof );
    #endif

    if ( !hp->items.nel )
    {
        #ifdef HASH_DEBUG_PROFILE
        if ( is_debug_profile() )
            profile_exit( prof );
        #endif
        return 0;
    }

    i = hash_search( hp, keyval, key, 0 );

    #ifdef HASH_DEBUG_PROFILE
    if ( is_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 )
{
    int32_t 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 )
    {
        int32_t 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;
        }
    }
}


#if defined(__clang__) && defined(__has_feature)
#if __has_feature(address_sanitizer)
// This function calls not properly type-erased callbacks
__attribute__((no_sanitize("undefined")))
#endif
#endif
void hashenumerate( struct hash * hp, void (* f)( void *, void * ), void * data
    )
{
    int32_t i;
    for ( i = 0; i <= hp->items.list; ++i )
    {
        char * next = hp->items.lists[ i ].base;
        int32_t 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 )
{
    int32_t 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 )
{
    out_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 ( is_debug_mem() || is_debug_profile() )
        hashstat( hp );
    hash_free( hp );
}