Binary tree data structure. More...

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

Typedefs
typedef struct PTree_	PTree
	Tree opaque data structure.

typedef enum PTreeType_	PTreeType
	Internal data organization algorithm for PTree.

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 PTree *	p_tree_new (PTreeType type, PCompareFunc func)
	Initializes new PTree.

P_LIB_API PTree *	p_tree_new_with_data (PTreeType type, PCompareDataFunc func, ppointer data)
	Initializes new PTree with additional data.

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.

P_LIB_API void	p_tree_insert (PTree *tree, ppointer key, ppointer value)
	Inserts a new key-value pair into a tree.

P_LIB_API pboolean	p_tree_remove (PTree *tree, pconstpointer key)
	Removes a key from a tree.

P_LIB_API ppointer	p_tree_lookup (PTree *tree, pconstpointer key)
	Lookups a value by a given key.

P_LIB_API void	p_tree_foreach (PTree *tree, PTraverseFunc traverse_func, ppointer user_data)
	Iterates in-order through the tree nodes.

P_LIB_API void	p_tree_clear (PTree *tree)
	Clears a tree.

P_LIB_API PTreeType	p_tree_get_type (const PTree *tree)
	Gets a tree algorithm type.

P_LIB_API pint	p_tree_get_nnodes (const PTree *tree)
	Gets node count.

P_LIB_API void	p_tree_free (PTree *tree)
	Frees a previously initialized tree object.

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:

unbalanced binary search tree;
red-black self-balancing tree;
AVL self-balancing tree.

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.

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

tree	PTree 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

tree	A tree to traverse.
traverse_func	Function for traversing.
user_data	Additional (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

tree	PTree 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

tree	PTree 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

tree	PTree 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

tree	PTree to insert a node in.
key	Key to insert.
value	Value 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

tree	PTree to lookup in.
key	Key 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

type	Tree algorithm type to use, can't be changed later.
func	Key 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

type	Tree algorithm type to use, can't be changed later.
func	Key compare function.
data	Data to be passed to func along with the keys.
key_destroy	Function to call on every key before the node destruction, maybe NULL.
value_destroy	Function 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

type	Tree algorithm type to use, can't be changed later.
func	Key compare function.
data	Data 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

tree	PTree to remove a key from.
key	A 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.

Typedefs

Enumerations

Functions

Detailed Description

Typedef Documentation

◆ PTree

Enumeration Type Documentation

◆ PTreeType_

Function Documentation

◆ p_tree_clear()

◆ p_tree_foreach()

◆ p_tree_free()

◆ p_tree_get_nnodes()

◆ p_tree_get_type()

◆ p_tree_insert()

◆ p_tree_lookup()

◆ p_tree_new()

◆ p_tree_new_full()

◆ p_tree_new_with_data()

◆ p_tree_remove()