ompi_rb_tree.c

MPI stands for the Message Passing Interface. Written by the MPI Forum (a large committee comprising

/* Find the next inorder successor of a node    */

ompi_rb_tree_node_t * btree_successor(ompi_rb_tree_t * tree, ompi_rb_tree_node_t * node)
{
    ompi_rb_tree_node_t * p;

    if (node->right == tree->nill) {
        p = node->parent;
        while (node == p->right) {
            node = p;
            p = p->parent;
        }
        if(p == tree->root_ptr) {
            return(tree->nill);
        }
        return p;
    }

    p = node->right;
    while(p->left != tree->nill) {
        p = p->left;
    }
    return p;
}


/* Insert an element in the normal binary search tree fashion    */
/* this function goes through the tree and finds the leaf where
 * the node will be inserted   */
void btree_insert(ompi_rb_tree_t *tree, ompi_rb_tree_node_t * node)
{
    ompi_rb_tree_node_t * parent = tree->root_ptr;
    ompi_rb_tree_node_t * n = parent->left; /* the real root of the tree */

    /* set up initial values for the node */
    node->color = RED;
    node->parent = NULL;
    node->left = tree->nill;
    node->right = tree->nill;

    /* find the leaf where we will insert the node */
    while (n != tree->nill) {
        parent = n;
        (tree->comp(node->key, n->key) <= 0) ? (n = n->left) : (n = n->right);
    }

    /* place it on either the left or the right */
    if((parent == tree->root_ptr) || (tree->comp(node->key, parent->key) <= 0)) {
        parent->left = node;
    } else {
        parent->right = node;
    }

    /* set its parent and children */
    node->parent = parent;
    node->left = tree->nill;
    node->right = tree->nill;
    ++(tree->tree_size);
    return;
}

/* Fixup the balance of the btree after deletion    */
void btree_delete_fixup(ompi_rb_tree_t *tree, ompi_rb_tree_node_t * x)
{
    ompi_rb_tree_node_t * w;
    ompi_rb_tree_node_t * root = tree->root_ptr->left;
    while ((x != root) && (x->color == BLACK)) {
        if (x == x->parent->left) {
            w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                left_rotate(tree, x->parent);
                w = x->parent->right;
            }
            if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    right_rotate(tree, w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                left_rotate(tree, x->parent);
                x = root;
            }
        } else { /* right    */

            w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                right_rotate(tree, x->parent);
                w = x->parent->left;
            }
            if ((w->right->color == BLACK) && (w->left->color == BLACK)) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    left_rotate(tree, w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                right_rotate(tree, x->parent);
                x = root;
            }
        }
    }

    x->color = BLACK;
    return;
}


/* Free the nodes in inorder fashion    */

void
inorder_destroy(ompi_rb_tree_t *tree, ompi_rb_tree_node_t * node)
{
    ompi_free_list_item_t * item;

    if (node == tree->nill) {
        return;
    }

    inorder_destroy(tree, node->left);

    if (node->left != tree->nill) {
        item = (ompi_free_list_item_t *) node->left;
        --tree->tree_size;
        OMPI_FREE_LIST_RETURN(&(tree->free_list), item);
    }

    inorder_destroy(tree, node->right);
    if (node->right != tree->nill) {
        item = (ompi_free_list_item_t *) node->right;
        --tree->tree_size;
        OMPI_FREE_LIST_RETURN(&(tree->free_list), item);
    }
}

/* Try to access all the elements of the hashmap conditionally */

int ompi_rb_tree_traverse(ompi_rb_tree_t *tree,
                          ompi_rb_tree_condition_fn_t cond,
                          ompi_rb_tree_action_fn_t action)
{
    if ((cond == NULL) || (action == NULL)) {
        return(OMPI_ERROR);
    }

    inorder_traversal(tree, cond, action, tree->root_ptr->left);

    return(OMPI_SUCCESS);
}


static void inorder_traversal(ompi_rb_tree_t *tree, 
                              ompi_rb_tree_condition_fn_t cond,
                              ompi_rb_tree_action_fn_t action,
                              ompi_rb_tree_node_t * node)
{
    if (node == tree->nill) {
        return;
    }

    inorder_traversal(tree, cond, action, node->left);

    if (cond(node->value)) {
        action(node->key, node->value);
    }

    inorder_traversal(tree, cond, action, node->right);
}

/* Left rotate the tree    */
/* basically what we want to do is to make x be the left child
 * of its right child    */
void left_rotate(ompi_rb_tree_t *tree, ompi_rb_tree_node_t * x)
{
    ompi_rb_tree_node_t * y;

    y = x->right;
    /* make the left child of y's parent be x if it is not the sentinal node*/
    if (y->left != tree->nill) {
        y->left->parent=x;
    }

    /* normlly we would have to check to see if we are at the root.
     * however, the root sentinal takes care of it for us */
    if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    /* the old parent of x is now y's parent */
    y->parent = x->parent;
    /* x's parent is y */
    x->parent = y;
    x->right = y->left;
    y->left = x;

    return;
}


/* Right rotate the tree    */
/* basically what we want to do is to make x be the right child
 * of its left child */
void right_rotate(ompi_rb_tree_t *tree, ompi_rb_tree_node_t * x)
{
    ompi_rb_tree_node_t * y;

    y = x->left;

    if(y->right != tree->nill) {
        y->right->parent = x;
    }

    if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }

    y->parent = x->parent;
    x->parent = y;
    x->left = y->right;
    y->right = x;

    return;
}


/* returns the size of the tree */
int ompi_rb_tree_size(ompi_rb_tree_t *tree)
{
        return(tree->tree_size);
}

/* below are a couple of debugging functions */
#if 0
#include <stdio.h>
static void inorder(ompi_rb_tree_t * tree, ompi_rb_tree_node_t * node);
static void print_inorder(ompi_rb_tree_t * tree);

void inorder(ompi_rb_tree_t * tree, ompi_rb_tree_node_t * node)
{
    static int level = 0;
    if (node == tree->nill) {
        printf("nill\n");
        return;
    }
    level++;
    inorder(tree, node->left);
    level--;
    printf("%d, level: %d\n", *((int *)node->value), level);
    level++;
    inorder(tree, node->right);
    level--;
}


void print_inorder(ompi_rb_tree_t *tree)
{
    inorder(tree, tree->root_ptr->left);
}

#endif