RTEMS
5.0.0
|
A Red-Black Tree container. More...
Files | |
file | rbtree.c |
Initialize a Red-Black Tree. | |
Macros | |
#define | RTEMS_RBTREE_INITIALIZER_EMPTY(name) RBTREE_INITIALIZER_EMPTY(name) |
RBTree initializer for an empty rbtree with designator name. | |
#define | RTEMS_RBTREE_DEFINE_EMPTY(name) RBTREE_DEFINE_EMPTY(name) |
RBTree definition for an empty rbtree with designator name. | |
Typedefs | |
typedef RBTree_Node | rtems_rbtree_node |
typedef RBTree_Control | rtems_rbtree_control |
typedef long | rtems_rbtree_compare_result |
Integer type for compare results. More... | |
typedef rtems_rbtree_compare_result(* | rtems_rbtree_compare) (const RBTree_Node *first, const RBTree_Node *second) |
Compares two red-black tree nodes. More... | |
A Red-Black Tree container.
The red-black tree container offers no internal protection against concurrent access. The user must ensure that at most one thread at once can access a red-black tree instance.
typedef rtems_rbtree_compare_result( * rtems_rbtree_compare) (const RBTree_Node *first, const RBTree_Node *second) |
Compares two red-black tree nodes.
[in] | first | The first node. |
[in] | second | The second node. |
positive | The key value of the first node is greater than the one of the second node. |
0 | The key value of the first node is equal to the one of the second node. |
negative | The key value of the first node is less than the one of the second node. |
typedef long rtems_rbtree_compare_result |
Integer type for compare results.
The type is large enough to represent pointers and 32-bit signed integers.
The rbtree's control anchors the rbtree.
A node that can be manipulated in the rbtree.
RTEMS_INLINE_ROUTINE void rtems_rbtree_extract | ( | rtems_rbtree_control * | the_rbtree, |
rtems_rbtree_node * | the_node | ||
) |
Extracts (removes) the node from the red-black tree.
This function does not set the node off-tree. In case this is desired, then call _RBTree_Set_off_tree() after the extraction.
In case the node to extract is not a node of the tree, then this function yields unpredictable results.
[in] | the_rbtree | The red-black tree control. |
[in] | the_node | The node to extract. |
rtems_rbtree_node* rtems_rbtree_find | ( | const rtems_rbtree_control * | the_rbtree, |
const rtems_rbtree_node * | the_node, | ||
rtems_rbtree_compare | compare, | ||
bool | is_unique | ||
) |
Tries to find a node for the specified key in the tree.
[in] | the_rbtree | The red-black tree control. |
[in] | the_node | A node specifying the key. |
[in] | compare | The node compare function. |
[in] | is_unique | If true, then return the first node with a key equal to the one of the node specified if it exits, else return the last node if it exists. |
node | A node corresponding to the key. If the tree is not unique and contains duplicate keys, the set of duplicate keys acts as FIFO. |
NULL | No node exists in the tree for the key. |
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_get_max | ( | rtems_rbtree_control * | the_rbtree | ) |
Gets a node with the maximal key value from the red-black tree.
This function extracts a node with the maximum key value from tree and returns a pointer to that node if it exists. In case multiple nodes with a maximum key value exist, then they are extracted in LIFO order.
[in] | the_rbtree | The red-black tree control. |
NULL | The tree is empty. |
node | A node with the maximal key value on the tree. |
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_get_min | ( | rtems_rbtree_control * | the_rbtree | ) |
Gets a node with the minimum key value from the red-black tree.
This function extracts a node with the minimum key value from tree and returns a pointer to that node if it exists. In case multiple nodes with a minimum key value exist, then they are extracted in FIFO order.
[in] | the_rbtree | The red-black tree control. |
NULL | The tree is empty. |
node | A node with the minimal key value on the tree. |
void rtems_rbtree_initialize | ( | rtems_rbtree_control * | the_rbtree, |
rtems_rbtree_compare | compare, | ||
void * | starting_address, | ||
size_t | number_nodes, | ||
size_t | node_size, | ||
bool | is_unique | ||
) |
Initialize a RBTree header.
This routine initializes the_rbtree structure to manage the contiguous array of number_nodes nodes which starts at starting_address. Each node is of node_size bytes.
[in] | the_rbtree | is the pointer to rbtree header |
[in] | compare | The node compare function. |
[in] | starting_address | is the starting address of first node |
[in] | number_nodes | is the number of nodes in rbtree |
[in] | node_size | is the size of node in bytes |
[in] | is_unique | If true, then reject nodes with a duplicate key, else otherwise. |
RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty | ( | rtems_rbtree_control * | the_rbtree | ) |
Initialize this RBTree as Empty.
This routine initializes the_rbtree to contain zero nodes.
rtems_rbtree_node* rtems_rbtree_insert | ( | RBTree_Control * | the_rbtree, |
RBTree_Node * | the_node, | ||
rtems_rbtree_compare | compare, | ||
bool | is_unique | ||
) |
Inserts the node into the red-black tree.
In case the node is already a node of a tree, then this function yields unpredictable results.
[in] | the_rbtree | The red-black tree control. |
[in] | the_node | The node to insert. |
[in] | compare | The node compare function. |
[in] | is_unique | If true, then reject nodes with a duplicate key, else insert nodes in FIFO order in case the key value is equal to existing nodes. |
NULL | Successfully inserted. |
existing_node | This is a unique insert and there exists a node with an equal key in the tree already. |
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_empty | ( | const rtems_rbtree_control * | the_rbtree | ) |
Is the RBTree empty.
This function returns true if there a no nodes on the_rbtree and false otherwise.
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_max | ( | const rtems_rbtree_control * | the_rbtree, |
const rtems_rbtree_node * | the_node | ||
) |
Is this the maximum node on the RBTree.
This function returns true if the_node is the max node on the_rbtree and false otherwise.
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_min | ( | const rtems_rbtree_control * | the_rbtree, |
const rtems_rbtree_node * | the_node | ||
) |
Is this the minimum node on the RBTree.
This function returns true if the_node is the min node on the_rbtree and false otherwise.
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_node_off_tree | ( | const rtems_rbtree_node * | node | ) |
Is the Node off RBTree.
This function returns true if the node is not on a rbtree. A node is off rbtree if the next and previous fields are set to NULL.
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root | ( | const rtems_rbtree_node * | the_node | ) |
Returns true if this node is the root node of a red-black tree, and false otherwise.
The root node may change after insert or extract operations. In case the node is not a node of a tree, then this function yields unpredictable results.
[in] | the_node | The node of interest. |
true | The node is the root node. |
false | Otherwise. |
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_left | ( | const rtems_rbtree_node * | the_node | ) |
Return pointer to the left child node from this node.
This function returns a pointer to the left child node of the_node.
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_max | ( | const rtems_rbtree_control * | the_rbtree | ) |
Returns the maximum node of the red-black tree.
[in] | the_rbtree | The red-black tree control. |
NULL | The red-black tree is empty. |
node | The maximum node. |
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_min | ( | const rtems_rbtree_control * | the_rbtree | ) |
Returns the minimum node of the red-black tree.
[in] | the_rbtree | The red-black tree control. |
NULL | The red-black tree is empty. |
node | The minimum node. |
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_parent | ( | const rtems_rbtree_node * | the_node | ) |
Returns a pointer to the parent of this node.
The node must have a parent, thus it is invalid to use this function for the root node or a node that is not part of a tree. To test for the root node compare with _RBTree_Root() or use _RBTree_Is_root().
[in] | the_node | The node of interest. |
parent | The parent of this node. |
undefined | The node is the root node or not part of a tree. |
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_peek_max | ( | const rtems_rbtree_control * | the_rbtree | ) |
Peek at the max node on a rbtree.
This function returns a pointer to the max node from the_rbtree without changing the tree. If the_rbtree is empty, then NULL is returned.
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_peek_min | ( | const rtems_rbtree_control * | the_rbtree | ) |
Peek at the min node on a rbtree.
This function returns a pointer to the min node from the_rbtree without changing the tree. If the_rbtree is empty, then NULL is returned.
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor | ( | const rtems_rbtree_node * | node | ) |
Returns the predecessor of a node.
[in] | node | is the node. |
NULL | The predecessor does not exist. Otherwise it returns the predecessor node. |
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_right | ( | const rtems_rbtree_node * | the_node | ) |
Return pointer to the right child node from this node.
This function returns a pointer to the right child node of the_node.
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_root | ( | const rtems_rbtree_control * | the_rbtree | ) |
Return pointer to RBTree root.
This function returns a pointer to the root node of the_rbtree.
RTEMS_INLINE_ROUTINE void rtems_rbtree_set_off_tree | ( | rtems_rbtree_node * | node | ) |
Set off RBtree.
This function sets the next and previous fields of the node to NULL indicating the node is not part of any rbtree.
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor | ( | const rtems_rbtree_node * | node | ) |
Returns the successor of a node.
[in] | node | is the node. |
NULL | The successor does not exist. Otherwise the successor node. |