#include <errno.h>
#include <limits.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include "common.h"
#include "debug.h"
#include "key.h"

Include dependency graph for node.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	_RBT_NODE_TRAVERSE_WITH_KEY_STACK_T
	Linked list for implementing RBT_NODE_TRAVERSE_WITH_KEY's dynamic stack. More...

struct	RBT_KEY_DATA_T
	Rabbit Tree key data type with associated node. More...

struct	RBT_NODE_STACK_T
	Linked list of nodes. More...

struct	RBT_NODE_T
	Rabbit Tree node type. More...

Macros
#define	RBT_NODE_CACHE_OR_FREE(node) free(node)

#define	RBT_VALUE_IS_NULL(value) RBT_VALUE_IS_EQUAL(value, RBT_VALUE_NULL)

Typedefs
typedef struct _RBT_NODE_TRAVERSE_WITH_KEY_STACK_T	_RBT_NODE_TRAVERSE_WITH_KEY_STACK_T
	Linked list for implementing RBT_NODE_TRAVERSE_WITH_KEY's dynamic stack. More...

typedef struct RBT_KEY_DATA_T	RBT_KEY_DATA_T
	Rabbit Tree key data type with associated node. More...

typedef int(*	RBT_NODE_FILTER_FUNCTION_T) (RBT_VALUE_T *value, va_list args)
	The function type accepted by `RBT_NODE_FILTER()`. More...

typedef int(*	RBT_NODE_FILTER_WITH_KEY_FUNCTION_T) (RBT_KEY_DATA_T *key_data, va_list args)
	The function type accepted by `RBT_NODE_FILTER_WITH_KEY()`. More...

typedef struct RBT_NODE_STACK_T	RBT_NODE_STACK_T
	Linked list of nodes. More...

typedef struct RBT_NODE_T	RBT_NODE_T
	Rabbit Tree node type.

typedef int(*	RBT_NODE_TRAVERSE_FUNCTION_T) (RBT_NODE_T *node, RBT_KEY_SIZE_T height, va_list args)
	A tree traversal function. More...

typedef int(*	RBT_NODE_TRAVERSE_WITH_KEY_FUNCTION_T) (RBT_KEY_DATA_T *key_data, RBT_KEY_SIZE_T height, va_list args)
	A tree traversal function. More...

typedef RBT_VALUE_T	RBT_VALUE_T
	The node's value type.

Functions
RBT_NODE_T *	RBT_NODE_COPY (RBT_NODE_T *node)
	Copy a tree. More...

RBT_KEY_SIZE_T	RBT_NODE_COUNT (RBT_NODE_T *node)

RBT_NODE_T *	RBT_NODE_CREATE (RBT_PIN_T key, RBT_KEY_SIZE_T bits, RBT_VALUE_T value, RBT_NODE_T left, RBT_NODE_T *right)
	Create a node. More...

void	RBT_NODE_FILTER (RBT_NODE_T *node, RBT_NODE_FILTER_FUNCTION_T func_v, int include_empty,...)
	Filter tree nodes. More...

void	RBT_NODE_FPRINT (FILE fd, RBT_NODE_T node, int print_bits, int print_pointer)
	Print trees using box-drawing characters. More...

void	RBT_NODE_FPRINT_INTERNAL (FILE fd, RBT_NODE_T node, int print_bits, int print_pointer, RBT_KEY_SIZE_T indent, RBT_KEY_SIZE_T vert, int is_last_child, int skip)

void	RBT_NODE_FREE (RBT_NODE_T *node)

void	RBT_NODE_INSERT_CHILD (RBT_NODE_T *child_node_ptr, RBT_PIN_T key, RBT_KEY_SIZE_T bits, RBT_VALUE_T value)
	Insert a child node. More...

void	RBT_NODE_INSERT_PARENT (RBT_NODE_T *node, RBT_KEY_SIZE_T bits, RBT_VALUE_T value)
	Insert a parent node. More...

RBT_NODE_T *	RBT_NODE_INSERT_SIBLING (RBT_NODE_T node, RBT_PIN_T key, RBT_KEY_SIZE_T bits, RBT_KEY_SIZE_T common_bits, RBT_KEY_SIZE_T common_pins, RBT_KEY_SIZE_T common_staggered_bits, RBT_VALUE_T value)
	Insert a sibling node. More...

int	RBT_NODE_IS_COPY (RBT_NODE_T a, RBT_NODE_T b)
	Check if a tree is a copy. More...

void	RBT_NODE_MERGE_CHILD (RBT_NODE_T parent_node, RBT_NODE_T child_node)

RBT_NODE_T *	RBT_NODE_NEW ()
	Create a new tree. More...

RBT_VALUE_T	RBT_NODE_QUERY (RBT_NODE_T root_node, RBT_PIN_T key, RBT_KEY_SIZE_T bits, rbt_query_action_t action, RBT_VALUE_T value)
	Query a tree. More...

RBT_NODE_T *	RBT_NODE_REMOVE (RBT_NODE_T node, RBT_NODE_T parent_node)
	Remove a node from a tree. More...

RBT_NODE_T *	RBT_NODE_RETRIEVE (RBT_NODE_T node, RBT_PIN_T key, RBT_KEY_SIZE_T bits, rbt_retrieve_action_t action, RBT_VALUE_T value, RBT_NODE_T **parent_node_ptr)
	Retrieve a node matching the given key. More...

void	RBT_NODE_TRAVERSE (RBT_NODE_T *node, RBT_NODE_TRAVERSE_FUNCTION_T func_v,...)

int	RBT_NODE_WITH_PREFIX_SUBTREE_DO (RBT_NODE_T node, RBT_PIN_T key, RBT_KEY_SIZE_T bits, void(func_v)(RBT_NODE_T subtree, va_list args),...)
	Perform some action on the subtree defined by a common prefix. More...

Detailed Description

Author: Xyne

Copyright: GPL2 only

Required Headers

key.h

Required Macro Definitions:

RBT_NODE_H_PREFIX_

The prefix for visible variable and function declarations in this header.
RBT_VALUE_T

The type of the value held by each node in the tree.
RBT_VALUE_NULL

The "null" value. A node containing this value is considered empty. Empty leaf nodes are removed from the tree.
RBT_VALUE_IS_EQUAL(a, b)

A macro function that should evaluate to "true" if and only if the arguments a and b of type RBT_VALUE_T are considered equal. This must also handle RBT_VALUE_NULL arguments. It will be used to define an additional macro: RBT_VALUE_IS_NULL(x).
RBT_VALUE_COPY(a, b, fail)

Copy the value "b" to the variable "a". If the copy operation fails, run "fail". For statically allocated values, a = b will suffice. For dynamically allocated values, 4 cases must be handled, with proper allocation and freeing:
- both a and b are RBT_VALUE_NULL
- a is RBT_VALUE_NULL, b is not
- b is RBT_VALUE_NULL, a is not
- neither a nor b is RBT_VALUE_NULL
RBT_VALUE_FREE(val)

Free any dynamically allocated memory associated with the given value.
RBT_VALUE_FPRINT(fd, val)

Print a representation of the value to the given file descriptor. This should not print anything for the null value.

Optional Macro Definitions

RBT_NODE_CACHE_SIZE

An unsigned integer value. If set, a cache of previously allocated nodes will be kept for re-use to avoid redundant memory allocation requests. RBT_NODE_CREATE() will check the cache before allocating new memory and RBT_NODE_FREE() will return nodes to the cache instead of freeing them.

If the value is a positive then the number of nodes in the cache will be limited to this number. If it is zero, they will not.

Setting this value will also define the following:
- RBT_NODE_CACHE_T
  
  A typedef'd struct type to track the nodes in the cache.
- RBT_NODE_CACHE
  
  The global cache of type RBT_NODE_CACHE_T.
- RBT_NODE_CACHE_FREE
  
  A function to free all of the nodes in the cache. This should be called when no more nodes will be required and before the program exits.
This should be used when working with dynamic tree structures.
RBT_CONCURRENCY_PTHREAD

Define this macro to include concurrency/node_pthread.h

Examples

Statically allocated string values.

Note that RBT_VALUE_COPY does not use the "fail" statement because it is a simple assignment and cannot fail. RBT_VALUE_FREE does nothing because there is no dynamically allocated memory to free.

#define RBT_VALUE_T char *
#define RBT_VALUE_NULL NULL
#define RBT_VALUE_IS_EQUAL(a, b) \
( \
  ((a == NULL) == (b == NULL)) && \
  (a == NULL || ! strcmp(a,b)) \
)
#define RBT_VALUE_COPY(a, b, fail) a = b
#define RBT_VALUE_FREE(val)
#define RBT_VALUE_FPRINT(fd, val) \
do \
{ \
  if (val != NULL) \
  { \
    fprintf(fd, "%s", val); \
  } \
} while(0)

Dynamically allocated string values.

Each node will hold its own copy of the string in allocated memory. The memory will be managed automatically when working with the tree.

#define RBT_VALUE_T char *
#define RBT_VALUE_NULL NULL
#define RBT_VALUE_IS_EQUAL(a, b) \
( \
  ((a == NULL) == (b == NULL)) && \
  (a == NULL || ! strcmp(a,b)) \
)
#define RBT_VALUE_COPY(a, b, fail) \
do \
{ \
  free(a); \
  a = malloc(strlen(b) + 1); \
  if (a == NULL || strcpy(a, b) == NULL) \
  { \
    fail; \
  } \
}
while (0)
#define RBT_VALUE_FREE(val) free(val)
#define RBT_VALUE_FPRINT(fd, val) \
do \
{ \
  if (val != NULL) \
  { \
    fprintf(fd, "%s", val); \
  } \
} while(0)

Macro Definition Documentation

◆ RBT_NODE_CACHE_OR_FREE

#define RBT_NODE_CACHE_OR_FREE ( node ) free(node)

A conditional macro that either caches nodes or frees them depending on the value of RBT_NODE_CACHE_SIZE. It is used internally by RBT_NODE_FREE().

The displayed definition is for the non-caching variant.

◆ RBT_VALUE_IS_NULL

#define RBT_VALUE_IS_NULL ( value ) RBT_VALUE_IS_EQUAL(value, RBT_VALUE_NULL)

An expression that should evaluate to a non-zero int if the given value is equivalent to RBT_VALUE_NULL.

Parameters

[in] value The value to evaluate.

Typedef Documentation

◆ _RBT_NODE_TRAVERSE_WITH_KEY_STACK_T

typedef struct _RBT_NODE_TRAVERSE_WITH_KEY_STACK_T _RBT_NODE_TRAVERSE_WITH_KEY_STACK_T

Linked list for implementing RBT_NODE_TRAVERSE_WITH_KEY's dynamic stack.

Warning: This is an internal structure.

◆ RBT_KEY_DATA_T

typedef struct RBT_KEY_DATA_T RBT_KEY_DATA_T

Rabbit Tree key data type with associated node.

This is intended for use in tree traversal functions that require the full associated keys.

◆ RBT_NODE_FILTER_FUNCTION_T

typedef int(* RBT_NODE_FILTER_FUNCTION_T) (RBT_VALUE_T *value, va_list args)

The function type accepted by RBT_NODE_FILTER().

Parameters

[in]	value	A pointer to the current node's value.
[in]	args	A `va_list` containing the additional arguments passed to `RBT_NODE_FILTER()`.

Returns: An int. If it is non-zero, the current node will be removed.

◆ RBT_NODE_FILTER_WITH_KEY_FUNCTION_T

typedef int(* RBT_NODE_FILTER_WITH_KEY_FUNCTION_T) (RBT_KEY_DATA_T *key_data, va_list args)

The function type accepted by RBT_NODE_FILTER_WITH_KEY().

Parameters

[in]	key_data	The full key associated with the node. This must not be modified by the function.
[in]	args	A `va_list` containing the additional arguments passed to `RBT_NODE_FILTER()`.

Returns: An int. If it is non-zero, the current node will be removed.

◆ RBT_NODE_STACK_T

typedef struct RBT_NODE_STACK_T RBT_NODE_STACK_T

Linked list of nodes.

A unidirectional linked list used for implementing dynamic stacks of nodes for e.g. tracking parent nodes when traversing a tree.

◆ RBT_NODE_TRAVERSE_FUNCTION_T

typedef int(* RBT_NODE_TRAVERSE_FUNCTION_T) (RBT_NODE_T *node, RBT_KEY_SIZE_T height, va_list args)

A tree traversal function.

The type of function called by RBT_NODE_TRAVERSE() for each node as the tree is traversed.

The returned value can be used to stop traversal.

Parameters

[in]	node	The current node.
[in]	height	The height of the current node above the root node (or the depth if you view the root node as being at the top).
[in]	args	A `va_list` containing the additional arguments passed to `RBT_NODE_TRAVERSE()`.

Returns: An int that will stop traversal if non-zero.

◆ RBT_NODE_TRAVERSE_WITH_KEY_FUNCTION_T

typedef int(* RBT_NODE_TRAVERSE_WITH_KEY_FUNCTION_T) (RBT_KEY_DATA_T *key_data, RBT_KEY_SIZE_T height, va_list args)

A tree traversal function.

The type of function called by RBT_NODE_TRAVERSE_WITH_KEY() for each node as the tree is traversed.

The returned value can be used to stop traversal.

Parameters

[in]	key_data	The full key associated with the node. This must not be modified by the function.
[in]	height	The height of the current node above the root node (or the depth if you view the root node as being at the top).
[in]	args	A `va_list` containing the additional arguments passed to `RBT_NODE_TRAVERSE_WITH_KEY()`.

Returns: An int that will stop traversal if non-zero.

Function Documentation

◆ RBT_NODE_COPY()

RBT_NODE_T * RBT_NODE_COPY ( RBT_NODE_T * node )

Copy a tree.

Create a node-by-node copy of a tree given the root node.

Warning: If the values held by the tree are pointers then the data referenced by the copy will obviously be the same as the data referenced by the original and the two will not be independent. If, however, the data itself is held by the node then the copy will be completely independent.

Parameters

[in] node The root node of the original tree to copy.

Returns: A pointer to the root node of the copy.

◆ RBT_NODE_COUNT()

RBT_KEY_SIZE_T RBT_NODE_COUNT ( RBT_NODE_T * node )

Count the number of values in the tree.

Parameters

[in] node The root node.

◆ RBT_NODE_CREATE()

RBT_NODE_T * RBT_NODE_CREATE	(	RBT_PIN_T *	key,
		RBT_KEY_SIZE_T	bits,
		RBT_VALUE_T	value,
		RBT_NODE_T *	left,
		RBT_NODE_T *	right
	)

Create a node.

Create a node to hold the given key fragment and insert the given value. The memory is dynamically allocated and should be freed with RBT_NODE_FREE() when no longer needed.

If RBT_NODE_CACHE_SIZE is defined, a previously allocated node will be taken from the cache if available instead of allocating a new block of memory.

Attention: The value of errno should be checked for errors when this function returns.

Parameters

[in]	key	A pointer to the key fragment.
[in]	bits	The number of bits in the key fragment.
[in]	value	The value to insert.
[in]	left	The left child. The first new bit in this child will be 0.
[in]	right	The right child. The first new bit in this child will be 1.

Returns: A pointer to the new node, or NULL if an error occured.

◆ RBT_NODE_FILTER()

void RBT_NODE_FILTER	(	RBT_NODE_T *	node,
		RBT_NODE_FILTER_FUNCTION_T	func_v,
		int	include_empty,
			...
	)

Filter tree nodes.

Remove nodes for which the supplied function returns a non-zero int. The function is passed a pointer to the value instead of the value itself so that it can also modify it if necessary.

Attention: The value of errno should be checked for errors when this function returns.

Warning: See the warning for RBT_NODE_RETRIEVE() about directly inserting RBT_VALUE_NULL values.

Parameters

[in]	node	The root node.
[in]	func_v	A function of type `RBT_NODE_FILTER_FUNCTION_T` for filtering nodes by value.
[in]	include_empty	Pass empty nodes to the function.
[in]	...	Additional arguments to pass to `func_v`. They will be passed in a `va_list`, which will be re-initialized before each call.

See also

RBT_NODE_FILTER_FUNCTION_T

◆ RBT_NODE_FPRINT()

void RBT_NODE_FPRINT	(	FILE *	fd,
		RBT_NODE_T *	node,
		int	print_bits,
		int	print_pointer
	)

Print trees using box-drawing characters.

A function for printing representations of trees using box-drawing characters. This function is mostly for debugging purposes. It will visualize the tree hierarchy and optionally show the pointers of each node along with the key bits that they contain.

Attention: The value of errno should be checked for errors when this function returns.

Parameters

[in]	fd	The output file descriptor.
[in]	node	A pointer to the target root node.
[in]	print_bits	A boolean value to determine if the key bits of each node should be printed. If false, the character '●' will be printed instead.
[in]	print_pointer	A value indicating if the pointer should be printed. If non-zero, the value will be used as the width of the pointer in the call to fprintf.

◆ RBT_NODE_FPRINT_INTERNAL()

void RBT_NODE_FPRINT_INTERNAL	(	FILE *	fd,
		RBT_NODE_T *	node,
		int	print_bits,
		int	print_pointer,
		RBT_KEY_SIZE_T	indent,
		RBT_KEY_SIZE_T	vert,
		int	is_last_child,
		int	skip
	)

The internal function used by RBT_NODE_FPRINT() for printing trees using box-drawing characters.

Attention: The value of errno should be checked for errors when this function returns.

Parameters

[in]	fd	The output file descriptor.
[in]	node	A pointer to the target root node.
[in]	print_bits	A boolean value to determine if the key bits of each node should be printed. If false, the character '●' will be printed instead.
[in]	print_pointer	A value indicating if the pointer should be printed. If non-zero, the value will be used as the width of the pointer in the call to fprintf.
[in]	indent	The indentation level.
[in]	vert	A numerical value used to track vertical branches that should be printed to the left of the current node.
[in]	is_last_child	A boolean value indicating if the current node is the last child of its parent.
[in]	skip	The number of bits held by this node that should be skipped. These are the staggered bits of the parent node.

See also

RBT_NODE_FPRINT()

◆ RBT_NODE_FREE()

void RBT_NODE_FREE ( RBT_NODE_T * node )

Free the target node and all its descendents. If RBT_NODE_CACHE_SIZE is set then the nodes will be stored in the cache instead of being freed, if the cache is not full.

Parameters

[in] node The target node.

See also

RBT_NODE_CACHE_OR_FREE()

◆ RBT_NODE_INSERT_CHILD()

void RBT_NODE_INSERT_CHILD	(	RBT_NODE_T **	child_node_ptr,
		RBT_PIN_T *	key,
		RBT_KEY_SIZE_T	bits,
		RBT_VALUE_T	value
	)

Insert a child node.

Insert a child node to hold the given value.

Attention: The value of errno should be checked for errors when this function returns.

Parameters

[in]	child_node_ptr	The child node pointer of the parent node that should be set to point to this node.
[in]	key	The key fragment that should be held by this node.
[in]	bits	The number of bits in the key fragment.
[in]	value	The value to insert.

See also

◆ RBT_NODE_INSERT_PARENT()

void RBT_NODE_INSERT_PARENT	(	RBT_NODE_T *	node,
		RBT_KEY_SIZE_T	bits,
		RBT_VALUE_T	value
	)

Insert a parent node.

Insert a parent node above the given node to hold the given value. The key will be extracted from the beginning of the current key.

Attention: The value of errno should be checked for errors when this function returns.

Parameters

[in]	node	The current node.
[in]	bits	The number of key bits that will be made part of the parent node.
[in]	value	The value to insert.

See also

◆ RBT_NODE_INSERT_SIBLING()

RBT_NODE_T * RBT_NODE_INSERT_SIBLING	(	RBT_NODE_T *	node,
		RBT_PIN_T *	key,
		RBT_KEY_SIZE_T	bits,
		RBT_KEY_SIZE_T	common_bits,
		RBT_KEY_SIZE_T	common_pins,
		RBT_KEY_SIZE_T	common_staggered_bits,
		RBT_VALUE_T	value
	)

Insert a sibling node.

Insert a sibling node to hold the given value. The given node is made a placeholder parent and the current data in the node is moved to a new node that is inserted as a child of the parent. The new data is inserted into a second new node and made the second child of the parent.

Attention: The value of errno should be checked for errors when this function returns.

Parameters

[in]	node	The current node.
[in]	key	The key fragment that spans the current node and the target child node.
[in]	bits	The number of bits in the key fragment.
[in]	common_bits	The number of common bits between the current node's key fragment and the given key. These will form the key fragment of the new parent node.
[in]	common_pins	The number of common pins between the current node's key fragment and the given key.
[in]	common_staggered_bits	The number of uncommon bits in the current node's key fragment. These will form the key fragment of the sibling node.
[in]	value	The value to insert.

Returns: A pointer to the new node holding the value, or NULL if an error occured.

This function is called internally by RBT_NODE_RETRIEVE(), which calculates common_bits, common_pins and common_staggered_bits for tree traversal. The value are accepted as parameters here to avoid redundant calculations.

In contrast to the other insertion functions, this function returns a pointer to the inserted child. This is to avoid redundant calculations for determining whether the new child is the left or right child of the node.

See also

◆ RBT_NODE_IS_COPY()

int RBT_NODE_IS_COPY	(	RBT_NODE_T *	a,
		RBT_NODE_T *	b
	)

Check if a tree is a copy.

Determine if two trees are copies of each other. A node-by-node comparison is used.

Attention: The value of errno should be checked for errors when this function returns.

Parameters

[in]	a	The first root node.
[in]	b	The second root node.

Returns: An int that will be non-zero if the trees are copies.

◆ RBT_NODE_MERGE_CHILD()

void RBT_NODE_MERGE_CHILD	(	RBT_NODE_T *	parent_node,
		RBT_NODE_T *	child_node
	)

Merge a child node into the parent. The value and children of the target child will be inserted into the parent and the key bits will be merged.

The merged child should be the only child of the parent. If it is not, the sibling will be removed and freed along with the target child.

Logically this removes the parent node from the tree.

Attention: The value of errno should be checked for errors when this function returns.

Parameters

[in]	parent_node	The parent node.
[in]	child_node	The child node.

◆ RBT_NODE_NEW()

RBT_NODE_T * RBT_NODE_NEW ( )

Create a new tree.

Create a new, empty node. This should be used to create root nodes for new trees.

◆ RBT_NODE_QUERY()

RBT_VALUE_T RBT_NODE_QUERY	(	RBT_NODE_T *	root_node,
		RBT_PIN_T *	key,
		RBT_KEY_SIZE_T	bits,
		rbt_query_action_t	action,
		RBT_VALUE_T	value
	)

Query a tree.

A function to retrieve a node from a tree given a key. If a matching node is found, it is returned. Depending on the given action, missing nodes may also be inserted along with a given value, or the value of an existing node may be updated. The latter action is supported as a matter of algorithmic convenience.

This function does not remove nodes. Instead it will update a given pointer to point to the parent node of the returned node. A wrapper function such as RBT_NODE_ may then callRBT_NODE_REMOVE()`, perhaps conditionally given the current value of the node. This provides versatility without the complexity of handling multiple cases in this function along with the concomitant overhead of additional checks.

Attention: The value of errno should be checked for errors when this function returns.

Parameters

[in]	root_node	A pointer to the root node.
[in]	key	The key.
[in]	bits	The number of significant bits in the key. Bits beyond these will be ignored.
[in]	action	The action that should be performed.
[in]	value	The value with which the action will be performed.

Returns: The value determined by the action.

See also

RBT_NODE_RETRIEVE()

◆ RBT_NODE_REMOVE()

RBT_NODE_T * RBT_NODE_REMOVE	(	RBT_NODE_T *	node,
		RBT_NODE_T *	parent_node
	)

Remove a node from a tree.

Logically remove a node from a tree. If the node can be completely removed, it will be freed and the parent node will be restructured as necessary.

Attention: The value of errno should be checked for errors when this function returns.

Parameters

[in]	node	A pointer to the target node.
[in]	parent_node	The parent node of the target node.

Returns: The passed node if it remains in the tree, otherwise the parent.

◆ RBT_NODE_RETRIEVE()

RBT_NODE_T * RBT_NODE_RETRIEVE	(	RBT_NODE_T *	node,
		RBT_PIN_T *	key,
		RBT_KEY_SIZE_T	bits,
		rbt_retrieve_action_t	action,
		RBT_VALUE_T	value,
		RBT_NODE_T **	parent_node_ptr
	)

Retrieve a node matching the given key.

A function to retrieve a node from a tree given a key. If a matching node is found, it is returned. Depending on the given action, missing nodes may also be inserted along with a given value, or the value of an existing node may be updated. The latter action is supported as a matter of algorithmic convenience.

This function does not remove nodes. Instead it will update a given pointer to point to the parent node of the returned node. A wrapper function such as RBT_NODE_ may then callRBT_NODE_REMOVE()`, perhaps conditionally given the current value of the node. This provides versatility without the complexity of handling multiple cases in this function along with the concomitant overhead of additional checks.

Attention: The value of errno should be checked for errors when this function returns.

Warning: The value of a node that is not RBT_VALUE_NULL should not be directly set to RBT_VALUE_NULL. Nodes with a value of RBT_VALUE_NULL are considered placeholder nodes and are only used as parent nodes when required for the tree structure. Manually inserting RBT_VALUE_NULL will cause some assumptions about the tree structure to fail. To remove a node, pass it to RBT_NODE_REMOVE() along with the parent pointer, which will restructure the tree if necessary.; There are some exceptional cases in which this may nevertheless be useful. In those it should be possible to pass RBT_VALUE_NULL to RBT_NODE_FILTER() to remove the unexpected nodes. However, all functions are written under certain assumptions about the tree structure. It is up to you to determine if any would be broken by the presence of such nodes.; In summary, don't do this unless you really know what you're doing.

Parameters

[in]	node	A pointer to the root node.
[in]	key	The key.
[in]	bits	The number of significant bits in the key. Bits beyond these will be ignored.
[in]	action	The action that should be performed.
[in]	value	The value with which the action will be performed.
[out]	parent_node_ptr	An optional pointer to a parent node pointer. This pointer will be updated with the target node's parent for some actions if it is not NULL. This is required for deleting nodes in a wrapper function. For other actions it has a special use (mostly for wrapper functions).

RBT_RETRIEVE_ACTION_PREFIX_SUBTREE : The point must point to an allocated node. The bits field of the node will be updated to indicate the bit different between the retrieved node and the target prefix. This is used to construct the matching subtree in a separate function.

Returns: The target node pointer, or NULL if no matching node was found or an error occured.

See also

RBT_NODE_QUERY()

◆ RBT_NODE_TRAVERSE()

void RBT_NODE_TRAVERSE	(	RBT_NODE_T *	node,
		RBT_NODE_TRAVERSE_FUNCTION_T	func_v,
			...
	)

Traverse a tree and pass each node to a function along with its height.

This function does not reconstruct the key associated with each node.

See also: RBT_NODE_TRAVERSE_WITH_KEY()

Parameters

[in]	node	The root node.
[in]	func_v	The function to call with each node.
[in]	...	Additional argument to pass to the called function along with each node. These will be passed as a `va_list`.

◆ RBT_NODE_WITH_PREFIX_SUBTREE_DO()

int RBT_NODE_WITH_PREFIX_SUBTREE_DO	(	RBT_NODE_T *	node,
		RBT_PIN_T *	key,
		RBT_KEY_SIZE_T	bits,
		void()(RBT_NODE_T subtree, va_list args)	func_v,
			...
	)

Perform some action on the subtree defined by a common prefix.

Attention: The value of errno should be checked for errors when this function returns.

Parameters

[in]	node	A pointer to the root node.
[in]	key	The key, i.e. the prefix.
[in]	bits	The number of significant bits in the key. Bits beyond these will be ignored. This can thus determine the different prefixes for the same key.
[in]	func_v	The function to call with the subtree.
[in]	...	Additional arguments to func_v.

Returns: 1 if a matching subtree was found, 0 if no matching subtree was found or if an error occured (check errno).

Data Structures

Macros

Typedefs

Functions

Detailed Description

Required Headers

Required Macro Definitions:

Optional Macro Definitions

Examples

Statically allocated string values.

Dynamically allocated string values.

Macro Definition Documentation

◆ RBT_NODE_CACHE_OR_FREE

◆ RBT_VALUE_IS_NULL

Typedef Documentation

◆ _RBT_NODE_TRAVERSE_WITH_KEY_STACK_T

◆ RBT_KEY_DATA_T

◆ RBT_NODE_FILTER_FUNCTION_T

◆ RBT_NODE_FILTER_WITH_KEY_FUNCTION_T

◆ RBT_NODE_STACK_T

◆ RBT_NODE_TRAVERSE_FUNCTION_T

◆ RBT_NODE_TRAVERSE_WITH_KEY_FUNCTION_T

Function Documentation

◆ RBT_NODE_COPY()

◆ RBT_NODE_COUNT()

◆ RBT_NODE_CREATE()

◆ RBT_NODE_FILTER()

◆ RBT_NODE_FPRINT()

◆ RBT_NODE_FPRINT_INTERNAL()

◆ RBT_NODE_FREE()

◆ RBT_NODE_INSERT_CHILD()

◆ RBT_NODE_INSERT_PARENT()

◆ RBT_NODE_INSERT_SIBLING()

◆ RBT_NODE_IS_COPY()

◆ RBT_NODE_MERGE_CHILD()

◆ RBT_NODE_NEW()

◆ RBT_NODE_QUERY()

◆ RBT_NODE_REMOVE()

◆ RBT_NODE_RETRIEVE()

◆ RBT_NODE_TRAVERSE()

◆ RBT_NODE_WITH_PREFIX_SUBTREE_DO()