ucx
UAP Common Extensions
Data Structures | Macros | Typedefs | Functions
avl.h File Reference

AVL tree implementation. More...

#include "ucx.h"
#include "allocator.h"
#include <inttypes.h>

Go to the source code of this file.

Data Structures

struct  UcxAVLNode
 UCX AVL Node. More...
 
struct  UcxAVLTree
 UCX AVL Tree. More...
 

Macros

#define ucx_avl_default_new()   ucx_avl_new_a(ucx_ptrcmp, ucx_default_allocator())
 Macro for initializing a new UcxAVLTree with the default allocator and a ucx_ptrcmp() compare function. More...
 
#define UCX_AVL_FIND_EXACT   0
 A mode for ucx_avl_find_node() with the same behavior as ucx_avl_get_node().
 
#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.
 
#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...
 

Typedefs

typedef struct UcxAVLNode UcxAVLNode
 UCX AVL Node type. More...
 

Functions

UcxAVLTreeucx_avl_new (cmp_func cmpfunc)
 Initializes a new UcxAVLTree with a default allocator. More...
 
UcxAVLTreeucx_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...
 
UcxAVLNodeucx_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...
 
UcxAVLNodeucx_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...
 
UcxAVLNodeucx_avl_pred (UcxAVLNode *node)
 Finds the in-order predecessor of the given node. More...
 
UcxAVLNodeucx_avl_succ (UcxAVLNode *node)
 Finds the in-order successor of the given node. More...
 

Detailed Description

AVL tree implementation.

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

Author
Mike Becker
Olaf Wintermann

Macro Definition Documentation

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

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

Returns
a new default UcxAVLTree object
#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.

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

Typedef Documentation

typedef struct UcxAVLNode UcxAVLNode

UCX AVL Node type.

See also
UcxAVLNode

Function Documentation

size_t ucx_avl_count ( UcxAVLTree tree)

Counts the nodes in the specified UcxAVLTree.

Parameters
treethe AVL tree
Returns
the node count
void* ucx_avl_find ( UcxAVLTree tree,
intptr_t  key,
distance_func  dfnc,
int  mode 
)

Finds a value within the tree.

See ucx_avl_find_node() for details.

Parameters
treethe UcxAVLTree
keythe key
dfncthe distance function
modethe find mode
Returns
the value (or NULL, if no value can be found)
UcxAVLNode* ucx_avl_find_node ( UcxAVLTree tree,
intptr_t  key,
distance_func  dfnc,
int  mode 
)

Finds a node within the tree.

The following modes are supported:

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

Parameters
treethe UcxAVLTree
keythe key
dfncthe distance function
modethe find mode
Returns
the node (or NULL, if no node can be found)
void ucx_avl_free ( UcxAVLTree tree)

Destroys a UcxAVLTree.

Parameters
treethe tree to destroy
void* ucx_avl_get ( UcxAVLTree tree,
intptr_t  key 
)

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

Parameters
treethe UcxAVLTree
keythe key
Returns
the value (or NULL, if the key is not present)
UcxAVLNode* ucx_avl_get_node ( UcxAVLTree tree,
intptr_t  key 
)

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

Parameters
treethe UcxAVLTree
keythe key
Returns
the node (or NULL, if the key is not present)
UcxAVLTree* ucx_avl_new ( cmp_func  cmpfunc)

Initializes a new UcxAVLTree with a default allocator.

Parameters
cmpfuncthe compare function that shall be used
Returns
a new UcxAVLTree object
See also
ucx_avl_new_a()
UcxAVLTree* ucx_avl_new_a ( cmp_func  cmpfunc,
UcxAllocator allocator 
)

Initializes a new UcxAVLTree with the specified allocator.

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_strcmp() function here.

Parameters
cmpfuncthe compare function that shall be used
allocatorthe UcxAllocator that shall be used
Returns
a new UcxAVLTree object
UcxAVLNode* ucx_avl_pred ( UcxAVLNode node)

Finds the in-order predecessor of the given node.

Parameters
nodean AVL node
Returns
the in-order predecessor of the given node, or NULL if the given node is the in-order minimum
int ucx_avl_put ( UcxAVLTree tree,
intptr_t  key,
void *  value 
)

Puts a key/value pair into the tree.

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

Parameters
treethe UcxAVLTree
keythe key
valuethe new value
Returns
zero, if and only if the operation succeeded
int ucx_avl_put_s ( UcxAVLTree tree,
intptr_t  key,
void *  value,
void **  oldvalue 
)

Puts a key/value pair into the tree.

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

Parameters
treethe UcxAVLTree
keythe key
valuethe new value
oldvalueoptional: a pointer to the location where a possible old value shall be stored
Returns
zero, if and only if the operation succeeded
int ucx_avl_remove ( UcxAVLTree tree,
intptr_t  key 
)

Removes an element from the AVL tree.

Parameters
treethe UcxAVLTree
keythe key
Returns
zero, if and only if an element has been removed
int ucx_avl_remove_node ( UcxAVLTree tree,
UcxAVLNode node 
)

Removes a node from the AVL tree.

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.

Parameters
treethe UcxAVLTree
nodethe node to remove
Returns
zero, if and only if an element has been removed
int ucx_avl_remove_s ( UcxAVLTree tree,
intptr_t  key,
intptr_t *  oldkey,
void **  oldvalue 
)

Removes an element from the AVL tree.

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).

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

Parameters
treethe UcxAVLTree
keythe key of the element to remove
oldkeyoptional: a pointer to the location where the old key shall be stored
oldvalueoptional: a pointer to the location where the old value shall be stored
Returns
zero, if and only if an element has been removed
UcxAVLNode* ucx_avl_succ ( UcxAVLNode node)

Finds the in-order successor of the given node.

Parameters
nodean AVL node
Returns
the in-order successor of the given node, or NULL if the given node is the in-order maximum