#ifndef lint
static char sccsid[] = "@(#)eorptr.c 1.1 (UKC) 4/7/86 from retniop.c 1.6 (UKC) 3/7/86";
#endif lint
/*
* Pointer-eoring tree requires no extra space (including stack)
* to walk an arbitrarily big tree.
*
* Instead of regular pointers in each branch, we store the exclusive OR
* of the addresses of the child and the parent of the current node.
*
* State of the tree in mid-walk: (only history bits are modified)
*
* ROOT
* ---------
* A|wentleft |
* |---------|
* | B | C |
* ---------
* / \
* / \
* L J
* --------- ---------
* B|wentleft | C| |
* |---------| |---------|
* |A^D | A | | A | A |
* --------- ---------
* /
* /
* L
* ---------
* parent -->D|wentright|
* |---------|
* | B |B^E |
* ---------
* \
* \
* J
* ---------
* E| | <-- current
* |---------|
* | D | D |
* ---------
*/
#include
#include "ptr.h"
/*
* Some defines to move about in the tree.
*/
#define goleft(current, parent) do { \
node_t *child; \
\
/* go down left branch */ \
current->history = wentleft; \
child = (node_t *)((int)(current->left)^(int)parent); \
parent = current; \
current = child; \
} while (0)
/* goright: same as goleft, but to the right (surprise!) */
#define goright(current, parent) do { \
node_t *child; \
\
/* go down right branch */ \
current->history = wentright; \
child = (node_t *)((int)(current->right)^(int)parent);\
parent = current; \
current = child; \
} while (0)
/*
* find grandparent in one of the parent's pointers.
* Which one it was stored in depends upon which way
* we came down from the parent.
*
* Performs the exact inverse transformation of goleft or goright.
*/
#define goup(current, parent) do { \
node_t *grandparent; \
\
switch (parent->history) { \
case wentleft: \
grandparent = (node_t *)((int)(parent->left)^(int)current);\
break; \
case wentright: \
grandparent = (node_t *)((int)(parent->right)^(int)current);\
break; \
} \
current = parent; \
parent = grandparent; \
} while (0)
treewalk(order, current, process)
order_t order; /* which sort of treewalk to do */
node_t *current; /* pointer to root of tree */
void (*process)(); /* function to apply to each node */
{
node_t *parent = NULL;
if (current == NULL) return;
goto unvisited;
for (;;) switch (current->history) {
unvisited: /* Deal with a node to which we have just come down. */
if (order == preorder) (* process)(current);
if (current->left != parent) {
goleft(current, parent);
goto unvisited;
}
/* else we have processed the (null) left branch so */
/* go for the right branch */
case wentleft:
/* Deal with a node whose left branch has been processed. */
if (order == inorder) (* process)(current);
/* try going down the right branch */
if (current->right != parent) {
goright(current, parent);
goto unvisited;
}
/* else we have processed the right branch completely so */
/* do the necessary and go back up */
case wentright:
/* Deal with a node where both branches have been done */
if (order == postorder) (* process)(current);
/* the left branch, the current node and the right
* branch have been processed. Go back up. */
/* check to see if we are back at the root */
if (parent == NULL) return;
goup(current, parent);
/* loop and switch according to which branch we just came up */
}
}
addnode(root, n)
node_t **root; /* ptr to root (var for first node) */
{
char *malloc();
node_t *current = *root;
node_t *parent = NULL;
/* wend our way down to the leaf we have to add the new entry to */
while (current != NULL) {
if (n < current->contents)
goleft(current, parent);
else
goright(current, parent);
}
/* now current == NULL and parent points to the leaf node we are to
* add to. Parent->history determines which of the branches to add the
* new cell onto. This happens for free on the way back up.
*/
current = (node_t *) malloc(sizeof(node_t));
if (current == (node_t *) 0) {
fputs("Out of memory", stderr);
exit(1);
}
current->contents = n;
current->left = current->right = parent;
switch (parent->history) {
case wentleft:
parent->left = (node_t *)((int)(parent->left)^(int)current);
break;
case wentright:
parent->right = (node_t *)((int)(parent->right)^(int)current);
break;
}
while (parent != NULL) goup(current, parent);
/* This only has an effect for the first node.
* After that it is a no-op
*/
*root = current;
}