[bd9baa81] | 1 | /** |
---|
| 2 | * @file rtems/score/rbtree.h |
---|
| 3 | * |
---|
[319cb20] | 4 | * @brief Constants and Structures Associated with the Red-Black Tree Handler |
---|
| 5 | * |
---|
[bd9baa81] | 6 | * This include file contains all the constants and structures associated |
---|
| 7 | * with the Red-Black Tree Handler. |
---|
| 8 | */ |
---|
| 9 | |
---|
| 10 | /* |
---|
| 11 | * Copyright (c) 2010 Gedare Bloom. |
---|
| 12 | * |
---|
| 13 | * The license and distribution terms for this file may be |
---|
| 14 | * found in the file LICENSE in this distribution or at |
---|
[c499856] | 15 | * http://www.rtems.org/license/LICENSE. |
---|
[bd9baa81] | 16 | */ |
---|
| 17 | |
---|
| 18 | #ifndef _RTEMS_SCORE_RBTREE_H |
---|
| 19 | #define _RTEMS_SCORE_RBTREE_H |
---|
| 20 | |
---|
[050adc2] | 21 | #include <stddef.h> |
---|
| 22 | |
---|
[93fb3cb0] | 23 | #include <rtems/score/address.h> |
---|
| 24 | |
---|
| 25 | #ifdef __cplusplus |
---|
| 26 | extern "C" { |
---|
| 27 | #endif |
---|
| 28 | |
---|
[bd9baa81] | 29 | /** |
---|
| 30 | * @defgroup ScoreRBTree Red-Black Tree Handler |
---|
| 31 | * |
---|
[d8cd045c] | 32 | * @ingroup Score |
---|
| 33 | * |
---|
[bd9baa81] | 34 | * The Red-Black Tree Handler is used to manage sets of entities. This handler |
---|
| 35 | * provides two data structures. The rbtree Node data structure is included |
---|
| 36 | * as the first part of every data structure that will be placed on |
---|
| 37 | * a RBTree. The second data structure is rbtree Control which is used |
---|
| 38 | * to manage a set of rbtree Nodes. |
---|
| 39 | */ |
---|
| 40 | /**@{*/ |
---|
| 41 | |
---|
[4b72da4] | 42 | /** |
---|
| 43 | * @typedef RBTree_Node |
---|
| 44 | * |
---|
| 45 | * This type definition promotes the name for the RBTree Node used by |
---|
| 46 | * all RTEMS code. It is a separate type definition because a forward |
---|
| 47 | * reference is required to define it. See @ref RBTree_Node_struct for |
---|
| 48 | * detailed information. |
---|
| 49 | */ |
---|
| 50 | typedef struct RBTree_Node_struct RBTree_Node; |
---|
[bd9baa81] | 51 | |
---|
[4b72da4] | 52 | /** |
---|
| 53 | * This enum type defines the colors available for the RBTree Nodes |
---|
| 54 | */ |
---|
| 55 | typedef enum { |
---|
| 56 | RBT_BLACK, |
---|
| 57 | RBT_RED |
---|
| 58 | } RBTree_Color; |
---|
[bd9baa81] | 59 | |
---|
[4b72da4] | 60 | /** |
---|
| 61 | * @struct RBTree_Node_struct |
---|
| 62 | * |
---|
| 63 | * This is used to manage each element (node) which is placed |
---|
| 64 | * on a RBT. |
---|
| 65 | * |
---|
| 66 | * @note Typically, a more complicated structure will use the |
---|
| 67 | * rbtree package. The more complicated structure will |
---|
| 68 | * include a rbtree node as the first element in its |
---|
| 69 | * control structure. It will then call the rbtree package |
---|
| 70 | * with a pointer to that node element. The node pointer |
---|
| 71 | * and the higher level structure start at the same address |
---|
| 72 | * so the user can cast the pointers back and forth. |
---|
| 73 | * |
---|
| 74 | */ |
---|
| 75 | struct RBTree_Node_struct { |
---|
| 76 | /** This points to the node's parent */ |
---|
| 77 | RBTree_Node *parent; |
---|
| 78 | /** child[0] points to the left child, child[1] points to the right child */ |
---|
| 79 | RBTree_Node *child[2]; |
---|
| 80 | /** The color of the node. Either red or black */ |
---|
| 81 | RBTree_Color color; |
---|
| 82 | }; |
---|
[dacdda30] | 83 | |
---|
[4b72da4] | 84 | /** |
---|
[319cb20] | 85 | * @brief Macro to return the structure containing the @a node. |
---|
[4b72da4] | 86 | * |
---|
| 87 | * This macro returns a pointer of type @a container_type that points |
---|
| 88 | * to the structure containing @a node, where @a node_field_name is the |
---|
| 89 | * field name of the RBTree_Node structure in @a container_type. |
---|
| 90 | * |
---|
| 91 | */ |
---|
[b4959ec3] | 92 | #define _RBTree_Container_of(node, container_type, node_field_name) \ |
---|
| 93 | ( \ |
---|
| 94 | (container_type*) \ |
---|
| 95 | ( (uintptr_t)(node) - offsetof(container_type, node_field_name) ) \ |
---|
| 96 | ) |
---|
[bd9baa81] | 97 | |
---|
[4b72da4] | 98 | /** |
---|
| 99 | * This type indicates the direction. |
---|
| 100 | */ |
---|
| 101 | typedef enum { |
---|
| 102 | RBT_LEFT=0, |
---|
| 103 | RBT_RIGHT=1 |
---|
| 104 | } RBTree_Direction; |
---|
[bd9baa81] | 105 | |
---|
[74f1c73e] | 106 | /** |
---|
[64939bc] | 107 | * @brief Compares two red-black tree nodes. |
---|
| 108 | * |
---|
| 109 | * @param[in] first The first node. |
---|
| 110 | * @param[in] second The second node. |
---|
| 111 | * |
---|
| 112 | * @retval positive The key value of the first node is greater than the one of |
---|
| 113 | * the second node. |
---|
| 114 | * @retval 0 The key value of the first node is equal to the one of the second |
---|
| 115 | * node. |
---|
| 116 | * @retval negative The key value of the first node is less than the one of the |
---|
| 117 | * second node. |
---|
[74f1c73e] | 118 | */ |
---|
[64939bc] | 119 | typedef int ( *RBTree_Compare )( |
---|
| 120 | const RBTree_Node *first, |
---|
| 121 | const RBTree_Node *second |
---|
[74f1c73e] | 122 | ); |
---|
| 123 | |
---|
[4b72da4] | 124 | /** |
---|
| 125 | * @struct RBTree_Control |
---|
| 126 | * |
---|
| 127 | * This is used to manage a RBT. A rbtree consists of a tree of zero or more |
---|
| 128 | * nodes. |
---|
| 129 | * |
---|
| 130 | * @note This implementation does not require special checks for |
---|
| 131 | * manipulating the root element of the RBT. |
---|
| 132 | * To accomplish this the @a RBTree_Control structure can be overlaid |
---|
| 133 | * with a @ref RBTree_Node structure to act as a "dummy root", |
---|
| 134 | * which has a NULL parent and its left child is the root. |
---|
| 135 | */ |
---|
[bd9baa81] | 136 | |
---|
[4b72da4] | 137 | /* the RBTree_Control is actually part of the RBTree structure as an |
---|
| 138 | * RBTree_Node. The mapping of fields from RBTree_Control to RBTree_Node are: |
---|
| 139 | * permanent_null == parent |
---|
| 140 | * root == left |
---|
| 141 | * first[0] == right |
---|
| 142 | */ |
---|
| 143 | typedef struct { |
---|
| 144 | /** This points to a NULL. Useful for finding the root. */ |
---|
| 145 | RBTree_Node *permanent_null; |
---|
| 146 | /** This points to the root node of the RBT. */ |
---|
| 147 | RBTree_Node *root; |
---|
| 148 | /** This points to the min and max nodes of this RBT. */ |
---|
| 149 | RBTree_Node *first[2]; |
---|
| 150 | } RBTree_Control; |
---|
[bd9baa81] | 151 | |
---|
[4b72da4] | 152 | /** |
---|
| 153 | * @brief RBTree initializer for an empty rbtree with designator @a name. |
---|
| 154 | */ |
---|
[64939bc] | 155 | #define RBTREE_INITIALIZER_EMPTY( name ) \ |
---|
| 156 | { NULL, NULL, { NULL, NULL } } |
---|
[bd9baa81] | 157 | |
---|
[4b72da4] | 158 | /** |
---|
| 159 | * @brief RBTree definition for an empty rbtree with designator @a name. |
---|
| 160 | */ |
---|
[64939bc] | 161 | #define RBTREE_DEFINE_EMPTY( name ) \ |
---|
| 162 | RBTree_Control name = RBTREE_INITIALIZER_EMPTY( name ) |
---|
[bd9baa81] | 163 | |
---|
[4b72da4] | 164 | /** |
---|
| 165 | * @brief RBTree_Node initializer for an empty node with designator @a name. |
---|
| 166 | */ |
---|
[64939bc] | 167 | #define RBTREE_NODE_INITIALIZER_EMPTY( name ) \ |
---|
| 168 | { NULL, { NULL, NULL }, RBT_RED } |
---|
[bd9baa81] | 169 | |
---|
[4b72da4] | 170 | /** |
---|
| 171 | * @brief RBTree definition for an empty rbtree with designator @a name. |
---|
| 172 | */ |
---|
[64939bc] | 173 | #define RBTREE_NODE_DEFINE_EMPTY( name ) \ |
---|
| 174 | RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY( name ) |
---|
[bd9baa81] | 175 | |
---|
[4b72da4] | 176 | /** |
---|
[319cb20] | 177 | * @brief Initialize a RBTree Header. |
---|
[4b72da4] | 178 | * |
---|
| 179 | * This routine initializes @a the_rbtree structure to manage the |
---|
| 180 | * contiguous array of @a number_nodes nodes which starts at |
---|
| 181 | * @a starting_address. Each node is of @a node_size bytes. |
---|
[319cb20] | 182 | * |
---|
[f2f63d1] | 183 | * @param[in] the_rbtree is the pointer to rbtree header |
---|
[64939bc] | 184 | * @param[in] compare The node compare function. |
---|
[f2f63d1] | 185 | * @param[in] starting_address is the starting address of first node |
---|
| 186 | * @param[in] number_nodes is the number of nodes in rbtree |
---|
| 187 | * @param[in] node_size is the size of node in bytes |
---|
[64939bc] | 188 | * @param[in] is_unique If true, then reject nodes with a duplicate key, else |
---|
| 189 | * otherwise. |
---|
[4b72da4] | 190 | */ |
---|
| 191 | void _RBTree_Initialize( |
---|
[64939bc] | 192 | RBTree_Control *the_rbtree, |
---|
| 193 | RBTree_Compare compare, |
---|
| 194 | void *starting_address, |
---|
| 195 | size_t number_nodes, |
---|
| 196 | size_t node_size, |
---|
| 197 | bool is_unique |
---|
[4b72da4] | 198 | ); |
---|
[bd9baa81] | 199 | |
---|
[4b72da4] | 200 | /** |
---|
[833dd90] | 201 | * @brief Tries to find a node for the specified key in the tree. |
---|
[4b72da4] | 202 | * |
---|
[833dd90] | 203 | * @param[in] the_rbtree The red-black tree control. |
---|
| 204 | * @param[in] the_node A node specifying the key. |
---|
[64939bc] | 205 | * @param[in] compare The node compare function. |
---|
| 206 | * @param[in] is_unique If true, then return the first node with a key equal to |
---|
| 207 | * the one of the node specified if it exits, else return the last node if it |
---|
| 208 | * exists. |
---|
[4b72da4] | 209 | * |
---|
[833dd90] | 210 | * @retval node A node corresponding to the key. If the tree is not unique |
---|
| 211 | * and contains duplicate keys, the set of duplicate keys acts as FIFO. |
---|
| 212 | * @retval NULL No node exists in the tree for the key. |
---|
[53afcfd2] | 213 | */ |
---|
[4ea97d24] | 214 | RBTree_Node *_RBTree_Find( |
---|
[0ca61727] | 215 | const RBTree_Control *the_rbtree, |
---|
[64939bc] | 216 | const RBTree_Node *the_node, |
---|
| 217 | RBTree_Compare compare, |
---|
| 218 | bool is_unique |
---|
[53afcfd2] | 219 | ); |
---|
| 220 | |
---|
[4b72da4] | 221 | /** |
---|
[4ea97d24] | 222 | * @brief Insert @a the_node on the Red-Black Tree @a the_rbtree. |
---|
[4b72da4] | 223 | * |
---|
| 224 | * This routine inserts @a the_node on the Red-Black Tree @a the_rbtree. |
---|
| 225 | * |
---|
[64939bc] | 226 | * @param[in] the_rbtree The red-black tree control. |
---|
| 227 | * @param[in] the_node The node to insert. |
---|
| 228 | * @param[in] compare The node compare function. |
---|
| 229 | * @param[in] is_unique If true, then reject nodes with a duplicate key, else |
---|
| 230 | * otherwise. |
---|
| 231 | * |
---|
[4b72da4] | 232 | * @retval 0 Successfully inserted. |
---|
| 233 | * @retval -1 NULL @a the_node. |
---|
[74f1c73e] | 234 | * @retval RBTree_Node* if one with equal value to @a the_node 's key exists |
---|
| 235 | * in an unique @a the_rbtree. |
---|
[4b72da4] | 236 | */ |
---|
[4ea97d24] | 237 | RBTree_Node *_RBTree_Insert( |
---|
[4b72da4] | 238 | RBTree_Control *the_rbtree, |
---|
[64939bc] | 239 | RBTree_Node *the_node, |
---|
| 240 | RBTree_Compare compare, |
---|
| 241 | bool is_unique |
---|
[4b72da4] | 242 | ); |
---|
[bd9baa81] | 243 | |
---|
[4b72da4] | 244 | /** |
---|
[4ea97d24] | 245 | * @brief Extracts (removes) @a the_node from @a the_rbtree. |
---|
[4b72da4] | 246 | * |
---|
| 247 | * This routine extracts (removes) @a the_node from @a the_rbtree. |
---|
| 248 | */ |
---|
[4ea97d24] | 249 | void _RBTree_Extract( |
---|
[4b72da4] | 250 | RBTree_Control *the_rbtree, |
---|
| 251 | RBTree_Node *the_node |
---|
| 252 | ); |
---|
[bd9baa81] | 253 | |
---|
[dc62a48c] | 254 | /** |
---|
| 255 | * @brief Returns the in-order next node of a node. |
---|
| 256 | * |
---|
| 257 | * @param[in] node The node. |
---|
| 258 | * @param[in] dir The direction. |
---|
| 259 | * |
---|
| 260 | * @retval NULL The in-order next node does not exist. |
---|
| 261 | * @retval otherwise The next node. |
---|
| 262 | */ |
---|
[4ea97d24] | 263 | RBTree_Node *_RBTree_Next( |
---|
[dc62a48c] | 264 | const RBTree_Node *node, |
---|
| 265 | RBTree_Direction dir |
---|
| 266 | ); |
---|
| 267 | |
---|
[112396de] | 268 | /** |
---|
[93fb3cb0] | 269 | * @brief Set off RBtree. |
---|
[112396de] | 270 | * |
---|
[93fb3cb0] | 271 | * This function sets the parent and child fields of the @a node to NULL |
---|
| 272 | * indicating the @a node is not part of a rbtree. |
---|
[112396de] | 273 | * |
---|
[93fb3cb0] | 274 | */ |
---|
| 275 | RTEMS_INLINE_ROUTINE void _RBTree_Set_off_rbtree( |
---|
| 276 | RBTree_Node *node |
---|
| 277 | ) |
---|
| 278 | { |
---|
| 279 | node->parent = node->child[RBT_LEFT] = node->child[RBT_RIGHT] = NULL; |
---|
| 280 | } |
---|
| 281 | |
---|
| 282 | /** |
---|
| 283 | * @brief Is the node off RBTree. |
---|
[112396de] | 284 | * |
---|
[93fb3cb0] | 285 | * This function returns true if the @a node is not on a rbtree. A @a node is |
---|
| 286 | * off rbtree if the parent and child fields are set to NULL. |
---|
[112396de] | 287 | */ |
---|
[93fb3cb0] | 288 | RTEMS_INLINE_ROUTINE bool _RBTree_Is_node_off_rbtree( |
---|
| 289 | const RBTree_Node *node |
---|
| 290 | ) |
---|
| 291 | { |
---|
| 292 | return (node->parent == NULL) && |
---|
| 293 | (node->child[RBT_LEFT] == NULL) && |
---|
| 294 | (node->child[RBT_RIGHT] == NULL); |
---|
| 295 | } |
---|
[112396de] | 296 | |
---|
[93fb3cb0] | 297 | /** |
---|
| 298 | * @brief Return pointer to RBTree's root node. |
---|
| 299 | * |
---|
| 300 | * This function returns a pointer to the root node of @a the_rbtree. |
---|
| 301 | */ |
---|
| 302 | RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Root( |
---|
| 303 | const RBTree_Control *the_rbtree |
---|
| 304 | ) |
---|
| 305 | { |
---|
| 306 | return the_rbtree->root; |
---|
| 307 | } |
---|
| 308 | |
---|
| 309 | /** |
---|
| 310 | * @brief Return pointer to RBTree's first node. |
---|
| 311 | * |
---|
| 312 | * This function returns a pointer to the first node on @a the_rbtree, |
---|
| 313 | * where @a dir specifies whether to return the minimum (0) or maximum (1). |
---|
| 314 | */ |
---|
| 315 | RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_First( |
---|
| 316 | const RBTree_Control *the_rbtree, |
---|
| 317 | RBTree_Direction dir |
---|
| 318 | ) |
---|
| 319 | { |
---|
| 320 | return the_rbtree->first[dir]; |
---|
| 321 | } |
---|
| 322 | |
---|
| 323 | /** |
---|
| 324 | * @brief Return pointer to the parent of this node. |
---|
| 325 | * |
---|
| 326 | * This function returns a pointer to the parent node of @a the_node. |
---|
| 327 | */ |
---|
| 328 | RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Parent( |
---|
| 329 | const RBTree_Node *the_node |
---|
| 330 | ) |
---|
| 331 | { |
---|
| 332 | if (!the_node->parent->parent) return NULL; |
---|
| 333 | return the_node->parent; |
---|
| 334 | } |
---|
| 335 | |
---|
| 336 | /** |
---|
| 337 | * @brief Return pointer to the left of this node. |
---|
| 338 | * |
---|
| 339 | * This function returns a pointer to the left node of this node. |
---|
| 340 | * |
---|
| 341 | * @param[in] the_node is the node to be operated upon. |
---|
| 342 | * |
---|
| 343 | * @return This method returns the left node on the rbtree. |
---|
| 344 | */ |
---|
| 345 | RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Left( |
---|
| 346 | const RBTree_Node *the_node |
---|
| 347 | ) |
---|
| 348 | { |
---|
| 349 | return the_node->child[RBT_LEFT]; |
---|
| 350 | } |
---|
| 351 | |
---|
| 352 | /** |
---|
| 353 | * @brief Return pointer to the right of this node. |
---|
| 354 | * |
---|
| 355 | * This function returns a pointer to the right node of this node. |
---|
| 356 | * |
---|
| 357 | * @param[in] the_node is the node to be operated upon. |
---|
| 358 | * |
---|
| 359 | * @return This method returns the right node on the rbtree. |
---|
| 360 | */ |
---|
| 361 | RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Right( |
---|
| 362 | const RBTree_Node *the_node |
---|
| 363 | ) |
---|
| 364 | { |
---|
| 365 | return the_node->child[RBT_RIGHT]; |
---|
| 366 | } |
---|
| 367 | |
---|
| 368 | /** |
---|
| 369 | * @brief Is the RBTree empty. |
---|
| 370 | * |
---|
| 371 | * This function returns true if there are no nodes on @a the_rbtree and |
---|
| 372 | * false otherwise. |
---|
| 373 | * |
---|
| 374 | * @param[in] the_rbtree is the rbtree to be operated upon. |
---|
| 375 | * |
---|
| 376 | * @retval true There are no nodes on @a the_rbtree. |
---|
| 377 | * @retval false There are nodes on @a the_rbtree. |
---|
| 378 | */ |
---|
| 379 | RTEMS_INLINE_ROUTINE bool _RBTree_Is_empty( |
---|
| 380 | const RBTree_Control *the_rbtree |
---|
| 381 | ) |
---|
| 382 | { |
---|
| 383 | return (the_rbtree->root == NULL); |
---|
| 384 | } |
---|
| 385 | |
---|
| 386 | /** |
---|
| 387 | * @brief Is this the first node on the RBTree. |
---|
| 388 | * |
---|
| 389 | * This function returns true if @a the_node is the first node on |
---|
| 390 | * @a the_rbtree and false otherwise. @a dir specifies whether first means |
---|
| 391 | * minimum (0) or maximum (1). |
---|
| 392 | * |
---|
| 393 | * @retval true @a the_node is the first node on @a the_rbtree. |
---|
| 394 | * @retval false @a the_node is not the first node on @a the_rbtree. |
---|
| 395 | * |
---|
| 396 | */ |
---|
| 397 | RTEMS_INLINE_ROUTINE bool _RBTree_Is_first( |
---|
| 398 | const RBTree_Control *the_rbtree, |
---|
| 399 | const RBTree_Node *the_node, |
---|
| 400 | RBTree_Direction dir |
---|
| 401 | ) |
---|
| 402 | { |
---|
| 403 | return (the_node == _RBTree_First(the_rbtree, dir)); |
---|
| 404 | } |
---|
| 405 | |
---|
| 406 | /** |
---|
| 407 | * @brief Is this node the RBTree root. |
---|
| 408 | * |
---|
| 409 | * This function returns true if @a the_node is the root of @a the_rbtree and |
---|
| 410 | * false otherwise. |
---|
| 411 | * |
---|
| 412 | * @retval true @a the_node is the root of @a the_rbtree. |
---|
| 413 | * @retval false @a the_node is not the root of @a the_rbtree. |
---|
| 414 | */ |
---|
| 415 | RTEMS_INLINE_ROUTINE bool _RBTree_Is_root( |
---|
| 416 | const RBTree_Control *the_rbtree, |
---|
| 417 | const RBTree_Node *the_node |
---|
| 418 | ) |
---|
| 419 | { |
---|
| 420 | return (the_node == _RBTree_Root(the_rbtree)); |
---|
| 421 | } |
---|
| 422 | |
---|
| 423 | /** |
---|
| 424 | * @brief Find the RBTree_Control header given a node in the tree. |
---|
| 425 | * |
---|
| 426 | * This function returns a pointer to the header of the Red Black |
---|
| 427 | * Tree containing @a the_node if it exists, and NULL if not. |
---|
| 428 | */ |
---|
[4ea97d24] | 429 | RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header( |
---|
[93fb3cb0] | 430 | RBTree_Node *the_node |
---|
| 431 | ) |
---|
| 432 | { |
---|
| 433 | if(!the_node) return NULL; |
---|
| 434 | if(!(the_node->parent)) return NULL; |
---|
| 435 | while(the_node->parent) the_node = the_node->parent; |
---|
| 436 | return (RBTree_Control*)the_node; |
---|
| 437 | } |
---|
| 438 | |
---|
| 439 | /** |
---|
| 440 | * @brief Initialize this RBTree as empty. |
---|
| 441 | * |
---|
| 442 | * This routine initializes @a the_rbtree to contain zero nodes. |
---|
| 443 | */ |
---|
| 444 | RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty( |
---|
[64939bc] | 445 | RBTree_Control *the_rbtree |
---|
| 446 | ) |
---|
[93fb3cb0] | 447 | { |
---|
| 448 | the_rbtree->permanent_null = NULL; |
---|
| 449 | the_rbtree->root = NULL; |
---|
[64939bc] | 450 | the_rbtree->first[RBT_LEFT] = NULL; |
---|
| 451 | the_rbtree->first[RBT_RIGHT] = NULL; |
---|
[93fb3cb0] | 452 | } |
---|
| 453 | |
---|
| 454 | /** |
---|
| 455 | * @brief Returns the predecessor of a node. |
---|
| 456 | * |
---|
| 457 | * @param[in] node is the node. |
---|
| 458 | * |
---|
| 459 | * @retval NULL The predecessor does not exist. Otherwise it returns |
---|
| 460 | * the predecessor node. |
---|
| 461 | */ |
---|
[4ea97d24] | 462 | RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor( |
---|
[93fb3cb0] | 463 | const RBTree_Node *node |
---|
| 464 | ) |
---|
| 465 | { |
---|
[4ea97d24] | 466 | return _RBTree_Next( node, RBT_LEFT ); |
---|
[93fb3cb0] | 467 | } |
---|
| 468 | |
---|
| 469 | /** |
---|
| 470 | * @brief Returns the successor of a node. |
---|
| 471 | * |
---|
| 472 | * @param[in] node is the node. |
---|
| 473 | * |
---|
| 474 | * @retval NULL The successor does not exist. Otherwise the successor node. |
---|
| 475 | */ |
---|
[4ea97d24] | 476 | RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor( |
---|
[93fb3cb0] | 477 | const RBTree_Node *node |
---|
| 478 | ) |
---|
| 479 | { |
---|
[4ea97d24] | 480 | return _RBTree_Next( node, RBT_RIGHT ); |
---|
[93fb3cb0] | 481 | } |
---|
| 482 | |
---|
| 483 | /** |
---|
[4ea97d24] | 484 | * @brief Get the first node. |
---|
[93fb3cb0] | 485 | * |
---|
| 486 | * This function removes the minimum or maximum node from the_rbtree and |
---|
[833dd90] | 487 | * returns a pointer to that node. |
---|
[93fb3cb0] | 488 | * |
---|
| 489 | * @param[in] the_rbtree is the rbtree to attempt to get the min node from. |
---|
| 490 | * @param[in] dir specifies whether to get minimum (0) or maximum (1) |
---|
| 491 | * |
---|
| 492 | * @return This method returns the min or max node on the rbtree, or NULL. |
---|
| 493 | * |
---|
| 494 | * @note This routine may return NULL if the RBTree is empty. |
---|
| 495 | */ |
---|
[4ea97d24] | 496 | RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Get( |
---|
[93fb3cb0] | 497 | RBTree_Control *the_rbtree, |
---|
| 498 | RBTree_Direction dir |
---|
| 499 | ) |
---|
| 500 | { |
---|
| 501 | RBTree_Node *the_node = the_rbtree->first[dir]; |
---|
[4ea97d24] | 502 | _RBTree_Extract(the_rbtree, the_node); |
---|
[93fb3cb0] | 503 | return the_node; |
---|
| 504 | } |
---|
| 505 | |
---|
[bd9baa81] | 506 | /**@}*/ |
---|
| 507 | |
---|
[93fb3cb0] | 508 | #ifdef __cplusplus |
---|
| 509 | } |
---|
| 510 | #endif |
---|
| 511 | |
---|
[bd9baa81] | 512 | #endif |
---|
[53afcfd2] | 513 | /* end of include file */ |
---|