diff -r 92e482410453 -r d345541018fa docs/api-2.1/avl_8h.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/docs/api-2.1/avl_8h.html Sat Feb 06 19:11:44 2021 +0100 @@ -0,0 +1,883 @@ + + + + + + + +ucx: /home/mike/workspace/c/ucx/src/ucx/avl.h File Reference + + + + + + + + + +
+
+ + + + + + + +
+
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_cmp_ptr, ucx_default_allocator())
 Macro for initializing a new UcxAVLTree with the default allocator and a ucx_cmp_ptr() 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

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

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

+ +

◆ ucx_avl_default_new

+ +
+
+ + + + + + + +
#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.

+
Returns
a new default UcxAVLTree object
+ +
+
+ +

◆ UCX_AVL_FIND_CLOSEST

+ +
+
+ + + + +
#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

+ +

◆ UcxAVLNode

+ +
+
+ + + + +
typedef struct UcxAVLNode UcxAVLNode
+
+ +

UCX AVL Node type.

+
See also
UcxAVLNode
+ +
+
+

Function Documentation

+ +

◆ ucx_avl_count()

+ +
+
+ + + + + + + + +
size_t ucx_avl_count (UcxAVLTree * tree)
+
+ +

Counts the nodes in the specified UcxAVLTree.

+
Parameters
+ + +
treethe AVL tree
+
+
+
Returns
the node count
+ +
+
+ +

◆ ucx_avl_find()

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

◆ ucx_avl_find_node()

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

◆ ucx_avl_free()

+ +
+
+ + + + + + + + +
void ucx_avl_free (UcxAVLTree * tree)
+
+ +

Destroys a UcxAVLTree.

+

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

+
Parameters
+ + +
treethe tree to destroy
+
+
+
See also
ucx_avl_free_content()
+ +
+
+ +

◆ ucx_avl_free_content()

+ +
+
+ + + + + + + + + + + + + + + + + + +
void ucx_avl_free_content (UcxAVLTree * tree,
ucx_destructor destr 
)
+
+ +

Frees the contents of a UcxAVLTree.

+

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

+

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

+

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

+

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

+
Parameters
+ + + +
treefor which the contents shall be freed
destroptional pointer to a destructor function
+
+
+
See also
ucx_avl_free()
+ +
+
+ +

◆ ucx_avl_get()

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

◆ ucx_avl_get_node()

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

◆ ucx_avl_new()

+ +
+
+ + + + + + + + +
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()
+ +
+
+ +

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

+
Parameters
+ + + +
cmpfuncthe compare function that shall be used
allocatorthe UcxAllocator that shall be used
+
+
+
Returns
a new UcxAVLTree object
+ +
+
+ +

◆ ucx_avl_pred()

+ +
+
+ + + + + + + + +
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
+ +
+
+ +

◆ ucx_avl_put()

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + +
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
+ +
+
+ +

◆ ucx_avl_put_s()

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
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
+ +
+
+ +

◆ ucx_avl_remove()

+ +
+
+ + + + + + + + + + + + + + + + + + +
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
+ +
+
+ +

◆ ucx_avl_remove_node()

+ +
+
+ + + + + + + + + + + + + + + + + + +
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
+ +
+
+ +

◆ ucx_avl_remove_s()

+ +
+
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
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
+ +
+
+ +

◆ ucx_avl_succ()

+ +
+
+ + + + + + + + +
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
+ +
+
+
+ +
+Generated on Thu Dec 19 2019 19:58:24 for ucx by   +doxygen + 1.8.13 +
+ +