ckhash.c

CKHash is an implementation of Cuckoo Hashing that can receive the input in the form of strings dir

/*
** Copyright (C) 2005 Thai Computational Linguistics Laboratory (TCL)
** National Institute of Information and Communications Technology (NICT)
** Written by Canasai Kruengkrai <[e-mail]>
**
** This file is part of the `CKHash' library.
**
** This library is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 2 of the License, or
** (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/


#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>
#include "CKHash.h"

#define MAX_FUNCTION_SIZE 128
#define TRUE  1
#define FALSE 0
#define MALLOC_ERROR( str1, str2 ) fprintf( stderr, "MALLOC ERROR: In function `%s': Could not allocate memory for %s\n", str1, str2 ), exit( 1 )
#define MALLOC( type, n ) ( type * )malloc( ( n ) * sizeof( type ) )
#define CKH_INFINITY -999999999

void ckh_init( int a[], int function_size ) 
{
    int i;

    for( i = 0; i < function_size; i++ )
        a[i] = ( (int)rand() << 1 ) + 1;
}

void ckh_hash( unsigned long *h, int a[], int function_size, int shift, char *key )
{
    int i;

    *h = a[0]*( int )toascii( key[0] );

    for( i = 1; key[i] != '\0'; i++ )
        *h ^= ( a[ ( int )( i % function_size ) ]*( int )toascii( key[i] ) );

    *h = ( unsigned int )*h >> shift;
}

Dict *ckh_alloc_dict( int table_size )
{
    Dict *D;
    if( ( D = MALLOC( Dict, 1 ) ) == NULL )
        MALLOC_ERROR( "ckh_alloc_dict", "D" );
    D->size = 0;
    D->table_size = table_size;
    D->mean_size = 5 * ( 2 * table_size ) / 12;
    D->min_size = ( 2 * table_size ) / 5;
    D->shift = 32 - ( int )( log( table_size ) / log( 2 ) + 0.5 );
    D->max_chain = 4 + ( int )( 4 * log( table_size ) / log( 2 ) + 0.5 );

    if( ( D->T1 = MALLOC( Cell, table_size ) ) == NULL )
        MALLOC_ERROR( "ckh_alloc_dict", "D->T1" );
    if( ( D->T2 = MALLOC( Cell, table_size ) ) == NULL )
        MALLOC_ERROR( "ckh_alloc_dict", "D->T2" );

    D->function_size = MAX_FUNCTION_SIZE;
    if( ( D->a1 = MALLOC( int, D->function_size ) ) == NULL )
        MALLOC_ERROR( "ckh_alloc_dict", "D->a1" );
    if( ( D->a2 = MALLOC( int, D->function_size ) ) == NULL )
        MALLOC_ERROR( "ckh_alloc_dict", "D->a2" );

    ckh_init( D->a1, D->function_size );
    ckh_init( D->a2, D->function_size );

    int j;
    for( j = 0; j < D->table_size; j++ )
    {
         D->T1[j].key = D->T2[j].key = NULL;
         D->T1[j].value = D->T2[j].value = 0;
    }

    return( D );
}

Dict *ckh_construct_dict( int min_size )
{
    srand( time( NULL ) );
    return ckh_alloc_dict( min_size );
}

int ckh_rehash_insert( Dict *D, char *key, int value )
{
    unsigned long hkey;
    int j;
    Cell x, temp;

    if( ( x.key = MALLOC( char, strlen( key ) + 1 ) ) == NULL )
        MALLOC_ERROR( "ckh_rehash_insert", "x.key" );


    strcpy( x.key, key );
    x.value = value;

    for( j = 0; j < D->max_chain; j++ ) 
    {
        ckh_hash( &hkey, D->a1, D->function_size, D->shift, x.key );
        temp = D->T1[hkey];
        D->T1[hkey] = x;
        if( temp.key == NULL ) 
            return( TRUE );

        x = temp;
        ckh_hash( &hkey, D->a2, D->function_size, D->shift, x.key );
        temp = D->T2[hkey];
        D->T2[hkey] = x;
        if( temp.key == NULL ) 
            return( TRUE );

        x = temp;
    }

    for( j = 0; j < D->table_size; j++ )
    {
         D->T1[j].key = D->T2[j].key = NULL;
         D->T1[j].value = D->T2[j].value = 0;
    }

    ckh_init( D->a1, D->function_size );
    ckh_init( D->a2, D->function_size );

    return( FALSE );
} 

void ckh_rehash( Dict *D, int new_size )
{
    Dict *D_new;
    int k;

    D_new = ckh_alloc_dict( new_size );

    for( k = 0; k < D->table_size; k++ ) 
    {
        if( ( D->T1[k].key != NULL ) && ( !ckh_rehash_insert( D_new, D->T1[k].key, D->T1[k].value ) ) )
        { 
            k=-1; 
            continue; 
        }
        if( ( D->T2[k].key != NULL ) && ( !ckh_rehash_insert( D_new, D->T2[k].key, D->T2[k].value ) ) )
            k=-1;
    }

    free( D->T1 );
    free( D->T2 );

    D_new->size = D->size;
    *D = *D_new;
    free( D_new );
}

int ckh_insert( Dict *D, char *key, int value )
{
    unsigned long h1, h2; 
    int j;
    Cell x, temp;

    /*
    ** if element already in D then replace and return
    */
    ckh_hash( &h1, D->a1, D->function_size, D->shift, key );
    if( D->T1[h1].key != NULL )
        if( !strcmp( D->T1[h1].key, key ) )
        return( FALSE );

    ckh_hash( &h2, D->a2, D->function_size, D->shift, key );
    if( D->T2[h2].key != NULL )
        if( !strcmp( D->T2[h2].key, key ) )
        return( FALSE );

    /*
    ** else insert new element in D
    */
    if( ( x.key = MALLOC( char, strlen( key ) + 1 ) ) == NULL )
        MALLOC_ERROR( "ckh_insert", "x.key" );
    strcpy( x.key, key );
    x.value = value;

    for( j = 0; j < D->max_chain; j++ ) 
    {
        temp = D->T1[h1];
        D->T1[h1] = x;
        if( temp.key == NULL ) 
        {
            D->size++;
            if( D->table_size < D->size ) 
                ckh_rehash( D, 2*D->table_size );
            return( TRUE );
        }

        x = temp;
        ckh_hash( &h2, D->a2, D->function_size, D->shift, x.key );
        temp = D->T2[h2];
        D->T2[h2] = x;
        if( temp.key == NULL ) 
        {
            D->size++;
            if( D->table_size < D->size ) 
                ckh_rehash( D, 2*D->table_size );
            return( TRUE );
        }

        x = temp;
        ckh_hash( &h1, D->a1, D->function_size, D->shift, x.key );
    }
 
    /*
    ** Forced rehash
    */
    if( D->size < D->mean_size ) 
        ckh_rehash( D, D->table_size );
    else
        ckh_rehash( D, 2*D->table_size );

    ckh_insert( D, x.key, x.value );

    return( TRUE );
}

int ckh_lookup( Dict *D, char *key )
{
    unsigned long hkey;

    ckh_hash( &hkey, D->a1, D->function_size, D->shift, key );
    if( D->T1[hkey].key != NULL )
        if( !strcmp( D->T1[hkey].key, key ) )
            return( TRUE );

    ckh_hash( &hkey, D->a2, D->function_size, D->shift, key );
    if( D->T2[hkey].key != NULL )
        if( !strcmp( D->T2[hkey].key, key ) )
             return( TRUE );

    return( FALSE );
}

int ckh_delete( Dict *D, char *key )
{ 
    unsigned long hkey;

    ckh_hash( &hkey, D->a1, D->function_size, D->shift, key );
    if( D->T1[hkey].key != NULL )
        if( !strcmp( D->T1[hkey].key, key ) )
        {
            free( D->T1[hkey].key );
            D->T1[hkey].key = NULL;
            D->size--;
            if( D->size < D->min_size ) 
                ckh_rehash( D, D->table_size/2 );
            return( TRUE );
        }

    ckh_hash( &hkey, D->a2, D->function_size, D->shift, key );
    if( D->T2[hkey].key != NULL )
        if( !strcmp( D->T2[hkey].key, key ) )
        {
            free( D->T2[hkey].key );
            D->T2[hkey].key = NULL;
            D->size--;
            if( D->size < D->min_size) 
                ckh_rehash( D, D->table_size/2 );
            return( TRUE );
        }

    return( FALSE );
}

int ckh_get( Dict *D, char *key ) 
{
    unsigned long hkey;

    ckh_hash( &hkey, D->a1, D->function_size, D->shift, key );
    if( D->T1[hkey].key != NULL )
        if( !strcmp( D->T1[hkey].key, key ) )
            return( D->T1[hkey].value );

    ckh_hash( &hkey, D->a2, D->function_size, D->shift, key );
    if( D->T2[hkey].key != NULL )
        if( !strcmp( D->T2[hkey].key, key ) )
             return( D->T2[hkey].value );

    return( CKH_INFINITY );
}

int ckh_increase_value( Dict *D, char *key )
{
    unsigned long hkey;

    ckh_hash( &hkey, D->a1, D->function_size, D->shift, key );
    if( D->T1[hkey].key != NULL )
        if( !strcmp( D->T1[hkey].key, key ) )
        {
            D->T1[hkey].value++;
            return( TRUE );
        }

    ckh_hash( &hkey, D->a2, D->function_size, D->shift, key );
    if( D->T2[hkey].key != NULL )
        if( !strcmp( D->T2[hkey].key, key ) )
        {
             D->T2[hkey].value++;
             return( TRUE );
        }
    return( FALSE );
}

int ckh_decrease_value( Dict *D, char *key )
{
    unsigned long hkey;

    ckh_hash( &hkey, D->a1, D->function_size, D->shift, key );
    if( D->T1[hkey].key != NULL )
        if( !strcmp( D->T1[hkey].key, key ) )
        {
            D->T1[hkey].value--;
            return( TRUE );
        }

    ckh_hash( &hkey, D->a2, D->function_size, D->shift, key );
    if( D->T2[hkey].key != NULL )
        if( !strcmp( D->T2[hkey].key, key ) )
        {
             D->T2[hkey].value--;
             return( TRUE );
        }
    return( FALSE );
}

Dict *ckh_destruct_dict( Dict *D )
{
    int j;

    for( j = 0; j < D->table_size; j++ )
    {
        if( D->T1[j].key != NULL )
            free( D->T1[j].key );
        if( D->T2[j].key != NULL )
            free( D->T2[j].key );
    }
    free( D->T1 );
    free( D->T2 );
    free( D->a1 );
    free( D->a2 );
    free( D );

    return( NULL );
}

void ckh_print( Dict *D )
{
    int j;

    for( j = 0; j < D->table_size; j++ )
    {
        if( D->T1[j].key != NULL )
            printf( "%s %d\n", D->T1[j].key, D->T1[j].value );

        if( D->T2[j].key != NULL )
            printf( "%s %d\n", D->T2[j].key, D->T2[j].value );
    }
}