diff options
author | Joel Sherrill <joel.sherrill@OARcorp.com> | 2011-04-04 18:44:16 +0000 |
---|---|---|
committer | Joel Sherrill <joel.sherrill@OARcorp.com> | 2011-04-04 18:44:16 +0000 |
commit | bd9baa8184e8ff78b6644e8d88817a3ac8ec67fe (patch) | |
tree | 626eb6aa1a8779330e88e16987c6f25c226507f6 /cpukit/sapi | |
parent | 2011-04-04 Sebastien Bourdeauducq <sebastien.bourdeauducq@gmail.com> (diff) | |
download | rtems-bd9baa8184e8ff78b6644e8d88817a3ac8ec67fe.tar.bz2 |
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.
Diffstat (limited to '')
-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 |
4 files changed, 476 insertions, 2 deletions
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 |