Lines Matching refs:tree
725 /* ------------------------------- binary tree traversal (level 0) -------------------- */
728 #define SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, iteratedVariable, order, left, right, command) {\
729 /* this is non-recursive implementation of tree traversal */\
731 /* the _path_[0] contains the root of the tree; */\
742 _cn_ = (tree);\
773 #define SGLIB_BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, left, right, command) {\
774 SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, 1, left, right, command);\
777 #define SGLIB_BIN_TREE_MAP_ON_ELEMENTS_PREORDER(type, tree, _current_element_, left, right, command) {\
778 SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, 0, left, right, command);\
781 #define SGLIB_BIN_TREE_MAP_ON_ELEMENTS_POSTORDER(type, tree, _current_element_, left, right, command) {\
782 SGLIB___BIN_TREE_MAP_ON_ELEMENTS(type, tree, _current_element_, 2, left, right, command);\
785 #define SGLIB___BIN_TREE_FIND_MEMBER(type, tree, elem, left, right, comparator, res) {\
788 _s_ = (tree);\
1019 red-black tree as well.
1447 #define SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY(type, tree, leftt, rightt, bits, RED, BLACK) {\
1451 t = *tree;\
1471 *tree = b;\
1482 *tree = c;\
1488 #define SGLIB___RBTREE_FIX_DELETION_DISCREPANCY(type, tree, leftt, rightt, bits, RED, BLACK, res) {\
1491 t = a = *tree;\
1504 *tree = b;\
1515 *tree = b;\
1526 *tree = d;\
1534 *tree = c;\
1548 *tree = d;\
1567 *tree = b;\
1582 *tree = c;\
1596 *tree = c;\
1611 static void sglib___##type##_fix_left_insertion_discrepancy(type **tree) {\
1612 SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY(type, tree, left, right, bits, RED, BLACK);\
1615 static void sglib___##type##_fix_right_insertion_discrepancy(type **tree) {\
1616 SGLIB___RBTREE_FIX_INSERTION_DISCREPANCY(type, tree, right, left, bits, RED, BLACK);\
1619 static int sglib___##type##_fix_left_deletion_discrepancy(type **tree) {\
1621 SGLIB___RBTREE_FIX_DELETION_DISCREPANCY(type, tree, right, left, bits, RED, BLACK, res);\
1625 static int sglib___##type##_fix_right_deletion_discrepancy(type **tree) {\
1627 SGLIB___RBTREE_FIX_DELETION_DISCREPANCY(type, tree, left, right, bits, RED, BLACK, res);\
1631 static void sglib___##type##_add_recursive(type **tree, type *elem) {\
1634 t = *tree;\
1637 *tree =elem;\
1642 if (SGLIB___GET_VALUE(t->bits)==BLACK) sglib___##type##_fix_left_insertion_discrepancy(tree);\
1645 if (SGLIB___GET_VALUE(t->bits)==BLACK) sglib___##type##_fix_right_insertion_discrepancy(tree);\
1650 static int sglib___##type##_delete_rightmost_leaf(type **tree, type **theLeaf) {\
1653 t = *tree;\
1661 *tree = t->left;\
1663 *tree = NULL;\
1668 if (deepDecreased) res = sglib___##type##_fix_right_deletion_discrepancy(tree);\
1673 int sglib___##type##_delete_recursive(type **tree, type *elem) {\
1676 t = *tree;\
1679 assert(0 && "The element to delete not found in the tree, use 'delete_if_member'"!=NULL);\
1685 res = sglib___##type##_fix_left_deletion_discrepancy(tree);\
1690 res = sglib___##type##_fix_right_deletion_discrepancy(tree);\
1693 assert(elem==t && "Deleting an element which is non member of the tree, use 'delete_if_member'"!=NULL);\
1697 *tree = NULL;\
1702 *tree = t->right;\
1710 *tree = theLeaf;\
1711 if (deepDecreased) res = sglib___##type##_fix_left_deletion_discrepancy(tree);\
1718 void sglib_##type##_add(type **tree, type *elem) {\
1720 sglib___##type##_add_recursive(tree, elem);\
1721 SGLIB___SET_VALUE((*tree)->bits,BLACK);\
1724 void sglib_##type##_delete(type **tree, type *elem) {\
1725 sglib___##type##_delete_recursive(tree, elem);\
1726 if (*tree!=NULL) SGLIB___SET_VALUE((*tree)->bits,BLACK);\
1751 int sglib_##type##_delete_if_member(type **tree, type *elem, type **memb) {\
1752 if ((*memb=sglib_##type##_find_member(*tree, elem))!=NULL) {\
1753 sglib_##type##_delete(tree, *memb);\
1759 int sglib_##type##_add_if_not_member(type **tree, type *elem, type **memb) {\
1760 if ((*memb=sglib_##type##_find_member(*tree, elem))==NULL) {\
1761 sglib_##type##_add(tree, elem);\
1818 type *sglib__##type##_it_init(struct sglib_##type##_iterator *it, type *tree, int order, int (*subcomparator)(type *, type *), type *equalto) {\
1825 t = tree;\
1828 SGLIB___BIN_TREE_FIND_MEMBER(type, tree, equalto, left, right, comparator, t);\
1830 SGLIB___BIN_TREE_FIND_MEMBER(type, tree, equalto, left, right, subcomparator, t);\
1848 type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *tree) {\
1849 return(sglib__##type##_it_init(it, tree, 2, NULL, NULL));\
1851 type *sglib_##type##_it_init_preorder(struct sglib_##type##_iterator *it, type *tree) {\
1852 return(sglib__##type##_it_init(it, tree, 0, NULL, NULL));\
1854 type *sglib_##type##_it_init_inorder(struct sglib_##type##_iterator *it, type *tree) {\
1855 return(sglib__##type##_it_init(it, tree, 1, NULL, NULL));\
1857 type *sglib_##type##_it_init_postorder(struct sglib_##type##_iterator *it, type *tree) {\
1858 return(sglib__##type##_it_init(it, tree, 2, NULL, NULL));\
1860 type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *tree, int (*subcomparator)(type *, type *), type *equalto) {\
1861 return(sglib__##type##_it_init(it, tree, 1, subcomparator, equalto));\
1909 extern void sglib_##type##_add(type **tree, type *elem);\
1910 extern int sglib_##type##_add_if_not_member(type **tree, type *elem, type **memb);\
1911 extern void sglib_##type##_delete(type **tree, type *elem);\
1912 extern int sglib_##type##_delete_if_member(type **tree, type *elem, type **memb);\
1916 extern type *sglib_##type##_it_init(struct sglib_##type##_iterator *it, type *tree);\
1917 extern type *sglib_##type##_it_init_preorder(struct sglib_##type##_iterator *it, type *tree);\
1918 extern type *sglib_##type##_it_init_inorder(struct sglib_##type##_iterator *it, type *tree);\
1919 extern type *sglib_##type##_it_init_postorder(struct sglib_##type##_iterator *it, type *tree);\
1920 extern type *sglib_##type##_it_init_on_equal(struct sglib_##type##_iterator *it, type *tree, int (*subcomparator)(type *, type *), type *equalto);\