rbtree_template.h File Reference

Intrusive red-black tree. More...

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

Go to the source code of this file.

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

Macros
#define	PASTE(a, b)
	Paste two tokens together.
#define	XPASTE(a, b)
	First expand tokens, then paste them together.
#define	JOIN(a, b)
	First expand tokens, then paste them together with a _ in between.
#define	FUNCTION_DEFINITIONS
	Define the functions.
#define	TYPE_DEFINITIONS
	Define the types.
#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.
#define	FUNCTION_LINKAGE
	Specify function linkage e.g. static inline.

Functions
void	rbtree_init (rbtree_node_type **rootptr_ptr)
	Initialize a red-black tree struct.
void	rbtree_node_init (rbtree_node_type *node_ptr, KEY_TYPE key)
	Initialize a red-black tree node.
rbtree_node_type *	rbtree_node_get_parent_ptr (rbtree_node_type *node_ptr)
	Extract the parent pointer of a node.
bool	rbtree_node_is_black (const rbtree_node_type *node_ptr)
	Check if the given node is colored black.
bool	rbtree_node_is_red (const rbtree_node_type *node_ptr)
	Check if the given node is colored red.
bool	rbtree_is_empty (rbtree_node_type **rootptr_ptr)
	Check if the tree is empty.
bool	rbtree_contains_key (rbtree_node_type **rootptr_ptr, const KEY_TYPE key)
	Check if the tree contains a given key.
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.
void	rbtree_insert_node (rbtree_node_type **rootptr_ptr, rbtree_node_type *node_ptr)
	Insert a given node with a key in the tree.
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:

• https://en.wikipedia.org/wiki/Binary_search_tree#Operations
• https://en.wikipedia.org/wiki/Red-black_tree#Operations
• CLRS

Macro Definition Documentation

JOIN

#define JOIN	(		a,
			b )

Value:

XPASTE(a, XPASTE(_, b))

First expand tokens, then paste them together with a _ in between.

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.

PASTE

#define PASTE	(		a,
			b )

Value:

a##b

Paste two tokens together.

XPASTE

#define XPASTE	(		a,
			b )

Value:

PASTE(a, b)

First expand tokens, then paste them together.

Function Documentation

rbtree_contains_key()

bool rbtree_contains_key	(	rbtree_node_type **	rootptr_ptr,
		const KEY_TYPE	key )

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.

Examples

rbtree_example.c.

rbtree_delete_node()

rbtree_node_type * rbtree_delete_node	(	rbtree_node_type **	rootptr_ptr,
		rbtree_node_type *	node_ptr )

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.

Examples

rbtree_example.c.

rbtree_init()

void rbtree_init

(

rbtree_node_type **

rootptr_ptr

)

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.

Examples

rbtree_example.c.

rbtree_insert_node()

void rbtree_insert_node	(	rbtree_node_type **	rootptr_ptr,
		rbtree_node_type *	node_ptr )

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.

Examples

rbtree_example.c.

rbtree_is_empty()

bool rbtree_is_empty

(

rbtree_node_type **

rootptr_ptr

)

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.

Examples

rbtree_example.c.

rbtree_node_get_parent_ptr()

rbtree_node_type * rbtree_node_get_parent_ptr

(

rbtree_node_type *

node_ptr

)

Extract the parent pointer of a node.

Parameters

[in]

node_ptr

The node pointer.

rbtree_node_init()

void rbtree_node_init	(	rbtree_node_type *	node_ptr,
		KEY_TYPE	key )

Initialize a red-black tree node.

Parameters

[in]	node_ptr	The node pointer.
[in]	key	The key to initialize the node with.

Examples

rbtree_example.c.

rbtree_node_is_black()

bool rbtree_node_is_black

(

const rbtree_node_type *

node_ptr

)

Check if the given node is colored black.

Parameters

[in]

node_ptr

The node pointer.

rbtree_node_is_red()

bool rbtree_node_is_red

(

const rbtree_node_type *

node_ptr

)

Check if the given node is colored red.

Parameters

[in]

node_ptr

The node pointer.

rbtree_search_node()

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.

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.

Examples

rbtree_example.c.