opal/class/opal_rb_tree.c

/* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil -*- */
/*
 * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
 *                         University Research and Technology
 *                         Corporation.  All rights reserved.
 * Copyright (c) 2004-2013 The University of Tennessee and The University
 *                         of Tennessee Research Foundation.  All rights
 *                         reserved.
 * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
 *                         University of Stuttgart.  All rights reserved.
 * Copyright (c) 2004-2005 The Regents of the University of California.
 *                         All rights reserved.
 * Copyright (c) 2015      Los Alamos National Security, LLC. All rights
 *                         reserved.
 * $COPYRIGHT$
 *
 * Additional copyrights may follow
 *
 * $HEADER$
 */
/*
 * @file
 */

#include "opal_config.h"

#include "opal/class/opal_rb_tree.h"

/* Private functions */
static void btree_insert(opal_rb_tree_t *tree, opal_rb_tree_node_t * node);
static void btree_delete_fixup(opal_rb_tree_t *tree, opal_rb_tree_node_t * x);
static opal_rb_tree_node_t * btree_successor(opal_rb_tree_t * tree,
                                             opal_rb_tree_node_t * node);
static opal_rb_tree_node_t * opal_rb_tree_find_node(opal_rb_tree_t *tree, void *key);
static void left_rotate(opal_rb_tree_t *tree, opal_rb_tree_node_t * x);
static void right_rotate(opal_rb_tree_t *tree, opal_rb_tree_node_t * x);
static void inorder_destroy(opal_rb_tree_t *tree, opal_rb_tree_node_t * node);
static void inorder_traversal(opal_rb_tree_t *tree,
                              opal_rb_tree_condition_fn_t cond,
                              opal_rb_tree_action_fn_t action,
                              opal_rb_tree_node_t * node);


/**
 * the constructor function. creates the free list to get the nodes from
 *
 * @param object the tree that is to be used
 *
 * @retval NONE
 */
static void opal_rb_tree_construct(opal_object_t * object)
{
    opal_rb_tree_t * tree = (opal_rb_tree_t *) object;
    tree->root_ptr = NULL;
    OBJ_CONSTRUCT(&(tree->free_list), opal_free_list_t);
    opal_free_list_init (&(tree->free_list), sizeof(opal_rb_tree_node_t),
            opal_cache_line_size, OBJ_CLASS(opal_rb_tree_node_t),
            0,opal_cache_line_size, 0, -1 , 128, NULL, 0, NULL, NULL, NULL);
}

/**
 * the destructor function. Free the tree and destroys the free list.
 *
 * @param object the tree object
 */
static void opal_rb_tree_destruct(opal_object_t * object)
{
    if(NULL != ((opal_rb_tree_t *)object)->root_ptr) {
        opal_rb_tree_destroy((opal_rb_tree_t *) object);
    }
    OBJ_DESTRUCT(&(((opal_rb_tree_t *)object)->free_list));
    return;
}

/* declare the instance of the classes  */
OBJ_CLASS_INSTANCE(opal_rb_tree_node_t, opal_free_list_item_t, NULL, NULL);
OBJ_CLASS_INSTANCE(opal_rb_tree_t, opal_object_t, opal_rb_tree_construct,
                   opal_rb_tree_destruct);

/* Create the tree */
int opal_rb_tree_init(opal_rb_tree_t * tree,
                      opal_rb_tree_comp_fn_t comp)
{
    opal_free_list_item_t * node;
    /* we need to get memory for the root pointer from the free list */
    node = opal_free_list_get (&(tree->free_list));
    tree->root_ptr = (opal_rb_tree_node_t *) node;
    if (NULL == node) {
        return OPAL_ERR_OUT_OF_RESOURCE;
    }

    node = opal_free_list_get (&(tree->free_list));
    if (NULL == node) {
        opal_free_list_return (&tree->free_list, (opal_free_list_item_t*)tree->root_ptr);
        return OPAL_ERR_OUT_OF_RESOURCE;
    }
    tree->nill = (opal_rb_tree_node_t *) node;
    /* initialize tree->nill */
    tree->nill->color = BLACK;
    tree->nill->left = tree->nill;
    tree->nill->right = tree->nill;
    tree->nill->parent = tree->nill;

    /* initialize the 'root' pointer */
    tree->root_ptr->left = tree->nill;
    tree->root_ptr->right = tree->nill;
    tree->root_ptr->parent = tree->nill;
    tree->root_ptr->color = BLACK;

    tree->comp = comp;

    /* set the tree size to zero */
    tree->tree_size = 0;

    return OPAL_SUCCESS;
}


/* This inserts a node into the tree based on the passed values. */
int opal_rb_tree_insert(opal_rb_tree_t *tree, void * key, void * value)
{
    opal_rb_tree_node_t * y;
    opal_rb_tree_node_t * node;
    opal_free_list_item_t * item;

    /* get the memory for a node */
    item = opal_free_list_get (&tree->free_list);
    if (NULL == item) {
        return OPAL_ERR_OUT_OF_RESOURCE;
    }
    node = (opal_rb_tree_node_t *) item;
    /* insert the data into the node */
    node->key = key;
    node->value = value;

    /* insert the node into the tree */
    btree_insert(tree, node);

    /*do the rotations */
    /* usually one would have to check for NULL, but because of the sentinal,
     * we don't have to   */
    while (node->parent->color == RED) {
        if (node->parent == node->parent->parent->left) {
            y = node->parent->parent->right;
            if (y->color == RED) {
                node->parent->color = BLACK;
                y->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->right) {
                    node = node->parent;
                    left_rotate(tree, node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                right_rotate(tree, node->parent->parent);
            }
        } else {
            y = node->parent->parent->left;
            if (y->color == RED) {
                node->parent->color = BLACK;
                y->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->left) {
                    node = node->parent;
                    right_rotate(tree, node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                left_rotate(tree, node->parent->parent);
            }
        }
    }
    /* after the rotations the root is black */
    tree->root_ptr->left->color = BLACK;
    return OPAL_SUCCESS;
}

/* Finds the node in the tree based on the key */
void * opal_rb_tree_find_with(opal_rb_tree_t *tree, void *key,
        opal_rb_tree_comp_fn_t compfn)
{
    opal_rb_tree_node_t * node;
    int compvalue;

    node = tree->root_ptr->left;
    while (node != tree->nill) {
        compvalue = compfn(key, node->key);
        /* if the result of the comparison function is 0, we found it */
        if (compvalue == 0) {
            return node->value;
        }
        /* else if it is less than 0, go left, else right */
        node = ((compvalue < 0) ? node->left : node->right);
    }
    /* if we didn't find anything, return NULL */
    return NULL;
}

/* Finds the node in the tree based on the key and returns a pointer
 * to the node. This is a bit a code duplication, but this has to be fast
 * so we go ahead with the duplication */
static opal_rb_tree_node_t * opal_rb_tree_find_node(opal_rb_tree_t *tree, void *key)
{
    opal_rb_tree_node_t * node;
    int compvalue;

    node = tree->root_ptr->left;
    while (node != tree->nill) {
        compvalue = tree->comp(key, node->key);
        /* if the result of the comparison function is 0, we found it */
        if (compvalue == 0) {
            return node;
        }
        /* else if it is less than 0, go left, else right */
        node = ((compvalue < 0) ? node->left : node->right);
    }
    /* if we didn't find anything, return NULL */
    return NULL;
}

/* Delete a node from the tree based on the key */
int opal_rb_tree_delete(opal_rb_tree_t *tree, void *key)
{
    opal_rb_tree_node_t * p;
    opal_rb_tree_node_t * todelete;
    opal_rb_tree_node_t * y;
    opal_free_list_item_t * item;

    p = opal_rb_tree_find_node(tree, key);
    if (NULL == p) {
        return OPAL_ERR_NOT_FOUND;
    }
    if ((p->left == tree->nill) || (p->right == tree->nill)) {
        todelete = p;
    } else {
        todelete = btree_successor(tree, p);
    }

    if (todelete->left == tree->nill) {
        y = todelete->right;
    } else {
        y = todelete->left;
    }

    y->parent = todelete->parent;

    if (y->parent == tree->root_ptr) {
        tree->root_ptr->left = y;
    } else {
        if (todelete == todelete->parent->left) {
         todelete->parent->left = y;
        } else {
            todelete->parent->right = y;
        }
    }

    if (todelete != p) {
        p->key = todelete->key;
        p->value = todelete->value;
    }

    if (todelete->color == BLACK) {
        btree_delete_fixup(tree, y);
    }
    item = (opal_free_list_item_t *) todelete;
    opal_free_list_return (&(tree->free_list), item);
    --tree->tree_size;
    return OPAL_SUCCESS;
}


/* Destroy the hashmap    */
int opal_rb_tree_destroy(opal_rb_tree_t *tree)
{
    opal_free_list_item_t * item;
    /* Recursive inorder traversal for delete    */

    inorder_destroy(tree, tree->root_ptr);
    /* Now free the root -- root does not get free'd in the above
     * inorder destroy    */
    item = (opal_free_list_item_t *) tree->root_ptr;
    opal_free_list_return(&(tree->free_list), item);

    /* free the tree->nill node */
    item = (opal_free_list_item_t *) tree->nill;
    opal_free_list_return (&(tree->free_list), item);
    return OPAL_SUCCESS;
}


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

static opal_rb_tree_node_t * btree_successor(opal_rb_tree_t * tree, opal_rb_tree_node_t * node)
{
    opal_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   */
static void btree_insert(opal_rb_tree_t *tree, opal_rb_tree_node_t * node)
{
    opal_rb_tree_node_t * parent = tree->root_ptr;
    opal_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;
        n = ((tree->comp(node->key, n->key) <= 0) ? n->left : 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    */
static void btree_delete_fixup(opal_rb_tree_t *tree, opal_rb_tree_node_t * x)
{
    opal_rb_tree_node_t * w;
    opal_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    */

static void
inorder_destroy(opal_rb_tree_t *tree, opal_rb_tree_node_t * node)
{
    opal_free_list_item_t * item;

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

    inorder_destroy(tree, node->left);

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

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

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

int opal_rb_tree_traverse(opal_rb_tree_t *tree,
                          opal_rb_tree_condition_fn_t cond,
                          opal_rb_tree_action_fn_t action)
{
    if ((cond == NULL) || (action == NULL)) {
        return OPAL_ERROR;
    }

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

    return OPAL_SUCCESS;
}


static void inorder_traversal(opal_rb_tree_t *tree,
                              opal_rb_tree_condition_fn_t cond,
                              opal_rb_tree_action_fn_t action,
                              opal_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    */
static void left_rotate(opal_rb_tree_t *tree, opal_rb_tree_node_t * x)
{
    opal_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 */
static void right_rotate(opal_rb_tree_t *tree, opal_rb_tree_node_t * x)
{
    opal_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 opal_rb_tree_size(opal_rb_tree_t *tree)
{
        return tree->tree_size;
}

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

void inorder(opal_rb_tree_t * tree, opal_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(opal_rb_tree_t *tree)
{
    inorder(tree, tree->root_ptr->left);
}

#endif