Hash_Table.c

Go to the documentation of this file.

/* ############################ MALP License ############################## */
/* # Fri Jan 18 14:00:00 CET 2013                                         # */
/* # Copyright or (C) or Copr. Commissariat a l'Energie Atomique          # */
/* #                                                                      # */
/* # This software is governed by the CeCILL-C license under French law   # */
/* # and abiding by the rules of distribution of free software.  You can  # */
/* # use, modify and/ or redistribute the software under the terms of     # */
/* # the CeCILL-C license as circulated by CEA, CNRS and INRIA at the     # */
/* # following URL http://www.cecill.info.                                # */
/* #                                                                      # */
/* # The fact that you are presently reading this means that you have     # */
/* # had knowledge of the CeCILL-C license and that you accept its        # */
/* # terms.                                                               # */
/* #                                                                      # */
/* # Authors:                                                             # */
/* #   - BESNARD Jean-Baptiste jean-baptiste.besnard@cea.fr               # */
/* #                                                                      # */
/* ######################################################################## */
#include "Hash_Table.h"

//Basic Hash----------------------------------------------------------------------------------------------------
void Hash_Table_init_Internal( void *phi, uint64_t coll_avoid, uint64_t intern_payload_size )
{
        struct Hash_Table_Internal *h_intern = (struct Hash_Table_Internal *) phi;
        h_intern->count = 0;
        h_intern->lock = 0;
        Chained_List_init( &h_intern->next_pl,  coll_avoid, intern_payload_size );
}

void Hash_Table_release_Internal( void *phi )
{
        struct Hash_Table_Internal *h_intern = (struct Hash_Table_Internal *) phi;

        Chained_List_release(&h_intern->next_pl);

        h_intern->count = 0;
}

//coll_avoid is the number of elems (obvious isn't it ?)
void Hash_Table_init( struct Hash_Table *ht, size_t sizeof_payload, uint64_t table_size, uint8_t coll_avoid )
{

        ht->need_lock = 0;
        ht->sizeof_payload = sizeof_payload;
        ht->table_size = table_size;
        ht->coll_avoid = coll_avoid;

        ht->intern_payload_size = ( sizeof_payload - sizeof( struct Hash_Table_Internal) ) / ht->coll_avoid;

        //printf("Allocating a %.2f MB hashing table \n", (float)(sizeof_payload * table_size ) / (1024*1024) );
        ht->payload = malloc( table_size * sizeof_payload + table_size );

        if( !ht->payload ) {
                printf("Failled to alloc a %ld byte Hash table in %s at %d \n",table_size * sizeof_payload , __FILE__, __LINE__);
                abort();
        }

        int i = 0;

        for( i = 0 ; i < table_size ; i++) {
                Hash_Table_init_Internal( (char *)ht->payload + (i * ht->sizeof_payload), ht->coll_avoid, ht->intern_payload_size );
        }

}


void Hash_Table_release(  struct Hash_Table *ht, void (*free_f)(void *) )
{
        int i = 0;

        struct Hash_Table_Internal *phi = NULL;


        if( free_f )
                Hash_Table_walkthrought( ht, free_f);



        for( i = 0 ; i < ht->table_size ; i++) {
                phi = (struct Hash_Table_Internal *)( (char *)ht->payload + (i * ht->sizeof_payload) );
                if( ht->coll_avoid <= phi->count )
                        Hash_Table_release_Internal( phi );
        }

        free( ht->payload );
        
        memset( ht, 0, sizeof( struct Hash_Table ) );

}



static inline void * get_cell_at( struct Hash_Table *ht, uint64_t key )
{

        uint64_t hash = MALP_Trace_crc64( (char *)&key, sizeof( uint64_t) );

        //  printf(" key : %lld || size : %lld || hash: %llu || cell : %lld\n", key, ht->table_size, hash, hash % (uint64_t)ht->table_size);

        return ( (char *)ht->payload + (  ((uint64_t)hash % (uint64_t)ht->table_size)  * ht->sizeof_payload)  );
}



void Hash_Table_lock_cell( struct Hash_Table *ht, uint64_t key )
{


        struct Hash_Table_Internal *phi = NULL;

        phi = (struct Hash_Table_Internal *)get_cell_at( ht, key );

        MALP_Spinlock_lock(&phi->lock);

}

void Hash_Table_unlock_cell( struct Hash_Table *ht, uint64_t key )
{
        struct Hash_Table_Internal *phi = NULL;

        phi = (struct Hash_Table_Internal *)get_cell_at( ht, key );

        MALP_Spinlock_unlock(&phi->lock);
}



void * Hash_Table_get( struct Hash_Table *ht, uint64_t key , void *extra_arg, int (*test_func)(void *, uint64_t, void * ))
{

        struct Hash_Table_Internal *phi = NULL;

        int i = 0;

        if( !test_func )
                return NULL;

        if( ht->table_size == 0 )
                return NULL;

        phi = (struct Hash_Table_Internal *)get_cell_at( ht, key );

        //this scheme allows some collisions with low overhead
        if( ht->need_lock )
                MALP_Spinlock_lock( &phi->lock );


        void *payload_ptr = ( (struct Hash_Table_Internal *)phi + 1);
        void *ptr = NULL;

        for( i = 0 ; (i < phi->count) && (i < ht->coll_avoid) ; i++ ) {
                //printf("INTERN %d \n", i);
                ptr = (char *)payload_ptr + (i * ht->intern_payload_size);

                if( test_func( ptr , key, extra_arg ) ) {
                        if( ht->need_lock )
                                MALP_Spinlock_unlock( &phi->lock );
                        return ptr;
                }
        }

        int cc_len = Chained_List_count( &phi->next_pl );

        struct chained_list_view clv;
        chained_list_view_init( &clv );

        for( i = 0 ; i < cc_len ; i++) {
                //printf("LIST %d \n", i);
                ptr = Chained_List_get_nth_seq( &phi->next_pl , &clv , i);

                if( test_func( ptr , key, extra_arg ) ) {
                        if( ht->need_lock )
                                MALP_Spinlock_unlock( &phi->lock );
                        return ptr;
                }
        }

        if( ht->need_lock )
                MALP_Spinlock_unlock( &phi->lock );
        return NULL;
}


void * Hash_Table_push_unique( struct Hash_Table *ht, void *payload , uint64_t key, void *extra_arg, int (*test_func)(void *, uint64_t, void * ) )
{
        void *ret = Hash_Table_get( ht, key , extra_arg, test_func);

        if( !ret ) {
                ret = Hash_Table_push( ht, payload , key );
        } else {
                memcpy( ret, payload, ht->intern_payload_size );
        }

        return ret;
}


void * Hash_Table_push(  struct Hash_Table *ht, void *payload , uint64_t key )
{

        struct Hash_Table_Internal *phi = NULL;
        void *dest_ptr = NULL;

        phi = (struct Hash_Table_Internal *)get_cell_at( ht, key );

        if( ht->need_lock )
                MALP_Spinlock_lock( &phi->lock );

        void *payload_ptr = phi + 1;


        if( phi->count < ht->coll_avoid ) {
                dest_ptr = (char *)payload_ptr + (phi->count * ht->intern_payload_size);

                memcpy( dest_ptr, payload, ht->intern_payload_size );
        } else {
                dest_ptr = Chained_List_push( &phi->next_pl, payload);
                //printf("New collision of %d \n", phi->count);
        }

        phi->count++;

        if( ht->need_lock )
                MALP_Spinlock_unlock( &phi->lock );

        return dest_ptr;
}




void Hash_Table_walkthrought_cond( struct Hash_Table *ht, void (*action)(void *), int (*test_func)(void *, void * ), void *test_value )
{

        int i = 0, j = 0, k=0;
        struct Hash_Table_Internal *phi;
        void *payload = NULL;

        if( !action )
                return;

        for( i = 0 ; i < ht->table_size ; i++) {
                phi = (struct Hash_Table_Internal *)( (char* )ht->payload + (i * ht->sizeof_payload ) );

                if( phi->count == 0 )
                        continue;

                payload = ( phi + 1 );

                for( j = 0 ; j < ht->coll_avoid && j < phi->count ; j++ ) {
                        //printf("Pl over %d \n", j);

                        if( !test_func ) {
                                (action) ( (char *)payload + (j * ht->intern_payload_size) );
                        } else if( (test_func )( (char *)payload + (j * ht->intern_payload_size), test_value ) ) {
                                (action) ( (char *)payload + (j * ht->intern_payload_size) );
                        }

                }



                int cc_len = Chained_List_count( &phi->next_pl );

                struct chained_list_view clv;
                chained_list_view_init( &clv );


                for( k = 0 ; k < cc_len ; k++) {
                        //printf("%d is cclen doing %d \n", cc_len, k);
                        payload = Chained_List_get_nth_seq( &phi->next_pl, &clv , k);

                        if( !test_func ) {
                                (action) ( payload  );
                        } else if( (test_func )( payload , test_value ) ) {
                                (action) ( payload );
                        }
                }
        }
}

void Hash_Table_walkthrought_cond_2p( struct Hash_Table *ht, void *second_arg, void (*action)(void *, void *), int (*test_func)(void *, void * ), void *test_value )
{

        if( !action )
                return;

        int i = 0, j = 0, k=0;
        struct Hash_Table_Internal *phi;
        void *payload = NULL;

        for( i = 0 ; i < ht->table_size ; i++) {
                phi = (struct Hash_Table_Internal *)( (char* )ht->payload + (i * ht->sizeof_payload ) );

                if( phi->count == 0 )
                        continue;

                payload = ( phi + 1 );

                for( j = 0 ; j < ht->coll_avoid && j < phi->count ; j++ ) {
                        //printf("Pl over %d \n", j);
                        if( !test_func ) {
                                (action) ( (char *)payload + (j * ht->intern_payload_size), second_arg );
                        } else if( (test_func )( (char *)payload + (j * ht->intern_payload_size), test_value ) ) {
                                (action) ( (char *)payload + (j * ht->intern_payload_size), second_arg  );
                        }
                }
                
                        int cc_len = Chained_List_count( &phi->next_pl );

                        struct chained_list_view clv;
                        chained_list_view_init( &clv );

                        for( k = 0 ; k < cc_len ; k++) {
                                //printf("%d is cclen doing %d \n", cc_len, k);
                                payload = Chained_List_get_nth_seq( &phi->next_pl, &clv  , k);

                                if( !test_func ) {
                                        (action) ( payload , second_arg);
                                } else if( (test_func )( payload , test_value ) ) {
                                        (action) ( payload, second_arg);
                                }
                        }

        }
}


void* Hash_Table_get_an_entry( struct Hash_Table *ht )
{
        int i = 0, j = 0;
        struct Hash_Table_Internal *phi;
        void *payload = NULL;

        for( i = 0 ; i < ht->table_size ; i++) {
                phi = (struct Hash_Table_Internal *)( (char* )ht->payload + (i * ht->sizeof_payload ) );

                if( phi->count == 0 )
                        continue;

                payload = ( phi + 1 );

                return ( (char *)payload + (j * ht->intern_payload_size) );
        }

        return NULL;
}


void Hash_Table_walkthrought( struct Hash_Table *ht, void (*action)(void *) )
{

        int i = 0, j = 0, k=0;
        struct Hash_Table_Internal *phi;
        void *payload = NULL;

        for( i = 0 ; i < ht->table_size ; i++) {
                phi = (struct Hash_Table_Internal *)( (char* )ht->payload + (i * ht->sizeof_payload ) );

                if( phi->count == 0 )
                        continue;

                payload = ( phi + 1 );


                for( j = 0 ; j < ht->coll_avoid && j < phi->count ; j++ ) {
                        (action) ( (char *)payload + (j * ht->intern_payload_size) );
                }


                int cc_len = Chained_List_count( &phi->next_pl );

                struct chained_list_view clv;
                chained_list_view_init( &clv );

                for( k = 0 ; k < cc_len ; k++) {
                        //printf("%d is cclen doing %d \n", cc_len, k);
                        payload = Chained_List_get_nth_seq( &phi->next_pl, &clv  , k);
                        (action) ( payload  );
                }
        }
}


void Hash_Table_walkthrought_2p( struct Hash_Table *ht, void *second_arg,  void (*action)(void *, void *) )
{

        int i = 0, j = 0, k=0;
        struct Hash_Table_Internal *phi;
        void *payload = NULL;

        for( i = 0 ; i < ht->table_size ; i++) {
                phi = (struct Hash_Table_Internal *)( (char* )ht->payload + (i * ht->sizeof_payload ) );

                if( phi->count == 0 )
                        continue;

                payload = ( phi + 1 );

                for( j = 0 ; j < ht->coll_avoid && j < phi->count ; j++ ) {
                        //printf("Pl over %d \n", j);
                        (action) ( (char *)payload + (j * ht->intern_payload_size), second_arg );
                }
                
                        int cc_len = Chained_List_count( &phi->next_pl );

                        struct chained_list_view clv;
                        chained_list_view_init( &clv );

                        for( k = 0 ; k < cc_len ; k++) {
                                //printf("%d is cclen doing %d \n", cc_len, k);
                                payload = Chained_List_get_nth_seq( &phi->next_pl, &clv  , k);
                                (action) ( payload , second_arg );
                        }
        }
}


void ___Hash_Table_count_by_walk(void *elem, void *pcounter)
{
        uint64_t *counter = (uint64_t *)pcounter;
        *counter = *counter + 1;
}

uint64_t Hash_Table_count_by_walk(struct Hash_Table *ht)
{
        uint64_t ret = 0;

        Hash_Table_walkthrought_2p( ht, &ret, ___Hash_Table_count_by_walk );

        return ret;
}


void Hash_Table_walkthrought_3p( struct Hash_Table *ht, void *second_arg, void *third_arg, void (*action)(void *, void *, void *) )
{

        int i = 0, j = 0, k=0;
        struct Hash_Table_Internal *phi;
        void *payload = NULL;

        for( i = 0 ; i < ht->table_size ; i++) {
                phi = (struct Hash_Table_Internal *)( (char* )ht->payload + (i * ht->sizeof_payload ) );

                if( phi->count == 0 )
                        continue;

                payload = ( phi + 1 );

                for( j = 0 ; j < ht->coll_avoid && j < phi->count ; j++ ) {
                        //printf("Pl over %d \n", j);
                        (action) ( (char *)payload + (j * ht->intern_payload_size), second_arg, third_arg );
                }

                int cc_len = Chained_List_count( &phi->next_pl );

                struct chained_list_view clv;
                chained_list_view_init( &clv );

                for( k = 0 ; k < cc_len ; k++) {
                        //printf("%d is cclen doing %d \n", cc_len, k);
                        payload = Chained_List_get_nth_seq( &phi->next_pl, &clv  , k);
                        (action) ( payload , second_arg , third_arg);
                }

        }
}