Hash_Tree.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_Tree.h"

#include "Debug.h"
#include "CRC64.h"

/*
 * Hash tree node
 */

void Hash_Tree_node_init(struct Hash_Tree_node *node,
                         struct Hash_Tree_node *parent,
                         void *request,
                         size_t request_size,
                         void *payload,
                         size_t payload_size )
{
        node->parent = parent;

        Chained_List_init(&node->children, 5, sizeof(struct Hash_Tree_node *) );

        node->request_size = request_size;
        node->request_entry = malloc( request_size );
        
        if(!node->request_entry)
        {
                PERROR("malloc");
                exit(1);
        }

        memcpy( node->request_entry, request, request_size );

        node->request_entry_key = MALP_Trace_crc64((char*)node->request_entry, request_size);

        node->payload = malloc( payload_size );

        if(!node->payload)
        {
                PERROR("malloc");
                exit(1);
        }

        memcpy( node->payload, payload, payload_size );
}


void Hash_Tree_node_release( struct Hash_Tree_node *node )
{
        Chained_List_release(&node->children);

        free(node->request_entry);
        free(node->payload);

        memset(node, 0, sizeof(struct Hash_Tree_node ) );
}

void __Hash_Tree_node_release( void *node )
{
        Hash_Tree_node_release( (struct Hash_Tree_node *)node );        
}


void Hash_Tree_node_push_child( struct Hash_Tree_node *node, 
                                struct Hash_Tree_node *child)
{
        Chained_List_push( &node->children, (void*)&child);
}

/*
 * Hash Tree
 */


int Hash_Tree_test_func( void *elem, uint64_t key, void *arg )
{
        struct Hash_Tree_node *node = (struct Hash_Tree_node *)elem;

        if( key == node->request_entry_key )
        {
                if( arg )
                {
                        if( !memcmp( arg, node->request_entry, node->request_size ) )
                        {
                                return 1;
                        }
                        else
                        {
                                return 0;
                        }

                }
                else
                {
                        return 1;
                }
        }

        return 0;
}

void Hash_Tree_init( struct Hash_Tree *htr, size_t request_size, size_t payload_size )
{
        Hash_Table_init(&htr->nodes, sizeof(struct Hash_Tree_node_cell),
                        4142, HASH_TREE_NODE_COLL_AVOID );
        
        Hash_Table_use_lock( &htr->nodes );

        htr->payload_size = payload_size;
        htr->request_size = request_size;

        htr->node_count = 0;
        htr->lock = 0;
}


void Hash_Tree_call_free(void *elem, void *pfree_func)
{
        void (*free_func)(void *) = (void (*)(void *))pfree_func;

        if( free_func )
        {
                (free_func)(elem);
        }
}

void Hash_Tree_release( struct Hash_Tree *htr, void (*free_func)(void *) )
{
        if( free_func )
                Hash_Table_walkthrought_2p( &htr->nodes, free_func, Hash_Tree_call_free );

        Hash_Table_release( &htr->nodes, __Hash_Tree_node_release );
        memset( htr, 0, sizeof(struct Hash_Tree) );
}

int Hash_Tree_elem_exits( struct Hash_Tree *htr, void *request )
{
        uint64_t key = MALP_Trace_crc64((char *)request, htr->request_size);
        return (Hash_Table_get( &htr->nodes , key , request , Hash_Tree_test_func) != NULL)?1:0;
}

struct Hash_Tree_node * Hash_Tree_get_elem( struct Hash_Tree *htr, void *request )
{
        uint64_t key = MALP_Trace_crc64((char *)request, htr->request_size);
        return (struct Hash_Tree_node *)Hash_Table_get( &htr->nodes , key , request , Hash_Tree_test_func);
}

struct Hash_Tree_node * Hash_Tree_push( struct Hash_Tree *htr, void *parent_request, void *new_request, void *payload )
{

        struct Hash_Tree_node *parent =  NULL;
        struct Hash_Tree_node *elem =  NULL;
        
        if( parent_request )
        {
                parent = Hash_Tree_get_elem( htr, parent_request );
                
                /* Could not push as parent does not exist */
                if( !parent )
                        return NULL;
        }
        
        MALP_Spinlock_lock(&htr->lock);

        elem = Hash_Tree_get_elem( htr, new_request );

        if( elem )
        {
                if( elem->parent != parent )
                {
                        printf("Warning changing element parent in Hash_Tree\n");
                        elem->parent = parent;
                }

                memcpy(elem->payload, payload, htr->payload_size);
                MALP_Spinlock_unlock(&htr->lock);
                return elem;
        }

        struct Hash_Tree_node node;

        uint64_t key = MALP_Trace_crc64((char *)new_request, htr->request_size);

        Hash_Tree_node_init(&node, parent, new_request, htr->request_size, payload, htr->payload_size );
        
        elem = (struct Hash_Tree_node * )Hash_Table_push( &htr->nodes, &node , key );

        if( parent )
                Hash_Tree_node_push_child( parent, elem );

        htr->node_count++;

        MALP_Spinlock_unlock(&htr->lock);

        return elem;
}


void _Hash_Tree_walk_all_nodes_call_handler(void *p_node, void *phandler, void *extra_arg)
{
        struct Hash_Tree_node *node = (struct Hash_Tree_node *)p_node;
        void (*handler)(void *, void *) = (void (*)(void *, void *)) phandler;

        if(node)
        {
                (handler)(Hash_Tree_node_payload(node), extra_arg);
        }
}


void _Hash_Tree_walk_all_nodes(struct Hash_Tree *htr, void (*handler)(void *, void *), void *extra_arg)
{
        Hash_Table_walkthrought_3p( &htr->nodes, (void *)handler, (void *)extra_arg,  _Hash_Tree_walk_all_nodes_call_handler );
}

void _Hash_Tree_walk_topological(struct Hash_Tree *htr, struct Hash_Tree_node *node, void (*handler)(void *, void *), void *extra_arg)
{
        if(!node)
                return;

        (handler)(Hash_Tree_node_payload(node), extra_arg);

        int child_count =  Hash_Tree_node_get_child_count( node );

        int i;

        for( i = 0 ; i < child_count ; i++ )
        {
                struct Hash_Tree_node *child = Hash_Tree_node_get_nth_child( node, i );
                _Hash_Tree_walk_topological(htr, child, handler, extra_arg);
        }

}


void Hash_Tree_walk(struct Hash_Tree *htr, void *starting_point_request, void (*handler)(void *, void *), void *extra_arg)
{
        if( !handler )
                return;


        if( starting_point_request == NULL )
        {
                _Hash_Tree_walk_all_nodes( htr, handler, extra_arg);
        }
        else
        {
                struct Hash_Tree_node *starting_node = Hash_Tree_get_elem( htr, starting_point_request);
                if( starting_node )
                {
                        _Hash_Tree_walk_topological( htr, starting_node, handler, extra_arg );
                }
        }
}