traverse_with_key.h File Reference

#include "node.h"

Include dependency graph for traverse_with_key.h:

Go to the source code of this file.

Macros
#define	RBT_RESIZE_TO_FIT_KEY(current_size, required_size, fail)

Functions
void	RBT_NODE_FILTER_WITH_KEY (RBT_NODE_T *node, RBT_NODE_FILTER_WITH_KEY_FUNCTION_T func_v, int include_empty,...)
	Filter tree nodes. More...
void	RBT_NODE_TRAVERSE_WITH_KEY (RBT_NODE_T *node, RBT_NODE_TRAVERSE_WITH_KEY_FUNCTION_T func_v,...)

Detailed Description

Author

Xyne

Copyright

GPL2 only

Usage

These functions are kept outside of node.h to enable optimizations for key types of different lengths without redefinition of entries in node.h. For example, node.h may be used to declare key types with 8-bit pins. These may then be used by multiple key types such as integers or strings. The former use a fixed key size and thus can be used with static memory in the following functions.

If RBT_KEY_SIZE_FIXED is defined, it will be used to allocate a static array for tracking the key across nodes during traversal.

If it is not defined then the key will be resized dynamically, thus incurring additional overhead for memory allocation.

In the latter case no further definitions are required before including this file and it can be included immediately after each inclusion of node.h.

Required Headers

• node.h

Optional macro definitions

• RBT_TRAVERSE_H_PREFIX_

  This can be defined to enable variations of the traverse function with the same node and internal key type. If not defined it defaults to RBT_NODE_H_PREFIX_.

• RBT_KEY_SIZE_FIXED

  The size of the key, in bytes, if it is fixed or if a maximum key size can be anticipated.

Macro Definition Documentation

RBT_RESIZE_TO_FIT_KEY

#define RBT_RESIZE_TO_FIT_KEY	(		current_size,
			required_size,
			fail
	)

Value:

do \
{ \
  current_size = required_size * 2; \
  if (current_size < required_size) \
  { \
    current_size = -1; \
    if (current_size < required_size) \
    { \
      fail; \
    } \
  } \
} \
while(0)

As the tree is traversed, the key associated with each node is determined by tracking the key fragments associated with each preceding node. If the key does not have a fixed length then the memory must be allocated dynamically.

This macro accepts the current size of the memory block along with the required size and a fail statement. The current size should be set to a value that is at least equal to the required size.

The required size of continued traversal should be anticipated to avoid the overhead of multiple calls to realloc.

If the required size cannot be set due to overflow errors, the provided fail statement should be run.

Parameters

[in,out]	current_size	The current size.
[in]	required_size	The required size to hold the key of the current node.
[in]	fail	A statement or series of statements that should be run if the current size cannot be expanded to the required size due to integer overflow.

Function Documentation

RBT_NODE_FILTER_WITH_KEY()

void RBT_NODE_FILTER_WITH_KEY	(	RBT_NODE_T *	node,
		RBT_NODE_FILTER_WITH_KEY_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.

This function differs from RBT_NODE_FILTER() by passing the reconstructed key for each node and its size as the first arguments to the filter function.

Attention

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

Keys for empty nodes should not be cast back to key types unless you know exactly what you are doing. If the reason for this is not obvious then you do not know exactly what you are doing and should not do it. ;)

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__WITH_KEY_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() -RBT_NODE_FILTER_WITH_KEY_FUNCTION_T`

RBT_NODE_TRAVERSE_WITH_KEY()

void RBT_NODE_TRAVERSE_WITH_KEY	(	RBT_NODE_T *	node,
		RBT_NODE_TRAVERSE_WITH_KEY_FUNCTION_T	func_v,
			...
	)

Traverse a tree and pass each node and its full associated key to a function, along with the height of the node.

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.