/* tree.c: BINARY TREE IMPLEMENTATION
*
* $Id: //info.ravenbrook.com/project/mps/custom/cet/main/code/tree.c#6 $
* Copyright (C) 2014-2018 Ravenbrook Limited. See end of file for license.
*
* Simple binary trees with utilities, for use as building blocks.
* Keep it simple, like Rings (see ring.h).
*
* The performance requirements on tree implementation will depend on
* how each individual function is applied in the MPS.
*
* .note.stack: It's important that the MPS have a bounded stack size,
* and this is a problem for tree algorithms. Basically, we have to
* avoid recursion. See design.mps.sp.sol.depth.no-recursion.
*/
#include "tree.h"
#include "mpm.h"
SRCID(tree, "$Id: //info.ravenbrook.com/project/mps/custom/cet/main/code/tree.c#6 $");
Bool TreeCheck(Tree tree)
{
if (tree != TreeEMPTY) {
CHECKL(tree != NULL);
CHECKL(tree->left == TreeEMPTY || tree->left != NULL);
CHECKL(tree->right == TreeEMPTY || tree->right != NULL);
}
return TRUE;
}
Bool TreeCheckLeaf(Tree tree)
{
CHECKL(TreeCheck(tree));
CHECKL(tree != TreeEMPTY);
CHECKL(tree->left == TreeEMPTY);
CHECKL(tree->right == TreeEMPTY);
return TRUE;
}
/* TreeDebugCount -- count and check order of tree
*
* This function may be called from a debugger or temporarily inserted
* during development to check a tree's integrity. It may not be called
* from the production MPS because it uses indefinite stack depth.
* See .note.stack.
*/
static Count TreeDebugCountBetween(Tree node,
TreeCompareFunction compare,
TreeKeyFunction key,
TreeKey min, TreeKey max)
{
if (node == TreeEMPTY)
return 0;
AVERT(Tree, node);
AVER(min == NULL || compare(node, min) != CompareGREATER);
AVER(max == NULL || compare(node, max) != CompareLESS);
return TreeDebugCountBetween(TreeLeft(node), compare, key, min, key(node)) +
1 +
TreeDebugCountBetween(TreeRight(node), compare, key, key(node), max);
}
Count TreeDebugCount(Tree tree, TreeCompareFunction compare,
TreeKeyFunction key)
{
AVERT(Tree, tree);
return TreeDebugCountBetween(tree, compare, key, NULL, NULL);
}
/* TreeFind -- search for a node matching the key
*
* If a matching node is found, sets *treeReturn to that node and returns
* CompareEQUAL. Otherwise returns values useful for inserting a node with
* the key. If the tree is empty, returns CompareEQUAL and sets *treeReturn
* to NULL. Otherwise, sets *treeReturn to a potential parent for the new
* node and returns CompareLESS if the new node should be its left child,
* or CompareGREATER for its right.
*/
Compare TreeFind(Tree *treeReturn, Tree root, TreeKey key,
TreeCompareFunction compare)
{
Tree node, parent;
Compare cmp = CompareEQUAL;
AVERT_CRITICAL(Tree, root);
AVER_CRITICAL(treeReturn != NULL);
AVER_CRITICAL(FUNCHECK(compare));
/* key is arbitrary */
parent = NULL;
node = root;
while (node != TreeEMPTY) {
parent = node;
cmp = compare(node, key);
switch (cmp) {
case CompareLESS:
node = node->left;
break;
case CompareEQUAL:
*treeReturn = node;
return cmp;
case CompareGREATER:
node = node->right;
break;
default:
NOTREACHED;
*treeReturn = NULL;
return cmp;
}
}
*treeReturn = parent;
return cmp;
}
/* TreeFindNext -- search for node containing key, or next node
*
* If there is a node that is greater than key, set *treeReturn to that
* node and return TRUE.
*
* Otherwise, key is greater than all nodes in the tree, so leave
* *treeReturn unchanged and return FALSE.
*/
Bool TreeFindNext(Tree *treeReturn, Tree root, TreeKey key,
TreeCompareFunction compare)
{
Tree node, best = NULL;
Bool result = FALSE;
AVERT(Tree, root);
AVER(treeReturn != NULL);
AVER(FUNCHECK(compare));
/* key is arbitrary */
node = root;
while (node != TreeEMPTY) {
Compare cmp = compare(node, key);
switch (cmp) {
case CompareLESS:
best = node;
result = TRUE;
node = node->left;
break;
case CompareEQUAL:
case CompareGREATER:
node = node->right;
break;
default:
NOTREACHED;
return FALSE;
}
}
*treeReturn = best;
return result;
}
/* TreeInsert -- insert a node into a tree
*
* If the key doesn't exist in the tree, inserts a node as a leaf of the
* tree, returning the resulting tree in *treeReturn, and returns TRUE.
* Otherwise, *treeReturn points to the existing matching node, the tree
* is not modified, and returns FALSE.
*/
Bool TreeInsert(Tree *treeReturn, Tree root, Tree node,
TreeKey key, TreeCompareFunction compare)
{
Tree parent;
Compare cmp;
AVER(treeReturn != NULL);
AVERT(Tree, root);
AVER(TreeCheckLeaf(node));
AVER(FUNCHECK(compare));
/* key is arbitrary */
cmp = TreeFind(&parent, root, key, compare);
switch (cmp) {
case CompareLESS:
parent->left = node;
break;
case CompareEQUAL:
if (parent != NULL) {
*treeReturn = parent;
return FALSE;
}
AVER(root == TreeEMPTY);
root = node;
break;
case CompareGREATER:
parent->right = node;
break;
default:
NOTREACHED;
*treeReturn = NULL;
return FALSE;
}
*treeReturn = root;
return TRUE;
}
#if 0 /* This code is currently not in use in the MPS */
/* TreeTraverseMorris -- traverse tree inorder in constant space
*
* The tree may not be accessed or modified during the traversal, and
* the traversal must complete in order to repair the tree.
*
* The visitor should return FALSE to terminate the traversal early,
* in which case FALSE is returned.
*
* TreeTraverse is generally superior if comparisons are cheap, but
* TreeTraverseMorris does not require any comparison function.
*
* <http://en.wikipedia.org/wiki/Tree_traversal#Morris_in-order_traversal_using_threading>
*
* Joseph M. Morris (1979). "Traversing Binary Trees Simply and Cheaply".
* Information Processing Letters 9:5 pp. 197–200.
*/
Bool TreeTraverseMorris(Tree tree, TreeVisitor visit,
void *closure)
{
Tree node;
Bool visiting = TRUE;
AVERT(Tree, tree);
AVER(FUNCHECK(visit));
/* closure arbitrary */
node = tree;
while (node != TreeEMPTY) {
if (node->left == TreeEMPTY) {
if (visiting)
visiting = visit(node, closure);
node = node->right;
} else {
Tree pre = node->left;
for (;;) {
if (pre->right == TreeEMPTY) {
pre->right = node;
node = node->left;
break;
}
if (pre->right == node) {
pre->right = TreeEMPTY;
if (visiting)
visiting = visit(node, closure);
else if (node == tree)
return FALSE;
node = node->right;
break;
}
pre = pre->right;
}
}
}
return visiting;
}
#endif /* not currently in use */
/* TreeTraverse -- traverse tree in-order using pointer reversal
*
* The tree may not be accessed or modified during the traversal, and
* the traversal must complete in order to repair the tree.
*
* The visitor should return FALSE to terminate the traversal early,
* in which case FALSE is returned.
*
* TreeTraverseMorris is an alternative when no cheap comparison is available.
*/
static Tree stepDownLeft(Tree node, Tree *parentIO)
{
Tree parent = *parentIO;
Tree child = TreeLeft(node);
TreeSetLeft(node, parent);
*parentIO = node;
return child;
}
static Tree stepDownRight(Tree node, Tree *parentIO)
{
Tree parent = *parentIO;
Tree child = TreeRight(node);
TreeSetRight(node, parent);
*parentIO = node;
return child;
}
static Tree stepUpRight(Tree node, Tree *parentIO)
{
Tree parent = *parentIO;
Tree grandparent = TreeLeft(parent);
TreeSetLeft(parent, node);
*parentIO = grandparent;
return parent;
}
static Tree stepUpLeft(Tree node, Tree *parentIO)
{
Tree parent = *parentIO;
Tree grandparent = TreeRight(parent);
TreeSetRight(parent, node);
*parentIO = grandparent;
return parent;
}
Bool TreeTraverse(Tree tree,
TreeCompareFunction compare,
TreeKeyFunction key,
TreeVisitor visit, void *closure)
{
Tree parent, node;
AVERT(Tree, tree);
AVER(FUNCHECK(visit));
/* closure arbitrary */
parent = TreeEMPTY;
node = tree;
if (node == TreeEMPTY)
return TRUE;
down:
if (TreeHasLeft(node)) {
node = stepDownLeft(node, &parent);
AVER(compare(parent, key(node)) == CompareLESS);
goto down;
}
if (!visit(node, closure))
goto abort;
if (TreeHasRight(node)) {
node = stepDownRight(node, &parent);
AVER(compare(parent, key(node)) != CompareLESS);
goto down;
}
up:
if (parent == TreeEMPTY)
return TRUE;
if (compare(parent, key(node)) != CompareLESS) {
node = stepUpLeft(node, &parent);
goto up;
}
node = stepUpRight(node, &parent);
if (!visit(node, closure))
goto abort;
if (!TreeHasRight(node))
goto up;
node = stepDownRight(node, &parent);
goto down;
abort:
if (parent == TreeEMPTY)
return FALSE;
if (compare(parent, key(node)) != CompareLESS)
node = stepUpLeft(node, &parent);
else
node = stepUpRight(node, &parent);
goto abort;
}
/* TreeRotateLeft -- Rotate right child edge of node
*
* Rotates node, right child of node, and left child of right
* child of node, leftwards in the order stated. Preserves tree
* ordering.
*/
void TreeRotateLeft(Tree *treeIO)
{
Tree tree, right;
AVER(treeIO != NULL);
tree = *treeIO;
AVERT(Tree, tree);
right = TreeRight(tree);
AVERT(Tree, right);
TreeSetRight(tree, TreeLeft(right));
TreeSetLeft(right, tree);
*treeIO = right;
}
/* TreeRotateRight -- Rotate left child edge of node
*
* Rotates node, left child of node, and right child of left
* child of node, leftwards in the order stated. Preserves tree
* ordering.
*/
void TreeRotateRight(Tree *treeIO)
{
Tree tree, left;
AVER(treeIO != NULL);
tree = *treeIO;
AVERT(Tree, tree);
left = TreeLeft(tree);
AVERT(Tree, left);
TreeSetLeft(*treeIO, TreeRight(left));
TreeSetRight(left, *treeIO);
*treeIO = left;
}
/* TreeReverseLeftSpine -- reverse the pointers on the right spine
*
* Descends the left spine of a tree, updating each node's left child
* to point to its parent instead. The root's left child is set to
* TreeEMPTY. Returns the leftmost child, or TreeEMPTY if the tree
* was empty.
*/
Tree TreeReverseLeftSpine(Tree tree)
{
Tree node, parent;
AVERT(Tree, tree);
parent = TreeEMPTY;
node = tree;
while (node != TreeEMPTY) {
Tree child = TreeLeft(node);
TreeSetLeft(node, parent);
parent = node;
node = child;
}
return parent;
}
/* TreeReverseRightSpine -- reverse the pointers on the right spine
*
* Descends the right spine of a tree, updating each node's right child
* to point to its parent instead. The root's right child is set to
* TreeEMPTY. Returns the rightmost child or TreeEMPTY if the tree
* was empty.
*/
Tree TreeReverseRightSpine(Tree tree)
{
Tree node, parent;
AVERT(Tree, tree);
parent = TreeEMPTY;
node = tree;
while (node != TreeEMPTY) {
Tree child = TreeRight(node);
TreeSetRight(node, parent);
parent = node;
node = child;
}
return parent;
}
/* TreeToVine -- unbalance a tree into a single right spine */
Count TreeToVine(Tree *link)
{
Count count = 0;
AVER(link != NULL);
AVERT(Tree, *link);
while (*link != TreeEMPTY) {
while (TreeHasLeft(*link))
TreeRotateRight(link);
link = &((*link)->right);
++count;
}
return count;
}
/* TreeBalance -- rebalance a tree
*
* Linear time, constant space rebalance.
*
* Quentin F. Stout and Bette L. Warren,
* "Tree Rebalancing in Optimal Time and Space",
* Communications of the ACM, Vol. 29, No. 9 (September 1986), p. 902-908
*/
void TreeBalance(Tree *treeIO)
{
Count depth;
AVER(treeIO != NULL);
AVERT(Tree, *treeIO);
depth = TreeToVine(treeIO);
if (depth > 2) {
Count n = depth - 1;
do {
Count m = n / 2, i;
Tree *link = treeIO;
for (i = 0; i < m; ++i) {
TreeRotateLeft(link);
link = &((*link)->right);
}
n = n - m - 1;
} while (n > 1);
}
}
/* TreeTraverseAndDelete -- traverse a tree while deleting nodes
*
* The visitor function must return TRUE to delete the current node,
* or FALSE to keep it.
*
* See <design/arena/#chunk.delete.tricky>.
*/
void TreeTraverseAndDelete(Tree *treeIO, TreeVisitor visitor,
void *closure)
{
Tree *treeref = treeIO;
AVER(treeIO != NULL);
AVERT(Tree, *treeIO);
AVER(FUNCHECK(visitor));
/* closure arbitrary */
TreeToVine(treeIO);
while (*treeref != TreeEMPTY) {
Tree tree = *treeref; /* Current node. */
Tree *nextref = &tree->right; /* Location of pointer to next node. */
Tree next = *nextref; /* Next node. */
if ((*visitor)(tree, closure)) {
/* Delete current node. */
*treeref = next;
} else {
/* Keep current node. */
treeref = nextref;
}
}
TreeBalance(treeIO);
}
/* C. COPYRIGHT AND LICENSE
*
* Copyright (C) 2014-2018 Ravenbrook Limited <http://www.ravenbrook.com/>.
* All rights reserved. This is an open source license. Contact
* Ravenbrook for commercial licensing options.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* 3. Redistributions in any form must be accompanied by information on how
* to obtain complete source code for this software and any accompanying
* software that uses this software. The source code must either be
* included in the distribution or be available for no more than the cost
* of distribution plus a nominal fee, and must be freely redistributable
* under reasonable conditions. For an executable file, complete source
* code means the source code for all modules it contains. It does not
* include source code for modules or files that typically accompany the
* major components of the operating system on which the executable file
* runs.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
* PURPOSE, OR NON-INFRINGEMENT, ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT HOLDERS AND CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
* ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/