src/bst.h File Reference

A simple (non-balancing) binary search tree. More...

#include <string.h>
#include <stdbool.h>
#include "cdsa_types.h"

Include dependency graph for bst.h:

Go to the source code of this file.

Typedefs
typedef struct Bst	Bst
	The type of the binary search tree.
Functions
Core Functions
cdsa_status_t	bst_new (Bst **new_bst, cdsa_compare_func_t compare, cdsa_destroy_map_func_t destroy)
	Create a new binary search tree using the given compare function for ordering the nodes, setting *new_bst to the new tree on success.
cdsa_status_t	bst_destroy (Bst **tree)
	Destroy the tree pointed to and free its associated memory if tree and *tree are both non-NULL, and call the destroy function on each (key, value) pair in the tree if the function was non-NULL when the tree was created.
cdsa_status_t	bst_is_empty (const Bst *const tree, bool *is_empty)
	Answer if the tree contains at least 1 (key, value) pair, recording result in *is_empty if tree is valid.
cdsa_status_t	bst_size (const Bst *const tree, size_t *size)
	Answer the size of the tree if non-NULL, recording result in *size.
cdsa_status_t	bst_has_key (const Bst *const tree, const void *const key, bool *has_key)
	Answer whether tree contains key, recording result in *has_key.
cdsa_status_t	bst_get (const Bst *const tree, const void *const key, void *ptr)
	Answer the value, if any, for the key in tree, setting *ptr to value.
cdsa_status_t	bst_put (Bst *const tree, const void *const key, void *const value, void *prev)
	Put the (key, value) pair in the tree, setting *prev to the previous value for the given key if there was a previous value.
cdsa_status_t	bst_remove (Bst *const tree, const void *const key, void *prev_val)
	Remove the (key, value) pair for the given key from the tree, setting *prev_val to the value for the given key.
Additional Functions
cdsa_status_t	bst_predecessor (Bst *tree, void *key, void *pred)
	Answer a pointer to the predecessor of key in tree according to the compare function, recording result in *pred if key is in tree and has a predecessor.
cdsa_status_t	bst_successor (Bst *tree, void *key, void *succ)
	Answer a pointer to the successor of key in tree according to the compare function, recording result in *succ if key is in tree and has a successor.
cdsa_status_t	bst_min (Bst *tree, void *min_key)
	Answer a pointer to the smallest key in the tree according to the compare function, recording result in *min_key if tree is not empty.
cdsa_status_t	bst_max (Bst *tree, void *max_key)
	Answer a pointer to the largest key in the tree according to the compare function, recording result in *max_key if tree is not empty.
cdsa_status_t	bst_pre_order_walk (Bst *tree, cdsa_visit_map_func_t f)
	Perform pre-order walk over tree, calling the given function on each (key, value) pair in the tree (no-op if either arg is NULL).
cdsa_status_t	bst_in_order_walk (Bst *tree, cdsa_visit_map_func_t f)
	Perform in-order walk over tree, calling the given function on each (key, value) pair in the tree (no-op if either arg is NULL).
cdsa_status_t	bst_post_order_walk (Bst *tree, cdsa_visit_map_func_t f)
	Perform post-order walk over tree, calling the given function on each (key, value) pair in the tree (no-op if either arg is NULL).

---

Detailed Description

A simple (non-balancing) binary search tree.

This binary search tree implementation provides most operations in time proportional to the height of the tree, but it does NOT do any balancing or restructuring of the tree.

NULL values are permitted, but NULL keys are not. Duplicate keys are not allowed: any puts for an existing key replace the old value.

Since this implementation does not do any balancing, it is only suitable for use with large trees if you know or ensure that your data is reasonably random.

See randbst.h for a self-balancing tree.

Definition in file bst.h.

---

Typedef Documentation

Bst

The type of the binary search tree.

Functions are declared below for creating, destroying and manipulating a bst.

Definition at line 39 of file bst.h.

---

Function Documentation

cdsa_status_t bst_new	(	Bst **	new_bst,
		cdsa_compare_func_t	compare,
		cdsa_destroy_map_func_t	destroy
	)

Create a new binary search tree using the given compare function for ordering the nodes, setting *new_bst to the new tree on success.

Parameters:

	new_bst	A non-NULL pointer to a Bst pointer, which will be set to the newly created Bst on success.
	compare	A non-NULL function for comparing the keys of elements in the tree.
	destroy	A function to be applied to every (key, value) pair in the tree when bst_destroy is called, or NULL.

cdsa_status_t bst_destroy

(

Bst **

tree

)

Destroy the tree pointed to and free its associated memory if tree and *tree are both non-NULL, and call the destroy function on each (key, value) pair in the tree if the function was non-NULL when the tree was created.

Parameters:

tree

A non-NULL pointer to a Bst pointer, which is set to NULL success after the tree is destroyed.

cdsa_status_t bst_is_empty	(	const Bst *const	tree,
		bool *	is_empty
	)

Answer if the tree contains at least 1 (key, value) pair, recording result in *is_empty if tree is valid.

Parameters:

	tree	A non-NULL tree.
	is_empty	A non-NULL pointer to a bool to be set to true if tree is empty and to false if it contains elements.

cdsa_status_t bst_size	(	const Bst *const	tree,
		size_t *	size
	)

Answer the size of the tree if non-NULL, recording result in *size.

Parameters:

	tree	A non-NULL tree.
	size	A non-NULL pointer to a size_t variable, which will be set to the size of the tree if tree on success.

cdsa_status_t bst_has_key	(	const Bst *const	tree,
		const void *const	key,
		bool *	has_key
	)

Answer whether tree contains key, recording result in *has_key.

Parameters:

	tree	A non-NULL tree.
	key	A non-NULL key.
	has_key	A non-NULL pointer to a bool variable, which will be set to true if tree contains key and to false if tree and key are non-NULL and key is not in tree.

cdsa_status_t bst_get	(	const Bst *const	tree,
		const void *const	key,
		void *	ptr
	)

Answer the value, if any, for the key in tree, setting *ptr to value.

Parameters:

	tree	A non-NULL tree.
	key	A non-NULL key.
	ptr	A non-NULL pointer to the client pointer to store result on success.

Returns:

If key was in tree and value was retrieved, returns CDSA_SUCCESS; if not in tree, returns CDSA_NO_RESULT; other codes indicate an error.

cdsa_status_t bst_put	(	Bst *const	tree,
		const void *const	key,
		void *const	value,
		void *	prev
	)

Put the (key, value) pair in the tree, setting *prev to the previous value for the given key if there was a previous value.

Parameters:

	tree	A non-NULL tree.
	key	A non-NULL key.
	value	A pointer to the value, possibly NULL.
	prev	A non-NULL pointer to a client pointer, which will be set to the previous value for the given key if there was one.

cdsa_status_t bst_remove	(	Bst *const	tree,
		const void *const	key,
		void *	prev_val
	)

Remove the (key, value) pair for the given key from the tree, setting *prev_val to the value for the given key.

Parameters:

	tree	A non-NULL tree.
	key	A non-NULL key.
	prev_val	A non-NULL pointer to a client pointer, which will be set to the value for the given key before removal if key was in tree (and otherwise not set).

Returns:

If key was in tree and was removed, returns CDSA_SUCCESS; if not in tree, returns CDSA_NO_RESULT; other codes indicate an error.