a tree. tree. Each node has variable number of child nodes, the node is embeddable (like ring list). This tree is especially suited for parse trees. More...

Classes
struct	tagTREENODE
Defines
#define	TREE_FOREACH_CHILD(current, node)
#define	TREE_FOREACH_CHILD_REVERSE(current, node)
#define	TREE_FOREACH_PREORDER(current, tree)
#define	TREE_FOREACH_PREORDER_END
#define	TREE_FOREACH_POSTORDER(current, tree)
#define	TREE_FOREACH_POSTORDER_END
Typedefs
typedef struct tagTREENODE	TREENODE
typedef int(*	TREE_VISITOR )(TREENODE entry, void context)
typedef void(*	TREE_VISITOR_V )(TREENODE entry, void context)
typedef int(*	TREE_VISITOR_EXT_V )(TREENODE entry, TREE_VISIT_EVENT visit, void context)
Enumerations
enum	TREE_INSERT_MODE { TREE_INSERT_FIRST, TREE_INSERT_LAST }
enum	TREE_VISIT_EVENT { TREE_PREORDER, TREE_POSTORDER }
Functions
M_INLINE void	TREE_init_root (TREENODE *tree)
M_INLINE TREENODE *	TREE_parent (TREENODE *node)
M_INLINE TREENODE *	TREE_left_sibling (TREENODE *node)
M_INLINE TREENODE *	TREE_right_sibling (TREENODE *node)
M_INLINE TREENODE *	TREE_leftmost_sibling (TREENODE *node)
M_INLINE TREENODE *	TREE_rightmost_sibling (TREENODE *node)
M_INLINE TREENODE *	TREE_first_child (TREENODE *node)
M_INLINE TREENODE *	TREE_last_child (TREENODE *node)
M_INLINE int	TREE_insert_right_sibling (TREENODE current, TREENODE newnode, int node_is_leaf)
M_INLINE int	TREE_insert_left_sibling (TREENODE current, TREENODE newnode, int node_is_leaf)
M_INLINE void	TREE_insert_child (TREENODE parent, TREENODE newnode, TREE_INSERT_MODE mode, int node_is_leaf)
M_INLINE void	TREE_merge_childs (TREENODE parent, TREE_INSERT_MODE mode, TREENODE newnode)
M_INLINE TREENODE *	TREE_unlink_node (TREENODE *node)
M_INLINE size_t	TREE_count_child_nodes (TREENODE *current)
M_INLINE TREENODE *	TREE_preorder_next (TREENODE *current)
M_INLINE void	TREE_foreach_child (TREENODE lst, TREE_VISITOR_V eval, void context)
	iterate over all elements of a list of child nodes, callback is invoked for either element of the list. list is traversed from first element to the last element.
M_INLINE void	TREE_foreach_child_reverse (TREENODE lst, TREE_VISITOR_V eval, void context)
M_INLINE TREENODE *	TREE_findif_child (TREENODE tree, TREE_VISITOR eval, void context, int32_t *retval)
	find an element within the list of child nodes. callback is invoked for each element of the list, in forward direction from first element to last element; when the callback returns non zero value the iteration stops as we have found what we searched for.
M_INLINE TREENODE *	TREE_findif_child_reverse (TREENODE tree, TREE_VISITOR eval, void context, int32_t *retval)
M_INLINE TREENODE *	TREE_postorder_next (TREENODE current, TREENODE prev)
M_INLINE void	TREE_foreach_preorder (TREENODE node, TREE_VISITOR_V visit, void context)
M_INLINE TREENODE *	TREE_find_preorder (TREENODE node, TREE_VISITOR visit, void context)
M_INLINE void	TREE_foreach_postorder (TREENODE node, TREE_VISITOR_V visit, void context)
M_INLINE TREENODE *	TREE_find_postorder (TREENODE node, TREE_VISITOR visit, void context)
M_INLINE int	TREE_check_tree (TREENODE *root)
	check tree for consistency errors

Detailed Description

a tree. tree. Each node has variable number of child nodes, the node is embeddable (like ring list). This tree is especially suited for parse trees.

Define Documentation

#define TREE_FOREACH_CHILD	(	current,
		node
	)

Value:

for((current) = TREE_first_child(node); \
                (current); \
                (current) = TREE_right_sibling(current))

Definition at line 374 of file tree.h.

#define TREE_FOREACH_CHILD_REVERSE	(	current,
		node
	)

Value:

for((current) = TREE_last_child(node); \
                (current); \
                (current) = TREE_left_sibling(current))

Definition at line 379 of file tree.h.

#define TREE_FOREACH_POSTORDER	(	current,
		tree
	)

Value:

{\
        TREENODE *TREE_nextnode##next,*TREE_nextnode##prev;\
        TREE_nextnode##prev = 0; \
        current = TREE_postorder_next((tree),TREE_nextnode##prev);\
        if (current)\
                for( TREE_nextnode##next =  TREE_postorder_next(current,TREE_nextnode##prev);\
                            (current) && current != (tree); \
                                TREE_nextnode##prev = (current), \
                                (current) = TREE_nextnode##next, \
                                TREE_nextnode##next =  TREE_postorder_next(current,TREE_nextnode##prev)) {

Definition at line 604 of file tree.h.

#define TREE_FOREACH_POSTORDER_END

Value:

}\
}\

Definition at line 619 of file tree.h.

#define TREE_FOREACH_PREORDER	(	current,
		tree
	)

Value:

{\
        TREENODE *TREE_nextnode##next;\
        current = TREE_preorder_next((tree));\
        if (current)\
                for( TREE_nextnode##next =  TREE_preorder_next(current);\
                            (current) && current != (tree); \
                                (current) = TREE_nextnode##next, TREE_nextnode##next =  TREE_preorder_next(current)) {

Definition at line 554 of file tree.h.

#define TREE_FOREACH_PREORDER_END

Value:

}\
}

Definition at line 564 of file tree.h.

Typedef Documentation

typedef int(* TREE_VISITOR)(TREENODE *entry, void *context)

Definition at line 362 of file tree.h.

typedef int(* TREE_VISITOR_EXT_V)(TREENODE *entry, TREE_VISIT_EVENT visit, void *context)

Definition at line 371 of file tree.h.

typedef void(* TREE_VISITOR_V)(TREENODE *entry, void *context)

Definition at line 363 of file tree.h.

typedef struct tagTREENODE TREENODE

Enumeration Type Documentation

enum TREE_INSERT_MODE

Enumerator:

TREE_INSERT_FIRST
TREE_INSERT_LAST

Definition at line 190 of file tree.h.

             {
  TREE_INSERT_FIRST,
  TREE_INSERT_LAST,

} TREE_INSERT_MODE;

enum TREE_VISIT_EVENT

Enumerator:

TREE_PREORDER
TREE_POSTORDER

Definition at line 365 of file tree.h.

             {
  TREE_PREORDER,
  TREE_POSTORDER,

} TREE_VISIT_EVENT;

Function Documentation

M_INLINE int TREE_check_tree ( TREENODE * root )

check tree for consistency errors

Returns:: 0 if the tree is inconsistent

Definition at line 715 of file tree.h.

{
        TREENODE *firstch = root->nextlevel_first;
#ifdef TREE_NEXTLEVEL_LAST
        TREENODE *lastch   = root->nextlevel_last;
#endif
#ifndef TREE_NEXTLEVEL_LEFT     
        TREENODE *slow,*fast, *next;
#endif

        if (!firstch 
#ifdef TREE_NEXTLEVEL_LAST
                        || !lastch
#endif
                ) {

#ifdef TREE_NEXTLEVEL_LAST
                if (firstch || lastch) {
                        return 0;
                }
#endif
                return 1;               
        }       
        
        if (firstch->parent != root) {
                return 0;
        }

#ifdef TREE_NEXTLEVEL_LEFT      
        for(;;firstch = firstch->right) {
                TREENODE *next;
                
                if (!firstch) {
                        return 0;
                }

                if (!TREE_check_tree(firstch)) {
                        return 0;
                }

                next = firstch->right;
                if (!next) {
#ifdef TREE_NEXTLEVEL_LAST
                        if (lastch != firstch) {
                                return 0;
                        }
#endif
                        break;
                }

                if (next->left != firstch) {
                        return 0;
                }
        }
#else
        slow=fast=firstch;
        while(1) {
                if (!TREE_check_tree(slow)) {
                        return 0;
                }
                next = fast->right;
                if (!next) {
                        break;                  
                }
                fast = next;
                if (fast == slow) {
                        return 0;
                }
                next = fast->right;
                if (!next) {
                        break;                  
                }
                fast = next;
                if (fast == slow) {
                        return 0;
                }
                slow = slow->right;
        }
#ifdef TREE_NEXTLEVEL_LAST
        if (lastch != fast) {
                return 0;
        }
#endif

#endif
        return 1;
}

M_INLINE size_t TREE_count_child_nodes ( TREENODE * current )

Definition at line 385 of file tree.h.

{
        size_t ret = 0;
        TREENODE *c;

        TREE_FOREACH_CHILD(c,current) {
                ret++;
        }
        return ret;
}

M_INLINE TREENODE* TREE_find_postorder	(	TREENODE *	node,
		TREE_VISITOR	visit,
		void *	context
	)

Definition at line 695 of file tree.h.

{
        TREENODE *current;

        TREE_FOREACH_POSTORDER(current,node)
                if (visit(node,context)) {
                        return current;
                }
        TREE_FOREACH_POSTORDER_END
        return 0;
}

M_INLINE TREENODE* TREE_find_preorder	(	TREENODE *	node,
		TREE_VISITOR	visit,
		void *	context
	)

Definition at line 643 of file tree.h.

{
        TREENODE *current;

        TREE_FOREACH_PREORDER(current,node)
                if (visit(node,context)) {
                        return current;
                }
        TREE_FOREACH_POSTORDER_END
        return 0;
}

M_INLINE TREENODE* TREE_findif_child	(	TREENODE *	tree,
		TREE_VISITOR	eval,
		void *	context,
		int32_t *	retval
	)

find an element within the list of child nodes. callback is invoked for each element of the list, in forward direction from first element to last element; when the callback returns non zero value the iteration stops as we have found what we searched for.

Parameters:

tree	(in) node in a tree (parent of enumerated childs).
eval	(in) callback that is called to visit each set (or cleared) bit.
context	(in) pointer that is passed as context on each invocation of callback.
retval	(out) optional - the first non zero value returned by eval callback, if NULL then ignored.

Returns:: the list element that has matched (i.e. element that has been found).

Definition at line 499 of file tree.h.

{
        int ret;
    TREENODE *cur;

        if (retval) {
                *retval = 0;
        }

        if (!eval) {
                return 0;
        }
        

        TREE_FOREACH_CHILD( cur, tree) {
                ret = eval( cur, context );
                if (ret) {
                        if (retval) {
                                *retval = ret;
                        }
                        return cur;
                }
        }

        return 0;
}

M_INLINE TREENODE* TREE_findif_child_reverse	(	TREENODE *	tree,
		TREE_VISITOR	eval,
		void *	context,
		int32_t *	retval
	)

Definition at line 526 of file tree.h.

{
        int ret;
    TREENODE *cur;

        if (retval) {
                *retval = 0;
        }

        if (!eval) {
                return 0;
        }
        

        TREE_FOREACH_CHILD_REVERSE( cur, tree) {
                ret = eval( cur, context );
                if (ret) {
                        if (retval) {
                                *retval = ret;
                        }
                        return cur;
                }
        }

        return 0;
}

M_INLINE TREENODE* TREE_first_child ( TREENODE * node )

Definition at line 105 of file tree.h.

{
        return node->nextlevel_first;
}

M_INLINE void TREE_foreach_child	(	TREENODE *	lst,
		TREE_VISITOR_V	eval,
		void *	context
	)

iterate over all elements of a list of child nodes, callback is invoked for either element of the list. list is traversed from first element to the last element.

Parameters:

lst	(in) node in a tree (parent of enumerated childs).
eval	(in) callback that is called to visit each set (or cleared) bit.
context	(in) pointer that is passed as context on each invocation of callback.
save_from_del	(in) if non zero then callback can remove the current link from the list (a bit slower); if null then not; if zero then can't remove the current link from the list.

Definition at line 458 of file tree.h.

{
    TREENODE *cur;

        if (!eval) {
          return;
        }

        TREE_FOREACH_CHILD( cur, lst) {
                eval( cur, context );
        }
        
}

M_INLINE void TREE_foreach_child_reverse	(	TREENODE *	lst,
		TREE_VISITOR_V	eval,
		void *	context
	)

Definition at line 474 of file tree.h.

{
    TREENODE *cur;

        if (!eval) {
          return;
        }


        TREE_FOREACH_CHILD_REVERSE( cur,lst) {
                eval( cur, context );
        }
        
}

M_INLINE void TREE_foreach_postorder	(	TREENODE *	node,
		TREE_VISITOR_V	visit,
		void *	context
	)

Definition at line 668 of file tree.h.

{
        TREENODE *current;

        TREE_FOREACH_POSTORDER(current,node)
                visit(node,context);
        TREE_FOREACH_POSTORDER_END
}

M_INLINE void TREE_foreach_preorder	(	TREENODE *	node,
		TREE_VISITOR_V	visit,
		void *	context
	)

Definition at line 634 of file tree.h.

{
        TREENODE *current;

        TREE_FOREACH_PREORDER(current,node)
                visit(node,context);
        TREE_FOREACH_POSTORDER_END
}

M_INLINE void TREE_init_root ( TREENODE * tree )

Definition at line 37 of file tree.h.

{
        tree->right = tree->parent = tree->nextlevel_first = 0;
#ifdef TREE_NEXTLEVEL_LEFT
        tree->left = 0;
#endif
#ifdef TREE_NEXTLEVEL_LAST
        tree->nextlevel_last = 0;
#endif
}

M_INLINE void TREE_insert_child	(	TREENODE *	parent,
		TREENODE *	newnode,
		TREE_INSERT_MODE	mode,
		int	node_is_leaf
	)

Definition at line 196 of file tree.h.

{       
        /* init new node */
        if (node_is_leaf) {
                newnode->nextlevel_first = 0;
#ifdef TREE_NEXTLEVEL_LAST
                newnode->nextlevel_last = 0;
#endif
        }
        newnode->parent = parent;
        newnode->right = 0;
#ifdef TREE_NEXTLEVEL_LEFT
        newnode->left = 0;
#endif  

        
        if (!parent->nextlevel_first) {         

                /* insert as first child */
                //newnode->nextlevel_first = parent->nextlevel_first;
                parent->nextlevel_first = newnode;
#ifdef TREE_NEXTLEVEL_LAST
                //newnode->nextlevel_last = parent->nextlevel_last;
                parent->nextlevel_last = newnode;
#endif
                
        } else {

                /* insert as sibling */
                switch(mode) {
                        case TREE_INSERT_FIRST: {
                                        TREE_insert_left_sibling(parent->nextlevel_first,newnode, 0);
                                }
                                break;
                        case TREE_INSERT_LAST:
#ifdef TREE_NEXTLEVEL_LAST
                                TREE_insert_right_sibling( parent->nextlevel_last,newnode, 0);
#else
                                TREE_insert_right_sibling( TREE_rightmost_sibling(parent->nextlevel_first), newnode, 0);
#endif

                                break;
                }
        }

}

M_INLINE int TREE_insert_left_sibling	(	TREENODE *	current,
		TREENODE *	newnode,
		int	node_is_leaf
	)

Definition at line 157 of file tree.h.

{
        TREENODE *parent = current->parent;
        if (!parent) {
                return -1;
        }

        if (node_is_leaf) {
                TREE_init_root(newnode);
        }

        if (parent->nextlevel_first == current) {
                parent->nextlevel_first = newnode;
        }

        newnode->parent = parent;

#ifdef TREE_NEXTLEVEL_LEFT
        if (current->left) {
                current->left->right = newnode;
        }
#endif
        newnode->right = current;
#ifdef TREE_NEXTLEVEL_LEFT      
        newnode->left = current->left;
        current->left = newnode;
#endif



        return 0;
}

M_INLINE int TREE_insert_right_sibling	(	TREENODE *	current,
		TREENODE *	newnode,
		int	node_is_leaf
	)

Definition at line 123 of file tree.h.

{
        TREENODE *parent = current->parent;

        if (!parent) {
                return -1;
        }
        if (node_is_leaf) {
                TREE_init_root(newnode);
        }

#ifdef TREE_NEXTLEVEL_LAST
        if (parent->nextlevel_last == current) {
                parent->nextlevel_last = newnode;
        }
#endif

        newnode->parent = parent;
        
#ifdef TREE_NEXTLEVEL_LEFT
        newnode->left  = current;
        if (current->right) {
                current->right->left = newnode;
        }
#endif
        newnode->right = current->right;
        current->right = newnode;



        return 0;
}

M_INLINE TREENODE* TREE_last_child ( TREENODE * node )

Definition at line 110 of file tree.h.

{
#ifdef TREE_NEXTLEVEL_LAST
        return node->nextlevel_last;
#else
        return TREE_rightmost_sibling(node->nextlevel_first);
#endif
}

M_INLINE TREENODE* TREE_left_sibling ( TREENODE * node )

Definition at line 54 of file tree.h.

{
#ifdef TREE_NEXTLEVEL_LEFT
        return node->left;
#else
        TREENODE *tmp;

        if (!node->parent) {
                return 0;
        }
        tmp = node->parent->nextlevel_first;
        if (tmp == node) {
                return 0;
        }
        while(tmp && tmp->right != node) {
                tmp = tmp->right;
        }
        return tmp;
#endif
}

M_INLINE TREENODE* TREE_leftmost_sibling ( TREENODE * node )

Definition at line 80 of file tree.h.

{
        TREENODE *parent = node->parent;
        if (parent) {
                return parent->nextlevel_first;
        }
        return 0;
}

M_INLINE void TREE_merge_childs	(	TREENODE *	parent,
		TREE_INSERT_MODE	mode,
		TREENODE *	newnode
	)

Definition at line 244 of file tree.h.

{       
        TREENODE *ch;

        switch(mode) {

        case TREE_INSERT_LAST:  
                ch = TREE_first_child(newnode);
                if (!ch) {
                        return;
                }

                while(ch) {
                        TREE_insert_child(parent, ch, TREE_INSERT_LAST, 0 );
                        ch = TREE_right_sibling(ch);
                }
                break;

        case TREE_INSERT_FIRST: 
                ch = TREE_last_child(newnode);
                if (!ch) {
                        return;
                }

                while(ch) {
                        TREE_insert_child(parent, ch, TREE_INSERT_FIRST, 0 );
                        ch = TREE_left_sibling(ch);
                }
                break;
        }
}

M_INLINE TREENODE* TREE_parent ( TREENODE * node )

Definition at line 48 of file tree.h.

{
        return node->parent;
}

M_INLINE TREENODE* TREE_postorder_next	(	TREENODE *	current,
		TREENODE *	prev
	)

Definition at line 578 of file tree.h.

{

        if (current->nextlevel_first && (!prev || current->parent == prev)) {
next_level:
                do {            
                        current = current->nextlevel_first;
                }
                while(current->nextlevel_first);
        } else {
                if (current->right) {
                        current = current->right;
                        if (current->nextlevel_first) {
                          goto next_level;
                        }
                } else {
                        if (current->parent) {
                                current = current->parent;
                        }
                }
        }
        return current;
}

M_INLINE TREENODE* TREE_preorder_next ( TREENODE * current )

Definition at line 403 of file tree.h.

{
        if (current->nextlevel_first) {
                current = current->nextlevel_first;
        } else {
                if (current->right) {
                        current = current->right;
                } else {
                        while(current->parent) {
                                current = current->parent;
                                if (current->right) {
                                        current = current->right;
                                        break;
                                }
                        }
                }
        }

        return current;
}

M_INLINE TREENODE* TREE_right_sibling ( TREENODE * node )

Definition at line 75 of file tree.h.

{
        return node->right;
}

M_INLINE TREENODE* TREE_rightmost_sibling ( TREENODE * node )

Definition at line 89 of file tree.h.

{
#ifdef TREE_NEXTLEVEL_LAST
        TREENODE *parent = node->parent;
        if (parent) {
                return parent->nextlevel_last;
        }
        return 0;
#else
        while(node->right) {
                node = node->right;
        }
#endif
        return node;
}

M_INLINE TREENODE* TREE_unlink_node ( TREENODE * node )

Definition at line 277 of file tree.h.

{
        TREENODE *tmp,*tmp_next, *tmp_last;

        if (!node->parent) {
                return 0;
        }

        /* wrong */
        tmp = node->parent;
        if (tmp && tmp->nextlevel_first == node) {

                if (!node->nextlevel_first) {
                        tmp->nextlevel_first = node->right;
                        goto sdel;
                }

                tmp->nextlevel_first = node->nextlevel_first;                           
                tmp_next = tmp->nextlevel_first;
                tmp_last = TREE_rightmost_sibling(tmp_next);

                tmp_last->right = node->right;
#ifdef TREE_NEXTLEVEL_LEFT
                if (node->right) {
                        node->right->left = tmp_last;
                }
#endif
                do {
                        tmp_next->parent = tmp;
                        if (tmp_next == tmp_last) {
                                break;
                        }
                        tmp_next = tmp_next->right;
                } while(tmp_next);

                return node;
        }

#ifdef TREE_NEXTLEVEL_LAST
        if (tmp && tmp->nextlevel_last == node) {

                if (!node->nextlevel_last) {
                        tmp->nextlevel_last = TREE_left_sibling(node);
                        goto sdel;
                }

                tmp->nextlevel_last = node->nextlevel_last;     
                tmp_next = tmp->nextlevel_last;
                tmp_last = TREE_leftmost_sibling(tmp_next);

#ifdef TREE_NEXTLEVEL_LEFT
                tmp_last->left = node->left;
#endif
                TREE_left_sibling(node)->right = tmp_last;

                do {
                        tmp_last->parent = tmp;
                        if (tmp_next == tmp_last) {
                                break;
                        }
                        tmp_last = tmp_last->right;
                } while(tmp_last);                                      

                return node;
        }
#endif

sdel:

#ifdef TREE_NEXTLEVEL_LEFT
        tmp = node->right;
        if (tmp) {
                tmp->left = node->left;
        }
#endif

        tmp = TREE_left_sibling(node);
        if (tmp) {
                tmp->right = node->right;
        }

        return node;
}

Classes

Defines

Typedefs

Enumerations

Functions

Detailed Description

Define Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation