Intrusive red-black tree.
More...
#include "container_of.h"
#include "paste.h"
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
Go to the source code of this file.
|
struct | rbtree_node |
| Generated red-black tree node struct type for a given KEY_TYPE . More...
|
|
|
#define | rbtree_node_entry(ptr, type, member) |
| Obtain a pointer to the struct that contains the rbtree node as a member.
|
|
#define | NAME rbtree |
| Prefix to red black tree types and operations. This must be manually defined before including this header file.
|
|
#define | KEY_TYPE int |
| The key type. This must be manually defined before including this header file.
|
|
#define | KEY_IS_STRICTLY_LESS(a, b) |
| Used to compare two keys. This must be manually defined before including this header file.
|
|
|
static void | rbtree_init (rbtree_node_type **rootptr_ptr) |
| Initialize a red-black tree struct.
|
|
static void | rbtree_node_init (rbtree_node_type *node_ptr, KEY_TYPE key) |
| Initialize a red-black tree node.
|
|
static rbtree_node_type * | rbtree_node_get_parent_ptr (rbtree_node_type *node_ptr) |
| Extract the parent pointer of a node.
|
|
static bool | rbtree_node_is_black (const rbtree_node_type *node_ptr) |
| Check if the given node is colored black.
|
|
static bool | rbtree_node_is_red (const rbtree_node_type *node_ptr) |
| Check if the given node is colored red.
|
|
static bool | rbtree_is_empty (rbtree_node_type **rootptr_ptr) |
| Check if the tree is empty.
|
|
static bool | rbtree_contains_key (rbtree_node_type **rootptr_ptr, const KEY_TYPE key) |
| Check if the tree contains a given key.
|
|
static rbtree_node_type * | rbtree_search_node (rbtree_node_type **rootptr_ptr, const KEY_TYPE key) |
| Search for a given node and return a pointer to the node.
|
|
static void | rbtree_insert_node (rbtree_node_type **rootptr_ptr, rbtree_node_type *node_ptr) |
| Insert a given node with a key in the tree.
|
|
static rbtree_node_type * | rbtree_delete_node (rbtree_node_type **rootptr_ptr, rbtree_node_type *node_ptr) |
| Delete a given node from the tree.
|
|
Intrusive red-black tree.
Keys are sorted in the following manner:
Duplicates are allowed with a macro. Then the keys are sorted in this manner:
Note allowing duplicates this way incurs performance penalties as the number of duplicates increase. For supporting duplicate keys efficiently, you can store a counter for each node, and count up when a node key already exists. Or use a list.
The memory of the nodes are expected to managed seperately.
Inspired by:
Sources used:
◆ KEY_IS_STRICTLY_LESS
#define KEY_IS_STRICTLY_LESS |
( |
| a, |
|
|
| b ) |
Value:
Used to compare two keys. This must be manually defined before including this header file.
Is undefined once header is included.
Equality for two keys a and b is defined as:
!KEY_IS_STRICTLY_LESS(a,b) && !KEY_IS_STRICTLY_LESS(b,a)
- Return values
-
true | If key a is strictly less than b. |
false | If key a is greater than or equal to b. |
◆ KEY_TYPE
The key type. This must be manually defined before including this header file.
Is undefined once header is included.
◆ NAME
Prefix to red black tree types and operations. This must be manually defined before including this header file.
Is undefined after header is included.
◆ rbtree_node_entry
#define rbtree_node_entry |
( |
| ptr, |
|
|
| type, |
|
|
| member ) |
Value:
#define container_of(ptr, type, member)
Obtain a pointer to the struct that contains the member.
Definition container_of.h:34
Obtain a pointer to the struct that contains the rbtree node as a member.
- Parameters
-
[in] | ptr | Node pointer. |
[in] | type | Container type. |
[in] | member | Node member name. |
- Returns
- A pointer to the struct containing the node member.
◆ rbtree_contains_key()
static bool rbtree_contains_key |
( |
rbtree_node_type ** | rootptr_ptr, |
|
|
const KEY_TYPE | key ) |
|
inlinestatic |
Check if the tree contains a given key.
- Parameters
-
[in] | rootptr_ptr | A pointer to the pointer to the root node. |
[in] | key | The key |
- Returns
- Whether the tree contains the key.
◆ rbtree_delete_node()
static rbtree_node_type * rbtree_delete_node |
( |
rbtree_node_type ** | rootptr_ptr, |
|
|
rbtree_node_type * | node_ptr ) |
|
inlinestatic |
Delete a given node from the tree.
- Parameters
-
[in] | rootptr_ptr | A pointer to the pointer to the root node. |
[in] | node_ptr | The node pointer. |
- Returns
- Pointer to the deleted node reinitialized.
◆ rbtree_init()
static void rbtree_init |
( |
rbtree_node_type ** | rootptr_ptr | ) |
|
|
inlinestatic |
Initialize a red-black tree struct.
- Note
- This should be initialized with the address to a pointer to a node.
- Parameters
-
[in] | rootptr_ptr | A pointer to the pointer to the root node. |
◆ rbtree_insert_node()
static void rbtree_insert_node |
( |
rbtree_node_type ** | rootptr_ptr, |
|
|
rbtree_node_type * | node_ptr ) |
|
inlinestatic |
Insert a given node with a key in the tree.
- Parameters
-
[in] | rootptr_ptr | A pointer to the pointer to the root node. |
[in] | node_ptr | The node pointer. |
◆ rbtree_is_empty()
static bool rbtree_is_empty |
( |
rbtree_node_type ** | rootptr_ptr | ) |
|
|
inlinestatic |
Check if the tree is empty.
- Parameters
-
[in] | rootptr_ptr | A pointer to the pointer to the root node. |
- Returns
- Whether the tree is empty.
◆ rbtree_node_get_parent_ptr()
static rbtree_node_type * rbtree_node_get_parent_ptr |
( |
rbtree_node_type * | node_ptr | ) |
|
|
inlinestatic |
Extract the parent pointer of a node.
- Parameters
-
[in] | node_ptr | The node pointer. |
◆ rbtree_node_init()
static void rbtree_node_init |
( |
rbtree_node_type * | node_ptr, |
|
|
KEY_TYPE | key ) |
|
inlinestatic |
Initialize a red-black tree node.
- Parameters
-
[in] | node_ptr | The node pointer. |
[in] | key | The key to initialize the node with. |
◆ rbtree_node_is_black()
static bool rbtree_node_is_black |
( |
const rbtree_node_type * | node_ptr | ) |
|
|
inlinestatic |
Check if the given node is colored black.
- Parameters
-
[in] | node_ptr | The node pointer. |
◆ rbtree_node_is_red()
static bool rbtree_node_is_red |
( |
const rbtree_node_type * | node_ptr | ) |
|
|
inlinestatic |
Check if the given node is colored red.
- Parameters
-
[in] | node_ptr | The node pointer. |
◆ rbtree_search_node()
static rbtree_node_type * rbtree_search_node |
( |
rbtree_node_type ** | rootptr_ptr, |
|
|
const KEY_TYPE | key ) |
|
inlinestatic |
Search for a given node and return a pointer to the node.
- Parameters
-
[in] | rootptr_ptr | A pointer to the pointer to the root node. |
[in] | key | The key of the node being searched for. |
- Returns
- A pointer to the searched node
- Return values
-
NULL | If a node with the given key wasn't found. |