Listing 1

/*
 *      Traversal of multiple binary trees
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define BIGINT  (~(1 << ((8*sizeof(int))-1)))  /* maximum integer */
#define NNODES  25      /* the number of nodes per tree */
#define NTREES  10      /* the number of binary trees to traverse */

/* binary tree node definition */
typedef struct node     {
       struct node     *left;         /* left sub-tree */
       struct node     *right;        /* right sub-tree */
       int             key;           /* current node value */
}       NODE;

/***********************************************************************
* the following section is the single threaded example
***********************************************************************/
#ifdef SINGLE_THREAD

/* stack frame definition */
typedef struct frame    {
       struct node     *data;         /* the node being stacked */
       struct frame    *next;         /* the next stack entry */
}       FRAME;

/* push a tree node onto the stack */
void Push(FRAME **stackp, NODE *treep) {
FRAME *temp;
       assert(treep != NULL);
       temp = malloc(sizeof(FRAME));
       assert(temp != NULL);
       temp->data = treep;
       temp->next = *stackp;
       (*stackp) = temp;
       }

/* get the top data item from the stack (without popping) */
int Top(FRAME *stackp) {
NODE    *tempt;

       assert(stackp != NULL);
       temp = stackp->data;
       return(temp->key);
}

/* print the lowest value of all N trees */
void DisplayLowest(FRAME *stackp[], int *lowest) {
int current;
int topvalue;
int temp=BIGINT;
int i;

       /* for each tree in the list... */
       for (i=0; i < NTREES; i++) {
              /* if the tree has not been completely traversed, */
              if (stackp[i] != NULL) {
                     /* get the current key of this tree */
                     topvalue = Top(stackp[i]);
                     /* compare the current key with the other trees */
                     if (topvalue < temp) {
                            /* save the current tree number and its key */
                            current = i;
                            temp = topvalue;
                     }
              }
       }
       printf("key = %d\n", temp);
       *lowest = current;
}

/* removes and returns the top entry from the stack */
NODE *Pop(FRAME **stackp) {
FRAME *temp;
NODE *data;
       
       temp = *stackp;
       *stackp = (*stackp)->next;
       data = temp->data;
       free(temp);
       return(data);
}

/* traverse the right sub-tree */
void TraverseRightSub(FRAME **stackp) {
NODE *temp;
FRAME *sframe;
       
       /* find the right sub-tree of the current node */
       temp = Pop(stackp);
       temp = temp->right;

       /* traverse the sub tree as far left as possible */
       while (temp != NULL) {
              Push(stackp, temp);
              temp = temp->left;
       }
}

/* determine if there are unvisited nodes */
int StacksExist(FRAME *stackp[]) {
int i;

       for (i = 0; i < NTREES; i++){
              if (stackp[i] != NULL)
                     return(1);
       }
       return(0);
}

void MergeTrees(NODE *treep[]) {
FRAME *stackp[NTREES];
int i;

       /* preload all stacks */
       for (i = 0; i < NTREES; i++) {
              stackp[i] = NULL;
              while (treep[i] != NULL) {
                     Push(&stackp[i], treep[i]);
                     treep[i] = treep[i]->left;
              }
       }
       do {
              DisplayLowest(stackp, &i);
              TraverseRightSub(&stackp[i]);
       } while(StacksExist(stackp));
}

/*****************************************************************

* the following section is the multi threaded example

*****************************************************************/

#else

#include <multi_c.h>

/* print the contents of a node (wait until it
   is the lowest key)  */
void     PrintNode(NODE *tree) {
static   int     CurrentKey = BIGINT;

       /* wait until this node contains the lowest key value */
       do {
              if (CurrentKey > tree->key)
                     CurrentKey = tree->key;
              MtCYield();
       } while (CurrentKey != tree->key);
       /* reinitialize the current key */
       CurrentKey = BIGINT;
       printf("key = %d\n", tree->key);
}

/* recursively visit the nodes in a tree */
void  PrintTree(NODE *tree) {

       if (tree != NULL) {
              PrintTree(tree->left);
              PrintNode(tree);
              PrintTree(tree->right);
       }
}

/* traverse multiple binary trees */
void    MergeTrees(NODE **trees) {
int     i;

       /* create a thread for each tree... */
       for (i = 0; i < NTREES; i++) {
              MtCCoroutine(PrintTree(&trees[i]));
       }
}

#endif

/* recursively add a node to the tree */
void     AddKey(NODE **treep, int key) {

       if ((*treep) == NULL) {
              (*treep) = malloc(sizeof(NODE));
              assert(*treep != NULL);
              (*treep)->left = NULL;
              (*treep)->right = NULL;
              (*treep)->key = key;
       } else {
              if (key < (*treep)->key) {
                     AddKey(&((*treep)->left), key);
              } else {
                     AddKey(&((*treep)->right), key);
              }
       }
}

/* build a tree of NNODES random keys */
void    BuildTree(NODE **treep) {
int     i;

       for (i = 0; i < NNODES; i++) {
              AddKey(treep, rand());
       }
}


void    main() {
NODE    *trees[NTREES];
int     i;

       /* randomly build the trees */
       for (i = 0; i < NTREES; i++) {
              trees[i] = NULL;
              BuildTree(&trees[i]);
       }
       /* traverse the trees as a single tree */
       MergeTrees(trees);
}

/* End of File */