A generally useful Red-Black binary tree implementation. More...

#include "hqtypes.h"

Typedefs
typedef struct rbt_root	RBT_ROOT
	The root reference to a Red-Black binary tree.

typedef struct rbt_node	RBT_NODE
	An internal node of a Red-Black binary tree.

typedef int32(*	rbt_compare_keys_fn) (RBT_ROOT *root, uintptr_t key1, uintptr_t key2)
	Function type for comparing keys in a red-black tree. More...

typedef void (	rbt_alloc_fn) (size_t size, void *data)
	Function type for Red-Black tree code to call when it wants to allocate memory. More...

typedef void(*	rbt_free_fn) (void what, size_t size, void data)
	Function type for Red-Black tree code to call when it wants to free memory. More...

typedef HqBool(*	rbt_callback_fn) (RBT_ROOT root, RBT_NODE node, void *walk_data)
	Callback for walking trees - called once per node. More...

Functions
int32	rbt_compare_integer_keys (RBT_ROOT *root, uintptr_t key1, uintptr_t key2)
	Implementation of rbt_compare_keys_fn that compares key1 and key2 as unsigned integers. More...

int32	rbt_compare_string_keys (RBT_ROOT *root, uintptr_t key1, uintptr_t key2)
	Implementation of rbt_compare_keys_fn that compares key1 and key2 as zero-terminated strings. More...

int32	rbt_compare_binary_keys (RBT_ROOT *root, uintptr_t key1, uintptr_t key2)

void	rbt_free_node (RBT_ROOT root, RBT_NODE node)
	Free a node allocated for a Red-Black tree, but not currently attached to the tree structure. More...

RBT_NODE *	rbt_allocate_node (RBT_ROOT root, uintptr_t key, void data)
	Allocate a node for a Red-Black tree, but do not attach it to the tree structure. More...

RBT_NODE *	rbt_root_node (RBT_ROOT *root)
	Accessor for the root node of a Red-Black tree. More...

uintptr_t	rbt_get_node_key (RBT_NODE *node)
	Return a pointer to the key for a node. More...

void	rbt_set_node_key (RBT_ROOT root, RBT_NODE node, uintptr_t key)
	Setter function for the key of a node. More...

void *	rbt_get_node_data (RBT_NODE *node)
	Accessor for the private data pointer attached to a node. More...

void	rbt_set_node_data (RBT_ROOT root, RBT_NODE node, void *data)
	Setter function for the private data attached to a node. More...

RBT_ROOT *	rbt_init (void *data, rbt_alloc_fn alloc_fn, rbt_free_fn free_fn, rbt_compare_keys_fn compare_keys, size_t key_length, size_t node_data_size)
	Initialise a new Red-Black tree. More...

void *	rbt_get_root_data (RBT_ROOT *root)
	Accessor for the private data from the root. More...

void	rbt_dispose (RBT_ROOT *root)
	Dispose of an entire Red-Black tree, freeing all nodes, keys, and data. More...

void	rbt_insert (RBT_ROOT root, RBT_NODE x)
	Red-Black binary tree Insert method. More...

RBT_NODE *	rbt_remove (RBT_ROOT root, RBT_NODE z)
	Red-Black binary tree remove method (called "delete" in the reference algorithms, but renamed to make it clear that this operation does not free the node structure). More...

RBT_NODE *	rbt_search (RBT_ROOT *root, uintptr_t key)
	Search for a node in a Red-Black tree. More...

RBT_NODE *	rbt_minimum (RBT_ROOT root, RBT_NODE x)
	Find the node with the minimum key value at or below a given node in a Red-Black tree. More...

RBT_NODE *	rbt_maximum (RBT_ROOT root, RBT_NODE x)
	Find the node with the maximum key value at or below a given node in a Red-Black tree. More...

RBT_NODE *	rbt_successor (RBT_ROOT root, RBT_NODE x)
	Return the succeeding node in a Red-Black tree. More...

RBT_NODE *	rbt_predecessor (RBT_ROOT root, RBT_NODE x)
	Return the preceding node in a Red-Black tree. More...

HqBool	rbt_is_empty (RBT_ROOT *root)
	Predicate to determine if a Red-Black tree is empty. More...

uint32	rbt_node_count (RBT_ROOT *root)
	Count the number of nodes in a Red-Black tree. More...

HqBool	rbt_walk (RBT_ROOT root, rbt_callback_fn callback, void walk_data)
	Walk each element of the tree in turn, calling a callback function for each node. More...

RBT_NODE *	rbtsimple_create_node (RBT_ROOT *root, uintptr_t key)
	Make sure there's a node in the tree with the given key. More...

Detailed Description

A generally useful Red-Black binary tree implementation.

Copyright (C) 2023 Global Graphics Software Ltd. All rights reserved. This source code contains the confidential and trade secret information of Global Graphics Software Ltd. It may not be used, copied or distributed for any reason except as set forth in the applicable Global Graphics license agreement.

Typedef Documentation

◆ rbt_alloc_fn

typedef void*(* rbt_alloc_fn) (size_t size, void *data)

Function type for Red-Black tree code to call when it wants to allocate memory.

Parameters

size	The number of bytes to allocate
data	The private opaque data pointer from the tree root.

Returns: A newly-allocated block of memory, or NULL if none is available.

◆ rbt_callback_fn

typedef HqBool( * rbt_callback_fn) ( RBT_ROOT *root, RBT_NODE *node, void *walk_data)

Callback for walking trees - called once per node.

Parameters

[in]	root	The root of the tree being walked.
[in]	node	The current node being visited.
	walk_data	The opaque pointer passed to rbt_walk().

Return values

TRUE	Continue with the tree walk.
FALSE	Abort the tree walk, ultimately returning FALSE from rbt_walk().

The callback function should not modify the tree.

◆ rbt_compare_keys_fn

typedef int32(* rbt_compare_keys_fn) ( RBT_ROOT *root, uintptr_t key1, uintptr_t key2)

Function type for comparing keys in a red-black tree.

Parameters

[in]	root	The root of the containing tree.
	key1	Opaque key type for a node in the tree.
	key2	Opaque key type for another node in the tree.

Returns: A negative value if key1 is less than key2, zero if key1 is equivalent to key2 and a positive value if key1 is greater than key2.

◆ rbt_free_fn

typedef void( * rbt_free_fn) ( void *what, size_t size, void *data)

Function type for Red-Black tree code to call when it wants to free memory.

Parameters

what	Pointer to a memory block previously allocated through the tree's rbt_alloc_fn.
size	The size of the memory block, as initially requested from the tree's rbt_alloc_fn.
data	The private opaque data pointer from the tree root.

Function Documentation

◆ rbt_allocate_node()

RBT_NODE* rbt_allocate_node	(	RBT_ROOT *	root,
		uintptr_t	key,
		void *	data
	)

Allocate a node for a Red-Black tree, but do not attach it to the tree structure.

Parameters

[in]	root	The root of the Red-Black tree.
	key	The key for the node. If the tree has a fixed key length, the key is interpreted as a pointer to a data block, which is copied into the node. If the tree does not have a fixed key length, the key is stored by reference.
	data	Node-specific data to set for this node.

Returns: A newly-allocated node, or NULL if any of the allocations failed.

The node is allocated with any additional data space required by the tree. before the data is stored in the node. If rbt_root::node_data_size is zero, the data pointer is stored directly into the node. If rbt_root::node_data_size is non-zero, the data is copied into storage pre-allocated in the node.

◆ rbt_compare_binary_keys()

int32 rbt_compare_binary_keys	(	RBT_ROOT *	root,
		uintptr_t	key1,
		uintptr_t	key2
	)

Implementation of rbt_compare_keys_fn that compares key1 and key2 as raw binary keys, using a fixed key length tree.

Parameters

[in]	root	The root of the containing tree.
	key1	Opaque key type for a node in the tree.
	key2	Opaque key type for another node in the tree.

Returns: A negative value if key1 is less than key2, zero if key1 is equivalent to key2 and a positive value if key1 is greater than key2.

◆ rbt_compare_integer_keys()

int32 rbt_compare_integer_keys	(	RBT_ROOT *	root,
		uintptr_t	key1,
		uintptr_t	key2
	)

Implementation of rbt_compare_keys_fn that compares key1 and key2 as unsigned integers.

Parameters

[in]	root	The root of the containing tree.
	key1	Opaque key type for a node in the tree.
	key2	Opaque key type for another node in the tree.

Returns: A negative value if key1 is less than key2, zero if key1 is equivalent to key2 and a positive value if key1 is greater than key2.

◆ rbt_compare_string_keys()

int32 rbt_compare_string_keys	(	RBT_ROOT *	root,
		uintptr_t	key1,
		uintptr_t	key2
	)

Implementation of rbt_compare_keys_fn that compares key1 and key2 as zero-terminated strings.

Parameters

[in]	root	The root of the containing tree.
	key1	Opaque key type for a node in the tree.
	key2	Opaque key type for another node in the tree.

Returns: A negative value if key1 is less than key2, zero if key1 is equivalent to key2 and a positive value if key1 is greater than key2.

◆ rbt_dispose()

void rbt_dispose ( RBT_ROOT * root )

Dispose of an entire Red-Black tree, freeing all nodes, keys, and data.

Parameters

root	The tree to dispose of. This may be NULL.

◆ rbt_free_node()

void rbt_free_node	(	RBT_ROOT *	root,
		RBT_NODE *	node
	)

Free a node allocated for a Red-Black tree, but not currently attached to the tree structure.

Parameters

[in]	root	The root of the Red-Black tree.
[in]	node	The node to free.

This is so that a caller can remove a node from the tree (rbt_remove() returns a pointer to the newly-removed node) and stuff new values in before calling rbt_insert() once more - all without the memory churn that would happen if allocations were tied to inserts and removals led always to frees.

◆ rbt_get_node_data()

void* rbt_get_node_data ( RBT_NODE * node )

Accessor for the private data pointer attached to a node.

Parameters

[in] node The node to get the private data for.

Returns: The private data pointer set by rbt_set_node_data() or rbt_allocate_node().

◆ rbt_get_node_key()

uintptr_t rbt_get_node_key ( RBT_NODE * node )

Return a pointer to the key for a node.

Parameters

[in] node The node to return the key for.

Returns: The key stored in the node. If the tree has a fixed key length, this is a pointer to storage where the key is copied. If the tree does not have a fixed key length, this is the original key reference stored for the node.

◆ rbt_get_root_data()

void* rbt_get_root_data ( RBT_ROOT * root )

Accessor for the private data from the root.

Parameters

[in] root The tree root.

Returns: The opaque data pointer passed to rbt_init().

◆ rbt_init()

RBT_ROOT* rbt_init	(	void *	data,
		rbt_alloc_fn	alloc_fn,
		rbt_free_fn	free_fn,
		rbt_compare_keys_fn	compare_keys,
		size_t	key_length,
		size_t	node_data_size
	)

Initialise a new Red-Black tree.

Parameters

data	An opaque data pointer passed to the callback functions.
alloc_fn	A callback function to allocate memory for the tree nodes, keys, and data.
free_fn	A callback function to free memory for the tree nodes, keys, and data.
compare_keys	A callback function to compare keys.
key_length	The size of the node keys. If this is zero, keys are stored by reference (and therefore if keys are pointers to objects, they must have lifetimes at least as long as the nodes they are used for are stored in the tree). If non-zero, keys will be copied into storage allocated in the tree nodes.
node_data_size	The size of the node data. If this is zero, node data is stored by reference (and therefore if the data is a pointer to an object, it must have a lifetime at least as long as the nodes it's used for are stored in the tree). If non-zero, node data will be copied into storage allocated in the tree nodes.

Returns: A new tree root, or NULL if the allocations failed.

◆ rbt_insert()

void rbt_insert	(	RBT_ROOT *	root,
		RBT_NODE *	x
	)

Red-Black binary tree Insert method.

Parameters

root	The root of the Red-Black tree.
x	A node to insert in the tree, previously allocated by rbt_allocate_node() and not currently inserted in the tree.

This is an ordinary insert followed by a process which re-balances the tree, making sure the rules for red-black binary trees hold once the balancing is done.

Only x->key needs to be initialised on entry. The node data can be updated after insertion, but the node key must be set before insertion, and must not be changed after insertion.

◆ rbt_is_empty()

HqBool rbt_is_empty ( RBT_ROOT * root )

Predicate to determine if a Red-Black tree is empty.

Parameters

[in] root The root of the Red-Black tree.

Return values

TRUE	if the tree is empty;
FALSE	if the tree has stored nodes.

◆ rbt_maximum()

RBT_NODE* rbt_maximum	(	RBT_ROOT *	root,
		RBT_NODE *	x
	)

Find the node with the maximum key value at or below a given node in a Red-Black tree.

Parameters

[in]	root	The root of the Red-Black tree.
[in]	x	The node to get the maximum below. This should be the root node if no sub-tree node is provided.

Returns: The node with the maximum key at or below node x.

◆ rbt_minimum()

RBT_NODE* rbt_minimum	(	RBT_ROOT *	root,
		RBT_NODE *	x
	)

Find the node with the minimum key value at or below a given node in a Red-Black tree.

Parameters

[in]	root	The root of the Red-Black tree.
[in]	x	The node to get the minimum below. This should be the root node if no sub-tree node is provided.

Returns: The node with the minimum key at or below node x.

◆ rbt_node_count()

uint32 rbt_node_count ( RBT_ROOT * root )

Count the number of nodes in a Red-Black tree.

Parameters

[in] root The root of the Red-Black tree.

Returns: The number of nodes stored in the Red-Black tree.

◆ rbt_predecessor()

RBT_NODE* rbt_predecessor	(	RBT_ROOT *	root,
		RBT_NODE *	x
	)

Return the preceding node in a Red-Black tree.

Parameters

[in]	root	The root of the Red-Black tree.
[in]	x	The node to get the predecessor for.

Returns: The node before of x in the tree, according to the key sort order, or NULL if there are no predecessors.

◆ rbt_remove()

RBT_NODE* rbt_remove	(	RBT_ROOT *	root,
		RBT_NODE *	z
	)

Red-Black binary tree remove method (called "delete" in the reference algorithms, but renamed to make it clear that this operation does not free the node structure).

Does an ordinary binary tree delete, then balances the tree back up if necessary so it complies with The Rules. Returns the node ready for its memory to be freed if appropriate: it's important to realise that this might not be the location of the node which was passed in. Note that "x->p = y->p" can, by design, end up modifying the sentinel node.

Only z->key needs to be initialised on entry.

Parameters

root	The Red-Black tree to remove a node from.
z	The node to remove.

Returns: The removed node. This must either be freed with rbt_free_node(), or (possibly) modified and re-inserted using rbt_insert().

◆ rbt_root_node()

RBT_NODE* rbt_root_node ( RBT_ROOT * root )

Accessor for the root node of a Red-Black tree.

Parameters

[in] root The tree root.

Returns: The root node, or NULL if nothing has been added to the tree.

◆ rbt_search()

RBT_NODE* rbt_search	(	RBT_ROOT *	root,
		uintptr_t	key
	)

Search for a node in a Red-Black tree.

Parameters

[in]	root	The root of the Red-Black tree.
[in]	key	The key to search for.

Returns: A node with a matching key in the tree.

◆ rbt_set_node_data()

void rbt_set_node_data	(	RBT_ROOT *	root,
		RBT_NODE *	node,
		void *	data
	)

Setter function for the private data attached to a node.

Parameters

[in]	root	The tree root containing node.
	node	The node to set the private data for.
	data	A pointer to the private data.

Copies by reference or by value depending on the value of the tree's node data size. If RBT_ROOT::node_data_size is zero, the data pointer is stored directly into the node. If RBT_ROOT::node_data_size is non-zero, the data is copied into storage pre-allocated in the node.

◆ rbt_set_node_key()

void rbt_set_node_key	(	RBT_ROOT *	root,
		RBT_NODE *	node,
		uintptr_t	key
	)

Setter function for the key of a node.

Parameters

[in]	root	The root of the tree for which the node was allocated.
	node	The node to set key for.
	key	The key to set on node.

This function copies by reference or by value depending on the value of key_length in the tree root.

Note: This will corrupt the tree if the node is already inserted, but it could be used to change the key of a node which has been removed and is about to be reinserted.

◆ rbt_successor()

RBT_NODE* rbt_successor	(	RBT_ROOT *	root,
		RBT_NODE *	x
	)

Return the succeeding node in a Red-Black tree.

Parameters

[in]	root	The root of the Red-Black tree.
[in]	x	The node to get the successor for.

Returns: The node after of x in the tree, according to the key sort order, or NULL if there are no successors.

◆ rbt_walk()

HqBool rbt_walk	(	RBT_ROOT *	root,
		rbt_callback_fn	callback,
		void *	walk_data
	)

Walk each element of the tree in turn, calling a callback function for each node.

If is not safe for the callback to alter the structure of the tree, but it is OK if we're freeing the whole tree at once. This is the fastest way to enumerate every node, but nodes will be walked in an undefined order.

Parameters

root	The Red-Black tree to walk.
callback	A callback function to call for each node in the tree.
walk_data	An opaque pointer passed through to the callback function.

Return values

TRUE	If all of the callback functions returned TRUE.
FALSE	If any of the callback functions returned FALSE.

◆ rbtsimple_create_node()

RBT_NODE* rbtsimple_create_node	(	RBT_ROOT *	root,
		uintptr_t	key
	)

Make sure there's a node in the tree with the given key.

Simple Red-Black trees come in handy sometimes: they are defined as trees whose only data are the keys themselves. This function ensures that a key is in the tree, and returns the node for it.

Parameters

root	The root of a simple Red-Black tree.
key	A key to find and/or add to the tree.

Returns: The node corresponding to key, or NULL if it did not exist and could not be added.

Typedefs

Functions

Detailed Description

Typedef Documentation

◆ rbt_alloc_fn

◆ rbt_callback_fn

◆ rbt_compare_keys_fn

◆ rbt_free_fn

Function Documentation

◆ rbt_allocate_node()

◆ rbt_compare_binary_keys()

◆ rbt_compare_integer_keys()

◆ rbt_compare_string_keys()

◆ rbt_dispose()

◆ rbt_free_node()

◆ rbt_get_node_data()

◆ rbt_get_node_key()

◆ rbt_get_root_data()

◆ rbt_init()

◆ rbt_insert()

◆ rbt_is_empty()

◆ rbt_maximum()

◆ rbt_minimum()

◆ rbt_node_count()

◆ rbt_predecessor()

◆ rbt_remove()

◆ rbt_root_node()

◆ rbt_search()

◆ rbt_set_node_data()

◆ rbt_set_node_key()

◆ rbt_successor()

◆ rbt_walk()

◆ rbtsimple_create_node()