universe@390: universe@390:

AVL tree implementation. universe@390: More...

universe@390:

#include "ucx.h"
universe@390: #include "allocator.h"
universe@390: #include <inttypes.h>
universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

universe@390: Data Structures
struct	UcxAVLNode
	UCX AVL Node. More...

struct	UcxAVLTree
	UCX AVL Tree. More...

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

universe@390: Macros
#define	ucx_avl_default_new() ucx_avl_new_a(ucx_cmp_ptr, ucx_default_allocator())
	Macro for initializing a new UcxAVLTree with the default allocator and a ucx_cmp_ptr() compare function. More...

universe@390: #define	UCX_AVL_FIND_EXACT 0
	A mode for ucx_avl_find_node() with the same behavior as ucx_avl_get_node().

universe@390: #define	UCX_AVL_FIND_LOWER_BOUNDED 1
	A mode for ucx_avl_find_node() finding the node whose key is at least as large as the specified key.

universe@390: #define	UCX_AVL_FIND_UPPER_BOUNDED 2
	A mode for ucx_avl_find_node() finding the node whose key is at most as large as the specified key.

#define	UCX_AVL_FIND_CLOSEST 3
	A mode for ucx_avl_find_node() finding the node with a key that is as close to the specified key as possible. More...

universe@390: universe@390: universe@390: universe@390: universe@390:

universe@390: Typedefs
typedef struct UcxAVLNode	UcxAVLNode
	UCX AVL Node type. More...

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

universe@390: Functions
UcxAVLTree *	ucx_avl_new (cmp_func cmpfunc)
	Initializes a new UcxAVLTree with a default allocator. More...

UcxAVLTree *	ucx_avl_new_a (cmp_func cmpfunc, UcxAllocator *allocator)
	Initializes a new UcxAVLTree with the specified allocator. More...

void	ucx_avl_free (UcxAVLTree *tree)
	Destroys a UcxAVLTree. More...

void	ucx_avl_free_content (UcxAVLTree *tree, ucx_destructor destr)
	Frees the contents of a UcxAVLTree. More...

UcxAVLNode *	ucx_avl_get_node (UcxAVLTree *tree, intptr_t key)
	Gets the node from the tree, that is associated with the specified key. More...

void *	ucx_avl_get (UcxAVLTree *tree, intptr_t key)
	Gets the value from the tree, that is associated with the specified key. More...

UcxAVLNode *	ucx_avl_find_node (UcxAVLTree *tree, intptr_t key, distance_func dfnc, int mode)
	Finds a node within the tree. More...

void *	ucx_avl_find (UcxAVLTree *tree, intptr_t key, distance_func dfnc, int mode)
	Finds a value within the tree. More...

int	ucx_avl_put (UcxAVLTree tree, intptr_t key, void value)
	Puts a key/value pair into the tree. More...

int	ucx_avl_put_s (UcxAVLTree tree, intptr_t key, void value, void **oldvalue)
	Puts a key/value pair into the tree. More...

int	ucx_avl_remove_node (UcxAVLTree tree, UcxAVLNode node)
	Removes a node from the AVL tree. More...

int	ucx_avl_remove (UcxAVLTree *tree, intptr_t key)
	Removes an element from the AVL tree. More...

int	ucx_avl_remove_s (UcxAVLTree tree, intptr_t key, intptr_t oldkey, void **oldvalue)
	Removes an element from the AVL tree. More...

size_t	ucx_avl_count (UcxAVLTree *tree)
	Counts the nodes in the specified UcxAVLTree. More...

UcxAVLNode *	ucx_avl_pred (UcxAVLNode *node)
	Finds the in-order predecessor of the given node. More...

UcxAVLNode *	ucx_avl_succ (UcxAVLNode *node)
	Finds the in-order successor of the given node. More...

universe@390:

Detailed Description

universe@390:

AVL tree implementation.

universe@390:

This binary search tree implementation allows average O(1) insertion and removal of elements (excluding binary search time).

universe@390:

Author: Mike Becker; universe@390: Olaf Wintermann

universe@390:

Macro Definition Documentation

universe@390: universe@390:

◆ ucx_avl_default_new

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

#define ucx_avl_default_new ( ) ucx_avl_new_a(ucx_cmp_ptr, ucx_default_allocator())

universe@390:

universe@390: universe@390:

Macro for initializing a new UcxAVLTree with the default allocator and a ucx_cmp_ptr() compare function.

universe@390:

Returns: a new default UcxAVLTree object

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ UCX_AVL_FIND_CLOSEST

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390:

#define UCX_AVL_FIND_CLOSEST 3

universe@390:

universe@390: universe@390:

A mode for ucx_avl_find_node() finding the node with a key that is as close to the specified key as possible.

universe@390:

If the key is present, the behavior is like ucx_avl_get_node(). This mode only returns NULL on empty trees.

universe@390: universe@390:

universe@390:

Typedef Documentation

universe@390: universe@390:

◆ UcxAVLNode

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390:

typedef struct UcxAVLNode UcxAVLNode

universe@390:

universe@390: universe@390:

UCX AVL Node type.

universe@390:

See also: UcxAVLNode

universe@390: universe@390:

universe@390:

Function Documentation

universe@390: universe@390:

◆ ucx_avl_count()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

size_t ucx_avl_count ( UcxAVLTree * tree )

universe@390:

universe@390: universe@390:

Counts the nodes in the specified UcxAVLTree.

universe@390:

Parameters

universe@390: universe@390: universe@390:

tree	the AVL tree

universe@390:

Returns: the node count

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_avl_find()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

void* ucx_avl_find	(	UcxAVLTree *	tree,
		intptr_t	key,
		distance_func	dfnc,
		int	mode
	)

universe@390:

universe@390: universe@390:

Finds a value within the tree.

universe@390:

See ucx_avl_find_node() for details.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

tree	the UcxAVLTree
key	the key
dfnc	the distance function
mode	the find mode

universe@390:

Returns: the value (or NULL, if no value can be found)

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_avl_find_node()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

UcxAVLNode* ucx_avl_find_node	(	UcxAVLTree *	tree,
		intptr_t	key,
		distance_func	dfnc,
		int	mode
	)

universe@390:

universe@390: universe@390:

Finds a node within the tree.

universe@390:

The following modes are supported:

universe@390: UCX_AVL_FIND_EXACT: the same behavior as ucx_avl_get_node()
universe@390: UCX_AVL_FIND_LOWER_BOUNDED: finds the node whose key is at least as large as the specified key
universe@390: UCX_AVL_FIND_UPPER_BOUNDED: finds the node whose key is at most as large as the specified key
universe@390: UCX_AVL_FIND_CLOSEST: finds the node with a key that is as close to the specified key as possible. If the key is present, the behavior is like ucx_avl_get_node(). This mode only returns NULL on empty trees.

universe@390:

The distance function provided MUST agree with the compare function of the AVL tree.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

tree	the UcxAVLTree
key	the key
dfnc	the distance function
mode	the find mode

universe@390:

Returns: the node (or NULL, if no node can be found)

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_avl_free()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

void ucx_avl_free ( UcxAVLTree * tree )

universe@390:

universe@390: universe@390:

Destroys a UcxAVLTree.

universe@390:

Note, that the contents are not automatically freed. Use may use ucx_avl_free_content() before calling this function.

universe@390:

Parameters

universe@390: universe@390: universe@390:

tree	the tree to destroy

universe@390:

See also: ucx_avl_free_content()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_avl_free_content()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

void ucx_avl_free_content	(	UcxAVLTree *	tree,
		ucx_destructor	destr
	)

universe@390:

universe@390: universe@390:

Frees the contents of a UcxAVLTree.

universe@390:

This is a convenience function that iterates over the tree and passes all values to the specified destructor function.

universe@390:

If no destructor is specified (NULL), the free() function of the tree's own allocator is used.

universe@390:

You must ensure, that it is valid to pass each value in the map to the same destructor function.

universe@390:

You should free the entire tree afterwards, as the contents will be invalid.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

tree	for which the contents shall be freed
destr	optional pointer to a destructor function

universe@390:

See also: ucx_avl_free()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_avl_get()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

void* ucx_avl_get	(	UcxAVLTree *	tree,
		intptr_t	key
	)

universe@390:

universe@390: universe@390:

Gets the value from the tree, that is associated with the specified key.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

tree	the UcxAVLTree
key	the key

universe@390:

Returns: the value (or NULL, if the key is not present)

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_avl_get_node()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

UcxAVLNode* ucx_avl_get_node	(	UcxAVLTree *	tree,
		intptr_t	key
	)

universe@390:

universe@390: universe@390:

Gets the node from the tree, that is associated with the specified key.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

tree	the UcxAVLTree
key	the key

universe@390:

Returns: the node (or NULL, if the key is not present)

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_avl_new()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

UcxAVLTree* ucx_avl_new ( cmp_func cmpfunc )

universe@390:

universe@390: universe@390:

Initializes a new UcxAVLTree with a default allocator.

universe@390:

Parameters

universe@390: universe@390: universe@390:

cmpfunc the compare function that shall be used

universe@390:

Returns: a new UcxAVLTree object

universe@390:

See also: ucx_avl_new_a()

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_avl_new_a()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

UcxAVLTree* ucx_avl_new_a	(	cmp_func	cmpfunc,
		UcxAllocator *	allocator
	)

universe@390:

universe@390: universe@390:

Initializes a new UcxAVLTree with the specified allocator.

universe@390:

The cmpfunc should be capable of comparing two keys within this AVL tree. So if you want to use null terminated strings as keys, you could use the ucx_cmp_str() function here.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

cmpfunc	the compare function that shall be used
allocator	the UcxAllocator that shall be used

universe@390:

Returns: a new UcxAVLTree object

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_avl_pred()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

UcxAVLNode* ucx_avl_pred ( UcxAVLNode * node )

universe@390:

universe@390: universe@390:

Finds the in-order predecessor of the given node.

universe@390:

Parameters

universe@390: universe@390: universe@390:

node	an AVL node

universe@390:

Returns: the in-order predecessor of the given node, or NULL if the given node is the in-order minimum

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_avl_put()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

int ucx_avl_put	(	UcxAVLTree *	tree,
		intptr_t	key,
		void *	value
	)

universe@390:

universe@390: universe@390:

Puts a key/value pair into the tree.

universe@390:

Attention: use this function only, if a possible old value does not need to be preserved.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390:

tree	the UcxAVLTree
key	the key
value	the new value

universe@390:

Returns: zero, if and only if the operation succeeded

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_avl_put_s()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

int ucx_avl_put_s	(	UcxAVLTree *	tree,
		intptr_t	key,
		void *	value,
		void **	oldvalue
	)

universe@390:

universe@390: universe@390:

Puts a key/value pair into the tree.

universe@390:

This is a secure function which saves the old value to the variable pointed at by oldvalue.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

tree	the UcxAVLTree
key	the key
value	the new value
oldvalue	optional: a pointer to the location where a possible old value shall be stored

universe@390:

Returns: zero, if and only if the operation succeeded

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_avl_remove()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

int ucx_avl_remove	(	UcxAVLTree *	tree,
		intptr_t	key
	)

universe@390:

universe@390: universe@390:

Removes an element from the AVL tree.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

tree	the UcxAVLTree
key	the key

universe@390:

Returns: zero, if and only if an element has been removed

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_avl_remove_node()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

int ucx_avl_remove_node	(	UcxAVLTree *	tree,
		UcxAVLNode *	node
	)

universe@390:

universe@390: universe@390:

Removes a node from the AVL tree.

universe@390:

Note: the specified node is logically removed. The tree implementation decides which memory area is freed. In most cases the here provided node is freed, so its further use is generally undefined.

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390:

tree	the UcxAVLTree
node	the node to remove

universe@390:

Returns: zero, if and only if an element has been removed

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_avl_remove_s()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

int ucx_avl_remove_s	(	UcxAVLTree *	tree,
		intptr_t	key,
		intptr_t *	oldkey,
		void **	oldvalue
	)

universe@390:

universe@390: universe@390:

Removes an element from the AVL tree.

universe@390:

This is a secure function which saves the old key and value data from node to the variables at the location of oldkey and oldvalue (if specified), so they can be freed afterwards (if necessary).

universe@390:

Note: the returned key in oldkey is possibly not the same as the provided key for the lookup (in terms of memory location).

universe@390:

Parameters

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

tree	the UcxAVLTree
key	the key of the element to remove
oldkey	optional: a pointer to the location where the old key shall be stored
oldvalue	optional: a pointer to the location where the old value shall be stored

universe@390:

Returns: zero, if and only if an element has been removed

universe@390: universe@390:

universe@390:

universe@390: universe@390:

◆ ucx_avl_succ()

universe@390: universe@390:

universe@390:

universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390: universe@390:

UcxAVLNode* ucx_avl_succ ( UcxAVLNode * node )

universe@390:

universe@390: universe@390:

Finds the in-order successor of the given node.

universe@390:

Parameters

universe@390: universe@390: universe@390:

node	an AVL node

universe@390:

Returns: the in-order successor of the given node, or NULL if the given node is the in-order maximum

universe@390: universe@390:

universe@390:

universe@390: Data Structures

universe@390: Macros

universe@390: Typedefs

universe@390: Functions

Detailed Description

Macro Definition Documentation

◆ ucx_avl_default_new

◆ UCX_AVL_FIND_CLOSEST

Typedef Documentation

◆ UcxAVLNode

Function Documentation

◆ ucx_avl_count()

◆ ucx_avl_find()

◆ ucx_avl_find_node()

◆ ucx_avl_free()

◆ ucx_avl_free_content()

◆ ucx_avl_get()

◆ ucx_avl_get_node()

◆ ucx_avl_new()

◆ ucx_avl_new_a()

◆ ucx_avl_pred()

◆ ucx_avl_put()

◆ ucx_avl_put_s()

◆ ucx_avl_remove()

◆ ucx_avl_remove_node()

◆ ucx_avl_remove_s()

◆ ucx_avl_succ()