From bd9baa8184e8ff78b6644e8d88817a3ac8ec67fe Mon Sep 17 00:00:00 2001 From: Joel Sherrill Date: Mon, 4 Apr 2011 18:44:16 +0000 Subject: 2010-07-28 Gedare Bloom PR 1641/cpukit * sapi/Makefile.am, sapi/preinstall.am, score/Makefile.am, score/preinstall.am: Add Red Black Tree data structure to score. * sapi/include/rtems/rbtree.h, sapi/inline/rtems/rbtree.inl, score/include/rtems/score/rbtree.h, score/inline/rtems/score/rbtree.inl, score/src/rbtree.c, score/src/rbtreeextract.c, score/src/rbtreefind.c, score/src/rbtreefindheader.c, score/src/rbtreeget.c, score/src/rbtreeinsert.c, score/src/rbtreepeek.c: New files. --- cpukit/score/src/rbtreeextract.c | 245 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 245 insertions(+) create mode 100644 cpukit/score/src/rbtreeextract.c (limited to 'cpukit/score/src/rbtreeextract.c') diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c new file mode 100644 index 0000000000..97328beb49 --- /dev/null +++ b/cpukit/score/src/rbtreeextract.c @@ -0,0 +1,245 @@ +/* + * 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 +#include +#include +#include + +/** @brief Validate and fix-up tree properties after deleting a node + * + * This routine is called on a black node, @a the_node, after its deletion. + * This function maintains the properties of the red-black tree. + * + * @note It does NOT disable interrupts to ensure the atomicity + * of the extract operation. + */ +void _RBTree_Extract_validate_unprotected( + RBTree_Node *the_node + ) +{ + RBTree_Node *parent, *sibling; + RBTree_Direction dir; + + parent = the_node->parent; + if(!parent->parent) return; + + sibling = _RBTree_Sibling(the_node); + + /* continue to correct tree as long as the_node is black and not the root */ + while (!_RBTree_Is_red(the_node) && parent->parent) { + + /* if sibling is red, switch parent (black) and sibling colors, + * then rotate parent left, making the sibling be the_node's grandparent. + * Now the_node has a black sibling and red parent. After rotation, + * update sibling pointer. + */ + if (_RBTree_Is_red(sibling)) { + parent->color = RBT_RED; + sibling->color = RBT_BLACK; + dir = the_node != parent->child[0]; + _RBTree_Rotate(parent, dir); + sibling = parent->child[!dir]; + } + + /* sibling is black, see if both of its children are also black. */ + if (sibling && + !_RBTree_Is_red(sibling->child[RBT_RIGHT]) && + !_RBTree_Is_red(sibling->child[RBT_LEFT])) { + sibling->color = RBT_RED; + if (_RBTree_Is_red(parent)) { + parent->color = RBT_BLACK; + break; + } + the_node = parent; /* done if parent is red */ + parent = the_node->parent; + sibling = _RBTree_Sibling(the_node); + } else if(sibling) { + /* at least one of sibling's children is red. we now proceed in two + * cases, either the_node is to the left or the right of the parent. + * In both cases, first check if one of sibling's children is black, + * and if so rotate in the proper direction and update sibling pointer. + * Then switch the sibling and parent colors, and rotate through parent. + */ + dir = the_node != parent->child[0]; + if (!_RBTree_Is_red(sibling->child[!dir])) { + sibling->color = RBT_RED; + sibling->child[dir]->color = RBT_BLACK; + _RBTree_Rotate(sibling, !dir); + sibling = parent->child[!dir]; + } + sibling->color = parent->color; + parent->color = RBT_BLACK; + sibling->child[!dir]->color = RBT_BLACK; + _RBTree_Rotate(parent, dir); + break; /* done */ + } + } /* while */ + if(!the_node->parent->parent) the_node->color = RBT_BLACK; +} + +/** @brief Extract a Node (unprotected) + * + * This routine extracts (removes) @a the_node from @a the_rbtree. + * + * @note It does NOT disable interrupts to ensure the atomicity + * of the extract operation. + */ +void _RBTree_Extract_unprotected( + RBTree_Control *the_rbtree, + RBTree_Node *the_node + ) +{ + RBTree_Node *leaf, *target; + RBTree_Color victim_color; + RBTree_Direction dir; + + if(!the_node) return; + + /* check if min needs to be updated */ + if (the_node == the_rbtree->first[RBT_LEFT]) { + if (the_node->child[RBT_RIGHT]) + the_rbtree->first[RBT_LEFT] = the_node->child[RBT_RIGHT]; + else { + the_rbtree->first[RBT_LEFT] = the_node->parent; + if(_RBTree_Are_nodes_equal((RBTree_Node *)the_rbtree, + the_rbtree->first[RBT_LEFT])) + the_rbtree->first[RBT_LEFT] = NULL; + } + } + /* check if max needs to be updated: note, min can equal max (1 element) */ + if (the_node == the_rbtree->first[RBT_RIGHT]) { + if (the_node->child[RBT_LEFT]) + the_rbtree->first[RBT_RIGHT] = the_node->child[RBT_LEFT]; + else { + the_rbtree->first[RBT_RIGHT] = the_node->parent; + if(_RBTree_Are_nodes_equal((RBTree_Node *)the_rbtree, + the_rbtree->first[RBT_RIGHT])) + the_rbtree->first[RBT_RIGHT] = NULL; + } + } + + /* if the_node has at most one non-null child then it is safe to proceed + * check if both children are non-null, if so then we must find a target node + * either max in node->child[RBT_LEFT] or min in node->child[RBT_RIGHT], + * and replace the_node with the target node. This maintains the binary + * search tree property, but may violate the red-black properties. + */ + + if (the_node->child[RBT_LEFT] && the_node->child[RBT_RIGHT]) { + target = the_node->child[RBT_LEFT]; /* find max in node->child[RBT_LEFT] */ + while (target->child[RBT_RIGHT]) target = target->child[RBT_RIGHT]; + + /* if the target node has a child, need to move it up the tree into + * target's position (target is the right child of target->parent) + * when target vacates it. if there is no child, then target->parent + * should become NULL. This may cause the coloring to be violated. + * For now we store the color of the node being deleted in victim_color. + */ + leaf = target->child[RBT_LEFT]; + if(leaf) { + leaf->parent = target->parent; + } else { + /* fix the tree here if the child is a null leaf. */ + _RBTree_Extract_validate_unprotected(target); + } + victim_color = target->color; + dir = target != target->parent->child[0]; + target->parent->child[dir] = leaf; + + /* now replace the_node with target */ + dir = the_node != the_node->parent->child[0]; + the_node->parent->child[dir] = target; + + /* set target's new children to the original node's children */ + target->child[RBT_RIGHT] = the_node->child[RBT_RIGHT]; + the_node->child[RBT_RIGHT]->parent = target; + target->child[RBT_LEFT] = the_node->child[RBT_LEFT]; + the_node->child[RBT_LEFT]->parent = target; + + /* finally, update the parent node and recolor. target has completely + * replaced the_node, and target's child has moved up the tree if needed. + * the_node is no longer part of the tree, although it has valid pointers + * still. + */ + target->parent = the_node->parent; + target->color = the_node->color; + } else { + /* the_node has at most 1 non-null child. Move the child in to + * the_node's location in the tree. This may cause the coloring to be + * violated. We will fix it later. + * For now we store the color of the node being deleted in victim_color. + */ + leaf = the_node->child[RBT_LEFT] ? + the_node->child[RBT_LEFT] : the_node->child[RBT_RIGHT]; + if( leaf ) { + leaf->parent = the_node->parent; + } else { + /* fix the tree here if the child is a null leaf. */ + _RBTree_Extract_validate_unprotected(the_node); + } + victim_color = the_node->color; + + /* remove the_node from the tree */ + dir = the_node != the_node->parent->child[0]; + the_node->parent->child[dir] = leaf; + } + + /* fix coloring. leaf has moved up the tree. The color of the deleted + * node is in victim_color. There are three cases: + * 1. Deleted a red node, its child must be black. Nothing must be done. + * 2. Deleted a black node and the child is red. Paint child black. + * 3. Deleted a black node and its child is black. This requires some + * care and rotations. + */ + if (victim_color == RBT_BLACK) { /* eliminate case 1 */ + if (_RBTree_Is_red(leaf)) + leaf->color = RBT_BLACK; /* case 2 */ + else if(leaf) + _RBTree_Extract_validate_unprotected(leaf); /* case 3 */ + } + + /* Wipe the_node */ + _RBTree_Set_off_rbtree(the_node); + + /* set root to black, if it exists */ + if (the_rbtree->root) the_rbtree->root->color = RBT_BLACK; +} + + +/* + * _RBTree_Extract + * + * This kernel routine deletes the given node from a rbtree. + * + * Input parameters: + * node - pointer to node in rbtree to be deleted + * + * Output parameters: NONE + * + * INTERRUPT LATENCY: + * only case + */ + +void _RBTree_Extract( + RBTree_Control *the_rbtree, + RBTree_Node *the_node +) +{ + ISR_Level level; + + _ISR_Disable( level ); + _RBTree_Extract_unprotected( the_rbtree, the_node ); + _ISR_Enable( level ); +} -- cgit v1.2.3