plibsys  0.0.4
Typedefs | Enumerations | Functions
ptree.h File Reference

Binary tree data structure. More...

#include <pmacros.h>
#include <ptypes.h>

Go to the source code of this file.

Typedefs

typedef struct PTree_ PTree
 Tree opaque data structure. More...
 
typedef enum PTreeType_ PTreeType
 Internal data organization algorithm for PTree. More...
 

Enumerations

enum  PTreeType_ { P_TREE_TYPE_BINARY = 0, P_TREE_TYPE_RB = 1, P_TREE_TYPE_AVL = 2 }
 Internal data organization algorithm for PTree. More...
 

Functions

P_LIB_API PTreep_tree_new (PTreeType type, PCompareFunc func)
 Initializes new PTree. More...
 
P_LIB_API PTreep_tree_new_with_data (PTreeType type, PCompareDataFunc func, ppointer data)
 Initializes new PTree with additional data. More...
 
P_LIB_API PTreep_tree_new_full (PTreeType type, PCompareDataFunc func, ppointer data, PDestroyFunc key_destroy, PDestroyFunc value_destroy)
 Initializes new PTree with additional data and memory management. More...
 
P_LIB_API void p_tree_insert (PTree *tree, ppointer key, ppointer value)
 Inserts a new key-value pair into a tree. More...
 
P_LIB_API pboolean p_tree_remove (PTree *tree, pconstpointer key)
 Removes a key from a tree. More...
 
P_LIB_API ppointer p_tree_lookup (PTree *tree, pconstpointer key)
 Lookups a value by a given key. More...
 
P_LIB_API void p_tree_foreach (PTree *tree, PTraverseFunc traverse_func, ppointer user_data)
 Iterates in-order through the tree nodes. More...
 
P_LIB_API void p_tree_clear (PTree *tree)
 Clears a tree. More...
 
P_LIB_API PTreeType p_tree_get_type (const PTree *tree)
 Gets a tree algorithm type. More...
 
P_LIB_API pint p_tree_get_nnodes (const PTree *tree)
 Gets node count. More...
 
P_LIB_API void p_tree_free (PTree *tree)
 Frees a previously initialized tree object. More...
 

Detailed Description

Binary tree data structure.

Author
Alexander Saprykin

PTree represents a binary search tree structure for faster lookup than a plain array or a list. It has average O(logN) time complexity to search a key-value pair, and O(N) in the worst case (when a tree is degenerated into the list).

Currently PTree supports the following tree types:

Use p_tree_new(), or its detailed variations like p_tree_new_with_data() and p_tree_new_full() to create a tree structure. Take attention that a caller owns the key and the value data passed when inserting new nodes, so you should manually free the memory after the tree usage. Or you can provide destroy notification functions for the keys and the values separately.

New key-value pairs can be inserted with p_tree_insert() and removed with p_tree_remove().

Use p_tree_lookup() to find the value by a given key. You can also traverse the tree in-order with p_tree_foreach().

Release memory with p_tree_free() or clear a tree with p_tree_clear(). Keys and values would be destroyed only if the corresponding notification functions were provided.

Note: all operations with the tree are non-recursive, only iterative calls are used.

Definition in file ptree.h.

Typedef Documentation

◆ PTree

typedef struct PTree_ PTree

Tree opaque data structure.

Definition at line 74 of file ptree.h.

◆ PTreeType

typedef enum PTreeType_ PTreeType

Internal data organization algorithm for PTree.

Enumeration Type Documentation

◆ PTreeType_

enum PTreeType_

Internal data organization algorithm for PTree.

Enumerator
P_TREE_TYPE_BINARY 

Unbalanced binary tree.

P_TREE_TYPE_RB 

Red-black self-balancing tree.

P_TREE_TYPE_AVL 

AVL self-balancing tree.

Definition at line 77 of file ptree.h.

Function Documentation

◆ p_tree_clear()

P_LIB_API void p_tree_clear ( PTree tree)

Clears a tree.

Parameters
treePTree to clear.
Since
0.0.1
Note
Modified Morris (non-recursive, non-stack) traversing algorithm is being used.

All the keys will be deleted. Key and value destroy functions would be called on every node if any of them was provided.

◆ p_tree_foreach()

P_LIB_API void p_tree_foreach ( PTree tree,
PTraverseFunc  traverse_func,
ppointer  user_data 
)

Iterates in-order through the tree nodes.

Parameters
treeA tree to traverse.
traverse_funcFunction for traversing.
user_dataAdditional (maybe NULL) user-provided data for the traverse_func.
Since
0.0.1
Note
Morris (non-recursive, non-stack) traversing algorithm is being used.

The tree should not be modified while traversing. The internal tree structure can be modified along the traversing process, so keep it in mind for concurrent access.

◆ p_tree_free()

P_LIB_API void p_tree_free ( PTree tree)

Frees a previously initialized tree object.

Parameters
treePTree object to free.
Since
0.0.1
Note
Modified Morris (non-recursive, non-stack) traversing algorithm is being used.

All the keys will be deleted. Key and value destroy functions would be called on every node if any of them was provided.

◆ p_tree_get_nnodes()

P_LIB_API pint p_tree_get_nnodes ( const PTree tree)

Gets node count.

Parameters
treePTree to get node count for.
Returns
Node count.
Since
0.0.1

If the tree is empty or an invalid pointer is given it returns 0.

◆ p_tree_get_type()

P_LIB_API PTreeType p_tree_get_type ( const PTree tree)

Gets a tree algorithm type.

Parameters
treePTree object to get the type for.
Returns
Tree internal organization algorithm used for a given object.
Since
0.0.1

◆ p_tree_insert()

P_LIB_API void p_tree_insert ( PTree tree,
ppointer  key,
ppointer  value 
)

Inserts a new key-value pair into a tree.

Parameters
treePTree to insert a node in.
keyKey to insert.
valueValue corresponding to the given key.
Since
0.0.1

If the key already exists in the tree then it will be replaced with the new one. If a key destroy function was provided it would be called on the old key. If a value destroy function was provided it would be called on the old value.

◆ p_tree_lookup()

P_LIB_API ppointer p_tree_lookup ( PTree tree,
pconstpointer  key 
)

Lookups a value by a given key.

Parameters
treePTree to lookup in.
keyKey to lookup.
Returns
Value for the given key in case of success, NULL otherwise.
Since
0.0.1

◆ p_tree_new()

P_LIB_API PTree* p_tree_new ( PTreeType  type,
PCompareFunc  func 
)

Initializes new PTree.

Parameters
typeTree algorithm type to use, can't be changed later.
funcKey compare function.
Returns
Newly initialized PTree object in case of success, NULL otherwise.
Since
0.0.1

The caller takes ownership of all the keys and the values passed to the tree.

◆ p_tree_new_full()

P_LIB_API PTree* p_tree_new_full ( PTreeType  type,
PCompareDataFunc  func,
ppointer  data,
PDestroyFunc  key_destroy,
PDestroyFunc  value_destroy 
)

Initializes new PTree with additional data and memory management.

Parameters
typeTree algorithm type to use, can't be changed later.
funcKey compare function.
dataData to be passed to func along with the keys.
key_destroyFunction to call on every key before the node destruction, maybe NULL.
value_destroyFunction to call on every value before the node destruction, maybe NULL.
Returns
Newly initialized PTree object in case of success, NULL otherwise.
Since
0.0.1

Upon every node destruction the corresponding key and value functions would be called.

◆ p_tree_new_with_data()

P_LIB_API PTree* p_tree_new_with_data ( PTreeType  type,
PCompareDataFunc  func,
ppointer  data 
)

Initializes new PTree with additional data.

Parameters
typeTree algorithm type to use, can't be changed later.
funcKey compare function.
dataData to be passed to func along with the keys.
Returns
Newly initialized PTree object in case of success, NULL otherwise.
Since
0.0.1

The caller takes ownership of all the keys and the values passed to the tree.

◆ p_tree_remove()

P_LIB_API pboolean p_tree_remove ( PTree tree,
pconstpointer  key 
)

Removes a key from a tree.

Parameters
treePTree to remove a key from.
keyA key to lookup.
Returns
TRUE if the key was removed, FALSE if the key was not found.
Since
0.0.1

If a key destroy function was provided it would be called on the key. If a value destroy function was provided it would be called on the old value.