Changeset 2445bda in rtems for cpukit/sapi


Ignore:
Timestamp:
07/23/13 07:50:22 (11 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
4.11, 5, master
Children:
ac252bdc
Parents:
98c7eaca
git-author:
Sebastian Huber <sebastian.huber@…> (07/23/13 07:50:22)
git-committer:
Sebastian Huber <sebastian.huber@…> (07/23/13 13:12:51)
Message:

sapi: Merge rbtree API into one file

Location:
cpukit/sapi
Files:
1 deleted
3 edited

Legend:

Unmodified
Added
Removed
  • cpukit/sapi/Makefile.am

    r98c7eaca r2445bda  
    2121
    2222include_rtems_HEADERS += inline/rtems/extension.inl
    23 include_rtems_HEADERS += inline/rtems/rbtree.inl
    2423
    2524## src
  • cpukit/sapi/include/rtems/rbtree.h

    r98c7eaca r2445bda  
    2121#define _RTEMS_RBTREE_H
    2222
     23#include <rtems/score/rbtree.h>
     24
    2325#ifdef __cplusplus
    2426extern "C" {
    2527#endif
    26 
    27 #include <rtems/system.h>
    28 #include <rtems/score/rbtree.h>
    2928
    3029/**
     
    7372  _RBTree_Container_of(node,object_type,object_member)
    7473
    75 #include <rtems/rbtree.inl>
     74/**
     75 * @brief Initialize a RBTree header.
     76 *
     77 * This routine initializes @a the_rbtree structure to manage the
     78 * contiguous array of @a number_nodes nodes which starts at
     79 * @a starting_address.  Each node is of @a node_size bytes.
     80 */
     81RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize(
     82  rtems_rbtree_control          *the_rbtree,
     83  rtems_rbtree_compare_function  compare_function,
     84  void                          *starting_address,
     85  size_t                         number_nodes,
     86  size_t                         node_size,
     87  bool                           is_unique
     88)
     89{
     90  _RBTree_Initialize( the_rbtree, compare_function, starting_address,
     91    number_nodes, node_size, is_unique);
     92}
     93
     94/**
     95 * @brief Initialize this RBTree as Empty
     96 *
     97 * This routine initializes @a the_rbtree to contain zero nodes.
     98 */
     99RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty(
     100  rtems_rbtree_control          *the_rbtree,
     101  rtems_rbtree_compare_function  compare_function,
     102  bool                           is_unique
     103)
     104{
     105  _RBTree_Initialize_empty( the_rbtree, compare_function, is_unique );
     106}
     107
     108/**
     109 * @brief Set off RBtree.
     110 *
     111 * This function sets the next and previous fields of the @a node to NULL
     112 * indicating the @a node is not part of any rbtree.
     113 */
     114RTEMS_INLINE_ROUTINE void rtems_rbtree_set_off_rbtree(
     115  rtems_rbtree_node *node
     116)
     117{
     118  _RBTree_Set_off_rbtree( node );
     119}
     120
     121/**
     122 * @brief Is the Node off RBTree.
     123 *
     124 * This function returns true if the @a node is not on a rbtree. A @a node is
     125 * off rbtree if the next and previous fields are set to NULL.
     126 */
     127RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_node_off_rbtree(
     128  const rtems_rbtree_node *node
     129)
     130{
     131  return _RBTree_Is_node_off_rbtree( node );
     132}
     133
     134/**
     135 * @brief Is the RBTree Node Pointer NULL.
     136 *
     137 * This function returns true if @a the_node is NULL and false otherwise.
     138 */
     139RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_null_node(
     140  const rtems_rbtree_node *the_node
     141)
     142{
     143  return _RBTree_Is_null_node( the_node );
     144}
     145
     146/**
     147 * @brief Return pointer to RBTree root.
     148 *
     149 * This function returns a pointer to the root node of @a the_rbtree.
     150 */
     151RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_root(
     152  const rtems_rbtree_control *the_rbtree
     153)
     154{
     155  return _RBTree_Root( the_rbtree );
     156}
     157
     158/**
     159 * @brief Return pointer to RBTree Minimum
     160 *
     161 * This function returns a pointer to the minimum node of @a the_rbtree.
     162 */
     163RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_min(
     164  const rtems_rbtree_control *the_rbtree
     165)
     166{
     167  return _RBTree_First( the_rbtree, RBT_LEFT );
     168}
     169
     170/**
     171 * @brief Return pointer to RBTree maximum.
     172 *
     173 * This function returns a pointer to the maximum node of @a the_rbtree.
     174 */
     175RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_max(
     176  const rtems_rbtree_control *the_rbtree
     177)
     178{
     179  return _RBTree_First( the_rbtree, RBT_RIGHT );
     180}
     181
     182/**
     183 * @brief Return pointer to the left child node from this node.
     184 *
     185 * This function returns a pointer to the left child node of @a the_node.
     186 */
     187RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_left(
     188  const rtems_rbtree_node *the_node
     189)
     190{
     191  return _RBTree_Left( the_node );
     192}
     193
     194/**
     195 * @brief Return pointer to the right child node from this node.
     196 *
     197 * This function returns a pointer to the right child node of @a the_node.
     198 */
     199RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_right(
     200  const rtems_rbtree_node *the_node
     201)
     202{
     203  return _RBTree_Right( the_node );
     204}
     205
     206/**
     207 * @brief Return pointer to the parent child node from this node.
     208 *
     209 * This function returns a pointer to the parent node of @a the_node.
     210 */
     211RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_parent(
     212  const rtems_rbtree_node *the_node
     213)
     214{
     215  return _RBTree_Parent( the_node );
     216}
     217
     218/**
     219 * @brief Are two nodes equal.
     220 *
     221 * This function returns true if @a left and @a right are equal,
     222 * and false otherwise.
     223 */
     224RTEMS_INLINE_ROUTINE bool rtems_rbtree_are_nodes_equal(
     225  const rtems_rbtree_node *left,
     226  const rtems_rbtree_node *right
     227)
     228{
     229  return _RBTree_Are_nodes_equal( left, right );
     230}
     231
     232/**
     233 * @brief Is the RBTree empty.
     234 *
     235 * This function returns true if there a no nodes on @a the_rbtree and
     236 * false otherwise.
     237 */
     238RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_empty(
     239  const rtems_rbtree_control *the_rbtree
     240)
     241{
     242  return _RBTree_Is_empty( the_rbtree );
     243}
     244
     245/**
     246 * @brief Is this the minimum node on the RBTree.
     247 *
     248 * This function returns true if @a the_node is the min node on @a the_rbtree
     249 * and false otherwise.
     250 */
     251RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_min(
     252  const rtems_rbtree_control *the_rbtree,
     253  const rtems_rbtree_node *the_node
     254)
     255{
     256  return _RBTree_Is_first( the_rbtree, the_node, RBT_LEFT );
     257}
     258
     259/**
     260 * @brief Is this the maximum node on the RBTree.
     261 *
     262 * This function returns true if @a the_node is the max node on @a the_rbtree
     263 * and false otherwise.
     264 */
     265RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_max(
     266  const rtems_rbtree_control *the_rbtree,
     267  const rtems_rbtree_node *the_node
     268)
     269{
     270  return _RBTree_Is_first( the_rbtree, the_node, RBT_RIGHT );
     271}
     272
     273
     274/**
     275 * @brief Does this RBTree have only one node.
     276 *
     277 * This function returns true if there is only one node on @a the_rbtree and
     278 * false otherwise.
     279 */
     280RTEMS_INLINE_ROUTINE bool rtems_rbtree_has_only_one_node(
     281  const rtems_rbtree_control *the_rbtree
     282)
     283{
     284  return _RBTree_Has_only_one_node( the_rbtree );
     285}
     286
     287/**
     288 * @brief Is this node the RBTree root.
     289 *
     290 * This function returns true if @a the_node is the root of @a the_rbtree and
     291 * false otherwise.
     292 */
     293RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root(
     294  const rtems_rbtree_control *the_rbtree,
     295  const rtems_rbtree_node *the_node
     296)
     297{
     298  return _RBTree_Is_root( the_rbtree, the_node );
     299}
     300
     301/**
     302 * @copydoc _RBTree_Find_unprotected()
     303 */
     304RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find_unprotected(
     305  const rtems_rbtree_control *the_rbtree,
     306  const rtems_rbtree_node *the_node
     307)
     308{
     309  return _RBTree_Find_unprotected( the_rbtree, the_node );
     310}
     311
     312/** @brief Find the node with given key in the tree.
     313 *
     314 * This function returns a pointer to the node having key equal to the key
     315 * of @a the_node if it exists within @a the_rbtree, and NULL if not.
     316 * @a the_node has to be made up before a search.
     317 *
     318 * @note If the tree is not unique and contains duplicate keys, the set
     319 *       of duplicate keys acts as FIFO.
     320 */
     321RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
     322  const rtems_rbtree_control *the_rbtree,
     323  const rtems_rbtree_node *the_node
     324)
     325{
     326  return _RBTree_Find( the_rbtree, the_node );
     327}
     328
     329/**
     330 * @copydoc _RBTree_Predecessor_unprotected()
     331 */
     332RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor_unprotected(
     333  const rtems_rbtree_node *node
     334)
     335{
     336  return _RBTree_Predecessor_unprotected( node );
     337}
     338
     339/**
     340 * @copydoc _RBTree_Predecessor()
     341 */
     342RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor(
     343  const rtems_rbtree_node *node
     344)
     345{
     346  return _RBTree_Predecessor( node );
     347}
     348
     349/**
     350 * @copydoc _RBTree_Successor_unprotected()
     351 */
     352RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor_unprotected(
     353  const rtems_rbtree_node *node
     354)
     355{
     356  return _RBTree_Successor_unprotected( node );
     357}
     358
     359/**
     360 * @copydoc _RBTree_Successor()
     361 */
     362RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor(
     363  const rtems_rbtree_node *node
     364)
     365{
     366  return _RBTree_Successor( node );
     367}
     368
     369/**
     370 * @copydoc _RBTree_Extract_unprotected()
     371 */
     372RTEMS_INLINE_ROUTINE void rtems_rbtree_extract_unprotected(
     373  rtems_rbtree_control *the_rbtree,
     374  rtems_rbtree_node *the_node
     375)
     376{
     377  _RBTree_Extract_unprotected( the_rbtree, the_node );
     378}
     379
     380/**
     381 * @brief Extract the specified node from a rbtree.
     382 *
     383 * This routine extracts @a the_node from @a the_rbtree on which it resides.
     384 * It disables interrupts to ensure the atomicity of the extract operation.
     385 */
     386RTEMS_INLINE_ROUTINE void rtems_rbtree_extract(
     387  rtems_rbtree_control *the_rbtree,
     388  rtems_rbtree_node *the_node
     389)
     390{
     391  _RBTree_Extract( the_rbtree, the_node );
     392}
     393
     394/**
     395 * @brief Obtain the min node on a rbtree.
     396 *
     397 * This function removes the min node from @a the_rbtree and returns
     398 * a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
     399 */
     400
     401RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_min_unprotected(
     402  rtems_rbtree_control *the_rbtree
     403)
     404{
     405  return _RBTree_Get_unprotected( the_rbtree, RBT_LEFT );
     406}
     407
     408/**
     409 * @brief Obtain the min node on a rbtree.
     410 *
     411 * This function removes the min node from @a the_rbtree and returns
     412 * a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
     413 * It disables interrupts to ensure the atomicity of the get operation.
     414 */
     415RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_min(
     416  rtems_rbtree_control *the_rbtree
     417)
     418{
     419  return _RBTree_Get( the_rbtree, RBT_LEFT );
     420}
     421
     422/**
     423 * @brief Obtain the max node on a rbtree.
     424 *
     425 * This function removes the max node from @a the_rbtree and returns
     426 * a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
     427 */
     428
     429RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_max_unprotected(
     430  rtems_rbtree_control *the_rbtree
     431)
     432{
     433  return _RBTree_Get_unprotected( the_rbtree, RBT_RIGHT );
     434}
     435
     436/**
     437 * @brief Obtain the max node on a rbtree.
     438 *
     439 * This function removes the max node from @a the_rbtree and returns
     440 * a pointer to that node.  If @a the_rbtree is empty, then NULL is returned.
     441 * It disables interrupts to ensure the atomicity of the get operation.
     442 */
     443RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_max(
     444  rtems_rbtree_control *the_rbtree
     445)
     446{
     447  return _RBTree_Get( the_rbtree, RBT_RIGHT );
     448}
     449
     450/**
     451 * @brief Peek at the min node on a rbtree.
     452 *
     453 * This function returns a pointer to the min node from @a the_rbtree
     454 * without changing the tree.  If @a the_rbtree is empty,
     455 * then NULL is returned.
     456 */
     457RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_min(
     458  const rtems_rbtree_control *the_rbtree
     459)
     460{
     461  return _RBTree_First( the_rbtree, RBT_LEFT );
     462}
     463
     464/**
     465 * @brief Peek at the max node on a rbtree.
     466 *
     467 * This function returns a pointer to the max node from @a the_rbtree
     468 * without changing the tree.  If @a the_rbtree is empty,
     469 * then NULL is returned.
     470 */
     471RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_max(
     472  const rtems_rbtree_control *the_rbtree
     473)
     474{
     475  return _RBTree_First( the_rbtree, RBT_RIGHT );
     476}
     477
     478/**
     479 * @copydoc _RBTree_Find_header_unprotected()
     480 */
     481RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header_unprotected(
     482  rtems_rbtree_node *the_node
     483)
     484{
     485  return _RBTree_Find_header_unprotected( the_node );
     486}
     487
     488/**
     489 * @brief Find the control header of the tree containing a given node.
     490 *
     491 * This routine finds the rtems_rbtree_control structure of the tree
     492 * containing @a the_node.
     493 * It disables interrupts to ensure the atomicity of the find operation.
     494 */
     495RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header(
     496  rtems_rbtree_node *the_node
     497)
     498{
     499  return _RBTree_Find_header( the_node );
     500}
     501
     502/**
     503 * @copydoc _RBTree_Insert_unprotected()
     504 */
     505RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert_unprotected(
     506  rtems_rbtree_control *the_rbtree,
     507  rtems_rbtree_node *the_node
     508)
     509{
     510  return _RBTree_Insert_unprotected( the_rbtree, the_node );
     511}
     512
     513/**
     514 * @brief Insert a node on a rbtree.
     515 *
     516 * This routine inserts @a the_node on @a the_rbtree.
     517 * It disables interrupts to ensure the atomicity of the insert operation.
     518 *
     519 * @retval 0 Successfully inserted.
     520 * @retval -1 NULL @a the_node.
     521 * @retval RBTree_Node* if one with equal key to the key of @a the_node exists
     522 *         in an unique @a the_rbtree.
     523 */
     524RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
     525  rtems_rbtree_control *the_rbtree,
     526  rtems_rbtree_node *the_node
     527)
     528{
     529  return _RBTree_Insert( the_rbtree, the_node );
     530}
     531
     532/**
     533 * @brief Determines whether the tree is unique.
     534 */
     535RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_unique(
     536  const rtems_rbtree_control *the_rbtree
     537)
     538{
     539  return _RBTree_Is_unique(the_rbtree);
     540}
    76541
    77542#ifdef __cplusplus
  • cpukit/sapi/preinstall.am

    r98c7eaca r2445bda  
    8585PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/extension.inl
    8686
    87 $(PROJECT_INCLUDE)/rtems/rbtree.inl: inline/rtems/rbtree.inl $(PROJECT_INCLUDE)/rtems/$(dirstamp)
    88         $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/rbtree.inl
    89 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/rbtree.inl
    90 
    9187$(PROJECT_LIB)/libsapi.a: libsapi.a $(PROJECT_LIB)/$(dirstamp)
    9288        $(INSTALL_DATA) $< $(PROJECT_LIB)/libsapi.a
Note: See TracChangeset for help on using the changeset viewer.