Intrusive red-black tree. More...

#include "container_of.h"
#include "paste.h"
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

Classes
struct	rbtree_node
	Generated red-black tree node struct type for a given `KEY_TYPE`. More...

Macros
#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.

Functions
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.

Detailed Description

Intrusive red-black tree.

Keys are sorted in the following manner:

left < key < right

Duplicates are allowed with a macro. Then the keys are sorted in this manner:

left <= key <= right

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:

https://github.com/torvalds/linux/blob/master/include/linux/rbtree.h

Sources used:

Macro Definition Documentation

◆ KEY_IS_STRICTLY_LESS

#define KEY_IS_STRICTLY_LESS	(		a,
			b )

Value:

((a) < (b))

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

#define KEY_TYPE int

The key type. This must be manually defined before including this header file.

Is undefined once header is included.

◆ NAME

#define NAME rbtree

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:

container_of(ptr, type, member)

container_of

#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.

Function Documentation

◆ 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.

Classes

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ KEY_IS_STRICTLY_LESS

◆ KEY_TYPE

◆ NAME

◆ rbtree_node_entry

Function Documentation

◆ rbtree_contains_key()

◆ rbtree_delete_node()

◆ rbtree_init()

◆ rbtree_insert_node()

◆ rbtree_is_empty()

◆ rbtree_node_get_parent_ptr()

◆ rbtree_node_init()

◆ rbtree_node_is_black()

◆ rbtree_node_is_red()

◆ rbtree_search_node()