Hash_Tree.h

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               # */
/* #                                                                      # */
/* ######################################################################## */

#ifndef HASH_TREE_H
#define HASH_TREE_H


#ifdef __cplusplus
extern "C"
{
#endif

#include "Hash_Table.h"
#include "Spinlock.h"
#include "Chained_List.h"

/*
 * Hash tree nodes
 */


struct Hash_Tree_node
{
        uint64_t request_entry_key;

        void *request_entry;
        size_t request_size;

        void *payload;
        
        /* Tree links */
        struct Hash_Tree_node *parent;
        struct Chained_List children;
};

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 );

void 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);


static inline struct Hash_Tree_node * Hash_Tree_node_get_parent(  struct Hash_Tree_node *node )
{
        return  node?node->parent:NULL;
}

static inline int Hash_Tree_node_get_child_count(  struct Hash_Tree_node *node )
{
        return  node?Chained_List_count(&node->children):0;
}

static inline struct Hash_Tree_node * Hash_Tree_node_get_nth_child(  struct Hash_Tree_node *node, int id )
{
        if(!node )
                return NULL;
        

        struct Hash_Tree_node **ret = (struct Hash_Tree_node **)Chained_List_get_nth(&node->children, id);

        if(!ret)
                return NULL;
        
        return *ret;
}

static inline void * Hash_Tree_node_payload( struct Hash_Tree_node *node )
{
        return node?node->payload:NULL;
}

static inline void * Hash_Tree_node_request( struct Hash_Tree_node *node )
{
        return node?node->request_entry:NULL;
}


/*
 * Hash table handling
 */

#define HASH_TREE_NODE_COLL_AVOID 2

struct Hash_Tree_node_cell
{
        struct Hash_Table_Internal ___;
        struct Hash_Tree_node nodes[HASH_TREE_NODE_COLL_AVOID];
};


struct Hash_Tree
{
        struct Hash_Table nodes;    
        size_t payload_size;        
        size_t request_size;        
        uint64_t node_count;        
        MALP_Spinlock lock;         
};

void Hash_Tree_init( struct Hash_Tree *htr, size_t request_size, size_t payload_size );
void Hash_Tree_release( struct Hash_Tree *htr, void (*free_func)(void *elemp) );

int Hash_Tree_elem_exits( struct Hash_Tree *htr, void *prequest );

struct Hash_Tree_node * Hash_Tree_get_elem( struct Hash_Tree *htr, void *prequest );
struct Hash_Tree_node * Hash_Tree_push( struct Hash_Tree *htr, void *parent_request, void *new_request, void *payload );

void Hash_Tree_walk(struct Hash_Tree *htr, void *starting_point_request, void (*handler)(void *, void *), void *extra_arg);

#ifdef __cplusplus
}
#endif


#endif /* HASH_TREE_H */