eg_bbtree.c File Reference

---

Detailed Description

Definition in file eg_bbtree.c.

#include "eg_bbtree.h"

Include dependency graph for eg_bbtree.c:

Go to the source code of this file.

#define	EGbbtreeLeftDepth(__node)   ((__node)->left?(__node)->left->depth:0U)
	Macro to access the depth of the left child of a nodo.
#define	EGbbtreeRightDepth(__node)   ((__node)->right?(__node)->right->depth:0U)
	Macro to access the depth of the right child of a nodo.
EGbbtreeNode_t *	EGbbtreeAdd (EGbbtree_t *tree, void *elem)
	Add a new element to the tree.
static int	EGbbtreeBalance (EGbbtree_t *tree, EGbbtreeNode_t **p_node)
	This function balances a tree by rotations, starting in the given node and working upwards.
int	EGbbtreeClear (EGbbtree_t *tree, EGfree_f dataFree)
	Given an initialized bbtree, left it at it initial state (just after EGnewBbtree).
int	EGbbtreeClearMP (EGbbtree_t *tree, EGfreeMP_f dataFree, EGmemPool_t *datamem)
	Given an initialized bbtree, left it at it initial state (just after EGnewBbtree).
void	EGbbtreeDisplay (EGbbtree_t *tree, EGdisplay_f dataDisplay, FILE *file)
	Display function for the tree.
EGbbtreeNode_t *	EGbbtreeFind (EGbbtree_t *tree, const void *elem)
	Find an element in the tree.
EGbbtreeNode_t *	EGbbtreeMax (EGbbtree_t *tree)
	Return the maximum element in the tree.
EGbbtreeNode_t *	EGbbtreeMin (EGbbtree_t *tree)
	Return the minimum element in the tree.
EGbbtreeNode_t *	EGbbtreePredecessor (EGbbtreeNode_t *node)
	, get the predecessor of the current node.
int	EGbbtreeRemove (EGbbtree_t *tree, EGbbtreeNode_t *node)
	Delete an element from the tree.
static int	EGbbtreeRotateLeft (EGbbtree_t *tree, EGbbtreeNode_t **p_node)
	Rotate the given node to the left, and update the correspondig depths.
static int	EGbbtreeRotateRight (EGbbtree_t *tree, EGbbtreeNode_t **p_node)
	Rotate the given node to the right, and update the correspondig depths.
EGbbtreeNode_t *	EGbbtreeSuccessor (EGbbtreeNode_t *node)
	, get the successor of the current node.
static int	EGbbtreeUpdateDepth (EGbbtreeNode_t *const p_node)
	Update the depth of a node, this function assumes that the depth of the sons of the node are correctly set-up.
void	EGfreeBbtree (void *tree)
	Defeault destructor.
EGbbtree_t *	EGnewBbtree (EGmemPool_t *mem, EGcompare_f compare)
	Defeault constructor.

---

Define Documentation

#define EGbbtreeLeftDepth (  __node   )     ((__node)->left?(__node)->left->depth:0U)

Macro to access the depth of the left child of a nodo. Definition at line 223 of file eg_bbtree.c.

#define EGbbtreeRightDepth (  __node   )     ((__node)->right?(__node)->right->depth:0U)

Macro to access the depth of the right child of a nodo. Definition at line 227 of file eg_bbtree.c.

---

Function Documentation

EGbbtreeNode_t* EGbbtreeAdd (  EGbbtree_t *  tree, void *  elem )

Add a new element to the tree. Parameters: tree  EGbbtree_t* pointer to the tree where we will add the new element. elem  void* pointer to the element to be added to the tree. Returns: EGbbtreeNode_t* pointer to the newly created node containing the inserted element, if the eement already existed, we return NULL. Description: Add a new element (according to the comopare function) to the tree and maintain the balance on the tree. If the element is repeated on the tree, it will return NULL. Definition at line 401 of file eg_bbtree.c. Here is the call graph for this function:

static int EGbbtreeBalance (  EGbbtree_t *  tree, EGbbtreeNode_t **  p_node )  [inline, static]

This function balances a tree by rotations, starting in the given node and working upwards. Parameters: p_node  EGbbtreeNode_t** pointer to the pointer of the tree to rotate. tree  EGbbtree_t* pointer to the tree where the rotation is being performed. Returns: zero on success, non-zero otherwise. Definition at line 325 of file eg_bbtree.c. Here is the call graph for this function:

int EGbbtreeClear (  EGbbtree_t *  tree, EGfree_f  dataFree )

Given an initialized bbtree, left it at it initial state (just after EGnewBbtree). Parameters: tree  EGbbtree_t* pointer to the tree to be reseted to its initial state. dataFree  free function for the satelite data. Returns: zero on success, non-zero otherwise. Description: Set the structure to its initiial state, free all internal data to the memory pool, and apply the given free function to the satelite data. Definition at line 102 of file eg_bbtree.c.

int EGbbtreeClearMP (  EGbbtree_t *  tree, EGfreeMP_f  dataFree, EGmemPool_t *  datamem )

Given an initialized bbtree, left it at it initial state (just after EGnewBbtree). Parameters: tree  EGbbtree_t* pointer to the tree to be reseted to its initial state. dataFree  free function for the satelite data. datamem  pointer to the memory pool used to allocate the satelite data. Returns: zero on success, non-zero otherwise. Description: Set the structure to its initiial state, free all internal data to the memory pool, and apply the given free function to the satelite data. Definition at line 150 of file eg_bbtree.c.

void EGbbtreeDisplay (  EGbbtree_t *  tree, EGdisplay_f  dataDisplay, FILE *  file )

Display function for the tree. Parameters: tree  EGbbtree_t* pointer to the tree to be displayed. dataDisplay  EGdisplay_f function that display the internal data (can be NULL). file  FILE* pointer to the output stream. Description: Display information of the tree, it's nodes, and the internal data. Definition at line 659 of file eg_bbtree.c.

EGbbtreeNode_t* EGbbtreeFind (  EGbbtree_t *  tree, const void *  elem )

Find an element in the tree. Parameters: tree  EGbbtree_t* pointer to the tree where we will perform the search. elem  void* pointer to the structure that we are looking for. Returns: EGbbtreeNode_t pointer to the node in the tree containing the element, if no such node exists, return NULL. Description: This function will searxh for the element in the tree that satisfy compare(elem,found)==0. Definition at line 196 of file eg_bbtree.c.

EGbbtreeNode_t* EGbbtreeMax (  EGbbtree_t *  tree  )

Return the maximum element in the tree. Parameters: tree  EGbbtree_t* pointer to the tree to be displayed. Returns: pointer to the treeNode pointing to the maximum element. Description: Given a tree, return the maximum eloement on the tree (pointer to the connector). Definition at line 729 of file eg_bbtree.c.

EGbbtreeNode_t* EGbbtreeMin (  EGbbtree_t *  tree  )

Return the minimum element in the tree. Parameters: tree  EGbbtree_t* pointer to the tree to be displayed. Returns: pointer to the treeNode pointing to the minimum element. Description: Given a tree, return the minimum eloement on the tree (pointer to the connector). Definition at line 711 of file eg_bbtree.c.

EGbbtreeNode_t* EGbbtreePredecessor (  EGbbtreeNode_t *  node  )

, get the predecessor of the current node. Parameters: node  EGbbtreeNode_t* pointer to the node to wich we are looking for its predecessor. Returns: EGbbtreeNode_t* pointer to the predecessor of the given node. Description: This function try to find the predecessor of the given node, if no such node exists, return NULL. Definition at line 455 of file eg_bbtree.c.

int EGbbtreeRemove (  EGbbtree_t *  tree, EGbbtreeNode_t *  node )

Delete an element from the tree. Parameters: tree  EGbbtree_t* pointer to the tree from where we will eliminate the given node. node  EGbbtreeNode_t* pointer to the node of the tree to be eliminated. Returns: zero on success, non-zero otherwise. Description: Given an initialized tree, and a ode pertaianing to it (the code won't check this), it will eliminate the node form the tree. If an error occour, it will return non-zero. Note that this funcion won't free the internal satelite data of the given node, this should be done by the caller of the function __BEFORE__ using this function. Definition at line 524 of file eg_bbtree.c. Here is the call graph for this function:

static int EGbbtreeRotateLeft (  EGbbtree_t *  tree, EGbbtreeNode_t **  p_node )  [inline, static]

Rotate the given node to the left, and update the correspondig depths. Parameters: p_node  EGbbtreeNode_t** pointer to the pointer of the tree to rotate. tree  EGbbtree_t* pointer to the tree where the rotation is being performed. Returns: zero on success, non-zero otherwise. Definition at line 286 of file eg_bbtree.c. Here is the call graph for this function:

static int EGbbtreeRotateRight (  EGbbtree_t *  tree, EGbbtreeNode_t **  p_node )  [inline, static]

Rotate the given node to the right, and update the correspondig depths. Parameters: p_node  EGbbtreeNode_t** pointer to the pointer of the tree to rotate. tree  EGbbtree_t* pointer to the tree where the rotation is being performed. Returns: zero on success, non-zero otherwise. Definition at line 248 of file eg_bbtree.c. Here is the call graph for this function:

EGbbtreeNode_t* EGbbtreeSuccessor (  EGbbtreeNode_t *  node  )

, get the successor of the current node. Parameters: node  EGbbtreeNode_t* pointer to the node to wich we are looking for its successor. Returns: EGbbtreeNode_t* pointer to the successor of the given node. Description: This function try to find the successor of the given node, if no such node exists, return NULL. Definition at line 487 of file eg_bbtree.c.

static int EGbbtreeUpdateDepth (  EGbbtreeNode_t *const   p_node  )  [inline, static]

Update the depth of a node, this function assumes that the depth of the sons of the node are correctly set-up. Definition at line 232 of file eg_bbtree.c.

void EGfreeBbtree (  void *  tree  )

Defeault destructor. Parameters: tree  EGbbtree_t pointer to the tree to be freed. Description: Given an initialized bbtree, this function free al internal data to the local memory pool, but won't free the satelite data. Definition at line 56 of file eg_bbtree.c.

EGbbtree_t* EGnewBbtree (  EGmemPool_t *  mem, EGcompare_f  compare )

Defeault constructor. Parameters: mem  EGmemPool_t* pointer to the memory pool from where we will alocate all memory for internal structures. compare  EGcompare_f pointer to a comparison function, used to mantain the tree structure. Returns: EGbbtree_t pointer to an initialized bbtree. Description: Given a memory pool, and a comparison function, we create an empty (and initialized) bbtree that works on elements comparable by the given function. Definition at line 37 of file eg_bbtree.c.

---