eg_bbtree.h File Reference

---

Detailed Description

Definition in file eg_bbtree.h.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <float.h>
#include <math.h>
#include "eg_io.h"
#include "eg_config.h"
#include "eg_macros.h"
#include "eg_mempool.h"
#include "eg_compare.h"

Include dependency graph for eg_bbtree.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	EGbbtree_t
	Balance Binary Tree structure. More...
struct	EGbbtreeNode_t
	Balance Binary Tree Node structure. More...
#define	EG_BBTREE_DEBUGL   10
	Macro controling the debuging level for this structure.
typedef EGbbtree_t	EGbbtree_t
	Balance Binary Tree structure.
typedef EGbbtreeNode_t	EGbbtreeNode_t
	Balance Binary Tree Node structure.
EGbbtreeNode_t *	EGbbtreeAdd (EGbbtree_t *tree, void *elem)
	Add a new element to the tree.
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.
EGbbtreeNode_t *	EGbbtreeSuccessor (EGbbtreeNode_t *node)
	, get the successor of the current node.
void	EGfreeBbtree (void *tree)
	Defeault destructor.
EGbbtree_t *	EGnewBbtree (EGmemPool_t *mem, EGcompare_f compare)
	Defeault constructor.

---

Define Documentation

#define EG_BBTREE_DEBUGL   10

Macro controling the debuging level for this structure. Definition at line 56 of file eg_bbtree.h.

---

Typedef Documentation

typedef struct EGbbtree_t EGbbtree_t

Balance Binary Tree structure. Description: This structure has a pointer to a root node, the number of nodes in the tree structure, and a pointer to a comparison function used to build the tree and to add/remove elements from the tree, and a pointer to a memory manager from where the local memory will be draw.

typedef struct EGbbtreeNode_t EGbbtreeNode_t

Balance Binary Tree Node structure. Description: This structure stores a pointer to satellite data, the depth of the node, and pointers to it parent and sons.

---

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:

int EGbbtreeClear (  EGbbtree_t *  tree, EGfree_f  dataFree )  [inline]

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 173 of file eg_bbtree.h.

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

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 221 of file eg_bbtree.h.

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 )  [inline]

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 268 of file eg_bbtree.h.

EGbbtreeNode_t* EGbbtreeMax (  EGbbtree_t *  tree  )  [inline]

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 416 of file eg_bbtree.h.

EGbbtreeNode_t* EGbbtreeMin (  EGbbtree_t *  tree  )  [inline]

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 398 of file eg_bbtree.h.

EGbbtreeNode_t* EGbbtreePredecessor (  EGbbtreeNode_t *  node  )  [inline]

, 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 334 of file eg_bbtree.h.

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:

EGbbtreeNode_t* EGbbtreeSuccessor (  EGbbtreeNode_t *  node  )  [inline]

, 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 366 of file eg_bbtree.h.

void EGfreeBbtree (  void *  tree  )  [inline]

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 127 of file eg_bbtree.h.

EGbbtree_t* EGnewBbtree (  EGmemPool_t *  mem, EGcompare_f  compare )  [inline]

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 108 of file eg_bbtree.h.

---