blob: 8a694063ffa86fc06f99ade88960df78619571d7 (
plain) (
tree)
|
|
/*
* Copyright (c) 2010 Gedare Bloom.
*
* The license and distribution terms for this file may be
* found in the file LICENSE in this distribution or at
* http://www.rtems.com/license/LICENSE.
*
* $Id$
*/
#if HAVE_CONFIG_H
#include "config.h"
#endif
#include <rtems/system.h>
#include <rtems/score/address.h>
#include <rtems/score/rbtree.h>
#include <rtems/score/isr.h>
/** @brief Validate and fix-up tree properties for a new insert/colored node
*
* This routine checks and fixes the Red-Black Tree properties based on
* @a the_node being just added to the tree.
*
* @note It does NOT disable interrupts to ensure the atomicity of the
* append operation.
*/
void _RBTree_Validate_insert_unprotected(
RBTree_Node *the_node
)
{
RBTree_Node *u,*g;
/* note: the insert root case is handled already */
/* if the parent is black, nothing needs to be done
* otherwise may need to loop a few times */
while (_RBTree_Is_red(_RBTree_Parent(the_node))) {
u = _RBTree_Parent_sibling(the_node);
g = the_node->parent->parent;
/* if uncle is red, repaint uncle/parent black and grandparent red */
if(_RBTree_Is_red(u)) {
the_node->parent->color = RBT_BLACK;
u->color = RBT_BLACK;
g->color = RBT_RED;
the_node = g;
} else { /* if uncle is black */
RBTree_Direction dir = the_node != the_node->parent->child[0];
RBTree_Direction pdir = the_node->parent != g->child[0];
/* ensure node is on the same branch direction as parent */
if (dir != pdir) {
_RBTree_Rotate(the_node->parent, pdir);
the_node = the_node->child[pdir];
}
the_node->parent->color = RBT_BLACK;
g->color = RBT_RED;
/* now rotate grandparent in the other branch direction (toward uncle) */
_RBTree_Rotate(g, (1-pdir));
}
}
if(!the_node->parent->parent) the_node->color = RBT_BLACK;
}
/** @brief Insert a Node (unprotected)
*
* This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
*
* @retval 0 Successfully inserted.
* @retval -1 NULL @a the_node.
* @retval RBTree_Node* if one with equal value to @a the_node->value exists
* in @a the_rbtree.
*
* @note It does NOT disable interrupts to ensure the atomicity
* of the extract operation.
*/
RBTree_Node *_RBTree_Insert_unprotected(
RBTree_Control *the_rbtree,
RBTree_Node *the_node
)
{
if(!the_node) return (RBTree_Node*)-1;
RBTree_Node *iter_node = the_rbtree->root;
if (!iter_node) { /* special case: first node inserted */
the_node->color = RBT_BLACK;
the_rbtree->root = the_node;
the_rbtree->first[0] = the_rbtree->first[1] = the_node;
the_node->parent = (RBTree_Node *) the_rbtree;
the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
} else {
/* typical binary search tree insert, descend tree to leaf and insert */
while (iter_node) {
if(the_node->value == iter_node->value) return(iter_node);
RBTree_Direction dir = the_node->value > iter_node->value;
if (!iter_node->child[dir]) {
the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
the_node->color = RBT_RED;
iter_node->child[dir] = the_node;
the_node->parent = iter_node;
/* update min/max */
if (_RBTree_Is_first(the_rbtree, iter_node, dir)) {
the_rbtree->first[dir] = the_node;
}
break;
} else {
iter_node = iter_node->child[dir];
}
} /* while(iter_node) */
/* verify red-black properties */
_RBTree_Validate_insert_unprotected(the_node);
}
return (RBTree_Node*)0;
}
/*
* _RBTree_Insert
*
* This kernel routine inserts a given node after a specified node
* a requested rbtree.
*
* Input parameters:
* tree - pointer to RBTree Control for tree to insert to
* node - pointer to node to be inserted
*
* Output parameters: NONE
*
* INTERRUPT LATENCY:
* only case
*/
void _RBTree_Insert(
RBTree_Control *tree,
RBTree_Node *node
)
{
ISR_Level level;
_ISR_Disable( level );
_RBTree_Insert_unprotected( tree, node );
_ISR_Enable( level );
}
|