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/rbtree.c | 58 +++++++++ cpukit/score/src/rbtreeextract.c | 245 ++++++++++++++++++++++++++++++++++++ cpukit/score/src/rbtreefind.c | 52 ++++++++ cpukit/score/src/rbtreefindheader.c | 50 ++++++++ cpukit/score/src/rbtreeget.c | 52 ++++++++ cpukit/score/src/rbtreeinsert.c | 149 ++++++++++++++++++++++ cpukit/score/src/rbtreepeek.c | 51 ++++++++ 7 files changed, 657 insertions(+) create mode 100644 cpukit/score/src/rbtree.c create mode 100644 cpukit/score/src/rbtreeextract.c create mode 100644 cpukit/score/src/rbtreefind.c create mode 100644 cpukit/score/src/rbtreefindheader.c create mode 100644 cpukit/score/src/rbtreeget.c create mode 100644 cpukit/score/src/rbtreeinsert.c create mode 100644 cpukit/score/src/rbtreepeek.c (limited to 'cpukit/score/src') diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c new file mode 100644 index 0000000000..2c1035b3dc --- /dev/null +++ b/cpukit/score/src/rbtree.c @@ -0,0 +1,58 @@ +/* + * 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 + +/*PAGE + * + * _RBTree_Initialize + * + * This kernel routine initializes a Red-Black Tree. + * + * Input parameters: + * the_rbtree - pointer to rbtree header + * starting_address - starting address of first node + * number_nodes - number of nodes in rbtree + * node_size - size of node in bytes + * + * Output parameters: NONE + */ + +void _RBTree_Initialize( + RBTree_Control *the_rbtree, + void *starting_address, + size_t number_nodes, + size_t node_size +) +{ + size_t count; + RBTree_Node *next; + + /* TODO: Error message? */ + if (!the_rbtree) return; + + /* could do sanity checks here */ + _RBTree_Initialize_empty(the_rbtree); + + count = number_nodes; + next = starting_address; + while ( count-- ) { + _RBTree_Insert(the_rbtree, next); + next = (RBTree_Node *) + _Addresses_Add_offset( (void *) next, node_size ); + } +} 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 ); +} diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c new file mode 100644 index 0000000000..a11918ebde --- /dev/null +++ b/cpukit/score/src/rbtreefind.c @@ -0,0 +1,52 @@ +/* + * 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 + +/* + * _RBTree_Find + * + * This kernel routine returns a pointer to the rbtree node containing the + * given value within the given tree, if it exists, or NULL otherwise. + * + * Input parameters: + * the_rbtree - pointer to rbtree control + * the_value - value of the node to search for + * + * Output parameters: + * return_node - pointer to control header of rbtree + * NULL - if there is no control header available (the node is not part + * of a tree) + * + * INTERRUPT LATENCY: + * only case + */ + +RBTree_Node *_RBTree_Find( + RBTree_Control *the_rbtree, + unsigned int the_value +) +{ + ISR_Level level; + RBTree_Node *return_node; + + return_node = NULL; + _ISR_Disable( level ); + return_node = _RBTree_Find_unprotected( the_rbtree, the_value ); + _ISR_Enable( level ); + return return_node; +} diff --git a/cpukit/score/src/rbtreefindheader.c b/cpukit/score/src/rbtreefindheader.c new file mode 100644 index 0000000000..f73514c3a7 --- /dev/null +++ b/cpukit/score/src/rbtreefindheader.c @@ -0,0 +1,50 @@ +/* + * 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 + +/* + * _RBTree_Find_header + * + * This kernel routine returns a pointer to the rbtree header of the tree + * containing the given node. + * + * Input parameters: + * the_node - pointer to rbtree node + * + * Output parameters: + * return_header - pointer to control header of rbtree + * NULL - if there is no control header available (the node is not part + * of a tree) + * + * INTERRUPT LATENCY: + * only case + */ + +RBTree_Control *_RBTree_Find_header( + RBTree_Node *the_node +) +{ + ISR_Level level; + RBTree_Control *return_header; + + return_header = NULL; + _ISR_Disable( level ); + return_header = _RBTree_Find_header_unprotected( the_node ); + _ISR_Enable( level ); + return return_header; +} diff --git a/cpukit/score/src/rbtreeget.c b/cpukit/score/src/rbtreeget.c new file mode 100644 index 0000000000..7e4c84db0a --- /dev/null +++ b/cpukit/score/src/rbtreeget.c @@ -0,0 +1,52 @@ +/* + * 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 + +/* + * _RBTree_Get + * + * This kernel routine returns a pointer to a node taken from the + * given rbtree. + * + * Input parameters: + * the_rbtree - pointer to rbtree header + * dir - specifies min (0) or max (1) + * + * Output parameters: + * return_node - pointer to node in rbtree allocated + * NULL - if no nodes available + * + * INTERRUPT LATENCY: + * only case + */ + +RBTree_Node *_RBTree_Get( + RBTree_Control *the_rbtree, + RBTree_Direction dir +) +{ + ISR_Level level; + RBTree_Node *return_node; + + return_node = NULL; + _ISR_Disable( level ); + return_node = _RBTree_Get_unprotected( the_rbtree, dir ); + _ISR_Enable( level ); + return return_node; +} + diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c new file mode 100644 index 0000000000..b9a7c994d8 --- /dev/null +++ b/cpukit/score/src/rbtreeinsert.c @@ -0,0 +1,149 @@ +/* + * 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 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 ); +} diff --git a/cpukit/score/src/rbtreepeek.c b/cpukit/score/src/rbtreepeek.c new file mode 100644 index 0000000000..3363197dc3 --- /dev/null +++ b/cpukit/score/src/rbtreepeek.c @@ -0,0 +1,51 @@ +/* + * 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 + +/* + * _RBTree_Get + * + * This kernel routine returns a pointer to the min or max node on the tree, + * without removing that node. + * + * Input parameters: + * the_rbtree - pointer to rbtree header + * dir - specifies whether to return minimum (0) or maximum (1) + * + * Output parameters: + * return_node - pointer to node in rbtree allocated + * NULL - if no nodes available + * + * INTERRUPT LATENCY: + * only case + */ + +RBTree_Node *_RBTree_Peek( + RBTree_Control *the_rbtree, + RBTree_Direction dir +) +{ + ISR_Level level; + RBTree_Node *return_node; + + return_node = NULL; + _ISR_Disable( level ); + return_node = _RBTree_Peek_unprotected( the_rbtree, dir ); + _ISR_Enable( level ); + return return_node; +} -- cgit v1.2.3