Data Structures | Files | Defines | Typedefs | Functions | Variables

EGeBTree

Data Structures

struct  EGeBTree_t
 Basic structure of a tree node, note that a node in a tree is in itself a (sub)tree. More...

Files

file  eg_ebtree.ex.c
file  eg_ebtree.h

Defines

#define EG_EBTREE_LEFT   1
 Left Child Index.
#define EG_EBTREE_PARENT   0
 Parent index.
#define EG_EBTREE_RIGHT   2
 Right Child Index.
#define EGeBTreeAddLeft(__parent, __child)
 Add a left __child to a node in a tree.
#define EGeBTreeAddRight(__parent, __child)
 Add a right child to a node in a tree.
#define EGeBTreeClear(__tn)
 Free any internal memory (not allocated by the user) related to this structure.
#define EGeBTreeCut(__member)
 Cut the given node from the tree containing it (and so create a sub-tree).
#define EGeBTreeDel(__leaf)
 Erase a leaf node from a tree.
#define EGeBTreeGetFirst(__node)
 return the first node in the (sub-)tree (according to the in-order).
#define EGeBTreeGetLast(__node)
 return the last node in the (sub-)tree (according to the in-order).
#define EGeBTreeGetLeft(__member)   ((__member)->cn[EG_EBTREE_LEFT])
#define EGeBTreeGetNext(__node)
 return the successor of the given node in it's tree according to the in-order ordering.
#define EGeBTreeGetParent(__member)   ((__member)->cn[EG_EBTREE_PARENT])
#define EGeBTreeGetPrev(__node)
 return the predecesor of the given node in it's tree according to the in-order ordering.
#define EGeBTreeGetRight(__member)   ((__member)->cn[EG_EBTREE_RIGHT])
#define EGeBTreeGetRoot(__member)
 return the root of the tree containing the given tree node.
#define EGeBTreeInit(__tn)   (*(__tn) = (EGeBTree_t){{0,0,0}})
 Initialize a tree structure. It let it as a tree containing only itself. and allocate any internal memory (not allocated by the user).
#define EGeBTreeReplace(__old, __rep)
 Replace a node in a tree.
#define EGeBTreeReset(__tn)   EGeBTreeInit(__tn)
 Let a tree just as after an init call.

Typedefs

typedef struct EGeBTree_t EGeBTree_t
 Basic structure of a tree node, note that a node in a tree is in itself a (sub)tree.

Functions

static int ebt_display (EGioFile_t *out_f, EGeBTree_t *root)
 display the given tree in-order.
static int ebt_parseargs (int argc, char **argv, unsigned int *s, unsigned int *z)
 parse external arguments.
static void ebt_usage (char const *const program)
 usage function, if we give the wrong number of parameters, we return an error message and print a help.
int main (int argc, char **argv)
 Tester program for the projection structure and functions.

Variables

static int verbose = 0

Detailed Description

Here we define a minimal implementation of binary trees, using the philosophy of embeded structures. Operations as adding nodes (in any position of the tree), deleting nodes, splicing trees, and separating sub-trees are performed in O(1) time. To obtain this running time information such as depth is not stored in the nodes of the tree.

-2005-07-08

Define Documentation

#define EG_EBTREE_LEFT   1

Left Child Index.

Definition at line 50 of file eg_ebtree.h.

#define EG_EBTREE_PARENT   0

Parent index.

Definition at line 46 of file eg_ebtree.h.

#define EG_EBTREE_RIGHT   2

Right Child Index.

Definition at line 54 of file eg_ebtree.h.

#define EGeBTreeAddLeft (   __parent,
  __child 
)
Value:
({\
  EGeBTree_t*const __EGeparent = (__parent);\
  EGeBTree_t*const __EGechild = (__child);\
  __EGeparent->cn[EG_EBTREE_LEFT] ? (fprintf(stderr,"Can't add left __child to "#__parent" because it already has a left __child, in %s:%s:%d\n",__func__,__FILE__,__LINE__),1): (__EGeparent->cn[EG_EBTREE_LEFT] = __EGechild, __EGechild->cn[EG_EBTREE_PARENT] = __EGeparent, 0);})

Add a left __child to a node in a tree.

Parameters:
__parent node to wich we will add a left child
__child node to be a left child
Returns:
zero on success, non zero otherwise.
Examples:
eg_ebtree.ex.c.

Definition at line 105 of file eg_ebtree.h.

Referenced by main().

#define EGeBTreeAddRight (   __parent,
  __child 
)
Value:
({\
  EGeBTree_t*const __EGeparent = (__parent);\
  EGeBTree_t*const __EGechild = (__child);\
  __EGeparent->cn[EG_EBTREE_RIGHT] ? (fprintf(stderr,"Can't add right __child to "#__parent" because it already has a right __child, in %s:%s:%d\n",__func__,__FILE__,__LINE__),1): (__EGeparent->cn[EG_EBTREE_RIGHT] = __EGechild, __EGechild->cn[EG_EBTREE_PARENT] = __EGeparent, 0);})

Add a right child to a node in a tree.

Parameters:
__parent node to wich we will add a right child
__child node to be a right child
Returns:
zero on success, non zero otherwise.
Examples:
eg_ebtree.ex.c.

Definition at line 116 of file eg_ebtree.h.

Referenced by main().

#define EGeBTreeClear (   __tn  ) 

Free any internal memory (not allocated by the user) related to this structure.

Parameters:
__tn tree to be cleared.
Note:
Note that this function is not really needed, it is provided for completness, but is defined as nothing.

Definition at line 97 of file eg_ebtree.h.

#define EGeBTreeCut (   __member  ) 
Value:
({\
  EGeBTree_t*const __EGeroot = (__member);\
  EGeBTree_t*const __EGepar = __EGeroot->cn[EG_EBTREE_PARENT];\
  if(__EGepar) \
  {\
    __EGeroot->cn[EG_EBTREE_PARENT] = 0; \
    if(__EGepar->cn[EG_EBTREE_LEFT] == __EGeroot)\
      __EGepar->cn[EG_EBTREE_LEFT] = 0;\
    else __EGepar->cn[EG_EBTREE_RIGHT] = 0;\
  }\
  0;})

Cut the given node from the tree containing it (and so create a sub-tree).

Parameters:
__member 
Returns:
zero on success, non-zero otherwise.
Examples:
eg_ebtree.ex.c.

Definition at line 292 of file eg_ebtree.h.

Referenced by main().

#define EGeBTreeDel (   __leaf  ) 
Value:
({\
  EGeBTree_t*const __EGelf = (__leaf);\
  EGeBTree_t*const __EGepar = __EGelf->cn[EG_EBTREE_PARENT];\
  int __rval = 0;\
  if(__EGelf->cn[EG_EBTREE_LEFT] || __EGelf->cn[EG_EBTREE_RIGHT]) __rval = 1;\
  else if(__EGepar)\
  {\
    if(__EGepar->cn[EG_EBTREE_LEFT] == __EGelf) \
      __EGepar->cn[EG_EBTREE_LEFT] = 0;\
    else __EGepar->cn[EG_EBTREE_RIGHT] = 0;\
  }\
  __rval;})

Erase a leaf node from a tree.

Parameters:
__leaf node to be erased from the tree.
Returns:
zero on success, non-zero otherwise, a failure means that the given node wasn't a leaf in the tree.
Examples:
eg_ebtree.ex.c.

Definition at line 273 of file eg_ebtree.h.

Referenced by main().

#define EGeBTreeGetFirst (   __node  ) 
Value:
({\
  EGeBTree_t* __EGecn = (__node);\
  while(__EGecn->cn[EG_EBTREE_LEFT]) __EGecn = __EGecn->cn[EG_EBTREE_LEFT];\
  __EGecn;})

return the first node in the (sub-)tree (according to the in-order).

Parameters:
__node pointer to a node of the tree.
Returns:
first node in the tree.
Examples:
eg_ebtree.ex.c.

Definition at line 252 of file eg_ebtree.h.

Referenced by ebt_display().

#define EGeBTreeGetLast (   __node  ) 
Value:
({\
  EGeBTree_t* __EGecn = (__node);\
  while(__EGecn->cn[EG_EBTREE_RIGHT]) __EGecn = __EGecn->cn[EG_EBTREE_RIGHT];\
  __EGecn;})

return the last node in the (sub-)tree (according to the in-order).

Parameters:
__node pointer to a node of the tree.
Returns:
last node in the tree.
Examples:
eg_ebtree.ex.c.

Definition at line 262 of file eg_ebtree.h.

Referenced by ebt_display().

#define EGeBTreeGetLeft (   __member  )     ((__member)->cn[EG_EBTREE_LEFT])
Returns:
a pointer to the left child of the given node, if NULL, then this node don;t have a left child
Parameters:
__member node for wich we are looking for the left child.
Returns:
pointer to the left child node in the tree.

Definition at line 135 of file eg_ebtree.h.

#define EGeBTreeGetNext (   __node  ) 
Value:
({\
  EGeBTree_t* __EGexn = (__node);\
  EGeBTree_t* __EGecn = __EGexn->cn[EG_EBTREE_RIGHT];\
  if(__EGecn) while(__EGecn->cn[EG_EBTREE_LEFT])\
      __EGecn = __EGecn->cn[EG_EBTREE_LEFT];\
  else do __EGecn = __EGexn->cn[EG_EBTREE_PARENT]; while(__EGecn && \
      __EGecn->cn[EG_EBTREE_RIGHT] == __EGexn && (__EGexn = __EGecn));\
  __EGecn;})

return the successor of the given node in it's tree according to the in-order ordering.

Parameters:
__node element for wich we want the successor.
Returns:
pointer to the successor, if NULL is returned, then there is no successor for the given node.
Note:
The in-order considered here is the one depicted in the next figure:

\[ \psset{unit=1cm,arrows=->} \begin{pspicture}(-1,-1)(7,3) \rput(0,0){\circlenode{a}{1}} \rput(1,1){\circlenode{b}{2}} \rput(2,0){\circlenode{c}{3}} \rput(3,2){\circlenode{d}{4}} \rput(4,0){\circlenode{e}{5}} \rput(5,1){\circlenode{f}{6}} \rput(6,0){\circlenode{g}{7}} \ncline{b}{a} \ncline{b}{c} \ncline{d}{b} \ncline{d}{f} \ncline{f}{e} \ncline{f}{g} \end{pspicture} \]

In this figure the numbers in the nodes represent the in-order order.
Examples:
eg_ebtree.ex.c.

Definition at line 204 of file eg_ebtree.h.

Referenced by ebt_display().

#define EGeBTreeGetParent (   __member  )     ((__member)->cn[EG_EBTREE_PARENT])
Returns:
a pointer to the parent of the given node, if NULL, then this node is the root node of the tree.
Parameters:
__member node for wich we are looking for the father.
Returns:
pointer to the parent node in the tree.

Definition at line 127 of file eg_ebtree.h.

#define EGeBTreeGetPrev (   __node  ) 
Value:
({\
  EGeBTree_t* __EGexn = (__node);\
  EGeBTree_t* __EGecn = __EGexn->cn[EG_EBTREE_LEFT];\
  if(__EGecn) while(__EGecn->cn[EG_EBTREE_RIGHT])\
      __EGecn = __EGecn->cn[EG_EBTREE_RIGHT];\
  else do __EGecn = __EGexn->cn[EG_EBTREE_PARENT]; while(__EGecn && \
      __EGecn->cn[EG_EBTREE_LEFT] == __EGexn && (__EGexn = __EGecn));\
  __EGecn;})

return the predecesor of the given node in it's tree according to the in-order ordering.

Parameters:
__node element for wich we want the predecesor.
Returns:
pointer to the predecesor, if NULL is returned, then there is no predecesor for the given node.
Note:
The in-order considered here is the one depicted in the next figure:

\[ \psset{unit=1cm,arrows=->} \begin{pspicture}(-1,-1)(7,3) \rput(0,0){\circlenode{a}{1}} \rput(1,1){\circlenode{b}{2}} \rput(2,0){\circlenode{c}{3}} \rput(3,2){\circlenode{d}{4}} \rput(4,0){\circlenode{e}{5}} \rput(5,1){\circlenode{f}{6}} \rput(6,0){\circlenode{g}{7}} \ncline{b}{a} \ncline{b}{c} \ncline{d}{b} \ncline{d}{f} \ncline{f}{e} \ncline{f}{g} \end{pspicture} \]

In this figure the numbers in the nodes represent the in-order order.
Examples:
eg_ebtree.ex.c.

Definition at line 238 of file eg_ebtree.h.

Referenced by ebt_display().

#define EGeBTreeGetRight (   __member  )     ((__member)->cn[EG_EBTREE_RIGHT])
Returns:
a pointer to the right child of the given node, if NULL, then this node don;t have a right child
Parameters:
__member node for wich we are looking for the right child.
Returns:
pointer to the right child node in the tree.

Definition at line 143 of file eg_ebtree.h.

#define EGeBTreeGetRoot (   __member  ) 
Value:
({\
  EGeBTree_t*__EGeroot = (__member);\
  while(__EGeroot->cn[EG_EBTREE_PARENT]) \
    __EGeroot = __EGeroot->cn[EG_EBTREE_PARENT];\
  __EGeroot;})

return the root of the tree containing the given tree node.

Parameters:
__member node for wich we are looking for the tree-root.
Returns:
pointer to the root of the tree containing the given node.

Definition at line 150 of file eg_ebtree.h.

#define EGeBTreeInit (   __tn  )     (*(__tn) = (EGeBTree_t){{0,0,0}})

Initialize a tree structure. It let it as a tree containing only itself. and allocate any internal memory (not allocated by the user).

Parameters:
__tn tree to initialize.
Note:
Note that the definition of EGeBTree_t does not need to initialize any memory, and basically reset and init do exactly the same, while clear do nothing.
Examples:
eg_ebtree.ex.c.

Definition at line 81 of file eg_ebtree.h.

Referenced by main().

#define EGeBTreeReplace (   __old,
  __rep 
)
Value:
({\
  EGeBTree_t*const __EGeold = (__old);\
  EGeBTree_t*const __EGenew = (__rep);\
  EGeBTree_t*const __EGepar = __EGeold->cn[EG_EBTREE_PARENT];\
  EGeBTree_t*const __EGelft = __EGeold->cn[EG_EBTREE_LEFT];\
  EGeBTree_t*const __EGergt = __EGeold->cn[EG_EBTREE_RIGHT];\
  *__EGenew = *__EGeold;\
  if(__EGepar)\
  {\
    if(__EGepar->cn[EG_EBTREE_LEFT] == __EGeold)\
      __EGepar->cn[EG_EBTREE_LEFT] = __EGenew;\
    else __EGepar->cn[EG_EBTREE_RIGHT] = __EGenew;\
  }\
  if(__EGelft) __EGelft->cn[EG_EBTREE_PARENT] = __EGenew;\
  if(__EGergt) __EGergt->cn[EG_EBTREE_PARENT] = __EGenew;\
  0;})

Replace a node in a tree.

Parameters:
__old node to be replaced.
__rep node to be used as replacement.
Returns:
zero on success, non-zero otherwise.
Examples:
eg_ebtree.ex.c.

Definition at line 162 of file eg_ebtree.h.

Referenced by main().

#define EGeBTreeReset (   __tn  )     EGeBTreeInit(__tn)

Let a tree just as after an init call.

Parameters:
__tn tree to reset.
Note:
Note that this macro is provided onll for completeness, because there is no need for it.

Definition at line 89 of file eg_ebtree.h.

Typedef Documentation

typedef struct EGeBTree_t EGeBTree_t

Basic structure of a tree node, note that a node in a tree is in itself a (sub)tree.

Function Documentation

static int ebt_display ( EGioFile_t *  out_f,
EGeBTree_t *  root 
) [static]

display the given tree in-order.

Parameters:
out_f output stream.
root tree to display.
Returns:
zero on success, non-zero otherwise.
Examples:
eg_ebtree.ex.c.

Definition at line 96 of file eg_ebtree.ex.c.

References EGeBTreeGetFirst, EGeBTreeGetLast, EGeBTreeGetNext, EGeBTreeGetPrev, EGioPrintf(), and verbose.

Referenced by main().

Here is the call graph for this function:

static int ebt_parseargs ( int  argc,
char **  argv,
unsigned int *  s,
unsigned int *  z 
) [static]

parse external arguments.

Parameters:
argc int, number of parameters to process.
argv char**, array of the parameters.
z unsigned int*, pointer to the number of elements in the tree.
s unsigned int*, pointer to the seed.
Returns:
zero on success, non-zero otherwise
Examples:
eg_ebtree.ex.c.

Definition at line 51 of file eg_ebtree.ex.c.

References ebt_usage(), and verbose.

Referenced by main().

Here is the call graph for this function:

static void ebt_usage ( char const *const   program  )  [static]

usage function, if we give the wrong number of parameters, we return an error message and print a help.

Parameters:
program Name of the command from comand-line
Examples:
eg_ebtree.ex.c.

Definition at line 32 of file eg_ebtree.ex.c.

Referenced by ebt_parseargs().

int main ( int  argc,
char **  argv 
)

Tester program for the projection structure and functions.

Parameters:
argc int number of comand line options
argv char** array of strings of length argc contaianing the command line arguments.
Returns:
zero on success, non-zero otherwise
Description:
This function create a set of 'z' elements in a bbtree, and print the resulting tree, perform some random operations.

Definition at line 131 of file eg_ebtree.ex.c.

References CHECKRVALG, ebt_display(), ebt_parseargs(), EGeBTreeAddLeft, EGeBTreeAddRight, EGeBTreeCut, EGeBTreeDel, EGeBTreeInit, EGeBTreeReplace, EGfree, EGioClose(), EGioOpen(), EGioPrintf(), EGlib_info(), EGlib_version(), EGsetLimits(), EGsigSet, EGsMalloc, and verbose.

Here is the call graph for this function:

Variable Documentation

int verbose = 0 [static]

Definition at line 26 of file eg_ebtree.ex.c.

Referenced by ebt_display(), ebt_parseargs(), and main().

Generated on Thu Mar 29 2012 10:10:24 for EGlib by  doxygen 1.7.1