hashtree.c File Reference

---

Detailed Description

Merkle Hash tree implementation, not yet memory and speed optimized yet.

Hashtree can be used to build any hashtree. This could be a SHA1 tree or a tigertree for example.

To create a new hash tree, use the function hash_tree_new, save the returned pointer as the parent. Add new leaf nodes to the hash tree using hash_tree_append_leaf_node, pass the parent as an argument, save the returned pointer as parent again. When you are done adding leaf nodes, call hash_tree_finish. After this you can read parent->hash to read the calculated hash. If you are done with this tree, free the tree with hash_tree_destroy. Look at the function header description for a more detailed information about the arguments and the returned values.

Author:

Jeroen Asselman <jeroen@asselman.com>

Version:

1.5

Date:

2003-2004

#include "common.h"
#include "hashtree.h"
#include "if/core/nodes.h"
#include "lib/walloc.h"
#include "lib/override.h"

Functions
	RCSID ("$Id:hashtree.c, v 1.9 2005/06/25 01:37:39 daichik Exp $")
node_t *	node_new ()
	Create a new node.
void	node_destroy (node_t *node)
	Destory a node.
node_t *	find_free_leaf_node (node_t *node)
	Find a free leaf node.
node_t *	find_free_node (node_t *node)
	Find a free node.
void	hashtree_create_tree (node_t *start_node)
	Build a new hashtree with only left nodes.
void	hashtree_increase_depth (hashtree *tree)
	Increases the depth of the hashtree.
void	build_hash (hashtree *tree, node_t *node)
	Calculate hash.
gboolean	node_is_leaf_node (node_t *node)
	Check wether node is a leaf node.
gboolean	node_is_free_leaf_node (node_t *node)
	Check wether node is a free leaf node.
gboolean	node_is_free_node (node_t *node)
	Check wether node is a free node.
hashtree *	hashtree_new (gpointer(*hash_func)(gpointer, gpointer))
	Create a new hashtree.
void	hashtree_append_leaf_node (hashtree *tree, gpointer hash)
	Append leaf node to hash tree.
void	hashtree_finish (hashtree *tree)
	Finish the hashtree.
void	hashtree_destroy (hashtree *tree)
	Destroy the hashtree.
Variables
gint	blocks

---

Function Documentation

void build_hash (  hashtree *  tree, node_t *  node )

Calculate hash. Calculates the hash for the current node and its child node by using this function recursively. If a node has only a node to the left and no nodes to the right it will promote the to the left up one level without recalculating. Parameters: tree  is a pointer to the hashtree to perform this action on. node  is the node for which the hash should be calculated

node_t * find_free_leaf_node (  node_t *  node  )

Find a free leaf node. Searches the tree to find a free leaf node. Parameters: node  is a pointer to a node from which the search should be started. It will search all its childeren using recursion. Returns: a pointer to the free leaf node that is found, if no free leaf node could be found NULL will be returned.

node_t * find_free_node (  node_t *  node  )

Find a free node. Searches the tree to find a free node. Parameters: node  is a pointer to a node from which the search should be started. It will search all its children using recursion. Returns: a pointer to the free node that is found, if no free node could be found NULL is returned. The returned node could also be a free leaf node.

void hashtree_append_leaf_node (  hashtree *  tree, gpointer  hash )

Append leaf node to hash tree. Adds a new leaf node to the hashtree, if necesarry it will expand the hashtree to include the new leaf node. Parameters: tree  is a pointer to the hashtree to perform this action on. hash  is a pointer to a hash which should be included with the leaf node. This hash must be a pointer allocated with g_malloc as this hashtree will free this pointer with g_free later when the hashtree is destroyed.

void hashtree_create_tree (  node_t *  start_node  )

Build a new hashtree with only left nodes. Builds a new hashtree until node->depth == 0. Only the nodes at the left are build, all right nodes are NULL. Parameters: start_node  is a pointer to the node to which the new tree should be build. this function will use node->depth to determine how deep the tree should be build.

void hashtree_destroy (  hashtree *  tree  )

Destroy the hashtree. Destroys the hash tree and all its included node. This will free all memory used by the hashtree, including all hashes assigned to a node which was added with hashtree_append_leaf_node which will be freed using g_free Parameters: tree  is a pointer to the hashtree to perform this action on.

void hashtree_finish (  hashtree *  tree  )

Finish the hashtree. Calculates all internal hashes in the hashtree. Call this function when you are ready with adding leaf nodes to the hashtree. Parameters: tree  is a pointer to the hashtree to perform this action on.

void hashtree_increase_depth (  hashtree *  tree  )

Increases the depth of the hashtree. Increases the hash tree by adding a new parrent to the tree. Parameters: tree  is a pointer to the hashtree to perform this action on.

hashtree* hashtree_new (  gpointer(*  hash_func)(gpointer, gpointer)  )

Create a new hashtree. Initializes a new hashtree. Save the returned hashtree pointer which you need to pass to the other hashtree functions. Parameters: hash_func  a hash function which should be used to calculate the internal hash. The signature of the hash_func must be: gpointer *hash_func(gpointer hash1, gpointer hash2) The returned hash must be allocated with g_malloc() as this hashtree implementation will free it later with g_free(). Returns: a pointer to the new created hashtree.

void node_destroy (  node_t *  node  )

Destory a node. Destorys a node and all its child nodes using recursing, all memory assinged to this node will be freed, including an assigned hash. Parameters: node  is a pointer to the node that should be destroyed.

gboolean node_is_free_leaf_node (  node_t *  node  )  [inline]

Check wether node is a free leaf node. Parameters: node  is a pointer to the node which should be checked. Returns: a boolean which is true if the node is a free leaf node, false otherwise.

gboolean node_is_free_node (  node_t *  node  )  [inline]

Check wether node is a free node. Parameters: node  is a pointer to the node which should be checked. Returns: a boolean which is true if the node is a free node or a free leaf node, false otherwise.

gboolean node_is_leaf_node (  node_t *  node  )  [inline]

Check wether node is a leaf node. Parameters: node  is a pointer to the node which should be checked. Returns: a boolean which is true if the node is a leaf node, false otherwise.

node_t * node_new (   )

Create a new node. Creates a new node by allocating memory for it. Returns: a pointer to the newly created node.

RCSID (  "$Id:hashtree.  c, v 1.9 2005/06/25 01:37:39 daichik Exp $"  )

---

Variable Documentation

gint blocks

---