Lines Matching refs:tree
38 The balanced tree insertion algorithm is directly taken from Donald E.
50 The CSCbinTree functions provide an interface to a balanced binary tree
51 subsystem. The tree is an opaque data type, and client code never has
53 tree can be deleted.
61 same tree.
64 tree
66 CSCbinTreeNew - create an empty libcsc balanced binary tree
67 CSCbinTreeDel - delete a libcsc balanced binary tree
68 CSCbinTreeInsert - insert a node into a libcsc balanced binary tree
69 CSCbinTreeTagOrderedInsert - put node into libcsc balanced binary tree
70 CSCbinTreeTraverse - traverse a libcsc balanced binary tree
71 CSCbinTreeUserSearch - arbitrary search of libcsc balanced binary tree
72 CSCbinTreeTagSearch - search a balanced binary tree for node with tag
73 CSCbinTreeStat - retrieve libcsc balanced binary tree statistics
74 CSCbinTreePrint - print a libcsc balanced binary tree
78 CSCbinTreeNodeNew - create a new empty libcsc binary tree node
79 CSCbinTreeNodeDel - deallocate a libcsc binary tree node
80 CSCbinTreeNodeJoin - join libcsc binary tree nodes
81 CSCbinTreeNodeBreak - break libcsc binary tree at a node
82 CSCbinTreeNodeTraverse - traverse a libcsc binary tree
83 CSCbinTreeNodeUserSearch - arbitrary libcsc binary tree traversal
84 CSCbinTreeNodeTagSearch - search a libcsc binary tree for a given tag
85 CSCbinTreeNodeStat - retrieve fields from a libcsc binary tree node
86 CSCbinTreeNodePrint - print the values of a libcsc binary tree node
100 tree signature. Tracked change to rtsMemDup().
102 19apr00 drj Fixed up DEBUG signatures. Made tree and node types
582 CSCbinTreeNew - create an empty libcsc balanced binary tree
596 represents the newly created libcsc balanced binary tree, or NULL if
600 CSCbinTreeNew() creates and initializes a libcsc balanced binary tree
603 DANGER Take care to never insert into a balanced binary tree a node
606 a balanced tree.
609 libcsc balanced binary tree.
612 functions on the same tree.
646 ASSERT_RTN (namePtr != NULL, "CSCbinTreeNew: no tree name", NULL);
691 CSCbinTreeDel - delete a libcsc balanced binary tree
697 CSCbinTreeType const tree,
703 represented by `tree' will be deallocated.
708 `tree' or `cbFn' is NULL.
712 tree or in some internal data.
715 CSCbinTreeDel() delete the balanced binary tree and the opaque
716 CSCbinTreeType data structure represented by `tree'. Probably the only
721 EACH NODE in the tree, before each node is deallocated. The prototype
762 CSCbinTreeType const tree,
768 ASSERT_RTN (tree != NULL, "CSCbinTreeDel: null tree", CSC_BADARG);
771 ASSERT_RTN (tree->sig_lo==TREE_SIG,"CSCbinTreeDel: tree blows",CSC_CORRUPT);
772 ASSERT_RTN (tree->sig_hi==TREE_SIG,"CSCbinTreeDel: tree blows",CSC_CORRUPT);
774 MON_ENTER(tree);
776 if (tree->root != NULL) delStat = binTreeDel (tree->root, cbFn);
780 MON_EXIT(tree);
785 CSCmemListType memList = tree->memList;
786 CSCmonFnType monFunc = tree->monFunc;
787 const void* monData = tree->monData;
788 (void)CSCmemFree (memList, (void**)&tree, 0);
804 CSCbinTreeInsert - insert a node into a libcsc balanced binary tree
810 CSCbinTreeType const tree,
818 CSC_DUPKEY .... if `node' already exists in `tree'; this is defined
819 by the value of tree nodes' tags and is discerned by
823 `tree', `node', or `cmpfn' is NULL.
827 tree or in some internal data.
830 CSCbinTreeInsert() inserts `node' into the libcsc balanced binary tree
831 `tree', and then maintains the balance.
835 and will completely whack a balanced tree.
838 for each node in the tree, until the node pointed to by node is
844 field values of the node at node with a node, P, in the tree (note
856 The tag field of libcsc balanced binary tree nodes is a long, but its
863 The balanced tree insertion algorithm is directly taken from Donald E.
890 CSCbinTreeType const tree,
898 * The balanced tree insertion algorithm is directly taken from Donald E.
914 ASSERT_RTN (tree != NULL, "CSCbinTreeInsert: null tree", CSC_BADARG);
918 ASSERT_RTN(tree->sig_lo==TREE_SIG,"CSCbinTreeInsert: tree sig",CSC_CORRUPT);
919 ASSERT_RTN(tree->sig_hi==TREE_SIG,"CSCbinTreeInsert: tree sig",CSC_CORRUPT);
924 MON_ENTER(tree);
926 if (tree->root == NULL)
928 tree->root = node;
932 S = P = tree->root;
935 * P will move down the tree; S will point to the place where rebalancing
942 tree->compares += 1;
946 MON_EXIT(tree);
988 tree->compares += 1;
998 tree->compares += 1;
1004 tree->compares += 1;
1013 tree->compares += 1;
1018 if (S->balance == 0) /* tree has grown higher */
1020 tree->height += 1;
1024 if (S->balance == -a) /* tree has gotten more balanced */
1029 if (S->balance == +a) /* tree has gotten out of balance */
1036 tree->rotates += 1;
1052 tree->rotates += 2;
1089 tree->root = P;
1099 if (insertStat == CSC_OK) tree->count += 1;
1101 MON_EXIT(tree);
1114 CSCbinTreeTagOrderedInsert - put node into libcsc balanced binary tree
1120 CSCbinTreeType const tree,
1127 CSC_DUPKEY .... if `node' already exists in `tree' (this is defined
1130 CSC_BADARG .... if libcsc was compiled with the DEBUG macro and `tree'
1135 up in the tree or in some internal data.
1139 binary tree `tree', and then CSCbinTreeTagOrderedInsert() maintains the
1144 tree.
1148 information and will completely whack a balanced tree.
1157 The balanced tree insertion algorithm is directly taken from Donald E.
1184 CSCbinTreeType const tree,
1188 return (CSCbinTreeInsert(tree,node,tagCompare));
1199 CSCbinTreeTraverse - traverse a libcsc balanced binary tree
1206 CSCbinTreeType const tree,
1219 `method', `tree', or `clientFn' is NULL.
1223 the tree or in some internal data.
1226 CSCbinTreeTraverse() traverses the libcsc balanced binary tree `tree'.
1238 called for EACH NODE in the tree. The prototype for CSCcmpFnType is:
1259 If clientFn is NULL, then the libcsc balanced binary tree is traversed
1261 was compiled with the DEBUG macro, in which case the tree will be
1288 CSCbinTreeType const tree,
1296 ASSERT_RTN (tree != NULL, "CSCbinTreeTraverse: null tree", CSC_BADARG);
1299 tree->sig_lo==TREE_SIG, \
1300 "CSCbinTreeTraverse: tree blows", \
1304 tree->sig_hi==TREE_SIG, \
1305 "CSCbinTreeTraverse: tree blows", \
1311 travStat = prefixTravel (tree->root, clientFn, clientData);
1315 travStat = infixTravel (tree->root, clientFn, clientData);
1319 travStat = postfixTravel (tree->root, clientFn, clientData);
1335 CSCbinTreeUserSearch - arbitrary search of libcsc balanced binary tree
1341 CSCbinTreeType const tree,
1348 that is a node from the libcsc balanced binary tree `tree'.
1352 CSCbinTreeUserSearch() traverses the libcsc balanced binary tree `tree'.
1353 The tree traversal algorithm and traversal termination are controlled by
1357 for each node in `tree'. The prototype for clientFn is:
1367 This gives the client control over tree traversal. `clientFn' should
1403 CSCbinTreeType const tree,
1410 ASSERT_RTN (tree != NULL, "CSCbinTreeUserSearch: null tree", NULL);
1413 ASSERT_RTN (tree->sig_lo==TREE_SIG,"CSCbinTreeUserSearch: tree blows",NULL);
1414 ASSERT_RTN (tree->sig_hi==TREE_SIG,"CSCbinTreeUserSearch: tree blows",NULL);
1416 tmpNode = userSearch (tree->root, clientFn, clientData);
1429 CSCbinTreeTagSearch - search a balanced binary tree for node with tag
1435 CSCbinTreeType const tree,
1441 is a libcsc balanced binary tree node whose tag-field value is equal to
1445 CSCbinTreeTagSearch() searches the libcsc balanced binary tree `tree'
1448 A recursive postfix tree traversal algorithm is used.
1473 CSCbinTreeType const tree,
1479 ASSERT_RTN (tree != NULL, "CSCbinTreeTagSearch: null tree", NULL);
1481 tree->sig_lo==TREE_SIG, \
1482 "CSCbinTreeTagSearch: tree blows", \
1486 tree->sig_hi==TREE_SIG, \
1487 "CSCbinTreeTagSearch: tree blows", \
1491 tempNode = tagSearch (tree->root, tag);
1504 CSCbinTreeStat - retrieve libcsc balanced binary tree statistics
1510 CSCbinTreeType const tree,
1520 If libcsc was compiled with the DEBUG macro and tree is NULL, then
1523 If libcsc was compiled with the DEBUG macro and some internal tree data
1528 binary tree `tree':
1532 count ......... total number of nodes in the tree.
1533 height ........ maximum current height of the tree.
1537 If `countPtr' is not NULL, then the total number of nodes in the tree is
1540 If `heightPtr' is not NULL, then the maximum current height of the tree
1575 CSCbinTreeType const tree,
1584 ASSERT_RTN (tree != NULL, "CSCbinTreeQuery: null tree", CSC_BADARG);
1586 ASSERT_RTN(tree->sig_lo==TREE_SIG,"CSCbinTreeQuery: tree blows",CSC_CORRUPT);
1587 ASSERT_RTN(tree->sig_hi==TREE_SIG,"CSCbinTreeQuery: tree blows",CSC_CORRUPT);
1589 MON_ENTER(tree);
1591 if (tree->profiling == CSC_DO_PROFILING)
1593 if (countPtr != NULL) *countPtr = tree->count;
1594 if (heightPtr != NULL) *heightPtr = tree->height;
1595 if (comparesPtr != NULL) *comparesPtr = tree->compares;
1596 if (rotatesPtr != NULL) *rotatesPtr = tree->rotates;
1601 MON_EXIT(tree);
1614 CSCbinTreePrint - print a libcsc balanced binary tree
1620 CSCbinTreeType const tree
1626 If libcsc was compiled with the DEBUG macro and tree is NULL, then
1629 If libcsc was compiled with the DEBUG macro and some internal tree data
1634 libcsc balanced binary tree `tree':
1638 count ......... total number of nodes in the tree.
1639 height ........ maximum current height of the tree.
1643 After the overall tree statistics, various fields of all the nodes in
1644 tree are written, to standard output, via an internal call to
1648 A prefix binary tree traversal algorithm is used.
1673 CSCbinTreeType const tree
1678 ASSERT_RTN (tree != NULL, "CSCbinTreeTagDump: null tree", CSC_BADARG);
1680 tree->sig_lo==TREE_SIG, \
1681 "CSCbinTreeTagDump: tree blows", \
1685 tree->sig_hi==TREE_SIG, \
1686 "CSCbinTreeTagDump: tree blows", \
1692 MON_ENTER(tree);
1694 printf (" count: %ld\n", (long)tree->count);
1695 printf (" height: %ld\n", (long)tree->height);
1696 printf ("compares: %ld\n", (long)tree->compares);
1697 printf (" rotates: %ld\n", (long)tree->rotates);
1699 printStat = tagsPrint (tree->root);
1701 MON_EXIT(tree);
1714 CSCbinTreeNodeNew - create a new empty libcsc binary tree node
1728 newly created libcsc binary tree node, or NULL if otherwise not
1732 CSCbinTreeNodeNew() creates a new libcsc binary tree node that is
1741 libcsc balanced binary tree nodes are inserted, searched, or traversed.
1840 CSCbinTreeNodeDel - deallocate a libcsc binary tree node
1858 internal tree data is munged up.
1863 NEVER, EVER do this to a node in a libcsc balanced binary tree. Only
1864 use CSCbinTreeNodeDel() on nodes removed from tree that are built with
1932 CSCbinTreeNodeJoin - join libcsc binary tree nodes
1946 some internal tree data is munged, then rtsBinTreeNodeJoin() returns
1992 ASSERT_RTN (node!= NULL, "CSCbinTreeNodeJoin: null tree", CSC_BADARG);
2054 CSCbinTreeNodeBreak - break libcsc binary tree at a node
2075 NEVER, EVER do this to a node in a libcsc balanced binary tree. Only
2123 ASSERT_RTN (node != NULL, "CSCbinTreeNodeBreak: null tree", CSC_BADARG);
2154 CSCbinTreeNodeTraverse - traverse a libcsc binary tree
2172 If libcsc was compiled with the DEBUG macro and some internal tree data
2179 CSCbinTreeNodeTraverse() traverses a libcsc binary tree beginning with
2191 function that is called for EACH NODE in the tree. The prototype for
2206 If `clientFn' returns any value besides CSC_NOTFOUND, then the tree
2213 If `clientFn' is NULL, then the libcsc binary tree is traversed
2264 "CSCbinTreeNodeTraverse: bad tree sig", \
2269 "CSCbinTreeNodeTraverse: bad tree sig", \
2299 CSCbinTreeNodeUserSearch - arbitrary libcsc binary tree traversal
2312 that is the desired libcsc binary tree node; otherwise NULL is returned
2316 CSCbinTreeNodeUserSearch() traverses the libcsc binary tree beginning
2317 with `node'. The tree traversal algorithm and traversal termination are
2321 node in the tree. The prototype for clientFn is:
2330 This gives the client control over tree traversal. `clientFn' should
2379 "CSCbinTreeNodeUserSearch: bad tree sig", \
2384 "CSCbinTreeNodeUserSearch: bad tree sig", \
2401 CSCbinTreeNodeTagSearch - search a libcsc binary tree for a given tag
2420 A recursive postfix tree traversal algorithm is used.
2454 "CSCbinTreeNodeTagSearch: bad tree sig", \
2459 "CSCbinTreeNodeTagSearch: bad tree sig", \
2476 CSCbinTreeNodeStat - retrieve fields from a libcsc binary tree node
2493 internal tree data is munged up then CSCbinTreeNodeStat() returns
2498 given libcsc binary tree node `node'.
2575 CSCbinTreeNodePrint - print the values of a libcsc binary tree node
2588 internal tree data is munged up then CSCbinTreeNodePrint() returns