diff options
-rw-r--r-- | cpukit/ChangeLog | 12 | ||||
-rw-r--r-- | cpukit/sapi/Makefile.am | 5 | ||||
-rw-r--r-- | cpukit/sapi/include/rtems/rbtree.h | 74 | ||||
-rw-r--r-- | cpukit/sapi/inline/rtems/rbtree.inl | 391 | ||||
-rw-r--r-- | cpukit/sapi/preinstall.am | 8 | ||||
-rw-r--r-- | cpukit/score/Makefile.am | 7 | ||||
-rw-r--r-- | cpukit/score/include/rtems/score/rbtree.h | 305 | ||||
-rw-r--r-- | cpukit/score/inline/rtems/score/rbtree.inl | 442 | ||||
-rw-r--r-- | cpukit/score/preinstall.am | 8 | ||||
-rw-r--r-- | cpukit/score/src/rbtree.c | 58 | ||||
-rw-r--r-- | cpukit/score/src/rbtreeextract.c | 245 | ||||
-rw-r--r-- | cpukit/score/src/rbtreefind.c | 52 | ||||
-rw-r--r-- | cpukit/score/src/rbtreefindheader.c | 50 | ||||
-rw-r--r-- | cpukit/score/src/rbtreeget.c | 52 | ||||
-rw-r--r-- | cpukit/score/src/rbtreeinsert.c | 149 | ||||
-rw-r--r-- | cpukit/score/src/rbtreepeek.c | 51 |
16 files changed, 1907 insertions, 2 deletions
diff --git a/cpukit/ChangeLog b/cpukit/ChangeLog index 5950fdd3e4..06391d58b5 100644 --- a/cpukit/ChangeLog +++ b/cpukit/ChangeLog @@ -1,3 +1,15 @@ +2010-07-28 Gedare Bloom <giddyup44@yahoo.com> + + 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. + 2011-04-04 Sebastien Bourdeauducq <sebastien.bourdeauducq@gmail.com> PR 1722/networking diff --git a/cpukit/sapi/Makefile.am b/cpukit/sapi/Makefile.am index fb35b914f0..6f9b4cc0fe 100644 --- a/cpukit/sapi/Makefile.am +++ b/cpukit/sapi/Makefile.am @@ -10,12 +10,13 @@ include_rtemsdir = $(includedir)/rtems include_rtems_HEADERS = include/confdefs.h include_rtems_HEADERS += include/rtems/chain.h include/rtems/config.h \ include/rtems/extension.h include/rtems/fatal.h include/rtems/init.h \ - include/rtems/io.h include/rtems/mptables.h include/rtems/sptables.h + include/rtems/io.h include/rtems/mptables.h include/rtems/rbtree.h \ + include/rtems/sptables.h EXTRA_DIST = include/rtems/README include_rtems_HEADERS += inline/rtems/chain.inl \ - inline/rtems/extension.inl + inline/rtems/extension.inl inline/rtems/rbtree.inl ## src AM_CPPFLAGS += -D__RTEMS_INSIDE__ diff --git a/cpukit/sapi/include/rtems/rbtree.h b/cpukit/sapi/include/rtems/rbtree.h new file mode 100644 index 0000000000..68f4ec697e --- /dev/null +++ b/cpukit/sapi/include/rtems/rbtree.h @@ -0,0 +1,74 @@ +/** + * @file rtems/rbtree.h + * + * This include file contains all the constants and structures associated + * with the RBTree API in RTEMS. The rbtree is a Red Black Tree that + * is part of the Super Core. This is the published interface to that + * code. + * + */ + +/* + * 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$ + */ + +#ifndef _RTEMS_RBTREE_H +#define _RTEMS_RBTREE_H + +#ifdef __cplusplus +extern "C" { +#endif + +#include <rtems/system.h> +#include <rtems/score/rbtree.h> + +/** + * @typedef rtems_rbtree_node + * + * A node that can be manipulated in the rbtree. + */ +typedef RBTree_Node rtems_rbtree_node; + +/** + * @typedef rtems_rbtree_control + * + * The rbtree's control anchors the rbtree. + */ +typedef RBTree_Control rtems_rbtree_control; + +/** + * @brief RBTree initializer for an empty rbtree with designator @a name. + */ +#define RTEMS_RBTREE_INITIALIZER_EMPTY(name) \ + RBTREE_INITIALIZER_EMPTY(name) + +/** + * @brief RBTree definition for an empty rbtree with designator @a name. + */ +#define RTEMS_RBTREE_DEFINE_EMPTY(name) \ + RBTREE_DEFINE_EMPTY(name) + +/** + * @brief macro to return the structure containing the @a node. + * + * This macro returns a pointer of type @a object_type that points + * to the structure containing @a node, where @a object_member is the + * field name of the rtems_rbtree_node structure in objects of @a object_type. + */ +#define rtems_rbtree_container_of(node,object_type, object_member) \ + _RBTree_Container_of(node,object_type,object_member) + +#include <rtems/rbtree.inl> + +#ifdef __cplusplus +} +#endif + +#endif +/* end of include file */ diff --git a/cpukit/sapi/inline/rtems/rbtree.inl b/cpukit/sapi/inline/rtems/rbtree.inl new file mode 100644 index 0000000000..3f2045189e --- /dev/null +++ b/cpukit/sapi/inline/rtems/rbtree.inl @@ -0,0 +1,391 @@ +/** + * @file rtems/rbtree.inl + * + * This include file contains all the constants and structures associated + * with the RBTree API in RTEMS. The rbtree is a Red Black Tree that + * is part of the Super Core. This is the published interface to that + * code. + * + */ + +/* + * 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$ + */ + +#ifndef _RTEMS_RBTREE_H +# error "Never use <rtems/rbtree.inl> directly; include <rtems/rbtree.h> instead." +#endif + +#ifndef _RTEMS_RBTREE_INL +#define _RTEMS_RBTREE_INL + +#include <rtems/score/rbtree.inl> + +/** + * @brief Initialize a RBTree Header + * + * This routine initializes @a the_rbtree structure to manage the + * contiguous array of @a number_nodes nodes which starts at + * @a starting_address. Each node is of @a node_size bytes. + */ +RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize( + rtems_rbtree_control *the_rbtree, + void *starting_address, + size_t number_nodes, + size_t node_size +) +{ + _RBTree_Initialize( the_rbtree, starting_address, number_nodes, node_size); +} + +/** + * @brief Initialize this RBTree as Empty + * + * This routine initializes @a the_rbtree to contain zero nodes. + */ +RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty( + rtems_rbtree_control *the_rbtree +) +{ + _RBTree_Initialize_empty( the_rbtree ); +} + +/** + * @brief Set off rbtree + * + * This function sets the next and previous fields of the @a node to NULL + * indicating the @a node is not part of any rbtree. + */ +RTEMS_INLINE_ROUTINE void rtems_rbtree_set_off_rbtree( + rtems_rbtree_node *node +) +{ + _RBTree_Set_off_rbtree( node ); +} + +/** + * @brief Is the Node off RBTree + * + * This function returns true if the @a node is not on a rbtree. A @a node is + * off rbtree if the next and previous fields are set to NULL. + */ +RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_node_off_rbtree( + const rtems_rbtree_node *node +) +{ + return _RBTree_Is_node_off_rbtree( node ); +} + +/** + * @brief Is the RBTree Node Pointer NULL + * + * This function returns true if @a the_node is NULL and false otherwise. + */ +RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_null_node( + const rtems_rbtree_node *the_node +) +{ + return _RBTree_Is_null_node( the_node ); +} + +/** + * @brief Return pointer to RBTree Root + * + * This function returns a pointer to the root node of @a the_rbtree. + */ +RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_root( + rtems_rbtree_control *the_rbtree +) +{ + return _RBTree_Root( the_rbtree ); +} + +/** + * @brief Return pointer to RBTree Minimum + * + * This function returns a pointer to the minimum node of @a the_rbtree. + */ +RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_min( + rtems_rbtree_control *the_rbtree +) +{ + return _RBTree_First( the_rbtree, RBT_LEFT ); +} + +/** + * @brief Return pointer to RBTree Maximum + * + * This function returns a pointer to the maximum node of @a the_rbtree. + */ +RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_max( + rtems_rbtree_control *the_rbtree +) +{ + return _RBTree_First( the_rbtree, RBT_RIGHT ); +} + +/** + * @brief Return pointer to the left child node from this node + * + * This function returns a pointer to the left child node of @a the_node. + */ +RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_left( + rtems_rbtree_node *the_node +) +{ + return _RBTree_Left( the_node ); +} + +/** + * @brief Return pointer to the right child node from this node + * + * This function returns a pointer to the right child node of @a the_node. + */ +RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_right( + rtems_rbtree_node *the_node +) +{ + return _RBTree_Right( the_node ); +} + +/** + * @brief Return pointer to the parent child node from this node + * + * This function returns a pointer to the parent node of @a the_node. + */ +RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_parent( + rtems_rbtree_node *the_node +) +{ + return _RBTree_Parent( the_node ); +} + +/** + * @brief Are Two Nodes Equal + * + * This function returns true if @a left and @a right are equal, + * and false otherwise. + */ +RTEMS_INLINE_ROUTINE bool rtems_rbtree_are_nodes_equal( + const rtems_rbtree_node *left, + const rtems_rbtree_node *right +) +{ + return _RBTree_Are_nodes_equal( left, right ); +} + +/** + * @brief Is the RBTree Empty + * + * This function returns true if there a no nodes on @a the_rbtree and + * false otherwise. + */ +RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_empty( + rtems_rbtree_control *the_rbtree +) +{ + return _RBTree_Is_empty( the_rbtree ); +} + +/** + * @brief Is this the Minimum Node on the RBTree + * + * This function returns true if @a the_node is the min node on @a the_rbtree + * and false otherwise. + */ +RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_min( + rtems_rbtree_control *the_rbtree, + const rtems_rbtree_node *the_node +) +{ + return _RBTree_Is_first( the_rbtree, the_node, RBT_LEFT ); +} + +/** + * @brief Is this the Maximum Node on the RBTree + * + * This function returns true if @a the_node is the max node on @a the_rbtree + * and false otherwise. + */ +RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_max( + rtems_rbtree_control *the_rbtree, + const rtems_rbtree_node *the_node +) +{ + return _RBTree_Is_first( the_rbtree, the_node, RBT_RIGHT ); +} + + +/** + * @brief Does this RBTree have only One Node + * + * This function returns true if there is only one node on @a the_rbtree and + * false otherwise. + */ +RTEMS_INLINE_ROUTINE bool rtems_rbtree_has_only_one_node( + const rtems_rbtree_control *the_rbtree +) +{ + return _RBTree_Has_only_one_node( the_rbtree ); +} + +/** + * @brief Is this Node the RBTree Root + * + * This function returns true if @a the_node is the root of @a the_rbtree and + * false otherwise. + */ +RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root( + rtems_rbtree_control *the_rbtree, + const rtems_rbtree_node *the_node +) +{ + return _RBTree_Is_root( the_rbtree, the_node ); +} + +/** @brief Find the node with given value in the tree + * + * This function returns a pointer to the node having value equal to @a value + * if it exists within @a the_rbtree, and NULL if not. + */ +RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find( + rtems_rbtree_control *the_rbtree, + unsigned int value +) +{ + return _RBTree_Find( the_rbtree, value ); +} + +/** @brief Find the node's in-order predecessor + * + * This function returns a pointer to the in-order predecessor + * of @a the_node if it exists, and NULL if not. + */ +RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor( + rtems_rbtree_node *the_node +) +{ + return _RBTree_Predecessor( the_node ); +} + +/** @brief Find the node's in-order successor + * + * This function returns a pointer to the in-order successor + * of @a the_node if it exists, and NULL if not. + */ +RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor( + rtems_rbtree_node *the_node +) +{ + return _RBTree_Successor( the_node ); +} + +/** + * @brief Extract the specified node from a rbtree + * + * This routine extracts @a the_node from @a the_rbtree on which it resides. + * It disables interrupts to ensure the atomicity of the extract operation. + */ +RTEMS_INLINE_ROUTINE void rtems_rbtree_extract( + rtems_rbtree_control *the_rbtree, + rtems_rbtree_node *the_node +) +{ + _RBTree_Extract( the_rbtree, the_node ); +} + +/** + * @brief Obtain the min node on a rbtree + * + * This function removes the min node from @a the_rbtree and returns + * a pointer to that node. If @a the_rbtree is empty, then NULL is returned. + * It disables interrupts to ensure the atomicity of the get operation. + */ +RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_min( + rtems_rbtree_control *the_rbtree +) +{ + return _RBTree_Get( the_rbtree, RBT_LEFT ); +} + +/** + * @brief Obtain the max node on a rbtree + * + * This function removes the max node from @a the_rbtree and returns + * a pointer to that node. If @a the_rbtree is empty, then NULL is returned. + * It disables interrupts to ensure the atomicity of the get operation. + */ +RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_max( + rtems_rbtree_control *the_rbtree +) +{ + return _RBTree_Get( the_rbtree, RBT_RIGHT ); +} + +/** + * @brief Peek at the min node on a rbtree + * + * This function returns a pointer to the min node from @a the_rbtree + * without changing the tree. If @a the_rbtree is empty, + * then NULL is returned. + * It disables interrupts to ensure the atomicity of the peek operation. + */ +RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_min( + rtems_rbtree_control *the_rbtree +) +{ + return _RBTree_Peek( the_rbtree, RBT_LEFT ); +} + +/** + * @brief Peek at the max node on a rbtree + * + * This function returns a pointer to the max node from @a the_rbtree + * without changing the tree. If @a the_rbtree is empty, + * then NULL is returned. + * It disables interrupts to ensure the atomicity of the peek operation. + */ +RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_max( + rtems_rbtree_control *the_rbtree +) +{ + return _RBTree_Peek( the_rbtree, RBT_RIGHT ); +} + + +/** + * @brief Find the control header of the tree containing a given node. + * + * This routine finds the rtems_rbtree_control structure of the tree + * containing @a the_node. + * It disables interrupts to ensure the atomicity of the find operation. + */ +RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header( + rtems_rbtree_node *the_node +) +{ + return(_RBTree_Find_header( the_node )); +} + +/** + * @brief Insert a node on a rbtree + * + * This routine inserts @a the_node on @a the_rbtree. + * It disables interrupts to ensure the atomicity of the insert operation. + */ +RTEMS_INLINE_ROUTINE void rtems_rbtree_insert( + rtems_rbtree_control *the_rbtree, + rtems_rbtree_node *the_node +) +{ + _RBTree_Insert( the_rbtree, the_node ); +} + +#endif +/* end of include file */ diff --git a/cpukit/sapi/preinstall.am b/cpukit/sapi/preinstall.am index 975828246c..f49f81427c 100644 --- a/cpukit/sapi/preinstall.am +++ b/cpukit/sapi/preinstall.am @@ -60,6 +60,10 @@ $(PROJECT_INCLUDE)/rtems/mptables.h: include/rtems/mptables.h $(PROJECT_INCLUDE) $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/mptables.h PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/mptables.h +$(PROJECT_INCLUDE)/rtems/rbtree.h: include/rtems/rbtree.h $(PROJECT_INCLUDE)/rtems/$(dirstamp) + $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/rbtree.h +PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/rbtree.h + $(PROJECT_INCLUDE)/rtems/sptables.h: include/rtems/sptables.h $(PROJECT_INCLUDE)/rtems/$(dirstamp) $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/sptables.h PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/sptables.h @@ -72,6 +76,10 @@ $(PROJECT_INCLUDE)/rtems/extension.inl: inline/rtems/extension.inl $(PROJECT_INC $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/extension.inl PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/extension.inl +$(PROJECT_INCLUDE)/rtems/rbtree.inl: inline/rtems/rbtree.inl $(PROJECT_INCLUDE)/rtems/$(dirstamp) + $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/rbtree.inl +PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/rbtree.inl + $(PROJECT_LIB)/libsapi.a: libsapi.a $(PROJECT_LIB)/$(dirstamp) $(INSTALL_DATA) $< $(PROJECT_LIB)/libsapi.a TMPINSTALL_FILES += $(PROJECT_LIB)/libsapi.a diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am index 9d3d97f593..b9ce843360 100644 --- a/cpukit/score/Makefile.am +++ b/cpukit/score/Makefile.am @@ -26,6 +26,7 @@ include_rtems_score_HEADERS = include/rtems/score/address.h \ include/rtems/score/interr.h include/rtems/score/isr.h \ include/rtems/score/object.h include/rtems/score/percpu.h \ include/rtems/score/priority.h include/rtems/score/prioritybitmap.h \ + include/rtems/score/rbtree.h \ include/rtems/score/scheduler.h include/rtems/score/schedulerpriority.h \ include/rtems/score/schedulersimple.h \ include/rtems/score/stack.h include/rtems/score/states.h \ @@ -57,6 +58,7 @@ include_rtems_score_HEADERS += inline/rtems/score/address.inl \ inline/rtems/score/coresem.inl inline/rtems/score/heap.inl \ inline/rtems/score/isr.inl inline/rtems/score/object.inl \ inline/rtems/score/priority.inl inline/rtems/score/prioritybitmap.inl \ + inline/rtems/score/rbtree.inl \ inline/rtems/score/scheduler.inl inline/rtems/score/schedulerpriority.inl \ inline/rtems/score/schedulersimple.inl \ inline/rtems/score/stack.inl inline/rtems/score/states.inl \ @@ -178,6 +180,11 @@ libscore_a_SOURCES += src/pheapallocate.c \ src/pheapgetblocksize.c src/pheapgetfreeinfo.c src/pheapgetinfo.c \ src/pheapinit.c src/pheapresizeblock.c src/pheapwalk.c +## RBTREE_C_FILES +libscore_a_SOURCES += src/rbtree.c \ + src/rbtreeextract.c src/rbtreefind.c src/rbtreefindheader.c \ + src/rbtreeget.c src/rbtreeinsert.c src/rbtreepeek.c + ## THREAD_C_FILES libscore_a_SOURCES += src/thread.c src/threadchangepriority.c \ src/threadclearstate.c src/threadclose.c src/threadcreateidle.c \ diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h new file mode 100644 index 0000000000..8360c99497 --- /dev/null +++ b/cpukit/score/include/rtems/score/rbtree.h @@ -0,0 +1,305 @@ + +/** + * @file rtems/score/rbtree.h + * + * This include file contains all the constants and structures associated + * with the Red-Black Tree Handler. + */ + +/* + * 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$ + */ + +#ifndef _RTEMS_SCORE_RBTREE_H +#define _RTEMS_SCORE_RBTREE_H + +/** + * @defgroup ScoreRBTree Red-Black Tree Handler + * + * The Red-Black Tree Handler is used to manage sets of entities. This handler + * provides two data structures. The rbtree Node data structure is included + * as the first part of every data structure that will be placed on + * a RBTree. The second data structure is rbtree Control which is used + * to manage a set of rbtree Nodes. + */ +/**@{*/ + +#ifdef __cplusplus +extern "C" { +#endif + +#include <rtems/score/address.h> + + /** + * @typedef RBTree_Node + * + * This type definition promotes the name for the RBTree Node used by + * all RTEMS code. It is a separate type definition because a forward + * reference is required to define it. See @ref RBTree_Node_struct for + * detailed information. + */ + typedef struct RBTree_Node_struct RBTree_Node; + + /** + * This enum type defines the colors available for the RBTree Nodes + */ + typedef enum { + RBT_BLACK, + RBT_RED + } RBTree_Color; + + /** + * @struct RBTree_Node_struct + * + * This is used to manage each element (node) which is placed + * on a RBT. + * + * @note Typically, a more complicated structure will use the + * rbtree package. The more complicated structure will + * include a rbtree node as the first element in its + * control structure. It will then call the rbtree package + * with a pointer to that node element. The node pointer + * and the higher level structure start at the same address + * so the user can cast the pointers back and forth. + * + */ + struct RBTree_Node_struct { + /** This points to the node's parent */ + RBTree_Node *parent; + /** child[0] points to the left child, child[1] points to the right child */ + RBTree_Node *child[2]; + /** This is the integer value stored by this node, used for sorting */ + unsigned int value; + /** The color of the node. Either red or black */ + RBTree_Color color; + }; + + /** + * @brief macro to return the structure containing the @a node. + * + * This macro returns a pointer of type @a container_type that points + * to the structure containing @a node, where @a node_field_name is the + * field name of the RBTree_Node structure in @a container_type. + * + */ + +#define _RBTree_Container_of(node,container_type, node_field_name) \ + ((container_type*) \ + ((size_t)node - ((size_t)(&((container_type *)0)->node_field_name)))) + + + typedef enum { + RBT_LEFT=0, + RBT_RIGHT=1 + } RBTree_Direction; + + /** + * @struct RBTree_Control + * + * This is used to manage a RBT. A rbtree consists of a tree of zero or more + * nodes. + * + * @note This implementation does not require special checks for + * manipulating the root element of the RBT. + * To accomplish this the @a RBTree_Control structure can be overlaid + * with a @ref RBTree_Node structure to act as a "dummy root", + * which has a NULL parent and its left child is the root. + */ + + /* the RBTree_Control is actually part of the RBTree structure as an + * RBTree_Node. The mapping of fields from RBTree_Control to RBTree_Node are: + * permanent_null == parent + * root == left + * first[0] == right + */ + typedef struct { + /** This points to a NULL. Useful for finding the root. */ + RBTree_Node *permanent_null; + /** This points to the root node of the RBT. */ + RBTree_Node *root; + /** This points to the min and max nodes of this RBT. */ + RBTree_Node *first[2]; + } RBTree_Control; + + /** + * @brief RBTree initializer for an empty rbtree with designator @a name. + */ +#define RBTREE_INITIALIZER_EMPTY(name) \ + { \ + .permanent_null = NULL, \ + .root = NULL, \ + .first[0] = NULL, \ + .first[1] = NULL, \ + } + + /** + * @brief RBTree definition for an empty rbtree with designator @a name. + */ +#define RBTREE_DEFINE_EMPTY(name) \ + RBTree_Control name = RBTREE_INITIALIZER_EMPTY(name) + + /** + * @brief RBTree_Node initializer for an empty node with designator @a name. + */ +#define RBTREE_NODE_INITIALIZER_EMPTY(name) \ + { \ + .parent = NULL, \ + .child[0] = NULL, \ + .child[1] = NULL, \ + .value = -1, \ + RBT_RED \ + } + + /** + * @brief RBTree definition for an empty rbtree with designator @a name. + */ +#define RBTREE_NODE_DEFINE_EMPTY(name) \ + RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY(name) + + + + + /** + * @brief Initialize a RBTree Header + * + * This routine initializes @a the_rbtree structure to manage the + * contiguous array of @a number_nodes nodes which starts at + * @a starting_address. Each node is of @a node_size bytes. + */ + void _RBTree_Initialize( + RBTree_Control *the_rbtree, + void *starting_address, + size_t number_nodes, + size_t node_size + ); + + /** + * @brief Obtain the min or max node of a rbtree + * + * This function removes the min or max node from @a the_rbtree and returns + * a pointer to that node. If @a the_rbtree is empty, then NULL is returned. + * @a dir specifies whether to return the min (0) or max (1). + * + * @return This method returns a pointer to a node. If a node was removed, + * then a pointer to that node is returned. If @a the_rbtree was + * empty, then NULL is returned. + * + * @note It disables interrupts to ensure the atomicity of the get operation. + */ + RBTree_Node *_RBTree_Get( + RBTree_Control *the_rbtree, + RBTree_Direction dir + ); + + /** + * @brief Check the min or max node on a rbtree + * + * This function returns a pointer to the min or max node of @a the_rbtree. + * If @a the_rbtree is empty, then NULL is returned. @a dir specifies + * whether to return the min (0) or max (1). + * + * @return This method returns a pointer to a node. + * If @a the_rbtree was empty, then NULL is returned. + * + * @note It disables interrupts to ensure the atomicity of the get operation. + */ + RBTree_Node *_RBTree_Peek( + RBTree_Control *the_rbtree, + RBTree_Direction dir + ); + + /** @brief Find the node with given value in the tree + * + * This function returns a pointer to the node with value equal to @a value + * if it exists in the Red-Black Tree @a the_rbtree, and NULL if not. + */ + RBTree_Node *_RBTree_Find( + RBTree_Control *the_rbtree, + unsigned int value + ); + + /** @brief Find the control structure of the tree containing the given node + * + * This function returns a pointer to the control structure of the tree + * containing @a the_node, if it exists, and NULL if not. + */ + RBTree_Control *_RBTree_Find_header( + RBTree_Node *the_node + ); + + /** @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 + ); + + /** + * @brief Insert a node on a rbtree + * + * This routine inserts @a the_node on the tree @a the_rbtree. + * + * @note It disables interrupts to ensure the atomicity + * of the extract operation. + */ + void _RBTree_Insert( + RBTree_Control *the_rbtree, + RBTree_Node *the_node + ); + + + /** @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 + ); + + + /** + * @brief Delete a node from the rbtree + * + * This routine deletes @a the_node from @a the_rbtree. + * + * @note It disables interrupts to ensure the atomicity of the + * append operation. + */ + void _RBTree_Extract( + RBTree_Control *the_rbtree, + RBTree_Node *the_node + ); + +#ifndef __RTEMS_APPLICATION__ +#include <rtems/score/rbtree.inl> +#endif + +#ifdef __cplusplus +} +#endif + +/**@}*/ + +#endif +/* end of include file */ diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl new file mode 100644 index 0000000000..097cede027 --- /dev/null +++ b/cpukit/score/inline/rtems/score/rbtree.inl @@ -0,0 +1,442 @@ +/** + * @file rtems/score/rbtree.inl + * + * This include file contains the bodies of the routines which are + * associated with Red-Black Trees and inlined. + * + * @note The routines in this file are ordered from simple + * to complex. No other RBTree Handler routine is referenced + * unless it has already been defined. + */ + +/* + * 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$ + */ + +#ifndef _RTEMS_SCORE_RBTREE_H +# error "Never use <rtems/score/rbtree.inl> directly; include <rtems/score/rbtree.h> instead." +#endif + +#ifndef _RTEMS_SCORE_RBTREE_INL +#define _RTEMS_SCORE_RBTREE_INL + +/** + * @addtogroup ScoreRBTree + * @{ + */ + +/** @brief Set off rbtree + * + * This function sets the parent and child fields of the @a node to NULL + * indicating the @a node is not part of a rbtree. + * + */ +RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree( + RBTree_Node *node + ) +{ + node->parent = node->child[RBT_LEFT] = node->child[RBT_RIGHT] = NULL; +} + +/** @brief Is the Node off RBTree + * + * This function returns true if the @a node is not on a rbtree. A @a node is + * off rbtree if the parent and child fields are set to NULL. + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_rbtree( + const RBTree_Node *node + ) +{ + return (node->parent == NULL) && (node->child[RBT_LEFT] == NULL) && (node->child[RBT_RIGHT] == NULL); +} + +/** @brief Are Two Nodes Equal + * + * This function returns true if @a left and @a right are equal, + * and false otherwise. + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Are_nodes_equal( + const RBTree_Node *left, + const RBTree_Node *right + ) +{ + return left == right; +} + +/** @brief Is this RBTree Control Pointer Null + * + * This function returns true if @a the_rbtree is NULL and false otherwise. + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Is_null( + const RBTree_Control *the_rbtree + ) +{ + return (the_rbtree == NULL); +} + +/** @brief Is the RBTree Node Pointer NULL + * + * This function returns true if @a the_node is NULL and false otherwise. + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Is_null_node( + const RBTree_Node *the_node + ) +{ + return (the_node == NULL); +} + + +/** @brief Return pointer to RBTree's root node + * + * This function returns a pointer to the root node of @a the_rbtree. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root( + RBTree_Control *the_rbtree + ) +{ + return the_rbtree->root; +} + +/** @brief Return pointer to RBTree's First node + * + * This function returns a pointer to the first node on @a the_rbtree, + * where @a dir specifies whether to return the minimum (0) or maximum (1). + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First( + RBTree_Control *the_rbtree, + RBTree_Direction dir + ) +{ + return the_rbtree->first[dir]; +} + +/** @brief Return pointer to the parent of this node + * + * This function returns a pointer to the parent node of @a the_node. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent( + RBTree_Node *the_node + ) +{ + if (!the_node->parent->parent) return NULL; + return the_node->parent; +} + +/** @brief Return pointer to the left of this node + * + * This function returns a pointer to the left node of this node. + * + * @param[in] the_node is the node to be operated upon. + * + * @return This method returns the left node on the rbtree. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left( + RBTree_Node *the_node + ) +{ + return the_node->child[RBT_LEFT]; +} + +/** @brief Return pointer to the right of this node + * + * This function returns a pointer to the right node of this node. + * + * @param[in] the_node is the node to be operated upon. + * + * @return This method returns the right node on the rbtree. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right( + RBTree_Node *the_node + ) +{ + return the_node->child[RBT_RIGHT]; +} + +/** @brief Is the RBTree Empty + * + * This function returns true if there are no nodes on @a the_rbtree and + * false otherwise. + * + * @param[in] the_rbtree is the rbtree to be operated upon. + * + * @return This function returns true if there are no nodes on + * @a the_rbtree and false otherwise. + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty( + RBTree_Control *the_rbtree + ) +{ + return (the_rbtree->root == NULL); +} + +/** @brief Is this the First Node on the RBTree + * + * This function returns true if @a the_node is the first node on + * @a the_rbtree and false otherwise. @a dir specifies whether first means + * minimum (0) or maximum (1). + * + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Is_first( + RBTree_Control *the_rbtree, + const RBTree_Node *the_node, + RBTree_Direction dir + ) +{ + return (the_node == _RBTree_First(the_rbtree, dir)); +} + +/** @brief Is this node red? + * + * This function returns true if @a the_node is red and false otherwise. + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Is_red( + const RBTree_Node *the_node + ) +{ + return (the_node && the_node->color == RBT_RED); +} + + +/** @brief Does this RBTree have only One Node + * + * This function returns true if there is only one node on @a the_rbtree and + * false otherwise. + * + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Has_only_one_node( + const RBTree_Control *the_rbtree + ) +{ + if(!the_rbtree) return NULL; /* TODO: expected behavior? */ + return (the_rbtree->root->child[RBT_LEFT] == NULL && the_rbtree->root->child[RBT_RIGHT] == NULL); +} + +/** @brief Is this Node the RBTree root + * + * This function returns true if @a the_node is the root of @a the_rbtree and + * false otherwise. + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Is_root( + RBTree_Control *the_rbtree, + const RBTree_Node *the_node + ) +{ + return (the_node == _RBTree_Root(the_rbtree)); +} + +/** @brief Initialize this RBTree as Empty + * + * This routine initializes @a the_rbtree to contain zero nodes. + */ +RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty( + RBTree_Control *the_rbtree + ) +{ + the_rbtree->permanent_null = NULL; + the_rbtree->root = NULL; + the_rbtree->first[0] = NULL; + the_rbtree->first[1] = NULL; +} + +/** @brief Return a pointer to node's grandparent + * + * This function returns a pointer to the grandparent of @a the_node if it + * exists, and NULL if not. + * + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Grandparent( + RBTree_Node *the_node + ) +{ + if(!the_node) return NULL; + if(!(the_node->parent)) return NULL; + if(!(the_node->parent->parent)) return NULL; + if(!(the_node->parent->parent->parent)) return NULL; + return(the_node->parent->parent); +} + +/** @brief Return a pointer to node's sibling + * + * This function returns a pointer to the sibling of @a the_node if it + * exists, and NULL if not. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Sibling( + RBTree_Node *the_node + ) +{ + if(!the_node) return NULL; + if(!(the_node->parent)) return NULL; + if(!(the_node->parent->parent)) return NULL; + + if(the_node == the_node->parent->child[RBT_LEFT]) + return the_node->parent->child[RBT_RIGHT]; + else + return the_node->parent->child[RBT_LEFT]; +} + +/** @brief Return a pointer to node's parent's sibling + * + * This function returns a pointer to the sibling of the parent of + * @a the_node if it exists, and NULL if not. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent_sibling( + RBTree_Node *the_node + ) +{ + if(!the_node) return NULL; + if(_RBTree_Grandparent(the_node) == NULL) return NULL; + + return _RBTree_Sibling(the_node->parent); +} + +/** @brief Find the RBTree_Control header given a node in the tree + * + * This function returns a pointer to the header of the Red Black + * Tree containing @a the_node if it exists, and NULL if not. + */ +RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header_unprotected( + RBTree_Node *the_node + ) +{ + if(!the_node) return NULL; + if(!(the_node->parent)) return NULL; + while(the_node->parent) the_node = the_node->parent; + return (RBTree_Control*)the_node; +} + +/** @brief Find the node with given value in the tree + * + * This function returns a pointer to the node in @a the_rbtree + * having value equal to @a the_value if it exists, and NULL if not. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected( + RBTree_Control *the_rbtree, + unsigned int the_value + ) +{ + RBTree_Node* iter_node = the_rbtree->root; + while (iter_node) { + if (the_value == iter_node->value) return(iter_node); + + RBTree_Direction dir = the_value > iter_node->value; + iter_node = iter_node->child[dir]; + } /* while(iter_node) */ + + return 0; +} + +/** @brief Find the nodes in-order predecessor + * + * This function returns a pointer to the in-order predecessor + * of @a the_node if it exists, and NULL if not. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor( + RBTree_Node *the_node + ) +{ + RBTree_Node* iter_node; + if (!the_node) return NULL; + iter_node = the_node->child[RBT_LEFT]; + if (!iter_node) return NULL; + while (iter_node->child[RBT_RIGHT]) { + iter_node = iter_node->child[RBT_RIGHT]; + } + return iter_node; +} + +/** @brief Find the nodes in-order successor + * + * This function returns a pointer to the in-order successor + * of @a the_node if it exists, and NULL if not. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor( + RBTree_Node *the_node + ) +{ + RBTree_Node* iter_node; + if (!the_node) return NULL; + iter_node = the_node->child[RBT_RIGHT]; + if (!iter_node) return NULL; + while (iter_node->child[RBT_LEFT]) { + iter_node = iter_node->child[RBT_LEFT]; + } + return iter_node; +} + +/** @brief Get the First Node (unprotected) + * + * This function removes the minimum or maximum node from the_rbtree and + * returns a pointer to that node. It does NOT disable interrupts to ensure + * the atomicity of the get operation. + * + * @param[in] the_rbtree is the rbtree to attempt to get the min node from. + * @param[in] dir specifies whether to get minimum (0) or maximum (1) + * + * @return This method returns the min or max node on the rbtree, or NULL. + * + * @note This routine may return NULL if the RBTree is empty. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get_unprotected( + RBTree_Control *the_rbtree, + RBTree_Direction dir + ) +{ + RBTree_Node *the_node = the_rbtree->first[dir]; + _RBTree_Extract_unprotected(the_rbtree, the_node); + return the_node; +} + +/** @brief Peek at the First Node (unprotected) + * + * This function returns a pointer to the first node, minimum if @a dir is 0 + * or maximum if @a dir is 1, from @a the_rbtree without extracting it. + * It does NOT disable interrupts to ensure the atomicity of the peek. + * + * @retval NULL if @a the_rbtree is empty. + */ +RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Peek_unprotected( + RBTree_Control *the_rbtree, + RBTree_Direction dir + ) +{ + return(the_rbtree->first[dir]); +} + +/** @brief Rotate the_node in the direction passed as second argument + * + * This routine rotates @a the_node to the direction @a dir, swapping + * @a the_node with its child\[@a dir\]. + */ +RTEMS_INLINE_ROUTINE void _RBTree_Rotate( + RBTree_Node *the_node, + RBTree_Direction dir + ) +{ + RBTree_Node *c; + if (the_node == NULL) return; + if (the_node->child[(1-dir)] == NULL) return; + + + c = the_node->child[(1-dir)]; + the_node->child[(1-dir)] = c->child[dir]; + + if (c->child[dir]) + c->child[dir]->parent = the_node; + + c->child[dir] = the_node; + + the_node->parent->child[the_node != the_node->parent->child[0]] = c; + + c->parent = the_node->parent; + the_node->parent = c; +} +/**@}*/ + +#endif +/* end of include file */ diff --git a/cpukit/score/preinstall.am b/cpukit/score/preinstall.am index 6979313a19..d228c69d86 100644 --- a/cpukit/score/preinstall.am +++ b/cpukit/score/preinstall.am @@ -115,6 +115,10 @@ $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.h: include/rtems/score/prioritybit $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.h PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.h +$(PROJECT_INCLUDE)/rtems/score/rbtree.h: include/rtems/score/rbtree.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp) + $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/rbtree.h +PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/rbtree.h + $(PROJECT_INCLUDE)/rtems/score/scheduler.h: include/rtems/score/scheduler.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp) $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/scheduler.h PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/scheduler.h @@ -265,6 +269,10 @@ $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.inl: inline/rtems/score/prioritybi $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.inl PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/prioritybitmap.inl +$(PROJECT_INCLUDE)/rtems/score/rbtree.inl: inline/rtems/score/rbtree.inl $(PROJECT_INCLUDE)/rtems/score/$(dirstamp) + $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/rbtree.inl +PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/rbtree.inl + $(PROJECT_INCLUDE)/rtems/score/scheduler.inl: inline/rtems/score/scheduler.inl $(PROJECT_INCLUDE)/rtems/score/$(dirstamp) $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/scheduler.inl PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/scheduler.inl 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 <rtems/system.h> +#include <rtems/score/address.h> +#include <rtems/score/rbtree.h> +#include <rtems/score/isr.h> + +/*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 <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 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 <rtems/system.h> +#include <rtems/score/address.h> +#include <rtems/score/rbtree.h> +#include <rtems/score/isr.h> + +/* + * _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 <rtems/system.h> +#include <rtems/score/address.h> +#include <rtems/score/rbtree.h> +#include <rtems/score/isr.h> + +/* + * _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 <rtems/system.h> +#include <rtems/score/address.h> +#include <rtems/score/rbtree.h> +#include <rtems/score/isr.h> + +/* + * _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 <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 ); +} 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 <rtems/system.h> +#include <rtems/score/address.h> +#include <rtems/score/rbtree.h> +#include <rtems/score/isr.h> + +/* + * _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; +} |