change log for rtems (2011-04-04)
rtems-vc at rtems.org
rtems-vc at rtems.org
Mon Apr 4 19:10:50 UTC 2011
*joel*:
2010-07-28 Gedare Bloom <giddyup44 at 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.
M 1.2795 cpukit/ChangeLog
M 1.41 cpukit/sapi/Makefile.am
A 1.1 cpukit/sapi/include/rtems/rbtree.h
A 1.1 cpukit/sapi/inline/rtems/rbtree.inl
M 1.12 cpukit/sapi/preinstall.am
M 1.95 cpukit/score/Makefile.am
A 1.1 cpukit/score/include/rtems/score/rbtree.h
A 1.1 cpukit/score/inline/rtems/score/rbtree.inl
M 1.28 cpukit/score/preinstall.am
A 1.1 cpukit/score/src/rbtree.c
A 1.1 cpukit/score/src/rbtreeextract.c
A 1.1 cpukit/score/src/rbtreefind.c
A 1.1 cpukit/score/src/rbtreefindheader.c
A 1.1 cpukit/score/src/rbtreeget.c
A 1.1 cpukit/score/src/rbtreeinsert.c
A 1.1 cpukit/score/src/rbtreepeek.c
diff -u rtems/cpukit/ChangeLog:1.2794 rtems/cpukit/ChangeLog:1.2795
--- rtems/cpukit/ChangeLog:1.2794 Mon Apr 4 12:08:34 2011
+++ rtems/cpukit/ChangeLog Mon Apr 4 13:44:15 2011
@@ -1,3 +1,15 @@
+2010-07-28 Gedare Bloom <giddyup44 at 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 at gmail.com>
PR 1722/networking
diff -u rtems/cpukit/sapi/Makefile.am:1.40 rtems/cpukit/sapi/Makefile.am:1.41
--- rtems/cpukit/sapi/Makefile.am:1.40 Tue Aug 24 09:29:55 2010
+++ rtems/cpukit/sapi/Makefile.am Mon Apr 4 13:44:16 2011
@@ -10,12 +10,13 @@
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 -u /dev/null rtems/cpukit/sapi/include/rtems/rbtree.h:1.1
--- /dev/null Mon Apr 4 14:10:49 2011
+++ rtems/cpukit/sapi/include/rtems/rbtree.h Mon Apr 4 13:44:16 2011
@@ -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 -u /dev/null rtems/cpukit/sapi/inline/rtems/rbtree.inl:1.1
--- /dev/null Mon Apr 4 14:10:49 2011
+++ rtems/cpukit/sapi/inline/rtems/rbtree.inl Mon Apr 4 13:44:16 2011
@@ -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 -u rtems/cpukit/sapi/preinstall.am:1.11 rtems/cpukit/sapi/preinstall.am:1.12
--- rtems/cpukit/sapi/preinstall.am:1.11 Wed Aug 5 16:18:29 2009
+++ rtems/cpukit/sapi/preinstall.am Mon Apr 4 13:44:16 2011
@@ -60,6 +60,10 @@
$(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 @@
$(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 -u rtems/cpukit/score/Makefile.am:1.94 rtems/cpukit/score/Makefile.am:1.95
--- rtems/cpukit/score/Makefile.am:1.94 Wed Mar 16 15:05:04 2011
+++ rtems/cpukit/score/Makefile.am Mon Apr 4 13:44:16 2011
@@ -26,6 +26,7 @@
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 @@
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 @@
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 -u /dev/null rtems/cpukit/score/include/rtems/score/rbtree.h:1.1
--- /dev/null Mon Apr 4 14:10:49 2011
+++ rtems/cpukit/score/include/rtems/score/rbtree.h Mon Apr 4 13:44:16 2011
@@ -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 -u /dev/null rtems/cpukit/score/inline/rtems/score/rbtree.inl:1.1
--- /dev/null Mon Apr 4 14:10:49 2011
+++ rtems/cpukit/score/inline/rtems/score/rbtree.inl Mon Apr 4 13:44:16 2011
@@ -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 -u rtems/cpukit/score/preinstall.am:1.27 rtems/cpukit/score/preinstall.am:1.28
--- rtems/cpukit/score/preinstall.am:1.27 Wed Mar 16 15:05:04 2011
+++ rtems/cpukit/score/preinstall.am Mon Apr 4 13:44:16 2011
@@ -115,6 +115,10 @@
$(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 @@
$(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 -u /dev/null rtems/cpukit/score/src/rbtree.c:1.1
--- /dev/null Mon Apr 4 14:10:49 2011
+++ rtems/cpukit/score/src/rbtree.c Mon Apr 4 13:44:16 2011
@@ -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 -u /dev/null rtems/cpukit/score/src/rbtreeextract.c:1.1
--- /dev/null Mon Apr 4 14:10:49 2011
+++ rtems/cpukit/score/src/rbtreeextract.c Mon Apr 4 13:44:16 2011
@@ -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 -u /dev/null rtems/cpukit/score/src/rbtreefind.c:1.1
--- /dev/null Mon Apr 4 14:10:49 2011
+++ rtems/cpukit/score/src/rbtreefind.c Mon Apr 4 13:44:16 2011
@@ -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 -u /dev/null rtems/cpukit/score/src/rbtreefindheader.c:1.1
--- /dev/null Mon Apr 4 14:10:49 2011
+++ rtems/cpukit/score/src/rbtreefindheader.c Mon Apr 4 13:44:16 2011
@@ -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 -u /dev/null rtems/cpukit/score/src/rbtreeget.c:1.1
--- /dev/null Mon Apr 4 14:10:49 2011
+++ rtems/cpukit/score/src/rbtreeget.c Mon Apr 4 13:44:16 2011
@@ -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 -u /dev/null rtems/cpukit/score/src/rbtreeinsert.c:1.1
--- /dev/null Mon Apr 4 14:10:50 2011
+++ rtems/cpukit/score/src/rbtreeinsert.c Mon Apr 4 13:44:16 2011
@@ -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 -u /dev/null rtems/cpukit/score/src/rbtreepeek.c:1.1
--- /dev/null Mon Apr 4 14:10:50 2011
+++ rtems/cpukit/score/src/rbtreepeek.c Mon Apr 4 13:44:16 2011
@@ -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;
+}
*joel*:
2011-04-04 Gedare Bloom <giddyup44 at yahoo.com>
PR 1641/cpukit
* Makefile.am, configure.ac: Create testcase for red black tree.
* sprbtree01/init.c, sprbtree01/Makefile.am, sprbtree01/sprbtree01.doc,
sprbtree01/sprbtree01.scn: New files.
M 1.446 testsuites/sptests/ChangeLog
M 1.109 testsuites/sptests/Makefile.am
M 1.116 testsuites/sptests/configure.ac
A 1.1 testsuites/sptests/sprbtree01/.cvsignore
A 1.1 testsuites/sptests/sprbtree01/Makefile.am
A 1.1 testsuites/sptests/sprbtree01/init.c
A 1.1 testsuites/sptests/sprbtree01/sprbtree01.doc
A 1.1 testsuites/sptests/sprbtree01/sprbtree01.scn
diff -u rtems/testsuites/sptests/ChangeLog:1.445 rtems/testsuites/sptests/ChangeLog:1.446
--- rtems/testsuites/sptests/ChangeLog:1.445 Wed Mar 16 15:08:39 2011
+++ rtems/testsuites/sptests/ChangeLog Mon Apr 4 13:45:38 2011
@@ -1,3 +1,10 @@
+2011-04-04 Gedare Bloom <giddyup44 at yahoo.com>
+
+ PR 1641/cpukit
+ * Makefile.am, configure.ac: Create testcase for red black tree.
+ * sprbtree01/init.c, sprbtree01/Makefile.am, sprbtree01/sprbtree01.doc,
+ sprbtree01/sprbtree01.scn: New files.
+
2011-03-16 Jennifer Averett <jennifer.averett at OARcorp.com>
PR 1729/cpukit
diff -u rtems/testsuites/sptests/Makefile.am:1.108 rtems/testsuites/sptests/Makefile.am:1.109
--- rtems/testsuites/sptests/Makefile.am:1.108 Wed Mar 16 11:33:04 2011
+++ rtems/testsuites/sptests/Makefile.am Mon Apr 4 13:45:38 2011
@@ -16,8 +16,8 @@
sp60 sp62 sp63 sp64 sp65 sp66 sp67 sp68 sp69 \
sp70 sp71 sp72 sp73 \
spassoc01 spchain spclockget spcoverage spobjgetnext \
- spnotepad01 spprintk spprivenv01 spsize spstkalloc spthreadq01 \
- spwatchdog spwkspace \
+ spnotepad01 spprintk spprivenv01 sprbtree01 spsize spstkalloc \
+ spthreadq01 spwatchdog spwkspace \
sperror01 sperror02 sperror03 \
spfatal01 spfatal02 spfatal03 spfatal04 spfatal05 spfatal06 spfatal07 \
spfatal08 spfatal09 spfatal10 spfatal11 spfatal12 spfatal13 spfatal14 \
diff -u rtems/testsuites/sptests/configure.ac:1.115 rtems/testsuites/sptests/configure.ac:1.116
--- rtems/testsuites/sptests/configure.ac:1.115 Wed Mar 16 11:33:04 2011
+++ rtems/testsuites/sptests/configure.ac Mon Apr 4 13:45:38 2011
@@ -160,6 +160,7 @@
spobjgetnext/Makefile
spprintk/Makefile
spprivenv01/Makefile
+sprbtree01/Makefile
spsimplesched01/Makefile
spsimplesched02/Makefile
spsimplesched03/Makefile
diff -u /dev/null rtems/testsuites/sptests/sprbtree01/.cvsignore:1.1
--- /dev/null Mon Apr 4 14:10:50 2011
+++ rtems/testsuites/sptests/sprbtree01/.cvsignore Mon Apr 4 13:45:38 2011
@@ -0,0 +1,2 @@
+Makefile
+Makefile.in
diff -u /dev/null rtems/testsuites/sptests/sprbtree01/Makefile.am:1.1
--- /dev/null Mon Apr 4 14:10:50 2011
+++ rtems/testsuites/sptests/sprbtree01/Makefile.am Mon Apr 4 13:45:38 2011
@@ -0,0 +1,28 @@
+##
+## $Id$
+##
+
+MANAGERS = all
+
+rtems_tests_PROGRAMS = sprbtree01
+sprbtree01_SOURCES = init.c
+
+dist_rtems_tests_DATA = sprbtree01.scn
+dist_rtems_tests_DATA += sprbtree01.doc
+
+include $(RTEMS_ROOT)/make/custom/@RTEMS_BSP at .cfg
+include $(top_srcdir)/../automake/compile.am
+include $(top_srcdir)/../automake/leaf.am
+
+sprbtree01_LDADD = $(MANAGERS_NOT_WANTED:%=$(PROJECT_LIB)/no-%.rel)
+
+AM_CPPFLAGS += -I$(top_srcdir)/../support/include
+
+LINK_OBJS = $(sprbtree01_OBJECTS) $(sprbtree01_LDADD)
+LINK_LIBS = $(sprbtree01_LDLIBS)
+
+sprbtree01$(EXEEXT): $(sprbtree01_OBJECTS) $(sprbtree01_DEPENDENCIES)
+ @rm -f sprbtree01$(EXEEXT)
+ $(make-exe)
+
+include $(top_srcdir)/../automake/local.am
diff -u /dev/null rtems/testsuites/sptests/sprbtree01/init.c:1.1
--- /dev/null Mon Apr 4 14:10:50 2011
+++ rtems/testsuites/sptests/sprbtree01/init.c Mon Apr 4 13:45:38 2011
@@ -0,0 +1,416 @@
+/*
+ * 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$
+ */
+
+#include <tmacros.h>
+#include <rtems/rbtree.h>
+
+int numbers[20] = {
+52, 99, 5, 85, 43, 44, 10, 60, 50, 19, 8, 68, 48, 57, 17, 67, 90, 12, 77, 71};
+
+int numbers_sorted[20] = {
+ 5, 8, 10, 12, 17, 19, 43, 44, 48, 50, 52, 57, 60, 67, 68, 71, 77, 85, 90, 99};
+
+typedef struct {
+ int id;
+ rtems_rbtree_node Node;
+} test_node;
+
+/*
+ * recursively checks tree. if the tree is built properly it should only
+ * be a depth of 7 function calls for 100 entries in the tree.
+ */
+int rb_assert ( rtems_rbtree_node *root )
+{
+ int lh, rh;
+
+ if ( root == NULL )
+ return 1;
+ else {
+ rtems_rbtree_node *ln = rtems_rbtree_left(root);
+ rtems_rbtree_node *rn = rtems_rbtree_right(root);
+
+ /* Consecutive red links */
+ if ( root->color == RBT_RED ) {
+ if ((ln && ln->color == RBT_RED) || (rn && rn->color == RBT_RED)) {
+ puts ( "Red violation" );
+ return -1;
+ }
+ }
+
+ lh = rb_assert ( ln );
+ rh = rb_assert ( rn );
+
+ /* Invalid binary search tree */
+ if ( ( ln != NULL && ln->value >= root->value )
+ || ( rn != NULL && rn->value <= root->value ) )
+ {
+ puts ( "Binary tree violation" );
+ return -1;
+ }
+
+ /* Black height mismatch */
+ if ( lh != -1 && rh != -1 && lh != rh ) {
+ puts ( "Black violation" );
+ return -1;
+ }
+
+ /* Only count black links */
+ if ( lh != -1 && rh != -1 )
+ return ( root->color == RBT_RED ) ? lh : lh + 1;
+ else
+ return -1;
+ }
+}
+
+
+
+rtems_task Init(
+ rtems_task_argument ignored
+ )
+{
+ rtems_rbtree_control rbtree1;
+ rtems_rbtree_node *p;
+ test_node node1, node2;
+ test_node node_array[100];
+ int id;
+ int i;
+
+ puts( "\n\n*** TEST OF RTEMS RBTREE API ***" );
+
+ puts( "Init - Initialize rbtree empty" );
+ rtems_rbtree_initialize_empty( &rbtree1 );
+
+ /* verify that the rbtree insert work */
+ puts( "INIT - Verify rtems_rbtree_insert with two nodes" );
+ node1.id = 1;
+ node1.Node.value = 1;
+ node2.id = 2;
+ node2.Node.value = 2;
+ rtems_rbtree_insert( &rbtree1, &node1.Node );
+ rtems_rbtree_insert( &rbtree1, &node2.Node );
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+
+ for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
+ p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
+ test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+ if ( id > 2 ) {
+ puts( "INIT - TOO MANY NODES ON RBTREE" );
+ rtems_test_exit(0);
+ }
+ if ( t->id != id ) {
+ puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
+ rtems_test_exit(0);
+ }
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+ if (id < 2) {
+ puts("INIT - NOT ENOUGH NODES ON RBTREE");
+ rtems_test_exit(0);
+ }
+
+ puts("INIT - Verify rtems_rbtree_insert with the same value twice");
+ node2.Node.value = node1.Node.value;
+ rtems_rbtree_insert(&rbtree1, &node1.Node);
+ rtems_rbtree_insert(&rbtree1, &node2.Node);
+ for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
+ p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
+ test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+ if ( id > 1 ) {
+ puts( "INIT - TOO MANY NODES ON RBTREE" );
+ rtems_test_exit(0);
+ }
+ if ( t->id != id ) {
+ puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
+ rtems_test_exit(0);
+ }
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+ if (id < 1) {
+ puts("INIT - NOT ENOUGH NODES ON RBTREE");
+ rtems_test_exit(0);
+ }
+ node2.Node.value = 2;
+
+ /* verify that the rbtree is empty */
+ puts( "INIT - Verify rtems_rbtree_is_empty" );
+ if(!rtems_rbtree_is_empty(&rbtree1)) {
+ puts( "INIT - TREE NOT EMPTY" );
+ rtems_test_exit(0);
+ }
+
+ puts( "INIT - Verify rtems_XXX on an empty tree" );
+ if(rtems_rbtree_get_min(&rbtree1)) {
+ puts("INIT - get_min on empty returned non-NULL");
+ rtems_test_exit(0);
+ }
+ if(rtems_rbtree_get_max(&rbtree1)) {
+ puts("INIT - get_max on empty returned non-NULL");
+ rtems_test_exit(0);
+ }
+ if(rtems_rbtree_peek_min(&rbtree1)) {
+ puts("INIT - peek_min on empty returned non-NULL");
+ rtems_test_exit(0);
+ }
+ if(rtems_rbtree_peek_max(&rbtree1)) {
+ puts("INIT - peek_max on empty returned non-NULL");
+ rtems_test_exit(0);
+ }
+
+
+ /* verify that the rbtree insert works after a tree is emptied */
+ puts( "INIT - Verify rtems_rbtree_insert after empty tree" );
+ node1.id = 2;
+ node1.Node.value = 2;
+ node2.id = 1;
+ node2.Node.value = 1;
+ rtems_rbtree_insert( &rbtree1, &node1.Node );
+ rtems_rbtree_insert( &rbtree1, &node2.Node );
+
+ puts( "INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract" );
+ if(rtems_rbtree_peek_max(&rbtree1)->value -
+ rtems_rbtree_peek_min(&rbtree1)->value != 1) {
+ puts( "INIT - Peek Min - Max failed" );
+ rtems_test_exit(0);
+ }
+ p = rtems_rbtree_peek_max(&rbtree1);
+ rtems_rbtree_extract(&rbtree1, p);
+ if (p->value != 2) {
+ puts( "INIT - rtems_rbtree_extract failed");
+ rtems_test_exit(0);
+ }
+ rtems_rbtree_insert(&rbtree1, p);
+
+ for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ;
+ p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
+ test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+ if ( id > 2 ) {
+ puts( "INIT - TOO MANY NODES ON RBTREE" );
+ rtems_test_exit(0);
+ }
+ if ( t->id != id ) {
+ puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
+ rtems_test_exit(0);
+ }
+ }
+
+ puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]" );
+ for (i = 0; i < 100; i++) {
+ node_array[i].id = i;
+ node_array[i].Node.value = i;
+ rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ puts( "INIT - Removing 100 nodes" );
+
+ for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
+ p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
+ test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+ if ( id > 99 ) {
+ puts( "INIT - TOO MANY NODES ON RBTREE" );
+ rtems_test_exit(0);
+ }
+ if ( t->id != id ) {
+ puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
+ rtems_test_exit(0);
+ }
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ if(!rtems_rbtree_is_empty(&rbtree1)) {
+ puts( "INIT - TREE NOT EMPTY" );
+ rtems_test_exit(0);
+ }
+
+ puts( "INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]" );
+ for (i = 0; i < 100; i++) {
+ node_array[i].id = 99-i;
+ node_array[i].Node.value = 99-i;
+ rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ puts( "INIT - Removing 100 nodes" );
+
+ for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
+ p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
+ test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+ if ( id > 99 ) {
+ puts( "INIT - TOO MANY NODES ON RBTREE" );
+ rtems_test_exit(0);
+ }
+ if ( t->id != id ) {
+ puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
+ rtems_test_exit(0);
+ }
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ if(!rtems_rbtree_is_empty(&rbtree1)) {
+ puts( "INIT - TREE NOT EMPTY" );
+ rtems_test_exit(0);
+ }
+
+ puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [99,0]" );
+ for (i = 0; i < 100; i++) {
+ node_array[i].id = 99-i;
+ node_array[i].Node.value = 99-i;
+ rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ puts( "INIT - Removing 100 nodes" );
+
+ for ( p = rtems_rbtree_get_max(&rbtree1), id = 0 ; p ;
+ p = rtems_rbtree_get_max(&rbtree1) , id++ ) {
+ test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+ if ( id > 99 ) {
+ puts( "INIT - TOO MANY NODES ON RBTREE" );
+ rtems_test_exit(0);
+ }
+ if ( t->id != 99-id ) {
+ puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
+ rtems_test_exit(0);
+ }
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ if(!rtems_rbtree_is_empty(&rbtree1)) {
+ puts( "INIT - TREE NOT EMPTY" );
+ rtems_test_exit(0);
+ }
+
+ puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [0,99]" );
+ for (i = 0; i < 100; i++) {
+ node_array[i].id = i;
+ node_array[i].Node.value = i;
+ rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ puts( "INIT - Verify rtems_rbtree_find" );
+ p = rtems_rbtree_find(&rbtree1, 50);
+ if(rtems_rbtree_container_of(p,test_node,Node)->id != 50) {
+ puts ("INIT - ERROR ON RBTREE ID MISMATCH");
+ rtems_test_exit(0);
+ }
+
+ puts( "INIT - Verify rtems_rbtree_predecessor/successor");
+ p = rtems_rbtree_predecessor(p);
+ if(p && rtems_rbtree_container_of(p,test_node,Node)->id > 50) {
+ puts ("INIT - ERROR ON RBTREE ID MISMATCH");
+ rtems_test_exit(0);
+ }
+ p = rtems_rbtree_find(&rbtree1, 50);
+ p = rtems_rbtree_successor(p);
+ if(p && rtems_rbtree_container_of(p,test_node,Node)->id < 50) {
+ puts ("INIT - ERROR ON RBTREE ID MISMATCH");
+ rtems_test_exit(0);
+ }
+
+ p = rtems_rbtree_find(&rbtree1, 50);
+ puts( "INIT - Verify rtems_rbtree_find_header" );
+ if (rtems_rbtree_find_header(p) != &rbtree1) {
+ puts ("INIT - ERROR ON RBTREE HEADER MISMATCH");
+ rtems_test_exit(0);
+ }
+
+ puts( "INIT - Removing 100 nodes" );
+
+ for ( p = rtems_rbtree_get_max(&rbtree1), id = 99 ; p ;
+ p = rtems_rbtree_get_max(&rbtree1) , id-- ) {
+ test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+ if ( id < 0 ) {
+ puts( "INIT - TOO MANY NODES ON RBTREE" );
+ rtems_test_exit(0);
+ }
+ if ( t->id != id ) {
+ puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
+ rtems_test_exit(0);
+ }
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ if(!rtems_rbtree_is_empty(&rbtree1)) {
+ puts( "INIT - TREE NOT EMPTY" );
+ rtems_test_exit(0);
+ }
+
+ puts("INIT - Insert 20 random numbers");
+ for (i = 0; i < 20; i++) {
+ node_array[i].id = numbers[i];
+ node_array[i].Node.value = numbers[i];
+ rtems_rbtree_insert( &rbtree1, &node_array[i].Node );
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ puts( "INIT - Removing 20 nodes" );
+
+ for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
+ p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
+ test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+ if ( id > 19 ) {
+ puts( "INIT - TOO MANY NODES ON RBTREE" );
+ rtems_test_exit(0);
+ }
+ if ( t->id != numbers_sorted[id] ) {
+ puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
+ rtems_test_exit(0);
+ }
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ if(!rtems_rbtree_is_empty(&rbtree1)) {
+ puts( "INIT - TREE NOT EMPTY" );
+ rtems_test_exit(0);
+ }
+
+ puts( "*** END OF RTEMS RBTREE API TEST ***" );
+ rtems_test_exit(0);
+}
+
+/* configuration information */
+
+#define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER
+#define CONFIGURE_APPLICATION_DOES_NOT_NEED_CLOCK_DRIVER
+
+#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
+#define CONFIGURE_MAXIMUM_TASKS 1
+
+#define CONFIGURE_INIT
+#include <rtems/confdefs.h>
+
+/* global variables */
diff -u /dev/null rtems/testsuites/sptests/sprbtree01/sprbtree01.doc:1.1
--- /dev/null Mon Apr 4 14:10:50 2011
+++ rtems/testsuites/sptests/sprbtree01/sprbtree01.doc Mon Apr 4 13:45:38 2011
@@ -0,0 +1,25 @@
+#
+# $Id$
+#
+# COPYRIGHT (c) 1989-2009.
+# On-Line Applications Research Corporation (OAR).
+#
+# 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.
+#
+
+This file describes the directives and concepts tested by this test set.
+
+test set name: sprbtree01
+
+directives:
+
+ rtems_rbtree_initialize_empty
+ rtems_rbtree_insert
+ rtems_rbtree_get
+ rtems_rbtree_peek
+
+concepts:
+
++ Ensure that the rbtree operations listed above behave as defined.
diff -u /dev/null rtems/testsuites/sptests/sprbtree01/sprbtree01.scn:1.1
--- /dev/null Mon Apr 4 14:10:50 2011
+++ rtems/testsuites/sptests/sprbtree01/sprbtree01.scn Mon Apr 4 13:45:38 2011
@@ -0,0 +1,19 @@
+*** TEST OF RTEMS RBTREE API ***
+Init - Initialize rbtree empty
+INIT - Verify rtems_rbtree_insert with two nodes
+INIT - Verify rtems_rbtree_insert with the same value twice
+INIT - Verify rtems_rbtree_is_empty
+INIT - Verify rtems_XXX on an empty tree
+INIT - Verify rtems_rbtree_insert after empty tree
+INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract
+INIT - Verify rtems_rbtree_insert with 100 nodes value [0,99]
+INIT - Removing 100 nodes
+INIT - Verify rtems_rbtree_insert with 100 nodes value [99,0]
+INIT - Removing 100 nodes
+INIT - Verify rtems_rbtree_get_max with 100 nodes value [99,0]
+INIT - Removing 100 nodes
+INIT - Verify rtems_rbtree_get_max with 100 nodes value [0,99]
+INIT - Verify rtems_rbtree_find
+INIT - Verify rtems_rbtree_find_header
+INIT - Removing 100 nodes
+*** END OF RTEMS RBTREE API TEST ***
--
Generated by Deluxe Loginfo [http://www.codewiz.org/projects/index.html#loginfo] 2.122 by Bernardo Innocenti <bernie at develer.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/vc/attachments/20110404/b88af2d2/attachment-0001.html>
More information about the vc
mailing list