/* -*- 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-2018 Los Alamos National Security, LLC. All rights
 *                         reserved.
 * Copyright (c) 2020      Google, LLC. All rights reserved.
 * Copyright (c) 2025      NVIDIA Corporation.  All rights reserved.
 * $COPYRIGHT$
 *
 * Additional copyrights may follow
 *
 * $HEADER$
 */
/*
 * @file
 */

#include "opal_config.h"

#include "opal/class/opal_interval_tree.h"
#include <limits.h>

/* Private functions */
static void opal_interval_tree_insert_node(opal_interval_tree_t *tree,
                                           opal_interval_tree_node_t *node);

/* tree rebalancing functions */
static void opal_interval_tree_delete_fixup(opal_interval_tree_t *tree,
                                            opal_interval_tree_node_t *node,
                                            opal_interval_tree_node_t *parent);
static void opal_interval_tree_insert_fixup(opal_interval_tree_t *tree,
                                            opal_interval_tree_node_t *x);

static opal_interval_tree_node_t *opal_interval_tree_next(opal_interval_tree_t *tree,
                                                          opal_interval_tree_node_t *node);
static opal_interval_tree_node_t *
opal_interval_tree_find_node(opal_interval_tree_t *tree, uint64_t low, uint64_t high, void *data);

static opal_interval_tree_node_t *left_rotate(opal_interval_tree_t *tree,
                                              opal_interval_tree_node_t *x);
static opal_interval_tree_node_t *right_rotate(opal_interval_tree_t *tree,
                                               opal_interval_tree_node_t *x);

static void inorder_destroy(opal_interval_tree_t *tree, opal_interval_tree_node_t *node);

#define max(x, y) (((x) > (y)) ? (x) : (y))

/**
 * 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_interval_tree_construct(opal_interval_tree_t *tree)
{
    OBJ_CONSTRUCT(&tree->root, opal_interval_tree_node_t);
    OBJ_CONSTRUCT(&tree->nill, opal_interval_tree_node_t);
    OBJ_CONSTRUCT(&tree->free_list, opal_free_list_t);
    OBJ_CONSTRUCT(&tree->gc_list, opal_list_t);

    /* initialize sentinel */
    tree->nill.color = OPAL_INTERVAL_TREE_COLOR_BLACK;
    tree->nill.left = tree->nill.right = tree->nill.parent = &tree->nill;
    tree->nill.max = 0;
    tree->nill.data = NULL;

    /* initialize root sentinel */
    tree->root.color = OPAL_INTERVAL_TREE_COLOR_BLACK;
    tree->root.left = tree->root.right = tree->root.parent = &tree->nill;
    /* this simplifies inserting at the root as we only have to check the
     * low value. */
    tree->root.low = (uint64_t) -1;
    tree->root.data = NULL;

    /* set the tree size to zero */
    tree->tree_size = 0;
    tree->lock = 0;
    tree->reader_count = 0;
    tree->reader_id = 0;
    tree->epoch = 0;

    /* set all reader epochs to UINT_MAX. this value is used to simplify
     * checks against the current epoch. */
    for (int i = 0; i < OPAL_INTERVAL_TREE_MAX_READERS; ++i) {
        tree->reader_epochs[i] = UINT_MAX;
    }
}

/**
 * the destructor function. Free the tree and destroys the free list.
 *
 * @param object the tree object
 */
static void opal_interval_tree_destruct(opal_interval_tree_t *tree)
{
    opal_interval_tree_destroy(tree);

    OBJ_DESTRUCT(&tree->free_list);
    OBJ_DESTRUCT(&tree->root);
    OBJ_DESTRUCT(&tree->nill);
}

/* declare the instance of the classes  */
OBJ_CLASS_INSTANCE(opal_interval_tree_node_t, opal_free_list_item_t, NULL, NULL);
OBJ_CLASS_INSTANCE(opal_interval_tree_t, opal_object_t, opal_interval_tree_construct,
                   opal_interval_tree_destruct);

typedef int32_t opal_interval_tree_token_t;

/**
 * @brief pick and return a reader slot
 */
static opal_interval_tree_token_t opal_interval_tree_reader_get_token(opal_interval_tree_t *tree)
{
    opal_interval_tree_token_t token = -1;

    if (token < 0) {
        int32_t reader_count = tree->reader_count;
        /* NTH: could have used an atomic here but all we are after is some distribution of threads
         * across the reader slots. with high thread counts i see no real performance difference
         * using atomics. */
        token = tree->reader_id++ % OPAL_INTERVAL_TREE_MAX_READERS;
        while (OPAL_UNLIKELY(reader_count <= token)) {
            if (opal_atomic_compare_exchange_strong_32(&tree->reader_count, &reader_count,
                                                       token + 1)) {
                break;
            }
        }
    }

    while (
        !OPAL_ATOMIC_COMPARE_EXCHANGE_STRONG_32((opal_atomic_int32_t *) &tree->reader_epochs[token],
                                                &(int32_t){UINT_MAX}, tree->epoch)) {
    }

    return token;
}

static void opal_interval_tree_reader_return_token(opal_interval_tree_t *tree,
                                                   opal_interval_tree_token_t token)
{
    tree->reader_epochs[token] = UINT_MAX;
}

/* Create the tree */
int opal_interval_tree_init(opal_interval_tree_t *tree)
{
    return opal_free_list_init(&tree->free_list, sizeof(opal_interval_tree_node_t),
                               opal_cache_line_size, OBJ_CLASS(opal_interval_tree_node_t), 0,
                               opal_cache_line_size, 0, -1, 128, NULL, 0, NULL, NULL, NULL);
}

static bool opal_interval_tree_write_trylock(opal_interval_tree_t *tree)
{
    opal_atomic_rmb();
    return !(tree->lock || opal_atomic_swap_32(&tree->lock, 1));
}

static void opal_interval_tree_write_lock(opal_interval_tree_t *tree)
{
    while (!opal_interval_tree_write_trylock(tree)) {
    }
}

static void opal_interval_tree_write_unlock(opal_interval_tree_t *tree)
{
    opal_atomic_wmb();
    tree->lock = 0;
}

static void opal_interval_tree_insert_fixup_helper(opal_interval_tree_t *tree,
                                                   opal_interval_tree_node_t *node)
{
    opal_interval_tree_node_t *y, *parent = node->parent;
    bool rotate_right = false;

    if (parent->color == OPAL_INTERVAL_TREE_COLOR_BLACK) {
        return;
    }

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

    if (y->color == OPAL_INTERVAL_TREE_COLOR_RED) {
        parent->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
        y->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
        parent->parent->color = OPAL_INTERVAL_TREE_COLOR_RED;
        opal_interval_tree_insert_fixup_helper(tree, parent->parent);
        return;
    }

    if (rotate_right) {
        if (node == parent->right) {
            node = left_rotate(tree, parent);
            parent = node->parent;
        }

        parent->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
        parent->parent->color = OPAL_INTERVAL_TREE_COLOR_RED;
        (void) right_rotate(tree, parent->parent);
    } else {
        if (node == parent->left) {
            node = right_rotate(tree, parent);
            parent = node->parent;
        }
        parent->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
        parent->parent->color = OPAL_INTERVAL_TREE_COLOR_RED;
        (void) left_rotate(tree, parent->parent);
    }

    opal_interval_tree_insert_fixup_helper(tree, node);
}

static void opal_interval_tree_insert_fixup(opal_interval_tree_t *tree,
                                            opal_interval_tree_node_t *node)
{
    /* do the rotations */
    /* usually one would have to check for NULL, but because of the sentinal,
     * we don't have to   */
    opal_interval_tree_insert_fixup_helper(tree, node);

    /* after the rotations the root is black */
    tree->root.left->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
}

/**
 * @brief Guts of the delete fixup
 *
 * @param[in] tree    opal interval tree
 * @param[in] node    node to fixup
 * @param[in] left    true if the node is a left child of its parent
 *
 * @returns the next node to fixup or root if done
 */
static inline opal_interval_tree_node_t *
opal_interval_tree_delete_fixup_helper(opal_interval_tree_t *tree, opal_interval_tree_node_t *node,
                                       opal_interval_tree_node_t *parent, const bool left)
{
    opal_interval_tree_node_t *w;

    /* get sibling */
    w = left ? parent->right : parent->left;
    if (w->color == OPAL_INTERVAL_TREE_COLOR_RED) {
        w->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
        parent->color = OPAL_INTERVAL_TREE_COLOR_RED;
        if (left) {
            (void) left_rotate(tree, parent);
            w = parent->right;
        } else {
            (void) right_rotate(tree, parent);
            w = parent->left;
        }
    }

    if ((w->left->color == OPAL_INTERVAL_TREE_COLOR_BLACK)
        && (w->right->color == OPAL_INTERVAL_TREE_COLOR_BLACK)) {
        w->color = OPAL_INTERVAL_TREE_COLOR_RED;
        return parent;
    }

    if (left) {
        if (w->right->color == OPAL_INTERVAL_TREE_COLOR_BLACK) {
            w->left->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
            w->color = OPAL_INTERVAL_TREE_COLOR_RED;
            (void) right_rotate(tree, w);
            w = parent->right;
        }
        w->color = parent->color;
        parent->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
        w->right->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
        (void) left_rotate(tree, parent);
    } else {
        if (w->left->color == OPAL_INTERVAL_TREE_COLOR_BLACK) {
            w->right->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
            w->color = OPAL_INTERVAL_TREE_COLOR_RED;
            (void) left_rotate(tree, w);
            w = parent->left;
        }
        w->color = parent->color;
        parent->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
        w->left->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
        (void) right_rotate(tree, parent);
    }

    /* return the root */
    return tree->root.left;
}

/* Fixup the balance of the btree after deletion    */
static void opal_interval_tree_delete_fixup(opal_interval_tree_t *tree,
                                            opal_interval_tree_node_t *node,
                                            opal_interval_tree_node_t *parent)
{
    while ((node != tree->root.left) && (node->color == OPAL_INTERVAL_TREE_COLOR_BLACK)) {
        node = opal_interval_tree_delete_fixup_helper(tree, node, parent, node == parent->left);
        parent = node->parent;
    }

    node->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
    tree->nill.color = OPAL_INTERVAL_TREE_COLOR_BLACK;
}

/* traverse the garbage-collection list and return any nodes that can not have any
 * references. this function MUST be called with the writer lock held. */
static void opal_interval_tree_gc_clean(opal_interval_tree_t *tree)
{
    opal_interval_tree_node_t *node, *next;
    uint32_t oldest_epoch = UINT_MAX;

    if (0 == opal_list_get_size(&tree->gc_list)) {
        return;
    }

    for (int i = 0; i < tree->reader_count; ++i) {
        oldest_epoch = (oldest_epoch < tree->reader_epochs[i]) ? oldest_epoch
                                                               : tree->reader_epochs[i];
    }

    OPAL_LIST_FOREACH_SAFE (node, next, &tree->gc_list, opal_interval_tree_node_t) {
        if (node->epoch < oldest_epoch) {
            opal_list_remove_item(&tree->gc_list, &node->super.super);
            opal_free_list_return_st(&tree->free_list, &node->super);
        }
    }
}

/* This inserts a node into the tree based on the passed values. */
int opal_interval_tree_insert(opal_interval_tree_t *tree, void *value, uint64_t low, uint64_t high)
{
    opal_interval_tree_node_t *node;

    if (low > high) {
        return OPAL_ERR_BAD_PARAM;
    }

    opal_interval_tree_write_lock(tree);

    opal_interval_tree_gc_clean(tree);

    /* get the memory for a node */
    node = (opal_interval_tree_node_t *) opal_free_list_get(&tree->free_list);
    if (OPAL_UNLIKELY(NULL == node)) {
        opal_interval_tree_write_unlock(tree);
        return OPAL_ERR_OUT_OF_RESOURCE;
    }

    /* insert the data into the node */
    node->data = value;
    node->low = low;
    node->high = high;
    node->max = high;
    node->epoch = tree->epoch;

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

    opal_interval_tree_insert_fixup(tree, node);
    opal_interval_tree_write_unlock(tree);

    return OPAL_SUCCESS;
}

static int opal_interval_tree_compare_node(opal_interval_tree_node_t *node, uint64_t low,
                                           uint64_t high, void *data)
{
    if ((data && node->low == low && node->high == high && node->data == data)
        || (!data && node->low <= low && node->high >= high)) {
        return 0;
    }
    if (node->low > low) {
        return -1;
    }
    if (node->low < low) {
        return 1;
    }
    if (node->high < high) {
        return -1;
    }
    if (node->high > high) {
        return 1;
    }
    if (node->data > data) {
        return -1;
    }
    return 1;
}

static opal_interval_tree_node_t *opal_interval_tree_find_interval(opal_interval_tree_t *tree,
                                                                   opal_interval_tree_node_t *node,
                                                                   uint64_t low, uint64_t high,
                                                                   void *data)
{
    if (node == &tree->nill) {
        return NULL;
    }

    int check = opal_interval_tree_compare_node(node, low, high, data);
    if (0 == check) {
        return node;
    }

    if (-1 == check) {
        return opal_interval_tree_find_interval(tree, node->left, low, high, data);
    }

    return opal_interval_tree_find_interval(tree, node->right, low, high, data);
}

/* 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_interval_tree_node_t *
opal_interval_tree_find_node(opal_interval_tree_t *tree, uint64_t low, uint64_t high, void *data)
{
    return opal_interval_tree_find_interval(tree, tree->root.left, low, high, data);
}

void *opal_interval_tree_find_overlapping(opal_interval_tree_t *tree, uint64_t low, uint64_t high)
{
    opal_interval_tree_token_t token;
    opal_interval_tree_node_t *node;

    token = opal_interval_tree_reader_get_token(tree);
    node = opal_interval_tree_find_node(tree, low, high, NULL);
    opal_interval_tree_reader_return_token(tree, token);

    return node ? node->data : NULL;
}

static size_t opal_interval_tree_depth_node(opal_interval_tree_t *tree,
                                            opal_interval_tree_node_t *node)
{
    if (&tree->nill == node) {
        return 0;
    }

    return 1
           + max(opal_interval_tree_depth_node(tree, node->right),
                 opal_interval_tree_depth_node(tree, node->left));
}

size_t opal_interval_tree_depth(opal_interval_tree_t *tree)
{
    opal_interval_tree_token_t token;
    size_t depth;

    token = opal_interval_tree_reader_get_token(tree);
    depth = opal_interval_tree_depth_node(tree, &tree->root);
    opal_interval_tree_reader_return_token(tree, token);

    return depth;
}

/* update the value of a tree pointer */
static inline void rp_publish(opal_interval_tree_node_t **ptr, opal_interval_tree_node_t *node)
{
    /* ensure all writes complete before continuing */
    opal_atomic_wmb();
    /* just set the value */
    *ptr = node;
}

static inline void rp_wait_for_readers(opal_interval_tree_t *tree)
{
    uint32_t epoch_id = ++tree->epoch;

    /* wait for all readers to see the new tree version */
    for (int i = 0; i < tree->reader_count; ++i) {
        while (tree->reader_epochs[i] < epoch_id) {
        }
    }
}

/* waits for all writers to finish with the node then releases the last reference */
static inline void rp_free_wait(opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
{
    rp_wait_for_readers(tree);
    /* no other threads are working on this node so go ahead and return it */
    opal_free_list_return_st(&tree->free_list, &node->super);
}

/* schedules the node for releasing */
static inline void rp_free(opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
{
    opal_list_append(&tree->gc_list, &node->super.super);
}

static opal_interval_tree_node_t *opal_interval_tree_node_copy(opal_interval_tree_t *tree,
                                                               opal_interval_tree_node_t *node)
{
    opal_interval_tree_node_t *copy = (opal_interval_tree_node_t *) opal_free_list_wait_st(
        &tree->free_list);
    size_t color_offset = offsetof(opal_interval_tree_node_t, color);
    assert(NULL != copy);
    memcpy((unsigned char *) copy + color_offset, (unsigned char *) node + color_offset,
           sizeof(*node) - color_offset);
    return copy;
}

/* this function deletes a node that is either a left or right leaf (or both) */
static void opal_interval_tree_delete_leaf(opal_interval_tree_t *tree,
                                           opal_interval_tree_node_t *node)
{
    const opal_interval_tree_node_t *nill = &tree->nill;
    opal_interval_tree_node_t **parent_ptr, *next, *parent = node->parent;
    opal_interval_tree_nodecolor_t color = node->color;

    assert(node->left == nill || node->right == nill);

    parent_ptr = (parent->right == node) ? &parent->right : &parent->left;

    next = (node->right == nill) ? node->left : node->right;

    next->parent = node->parent;
    rp_publish(parent_ptr, next);

    rp_free(tree, node);

    if (OPAL_INTERVAL_TREE_COLOR_BLACK == color) {
        if (OPAL_INTERVAL_TREE_COLOR_RED == next->color) {
            next->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
        } else {
            opal_interval_tree_delete_fixup(tree, next, parent);
        }
    }
}

static void opal_interval_tree_delete_interior(opal_interval_tree_t *tree,
                                               opal_interval_tree_node_t *node)
{
    opal_interval_tree_node_t **parent_ptr, *next, *next_copy, *parent = node->parent;
    opal_interval_tree_nodecolor_t color = node->color, next_color;

    parent_ptr = (parent->right == node) ? &parent->right : &parent->left;
    next = opal_interval_tree_next(tree, node);
    next_color = next->color;

    if (next != node->right) {
        /* case 3 */
        next_copy = opal_interval_tree_node_copy(tree, next);
        next_copy->color = node->color;
        next_copy->left = node->left;
        next_copy->left->parent = next_copy;
        next_copy->right = node->right;
        next_copy->right->parent = next_copy;
        next_copy->parent = node->parent;

        rp_publish(parent_ptr, next_copy);
        rp_free_wait(tree, node);

        opal_interval_tree_delete_leaf(tree, next);
    } else {
        /* case 2. no copies are needed */
        next->color = color;
        next->left = node->left;
        next->left->parent = next;
        next->parent = node->parent;
        rp_publish(parent_ptr, next);
        rp_free(tree, node);

        /* since we are actually "deleting" the next node the fixup needs to happen on the
         * right child of next (by definition next was a left child) */
        if (OPAL_INTERVAL_TREE_COLOR_BLACK == next_color) {
            if (OPAL_INTERVAL_TREE_COLOR_RED == next->right->color) {
                next->right->color = OPAL_INTERVAL_TREE_COLOR_BLACK;
            } else {
                opal_interval_tree_delete_fixup(tree, next->right, next);
            }
        }
    }
}

/* Delete a node from the tree based on the key */
int opal_interval_tree_delete(opal_interval_tree_t *tree, uint64_t low, uint64_t high, void *data)
{
    opal_interval_tree_node_t *node;

    opal_interval_tree_write_lock(tree);
    node = opal_interval_tree_find_node(tree, low, high, data);
    if (NULL == node) {
        opal_interval_tree_write_unlock(tree);
        return OPAL_ERR_NOT_FOUND;
    }

    /* there are three cases that have to be handled:
     * 1) the node p is a left leaf or a right left (one of p's children is nill)
     *    in this case we can delete p and we can replace it with one of it's children
     *    or nill (if both children are nill).
     * 2) the right child of p is a left leaf (node->right->left == nill)
     *    in this case we can set node->right->left = node->left and replace node with node->right
     * 3) p is a interior node
     *    we replace node with next(node)
     */

    if ((node->left == &tree->nill) || (node->right == &tree->nill)) {
        /* handle case 1 */
        opal_interval_tree_delete_leaf(tree, node);
    } else {
        /* handle case 2 and 3 */
        opal_interval_tree_delete_interior(tree, node);
    }

    --tree->tree_size;

    opal_interval_tree_write_unlock(tree);

    return OPAL_SUCCESS;
}

int opal_interval_tree_destroy(opal_interval_tree_t *tree)
{
    /* Recursive inorder traversal for delete */
    inorder_destroy(tree, &tree->root);
    tree->tree_size = 0;
    return OPAL_SUCCESS;
}

/* Find the next inorder successor of a node    */
static opal_interval_tree_node_t *opal_interval_tree_next(opal_interval_tree_t *tree,
                                                          opal_interval_tree_node_t *node)
{
    opal_interval_tree_node_t *p = node->right;

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

        if (p == &tree->root) {
            return &tree->nill;
        }

        return p;
    }

    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 opal_interval_tree_insert_node(opal_interval_tree_t *tree,
                                           opal_interval_tree_node_t *node)
{
    opal_interval_tree_node_t *parent = &tree->root;
    opal_interval_tree_node_t *n = parent->left; /* the real root of the tree */
    opal_interval_tree_node_t *nill = &tree->nill;

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

    /* find the leaf where we will insert the node */
    int check = -1;
    while (n != nill) {
        check = opal_interval_tree_compare_node(n, node->low, node->high, node->data);
        /* node already exists */
        assert(0 != check);

        if (n->max < node->high) {
            n->max = node->high;
        }

        parent = n;
        n = (-1 == check) ? n->left : n->right;
        assert(nill == n || n->parent == parent);
    }

    /* place it on either the left or the right */
    if (-1 == check) {
        parent->left = node;
    } else {
        parent->right = node;
    }

    /* set its parent and children */
    node->parent = parent;

    ++tree->tree_size;
}

static int inorder_traversal(opal_interval_tree_t *tree, uint64_t low, uint64_t high,
                             bool partial_ok, opal_interval_tree_action_fn_t action,
                             opal_interval_tree_node_t *node, void *ctx)
{
    int rc;

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

    rc = inorder_traversal(tree, low, high, partial_ok, action, node->left, ctx);
    if (OPAL_SUCCESS != rc) {
        return rc;
    }

    if ((!partial_ok && (node->low <= low && node->high >= high))
        || (partial_ok
            && ((low >= node->low && low <= node->high) || (high >= node->low && high <= node->high)
                || (node->low >= low && node->low <= high)
                || (node->high >= high && node->high <= high)))) {
        rc = action(node->low, node->high, node->data, ctx);
        if (OPAL_SUCCESS != rc) {
            return rc;
        }
    }

    return inorder_traversal(tree, low, high, partial_ok, action, node->right, ctx);
}

/* Free the nodes in inorder fashion    */

static void inorder_destroy(opal_interval_tree_t *tree, opal_interval_tree_node_t *node)
{
    if (node == &tree->nill) {
        return;
    }

    inorder_destroy(tree, node->left);
    inorder_destroy(tree, node->right);

    if (node->left != &tree->nill) {
        opal_free_list_return_st(&tree->free_list, &node->left->super);
    }

    if (node->right != &tree->nill) {
        opal_free_list_return_st(&tree->free_list, &node->right->super);
    }
}

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

int opal_interval_tree_traverse(opal_interval_tree_t *tree, uint64_t low, uint64_t high,
                                bool partial_ok, opal_interval_tree_action_fn_t action, void *ctx)
{
    opal_interval_tree_token_t token;
    int rc;

    if (action == NULL) {
        return OPAL_ERR_BAD_PARAM;
    }

    token = opal_interval_tree_reader_get_token(tree);
    rc = inorder_traversal(tree, low, high, partial_ok, action, tree->root.left, ctx);
    opal_interval_tree_reader_return_token(tree, token);
    return rc;
}

/* Left rotate the tree    */
/* basically what we want to do is to make x be the left child
 * of its right child    */
static opal_interval_tree_node_t *left_rotate(opal_interval_tree_t *tree,
                                              opal_interval_tree_node_t *x)
{
    opal_interval_tree_node_t *x_copy = x;
    opal_interval_tree_node_t *y = x->right;
    opal_interval_tree_node_t *parent = x->parent;

    /* 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_copy;
    }

    /* x's parent is now y */
    x_copy->parent = y;
    x_copy->right = y->left;
    x_copy->max = max(x_copy->high, max(x_copy->left->max, x_copy->left->max));

    rp_publish(&y->left, x_copy);

    /* normally 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 == parent->left) {
        rp_publish(&parent->left, y);
    } else {
        rp_publish(&parent->right, y);
    }

    /* the old parent of x is now y's parent */
    y->parent = parent;

    return x_copy;
}

/* Right rotate the tree    */
/* basically what we want to do is to make x be the right child
 * of its left child */
static opal_interval_tree_node_t *right_rotate(opal_interval_tree_t *tree,
                                               opal_interval_tree_node_t *x)
{
    opal_interval_tree_node_t *x_copy = x;
    opal_interval_tree_node_t *y = x->left;
    opal_interval_tree_node_t *parent = x->parent;

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

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

    rp_publish(&y->right, x_copy);

    /* the maximum value in the subtree rooted at y is now the value it
     * was at x */
    y->max = x->max;
    y->parent = parent;

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

    return x_copy;
}

/* returns the size of the tree */
size_t opal_interval_tree_size(opal_interval_tree_t *tree)
{
    return tree->tree_size;
}

static bool opal_interval_tree_verify_node(opal_interval_tree_t *tree,
                                           opal_interval_tree_node_t *node, int black_depth,
                                           int current_black_depth)
{
    if (node == &tree->nill) {
        return true;
    }

    if (OPAL_INTERVAL_TREE_COLOR_RED == node->color
        && (OPAL_INTERVAL_TREE_COLOR_BLACK != node->left->color
            || OPAL_INTERVAL_TREE_COLOR_BLACK != node->right->color)) {
        fprintf(stderr, "Red node has a red child!\n");
        return false;
    }

    if (OPAL_INTERVAL_TREE_COLOR_BLACK == node->color) {
        current_black_depth++;
    }

    if (node->left == &tree->nill && node->right == &tree->nill) {
        if (black_depth != current_black_depth) {
            fprintf(stderr, "Found leaf with unexpected black depth: %d, expected: %d\n",
                    current_black_depth, black_depth);
            return false;
        }

        return true;
    }

    return opal_interval_tree_verify_node(tree, node->left, black_depth, current_black_depth)
           || opal_interval_tree_verify_node(tree, node->right, black_depth, current_black_depth);
}

static int opal_interval_tree_black_depth(opal_interval_tree_t *tree,
                                          opal_interval_tree_node_t *node, int depth)
{
    if (node == &tree->nill) {
        return depth;
    }

    /* suffices to always go left */
    if (OPAL_INTERVAL_TREE_COLOR_BLACK == node->color) {
        depth++;
    }

    return opal_interval_tree_black_depth(tree, node->left, depth);
}

bool opal_interval_tree_verify(opal_interval_tree_t *tree)
{
    int black_depth;

    if (OPAL_INTERVAL_TREE_COLOR_BLACK != tree->root.left->color) {
        fprintf(stderr, "Root node of tree is NOT black!\n");
        return false;
    }

    if (OPAL_INTERVAL_TREE_COLOR_BLACK != tree->nill.color) {
        fprintf(stderr, "Leaf node color is NOT black!\n");
        return false;
    }

    black_depth = opal_interval_tree_black_depth(tree, tree->root.left, 0);

    return opal_interval_tree_verify_node(tree, tree->root.left, black_depth, 0);
}

static void opal_interval_tree_dump_node(opal_interval_tree_t *tree,
                                         opal_interval_tree_node_t *node, int black_rank, FILE *fh)
{
    const char *color = (node->color == OPAL_INTERVAL_TREE_COLOR_BLACK) ? "black" : "red";
    uintptr_t left = (uintptr_t) node->left, right = (uintptr_t) node->right;
    opal_interval_tree_node_t *nill = &tree->nill;

    if (node->color == OPAL_INTERVAL_TREE_COLOR_BLACK) {
        ++black_rank;
    }

    if (nill == node) {
        return;
    }

    /* print out nill nodes if any */
    if ((uintptr_t) nill == left) {
        left = (uintptr_t) node | 0x1;
        fprintf(fh, "  Node%lx [color=black,label=nill];\n\n", left);
    } else {
        left = (uintptr_t) node->left;
    }

    if ((uintptr_t) nill == right) {
        right = (uintptr_t) node | 0x2;
        fprintf(fh, "  Node%lx [color=black,label=nill];\n\n", right);
    } else {
        right = (uintptr_t) node->right;
    }

    /* print out this node and its edges */
    fprintf(fh,
            "  Node%lx [color=%s,shape=box,label=\"[0x%" PRIx64 ",0x%" PRIx64 "]\\nmax=0x%" PRIx64
            "\\ndata=0x%lx\\nblack rank=%d\"];\n",
            (uintptr_t) node, color, node->low, node->high, node->max, (uintptr_t) node->data,
            black_rank);
    fprintf(fh, "  Node%lx -> Node%lx;\n", (uintptr_t) node, left);
    fprintf(fh, "  Node%lx -> Node%lx;\n\n", (uintptr_t) node, right);
    if (node != tree->root.left) {
        fprintf(fh, "  Node%lx -> Node%lx;\n\n", (uintptr_t) node, (uintptr_t) node->parent);
    }
    opal_interval_tree_dump_node(tree, node->left, black_rank, fh);
    opal_interval_tree_dump_node(tree, node->right, black_rank, fh);
}

int opal_interval_tree_dump(opal_interval_tree_t *tree, const char *path)
{
    FILE *fh;

    fh = fopen(path, "w");
    if (NULL == fh) {
        return OPAL_ERR_BAD_PARAM;
    }

    fprintf(fh, "digraph {\n");
    fprintf(fh, "  graph [ordering=\"out\"];");
    opal_interval_tree_dump_node(tree, tree->root.left, 0, fh);
    fprintf(fh, "}\n");

    fclose(fh);

    return OPAL_SUCCESS;
}