GLAST / LAT > DAQ and FSW > FSW > Doxygen Index> LDT / V0-5-2 > encdec / sun-gcc

Interface   Data Structures   File List   Data Fields   Globals  
g » glast » flight » SVC » source » LDT » V0-5-2 » LDT

BTREE.h File Reference

Binary Tree, interface file. More...


Classes

struct  _BTREE_node
 Definition of a node in a binary tree. More...
struct  _BTREE
 Context structure for a binary tree. More...

Defines

#define NULL   ((void *)(0))

Typedefs

typedef struct _BTREE_node BTREE_node
 Typedef for struct _BTREE_node.
typedef int(* BTREE_compare )(const void *key1, const void *key2)
 Comparison function used to sort the tree.
typedef void(* BTREE_destroy )(void *data)
 Call back function to destroy (freed) the data.
typedef struct _BTREE BTREE
 Typedef for struct _BTREE.

Functions

void BTREE_init (BTREE *tree, BTREE_destroy destroy)
 Initializes the context control structure.
void BTREE_free (BTREE *tree)
 Frees all the data associated with the specified tree.
int BTREE_insertL (BTREE *tree, BTREE_node *node, const void *data)
 Inserts the data as the left node of the specified node.
int BTREE_insertR (BTREE *tree, BTREE_node *node, const void *data)
 Inserts the data as the right node of the specified node.
void BTREE_removeL (BTREE *tree, BTREE_node *node)
 Removes the left node and all its branches.
void BTREE_removeR (BTREE *tree, BTREE_node *node)
 Removes the right node and all its branches.
int BTREE_merge (BTREE *merge, BTREE *left, BTREE *right, const void *data)
 Merges two trees into a single parent tree, adding the data of the merged tree.
static __inline int BTREE__size (BTREE *tree)
 Returns the size (number of nodes) in the tree.
static __inline BTREE_node * BTREE__root (BTREE *tree)
 Returns the root of the tree.
static __inline void * BTREE__data (BTREE_node *node)
 Returns the data associated with the specified node.
static __inline BTREE_node * BTREE__left (BTREE_node *node)
 Return the left node of the specified node.
static __inline BTREE_node * BTREE__right (BTREE_node *node)
 Return the right node of the specified node.
static __inline int BTREE__is_eob (BTREE_node *node)
 Tests if this node is a terminal node.
static __inline int BTREE__is_leaf (BTREE_node *node)
 Tests if this node is a leaf node.

Detailed Description

Binary Tree, interface file.

Author:
JJRussell - russell@slac.stanford.edu

CVS $Id

Warning:
In their current state, these routines are not fit for Flight use. They can be used in studies. However they malloc all over the place and involve recursive calling techniques, neither of is appropriate for Flight code.

Typedef Documentation

int BTREE_compare

Comparison function used to sort the tree.

Return values:
<0 if key1 < key2
=0 if key1 = key2
>0 if key1 > key2
Parameters:
key1 Pointer to the first data structure to be sorted
key2 Pointer to the second data structure to be sorted

BTREE_destroy

Call back function to destroy (freed) the data.

Parameters:
data The data to be destroyed (freed)

Function Documentation

void * BTREE__data ( BTREE_node *  node  )  [static]

Returns the data associated with the specified node.

Returns:
The data associate with the specified node
Parameters:
node The parent node.

References _BTREE_node::data.

int BTREE__is_eob ( BTREE_node *  node  )  [static]

Tests if this node is a terminal node.

Return values:
==0,not a terminal node
!=0,is a terminal node
Parameters:
node The node to test.

int BTREE__is_leaf ( BTREE_node *  node  )  [static]

Tests if this node is a leaf node.

Return values:
==0,not a leaf node
!=0,is a leaf node
Parameters:
node The node to test.

References _BTREE_node::left, and _BTREE_node::right.

BTREE_node * BTREE__left ( BTREE_node *  node  )  [static]

Return the left node of the specified node.

Returns:
The left node of the specified node.
Parameters:
node The parent node.

References _BTREE_node::left.

Referenced by BTREE_insertL().

BTREE_node * BTREE__right ( BTREE_node *  node  )  [static]

Return the right node of the specified node.

Returns:
The right node of the specified node.
Parameters:
node The parent node.

References _BTREE_node::right.

Referenced by BTREE_insertR().

BTREE_node * BTREE__root ( BTREE *  tree  )  [static]

Returns the root of the tree.

Returns:
The root of the tree
Parameters:
tree The binary tree

References _BTREE::root.

Referenced by BTREE_merge().

int BTREE__size ( BTREE *  tree  )  [static]

Returns the size (number of nodes) in the tree.

Returns:
The size (number of nodes) in the tree
Parameters:
tree The binary tree

References _BTREE::size.

Referenced by BTREE_insertL(), BTREE_insertR(), BTREE_merge(), BTREE_removeL(), and BTREE_removeR().

void BTREE_free ( BTREE *  tree  ) 

Frees all the data associated with the specified tree.

Parameters:
tree The root of the tree to free

References BTREE_removeL().

Referenced by BTREE_merge().

void BTREE_init ( BTREE *  tree,
BTREE_destroy  destroy 
)

Initializes the context control structure.

Parameters:
tree The binary tree context to initialize
destroy Callback function to free the nodes in a binary tree, may be NULL.

References _BTREE::destroy, _BTREE::root, and _BTREE::size.

Referenced by BTREE_merge().

int BTREE_insertL ( BTREE *  tree,
BTREE_node *  node,
const void *  data 
)

Inserts the data as the left node of the specified node.

Return values:
0,if successful
-1,if failure
Parameters:
tree The binary tree
node The parent node, may be NULL if this is the first node
data Pointer to the data to be inserted
Failure can occur if
  • node is specified as NULL, but the tree is not empty
  • the left node of node is already filled
  • allocation of a new node fails

References BTREE__left(), BTREE__size(), _BTREE_node::data, _BTREE_node::left, _BTREE_node::right, _BTREE::root, and _BTREE::size.

Referenced by BTREE_merge().

int BTREE_insertR ( BTREE *  tree,
BTREE_node *  node,
const void *  data 
)

Inserts the data as the right node of the specified node.

Return values:
0,if successful
-1,if failure
Parameters:
tree The binary tree
node The parent node, may be NULL if this is the first node
data Pointer to the data to be inserted
Failure can occur if
  • node is specified as NULL, but the tree is not empty
  • the right node of node is already filled
  • allocation of a new node fails

References BTREE__right(), BTREE__size(), _BTREE_node::data, _BTREE_node::left, _BTREE_node::right, _BTREE::root, and _BTREE::size.

int BTREE_merge ( BTREE *  merge,
BTREE *  left,
BTREE *  right,
const void *  data 
)

Merges two trees into a single parent tree, adding the data of the merged tree.

Returns:
Status
Parameters:
merge The merged tree
left The left tree to merge
right The right tree to merge
data The data to add

References BTREE__root(), BTREE__size(), BTREE_free(), BTREE_init(), BTREE_insertL(), _BTREE::destroy, _BTREE_node::left, _BTREE_node::right, _BTREE::root, and _BTREE::size.

void BTREE_removeL ( BTREE *  tree,
BTREE_node *  node 
)

Removes the left node and all its branches.

Parameters:
tree The binary tree
node The parent node

References BTREE__size(), BTREE_removeL(), BTREE_removeR(), _BTREE::destroy, _BTREE_node::left, _BTREE::root, and _BTREE::size.

Referenced by BTREE_free(), BTREE_removeL(), and BTREE_removeR().

void BTREE_removeR ( BTREE *  tree,
BTREE_node *  node 
)

Removes the right node and all its branches.

Parameters:
tree The binary tree
node The parent node

References BTREE__size(), BTREE_removeL(), BTREE_removeR(), _BTREE::destroy, _BTREE_node::right, _BTREE::root, and _BTREE::size.

Referenced by BTREE_removeL(), and BTREE_removeR().

Generated on Tue Nov 29 23:15:50 2011 by  doxygen 1.5.8