tr_tree.c File Reference

#include "tr_tree.h"
#include "dict_private.h"
#include "tree_common.h"

Include dependency graph for tr_tree.c:

Go to the source code of this file.

Data Structures
struct	tr_node
struct	tr_tree
struct	tr_itor

Typedefs
typedef struct tr_node	tr_node

Functions
tr_tree *	tr_tree_new (dict_compare_func cmp_func, dict_prio_func prio_func)
	Create an empty treap that orders keys with |compare_func| (must not be NULL) and takes node priorities from |prio_func|, or at random if |prio_func| is NULL.
dict *	tr_dict_new (dict_compare_func cmp_func, dict_prio_func prio_func)
	Like tr_tree_new(), but wrapped in a generic dict for use with the dict_* macros.
size_t	tr_tree_free (tr_tree *tree, dict_delete_func delete_func)
	Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL, and free the tree.
size_t	tr_tree_clear (tr_tree *tree, dict_delete_func delete_func)
	Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL.
dict_insert_result	tr_tree_insert (tr_tree *tree, void *key)
	Insert |key| unless an equal key is present.
dict_remove_result	tr_tree_remove (tr_tree *tree, const void *key)
	Remove the element with key |key|.
void **	tr_tree_search (tr_tree *tree, const void *key)
	Return the address of the datum stored for |key|, or NULL if |key| is not present.
void **	tr_tree_search_le (tr_tree *tree, const void *key)
	Return the address of the datum of the greatest key less than or equal to |key|, or NULL if there is none.
void **	tr_tree_search_lt (tr_tree *tree, const void *key)
	Return the address of the datum of the greatest key less than |key|, or NULL if there is none.
void **	tr_tree_search_ge (tr_tree *tree, const void *key)
	Return the address of the datum of the least key greater than or equal to |key|, or NULL if there is none.
void **	tr_tree_search_gt (tr_tree *tree, const void *key)
	Return the address of the datum of the least key greater than |key|, or NULL if there is none.
size_t	tr_tree_traverse (tr_tree *tree, dict_visit_func visit, void *user_data)
	Call |visit|(key, datum, |user_data|) for each element in key order, stopping early if |visit| returns false.
bool	tr_tree_select (tr_tree *tree, size_t n, const void **key, void **datum)
	Store the key and datum of the |n|th element in key order (0-based) through |key| and |datum| and return true, or store NULL through them and return false if |n| is out of range.
size_t	tr_tree_count (const tr_tree *tree)
	Return the number of elements.
size_t	tr_tree_min_path_length (const tr_tree *tree)
	Return the shallowest depth at which a child link is absent, the root being at depth 1, or 0 for an empty tree.
size_t	tr_tree_max_path_length (const tr_tree *tree)
	Return the greatest depth of any node, the root being at depth 1, or 0 for an empty tree: the height of the tree.
size_t	tr_tree_total_path_length (const tr_tree *tree)
	Return the sum of the depths of all nodes, the root being at depth 1, or 0 for an empty tree.
bool	tr_tree_verify (const tr_tree *tree)
	Check the internal invariants of the tree and return true if they hold, or print the first failed check to stderr and return false.
tr_itor *	tr_itor_new (tr_tree *tree)
	Create an iterator over |tree| that is not positioned on any element yet.
dict_itor *	tr_dict_itor_new (tr_tree *tree)
	Like tr_itor_new(), but wrapped in a generic dict_itor for use with the dict_itor_* macros.
void	tr_itor_free (tr_itor *itor)
	Free an iterator.
bool	tr_itor_valid (const tr_itor *itor)
	Return whether |itor| is positioned on an element.
void	tr_itor_invalidate (tr_itor *itor)
	Unposition |itor|, so that it is not positioned on any element.
bool	tr_itor_next (tr_itor *itor)
	Move |itor| to the next element in key order and return true, or unposition it and return false if there is none.
bool	tr_itor_prev (tr_itor *itor)
	Move |itor| to the previous element in key order and return true, or unposition it and return false if there is none.
bool	tr_itor_nextn (tr_itor *itor, size_t count)
	Move |itor| |count| elements forward and return whether it is still positioned.
bool	tr_itor_prevn (tr_itor *itor, size_t count)
	Move |itor| |count| elements back and return whether it is still positioned.
bool	tr_itor_first (tr_itor *itor)
	Position |itor| on the first element in key order and return true, or unposition it and return false if the tree is empty.
bool	tr_itor_last (tr_itor *itor)
	Position |itor| on the last element in key order and return true, or unposition it and return false if the tree is empty.
bool	tr_itor_search (tr_itor *itor, const void *key)
	Position |itor| on |key| and return true, or unposition it and return false if |key| is not present.
bool	tr_itor_search_le (tr_itor *itor, const void *key)
	Position |itor| on the greatest key less than or equal to |key| and return true, or unposition it and return false if there is none.
bool	tr_itor_search_lt (tr_itor *itor, const void *key)
	Position |itor| on the greatest key less than |key| and return true, or unposition it and return false if there is none.
bool	tr_itor_search_ge (tr_itor *itor, const void *key)
	Position |itor| on the least key greater than or equal to |key| and return true, or unposition it and return false if there is none.
bool	tr_itor_search_gt (tr_itor *itor, const void *key)
	Position |itor| on the least key greater than |key| and return true, or unposition it and return false if there is none.
const void *	tr_itor_key (const tr_itor *itor)
	Return the key |itor| is positioned on, or NULL if it is not positioned.
void **	tr_itor_datum (tr_itor *itor)
	Return the address of the datum |itor| is positioned on, through which it can be read or replaced, or NULL if it is not positioned.
int	tr_itor_compare (const tr_itor *i1, const tr_itor *i2)
	Compare the positions of two iterators over the same tree: return a negative value, zero, or a positive value as |i1| is before, at, or after |i2| in key order.
bool	tr_itor_remove (tr_itor *it)
	Remove the element |itor| is positioned on and unposition |itor|; return false if it was not positioned.

Typedef Documentation

tr_node

typedef struct tr_node tr_node

Definition at line 50 of file tr_tree.c.

Function Documentation

tr_dict_itor_new()

dict_itor * tr_dict_itor_new

(

tr_tree *

tree

)

Like tr_itor_new(), but wrapped in a generic dict_itor for use with the dict_itor_* macros.

Free it with dict_itor_free().

Definition at line 304 of file tr_tree.c.

Here is the call graph for this function:

tr_dict_new()

dict * tr_dict_new	(	dict_compare_func	compare_func,
		dict_prio_func	prio_func )

Like tr_tree_new(), but wrapped in a generic dict for use with the dict_* macros.

Free it with dict_free(). Returns NULL if memory cannot be allocated.

Definition at line 134 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_compare()

int tr_itor_compare	(	const tr_itor *	i1,
		const tr_itor *	i2 )

Compare the positions of two iterators over the same tree: return a negative value, zero, or a positive value as |i1| is before, at, or after |i2| in key order.

An unpositioned iterator compares before every positioned one.

Definition at line 333 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_datum()

void ** tr_itor_datum

(

tr_itor *

itor

)

Return the address of the datum |itor| is positioned on, through which it can be read or replaced, or NULL if it is not positioned.

Definition at line 332 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_first()

bool tr_itor_first

(

tr_itor *

itor

)

Position |itor| on the first element in key order and return true, or unposition it and return false if the tree is empty.

Definition at line 324 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_free()

void tr_itor_free

(

tr_itor *

itor

)

Free an iterator.

Definition at line 317 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_invalidate()

void tr_itor_invalidate

(

tr_itor *

itor

)

Unposition |itor|, so that it is not positioned on any element.

Definition at line 319 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_key()

const void * tr_itor_key

(

const tr_itor *

itor

)

Return the key |itor| is positioned on, or NULL if it is not positioned.

The key belongs to the container and must not be modified in a way that changes how it compares.

Definition at line 331 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_last()

bool tr_itor_last

(

tr_itor *

itor

)

Position |itor| on the last element in key order and return true, or unposition it and return false if the tree is empty.

Definition at line 325 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_new()

tr_itor * tr_itor_new

(

tr_tree *

tree

)

Create an iterator over |tree| that is not positioned on any element yet.

Returns NULL if memory cannot be allocated.

Definition at line 293 of file tr_tree.c.

tr_itor_next()

bool tr_itor_next

(

tr_itor *

itor

)

Move |itor| to the next element in key order and return true, or unposition it and return false if there is none.

An unpositioned iterator stays unpositioned and returns false.

Definition at line 320 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_nextn()

bool tr_itor_nextn	(	tr_itor *	itor,
		size_t	count )

Move |itor| |count| elements forward and return whether it is still positioned.

It becomes unpositioned if it runs past the last element.

Definition at line 322 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_prev()

bool tr_itor_prev

(

tr_itor *

itor

)

Move |itor| to the previous element in key order and return true, or unposition it and return false if there is none.

An unpositioned iterator stays unpositioned and returns false.

Definition at line 321 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_prevn()

bool tr_itor_prevn	(	tr_itor *	itor,
		size_t	count )

Move |itor| |count| elements back and return whether it is still positioned.

It becomes unpositioned if it runs past the first element.

Definition at line 323 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_remove()

bool tr_itor_remove

(

tr_itor *

itor

)

Remove the element |itor| is positioned on and unposition |itor|; return false if it was not positioned.

No delete function is called, so fetch the key and datum first if they need freeing. See Iterator invalidation for which iterators this invalidates.

Definition at line 336 of file tr_tree.c.

tr_itor_search()

bool tr_itor_search	(	tr_itor *	itor,
		const void *	key )

Position |itor| on |key| and return true, or unposition it and return false if |key| is not present.

Definition at line 326 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_search_ge()

bool tr_itor_search_ge	(	tr_itor *	itor,
		const void *	key )

Position |itor| on the least key greater than or equal to |key| and return true, or unposition it and return false if there is none.

Definition at line 329 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_search_gt()

bool tr_itor_search_gt	(	tr_itor *	itor,
		const void *	key )

Position |itor| on the least key greater than |key| and return true, or unposition it and return false if there is none.

Definition at line 330 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_search_le()

bool tr_itor_search_le	(	tr_itor *	itor,
		const void *	key )

Position |itor| on the greatest key less than or equal to |key| and return true, or unposition it and return false if there is none.

Definition at line 327 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_search_lt()

bool tr_itor_search_lt	(	tr_itor *	itor,
		const void *	key )

Position |itor| on the greatest key less than |key| and return true, or unposition it and return false if there is none.

Definition at line 328 of file tr_tree.c.

Here is the call graph for this function:

tr_itor_valid()

bool tr_itor_valid

(

const tr_itor *

itor

)

Return whether |itor| is positioned on an element.

Definition at line 318 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_clear()

size_t tr_tree_clear	(	tr_tree *	tree,
		dict_delete_func	delete_func )

Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL.

Returns the number of elements removed. The tree stays usable. See Iterator invalidation for which iterators this invalidates.

Definition at line 148 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_count()

size_t tr_tree_count

(

const tr_tree *

tree

)

Return the number of elements.

Takes O(1) time.

Definition at line 237 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_free()

size_t tr_tree_free	(	tr_tree *	tree,
		dict_delete_func	delete_func )

Remove every element, calling |delete_func|(key, datum) for each unless |delete_func| is NULL, and free the tree.

Returns the number of elements removed. Iterators over the tree may afterwards only be freed.

Definition at line 147 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_insert()

dict_insert_result tr_tree_insert	(	tr_tree *	tree,
		void *	key )

Insert |key| unless an equal key is present.

Returns {&datum, true} for a new key, whose datum starts as NULL; the tree stores the |key| pointer itself, it does not copy the key. If an equal key is present, returns {&datum, false} with that key's datum, and |key| is not stored and still belongs to the caller. Returns {NULL, false} if memory cannot be allocated.

Definition at line 151 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_max_path_length()

size_t tr_tree_max_path_length

(

const tr_tree *

tree

)

Return the greatest depth of any node, the root being at depth 1, or 0 for an empty tree: the height of the tree.

A statistic for testing and benchmarking.

Definition at line 239 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_min_path_length()

size_t tr_tree_min_path_length

(

const tr_tree *

tree

)

Return the shallowest depth at which a child link is absent, the root being at depth 1, or 0 for an empty tree.

A statistic for testing and benchmarking.

Definition at line 238 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_new()

tr_tree * tr_tree_new	(	dict_compare_func	compare_func,
		dict_prio_func	prio_func )

Create an empty treap that orders keys with |compare_func| (must not be NULL) and takes node priorities from |prio_func|, or at random if |prio_func| is NULL.

A larger priority places a key closer to the root. Returns NULL if memory cannot be allocated.

Definition at line 118 of file tr_tree.c.

tr_tree_remove()

dict_remove_result tr_tree_remove	(	tr_tree *	tree,
		const void *	key )

Remove the element with key |key|.

Returns {key, datum, true}, handing the stored key and datum back to the caller (no delete function is called), or {NULL, NULL, false} if |key| is not present. See Iterator invalidation for which iterators this invalidates.

Definition at line 220 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_search()

void ** tr_tree_search	(	tr_tree *	tree,
		const void *	key )

Return the address of the datum stored for |key|, or NULL if |key| is not present.

Definition at line 230 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_search_ge()

void ** tr_tree_search_ge	(	tr_tree *	tree,
		const void *	key )

Return the address of the datum of the least key greater than or equal to |key|, or NULL if there is none.

Definition at line 233 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_search_gt()

void ** tr_tree_search_gt	(	tr_tree *	tree,
		const void *	key )

Return the address of the datum of the least key greater than |key|, or NULL if there is none.

Definition at line 234 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_search_le()

void ** tr_tree_search_le	(	tr_tree *	tree,
		const void *	key )

Return the address of the datum of the greatest key less than or equal to |key|, or NULL if there is none.

Definition at line 231 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_search_lt()

void ** tr_tree_search_lt	(	tr_tree *	tree,
		const void *	key )

Return the address of the datum of the greatest key less than |key|, or NULL if there is none.

Definition at line 232 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_select()

bool tr_tree_select	(	tr_tree *	tree,
		size_t	n,
		const void **	key,
		void **	datum )

Store the key and datum of the |n|th element in key order (0-based) through |key| and |datum| and return true, or store NULL through them and return false if |n| is out of range.

Either may be NULL. Takes O(n) time.

Definition at line 236 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_total_path_length()

size_t tr_tree_total_path_length

(

const tr_tree *

tree

)

Return the sum of the depths of all nodes, the root being at depth 1, or 0 for an empty tree.

A statistic for testing and benchmarking.

Definition at line 240 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_traverse()

size_t tr_tree_traverse	(	tr_tree *	tree,
		dict_visit_func	visit,
		void *	user_data )

Call |visit|(key, datum, |user_data|) for each element in key order, stopping early if |visit| returns false.

Returns the number of calls made.

Definition at line 235 of file tr_tree.c.

Here is the call graph for this function:

tr_tree_verify()

bool tr_tree_verify

(

const tr_tree *

tree

)

Check the internal invariants of the tree and return true if they hold, or print the first failed check to stderr and return false.

Meant for testing and debugging; takes O(n) time.

Definition at line 260 of file tr_tree.c.

Here is the call graph for this function: