hash_table.c

Go to the documentation of this file.

/* ----------------------------------------------------------------------------
@COPYRIGHT  :
              Copyright 1993,1994,1995 David MacDonald,
              McConnell Brain Imaging Centre,
              Montreal Neurological Institute, McGill University.
              Permission to use, copy, modify, and distribute this
              software and its documentation for any purpose and without
              fee is hereby granted, provided that the above copyright
              notice appear in all copies.  The author and McGill University
              make no representations about the suitability of this
              software for any purpose.  It is provided "as is" without
              express or implied warranty.
---------------------------------------------------------------------------- */

#include  <volume_io/internal_volume_io.h>
#include  <bicpl/data_structures.h>

#ifndef lint
static char rcsid[] = "$Header: /software/source//libraries/bicpl/Data_structures/hash_table.c,v 1.13 2000/02/06 15:30:11 stever Exp $";
#endif

#define  HASH_FUNCTION_CONSTANT          0.6180339887498948482

/* ----------------------------- MNI Header -----------------------------------
@NAME       : initialize_hash_table
@INPUT      : 
            : size
            : enlarge_threshold
            : new_density
@OUTPUT     : hash_table
@RETURNS    : Status
@DESCRIPTION: Initializes a hash table to empty, storing the
            : initial size, and parameters controlling automatic growth.
@METHOD     : 
@GLOBALS    : 
@CALLS      : 
@CREATED    :                      David MacDonald
@MODIFIED   : 
---------------------------------------------------------------------------- */

public   void  initialize_hash_table(
    hash_table_struct  *hash_table,
    int                size,
    int                data_size,
    Real               enlarge_threshold,
    Real               new_density )
{
    int        i;

    hash_table->size = size;
    hash_table->data_size = data_size;
    hash_table->n_entries = 0;
    hash_table->enlarge_threshold = enlarge_threshold;
    hash_table->new_density = new_density;

    ALLOC( hash_table->table, size );

    for( i = 0;  i < size;  ++i )
        hash_table->table[i] = NULL;
}

/* ----------------------------- MNI Header -----------------------------------
@NAME       : delete_hash_table_list
@INPUT      : hash_table
@OUTPUT     : 
@RETURNS    : Status
@DESCRIPTION: Deletes the list of pointers in the hash table.
@METHOD     : 
@GLOBALS    : 
@CALLS      : 
@CREATED    :                      David MacDonald
@MODIFIED   : 
---------------------------------------------------------------------------- */

private   void  delete_hash_table_list(
    hash_table_struct  *hash_table )
{
    if( hash_table->size > 0 )
        FREE( hash_table->table );
}

/* ----------------------------- MNI Header -----------------------------------
@NAME       : delete_hash_table
@INPUT      : hash_table
@OUTPUT     : 
@RETURNS    : Status
@DESCRIPTION: Deletes the given hash table.
@METHOD     : 
@GLOBALS    : 
@CALLS      : 
@CREATED    :                      David MacDonald
@MODIFIED   : 
---------------------------------------------------------------------------- */

public   void  delete_hash_table(
    hash_table_struct  *hash_table )
{
    int                 i;
    hash_entry_struct   *entry, *next;

    for( i = 0;  i < hash_table->size;  ++i )
    {
        entry = hash_table->table[i];

        while( entry != NULL )
        {
            next = entry->next;
            FREE( entry );
            entry = next;
        }
    }

    delete_hash_table_list( hash_table );
}

/* ----------------------------- MNI Header -----------------------------------
@NAME       : hash_function
@INPUT      : hash_table
            : key
@OUTPUT     : 
@RETURNS    : an index into the hash table.
@DESCRIPTION: Hashes the key to create an index into the table.  Uses
              the multiplicative hash method from Corman book on algorithms.
@METHOD     : 
@GLOBALS    : 
@CALLS      : 
@CREATED    :                      David MacDonald
@MODIFIED   : 
---------------------------------------------------------------------------- */

private   int  hash_function(
    hash_table_struct   *hash_table,
    int                 key )
{
    int    index;
    Real   v;

    v = (Real) key * HASH_FUNCTION_CONSTANT;

    index = (int) (FRACTION(v) * (Real) hash_table->size);

    return( index );
}

/* ----------------------------- MNI Header -----------------------------------
@NAME       : lookup
@INPUT      : hash_table
            : key
@OUTPUT     : 
@RETURNS    : a pointer to a pointer to the hash table entry
@DESCRIPTION: Looks up the given key in the hash table, and returns a pointer
            : to a pointer to the entry, suitable for inserting or deleting.
@METHOD     : 
@GLOBALS    : 
@CALLS      : 
@CREATED    :                      David MacDonald
@MODIFIED   : 
---------------------------------------------------------------------------- */

private   hash_entry_struct  **lookup(
    hash_table_struct  *hash_table,
    int                key )
{
    int                 i;
    hash_entry_struct   **ptr_to_entry;

    i = hash_function( hash_table, key );

    ptr_to_entry = &hash_table->table[i];

    while( *ptr_to_entry != NULL && (*ptr_to_entry)->key != key )
        ptr_to_entry = &(*ptr_to_entry)->next;

    return( ptr_to_entry );
}

/* ----------------------------- MNI Header -----------------------------------
@NAME       : insert_in_hash_table
@INPUT      : hash_table
            : key
            : data_ptr
@OUTPUT     : 
@RETURNS    : Status
@DESCRIPTION: Inserts the data_ptr in the hash table.
@METHOD     : 
@GLOBALS    : 
@CALLS      : 
@CREATED    :                      David MacDonald
@MODIFIED   : 
---------------------------------------------------------------------------- */

public  void  insert_in_hash_table(
    hash_table_struct  *hash_table,
    int                key,
    void               *data_ptr )
{
    hash_entry_struct   **ptr_to_entry;
    hash_entry_struct   *entry;

    ptr_to_entry = lookup( hash_table, key );

    entry = *ptr_to_entry;

    if( entry == NULL )
    {
        ALLOC_VAR_SIZED_STRUCT( entry, char, hash_table->data_size );

        entry->key = key;
        entry->next = *ptr_to_entry;
        (void) memcpy( (void *) entry->data, data_ptr,
                       (size_t) hash_table->data_size );

        *ptr_to_entry = entry; 

        ++hash_table->n_entries;

        if( (Real) hash_table->n_entries / (Real) hash_table->size >
            hash_table->enlarge_threshold )
        {
            int   new_size;

            new_size = ROUND( (Real) hash_table->n_entries /
                              hash_table->new_density );
            increase_hash_table_size( hash_table, new_size );
        }
    }
    else
    {
        print_error( "Insert in hash table: entry already present: %d\n", key );
    }
}

/* ----------------------------- MNI Header -----------------------------------
@NAME       : lookup_in_hash_table
@INPUT      : hash_table
            : key
@OUTPUT     : data_ptr
@RETURNS    : TRUE if found
@DESCRIPTION: Lookups the given key in the hash table, copying back the
              data if found.
@METHOD     : 
@GLOBALS    : 
@CALLS      : 
@CREATED    :                      David MacDonald
@MODIFIED   : 
---------------------------------------------------------------------------- */

public  BOOLEAN  lookup_in_hash_table(
    hash_table_struct  *hash_table,
    int                key,
    void               *data_ptr )
{
    BOOLEAN             found;
    hash_entry_struct   **ptr_to_entry;
    hash_entry_struct   *entry;

    ptr_to_entry = lookup( hash_table, key );

    entry = *ptr_to_entry;

    if( entry == NULL )
    {
        found = FALSE;
    }
    else
    {
        if( data_ptr != NULL )
        {
            (void) memcpy( data_ptr, (void *) entry->data,
                           (size_t) hash_table->data_size );
        }

        found = TRUE;
    }

    return( found );
}

/* ----------------------------- MNI Header -----------------------------------
@NAME       : remove_from_hash_table
@INPUT      : hash_table
            : keys
@OUTPUT     : : data_ptr
@RETURNS    : TRUE if it existed in the table
@DESCRIPTION: Finds and removes the given data from the hash table, copying
              the data back.
@METHOD     : 
@GLOBALS    : 
@CALLS      : 
@CREATED    :                      David MacDonald
@MODIFIED   : 
---------------------------------------------------------------------------- */

public  BOOLEAN  remove_from_hash_table(
    hash_table_struct  *hash_table,
    int                key,
    void               *data_ptr )
{
    BOOLEAN             removed;
    hash_entry_struct   **ptr_to_entry;
    hash_entry_struct   *entry;

    ptr_to_entry = lookup( hash_table, key );

    entry = *ptr_to_entry;

    if( entry == NULL )
    {
        removed = FALSE;
    }
    else
    {
        if( data_ptr != NULL )
        {
            (void) memcpy( data_ptr, (void *) entry->data,
                           (size_t) hash_table->data_size );
        }

        *ptr_to_entry = entry->next;

        FREE( entry );

        removed = TRUE;
        --hash_table->n_entries;
    }

    return( removed );
}

/* ----------------------------- MNI Header -----------------------------------
@NAME       : move_hash_entries_to_new_table
@INPUT      : src           hash_table
@OUTPUT     : dest          hash_table
@RETURNS    : 
@DESCRIPTION: Moves the entries of one hash table to the other, without
            : reallocating them.  Used when the hash table size is increased.
@METHOD     : 
@GLOBALS    : 
@CALLS      : 
@CREATED    :                      David MacDonald
@MODIFIED   : 
---------------------------------------------------------------------------- */

private   void  move_hash_entries_to_new_table(
    hash_table_struct  *dest,
    hash_table_struct  *src )
{
    int                 i, hash;
    hash_entry_struct   *entry, *next;

    for( i = 0;  i < src->size;  ++i )
    {
        entry = src->table[i];

        while( entry != NULL )
        {
            next = entry->next;

            hash = hash_function( dest, entry->key );
            entry->next = dest->table[hash];
            dest->table[hash] = entry;
            ++dest->n_entries;

            entry = next;
        }

        src->table[i] = NULL;
    }
}

/* ----------------------------- MNI Header -----------------------------------
@NAME       : increase_hash_table_size
@INPUT      : hash_table
            : new_size
@OUTPUT     : 
@RETURNS    : Status
@DESCRIPTION: Increases the size of the hash table, by creating a new hash
            : table, moving over the entries, then assigning the new table to
            : the old one.
@METHOD     : 
@GLOBALS    : 
@CALLS      : 
@CREATED    :                      David MacDonald
@MODIFIED   : 
---------------------------------------------------------------------------- */

public   void  increase_hash_table_size(
    hash_table_struct   *hash_table,
    int                 new_size )
{
    hash_table_struct   new_table;

    initialize_hash_table( &new_table, new_size, hash_table->data_size,
                           hash_table->enlarge_threshold,
                           hash_table->new_density );

    move_hash_entries_to_new_table( &new_table, hash_table );

    delete_hash_table_list( hash_table );

    *hash_table = new_table;
}

/* ----------------------------- MNI Header -----------------------------------
@NAME       : initialize_hash_pointer
@INPUT      : ptr
@OUTPUT     : 
@RETURNS    : 
@DESCRIPTION: Initializes a pointer to the beginning of the hash table.  This is
            : used to step through the hash table to visit every entry.
@METHOD     : 
@GLOBALS    : 
@CALLS      : 
@CREATED    :                      David MacDonald
@MODIFIED   : 
---------------------------------------------------------------------------- */

public  void  initialize_hash_pointer(
    hash_table_pointer  *ptr )
{
    ptr->current_index = -1;
    ptr->current_entry = NULL;
}

/* ----------------------------- MNI Header -----------------------------------
@NAME       : get_next_hash_entry
@INPUT      : hash_table
            : ptr
@OUTPUT     : data_ptr
@RETURNS    : TRUE if one is found
@DESCRIPTION: Steps to the next entry in the hash table, updating the ptr,
            : and passing back the data ptr stored in that entry.
@METHOD     : 
@GLOBALS    : 
@CALLS      : 
@CREATED    :                      David MacDonald
@MODIFIED   : 
---------------------------------------------------------------------------- */

public  BOOLEAN  get_next_hash_entry(
    hash_table_struct   *hash_table,
    hash_table_pointer  *ptr,
    void                *data_ptr )
{
    BOOLEAN   found;

    if( ptr->current_entry != NULL )
        ptr->current_entry = ptr->current_entry->next;

    if( ptr->current_entry == NULL )
    {
        do
        {
            ++ptr->current_index;
        }
        while( ptr->current_index < hash_table->size &&
               hash_table->table[ptr->current_index] == NULL );

        if( ptr->current_index < hash_table->size )
            ptr->current_entry = hash_table->table[ptr->current_index];
    }

    found = (ptr->current_entry != NULL);

    if( found && data_ptr != NULL )
    {
        (void) memcpy( data_ptr, (void *) ptr->current_entry->data,
                       (size_t) hash_table->data_size );
    }

    return( found );
}

---