dynamically-allocated binary tree

Macros
#define	zTreeClass(node_t, data_t)
	generate binary tree class. More...
#define	zTreeClassMethod(node_t, data_t, init, destroy)
#define	zHeapClass(node_t, data_t)
#define	zHeapClassMethod(node_t, data_t, init, destroy)
#define	zTreeIsEmpty(t)   ( (t)->size == 0 )
#define	zTreeIsLeaf(t)   ( !(t)->child[0] && !(t)->child[1] )
#define	_zTreeParentID(n)   ( (n)->parent->child[0] == (n) ? 0 : ( (n)->parent->child[1] == (n) ? 1 : -1 ) )
#define	_zTreeInitHeapMask(t, mask)
#define	zTreeInit(node_t, node)   node_t##Init( node )
#define	zTreeDestroy(node_t, tree)   node_t##Destroy( tree )
#define	zTreeNodeAlloc(node_t, val)   node_t##NodeAlloc( val )
#define	zTreeAddComplete(node_t, tree, val)   node_t##AddComplete( tree, val )
#define	zTreeUpHeap(node_t, tree, node, cmp, util)   node_t##UpHeap( tree, node, cmp, util )
#define	zTreeAddHeap(node_t, tree, val, cmp, util)   node_t##AddHeap( tree, val, cmp, util )
#define	zTreeDownHeap(node_t, node, cmp, util)   node_t##DownHeap( node, cmp, util )
#define	zTreeDeleteHeap(node_t, tree, cmp, util)   node_t##DeleteHeap( tree, cmp, util )
#define	zTreeHeapify(node_t, tree, cmp, util)   node_t##Heapify( tree, cmp, util )

Detailed Description

Macro Definition Documentation

zTreeClass

#define zTreeClass	(		node_t,
			data_t
	)

Value:

typedef struct __##node_t{\
  struct __##node_t *parent;\
  struct __##node_t *child[2];\
  uint size;\
  data_t data;\
} node_t;\
\
__EXPORT node_t *node_t##Init(node_t *node);\
__EXPORT void node_t##Destroy(node_t *tree);\
__EXPORT node_t *node_t##NodeAlloc(data_t *val)

generate binary tree class.

A macro zTreeClass() generates a new binary tree class and prototypes of some associated methods.

The tree class tree_t defines a node that contains data with the type data_t and two pointers to children.

The methods to be generated are (node_t)Init(), (node_t)Destroy(), and (node_t)NodeAlloc(), where (node_t)s are replaced by the actual type name. The body implementation of those functions are generated by calling zTreeClassMethod(node_t, data_t);

The methods (node_t)UpHeap, (node_t)AddHeap(), (node_t)DownHeap, (node_t)DeleteHeap(), and (node_t)Heapify() are additionally defined by calling zHeapClass() and zHeapClassMethod() instead of zTreeClass() and zTreeClassMethod().

zTreeClassMethod

#define zTreeClassMethod	(		node_t,
			data_t,
			init,
			destroy
	)

zHeapClass

#define zHeapClass	(		node_t,
			data_t
	)

Value:

zTreeClass(node_t,data_t); \
__EXPORT node_t *node_t##AddComplete(node_t *tree, data_t *val);\
__EXPORT node_t *node_t##UpHeap(node_t *tree, node_t *node, int (* cmp)(node_t*,node_t*,void*), void *util);\
__EXPORT node_t *node_t##AddHeap(node_t *tree, data_t *val, int (* cmp)(node_t*,node_t*,void*), void *util);\
__EXPORT node_t *node_t##DownHeap(node_t *node, int (* cmp)(node_t*,node_t*,void*), void *util);\
__EXPORT node_t *node_t##DeleteHeap(node_t *tree, int (* cmp)(node_t*,node_t*,void*), void *util);\
__EXPORT void node_t##Heapify(node_t *tree, int (* cmp)(node_t*,node_t*,void*), void *util)

zHeapClassMethod

#define zHeapClassMethod	(		node_t,
			data_t,
			init,
			destroy
	)

zTreeIsEmpty

#define zTreeIsEmpty

(

t

)

( (t)->size == 0 )

zTreeIsLeaf

#define zTreeIsLeaf

(

t

)

( !(t)->child[0] && !(t)->child[1] )

_zTreeParentID

#define _zTreeParentID

(

n

)

( (n)->parent->child[0] == (n) ? 0 : ( (n)->parent->child[1] == (n) ? 1 : -1 ) )

_zTreeInitHeapMask

#define _zTreeInitHeapMask	(		t,
			mask
	)

Value:

do{\
  *(mask) = 1 << ( sizeof(int)*8 - 2 );\
  while( !( *(mask) & (t)->size ) ) *(mask) >>= 1;\
  *(mask) >>= 1;\
} while(0)

zTreeInit

#define zTreeInit	(		node_t,
			node
	)		node_t##Init( node )

zTreeDestroy

#define zTreeDestroy	(		node_t,
			tree
	)		node_t##Destroy( tree )

zTreeNodeAlloc

#define zTreeNodeAlloc	(		node_t,
			val
	)		node_t##NodeAlloc( val )

zTreeAddComplete

#define zTreeAddComplete	(		node_t,
			tree,
			val
	)		node_t##AddComplete( tree, val )

zTreeUpHeap

#define zTreeUpHeap	(		node_t,
			tree,
			node,
			cmp,
			util
	)		node_t##UpHeap( tree, node, cmp, util )

zTreeAddHeap

#define zTreeAddHeap	(		node_t,
			tree,
			val,
			cmp,
			util
	)		node_t##AddHeap( tree, val, cmp, util )

zTreeDownHeap

#define zTreeDownHeap	(		node_t,
			node,
			cmp,
			util
	)		node_t##DownHeap( node, cmp, util )

zTreeDeleteHeap

#define zTreeDeleteHeap	(		node_t,
			tree,
			cmp,
			util
	)		node_t##DeleteHeap( tree, cmp, util )

zTreeHeapify

#define zTreeHeapify	(		node_t,
			tree,
			cmp,
			util
	)		node_t##Heapify( tree, cmp, util )