bloodhound.h File Reference

C89 implementation of an AVL self-balancing binary search tree with intrusive nodes. More...

#include <stddef.h>

Go to the source code of this file.

Classes
struct	AvlTree
	AVL self-balancing binary search tree. More...
struct	AvlNode
	Intrusive AVL tree node. More...

Typedefs
typedef int(*	AvlComparator) (const AvlNode *, const AvlNode *, void *)
typedef int(*	AvlHetComparator) (const void *, const AvlNode *, void *)
typedef void(*	AvlTraverseCb) (void *, const AvlNode *)
typedef void(*	AvlTraverseMutCb) (void *, AvlNode *)
typedef void(*	AvlDeleter) (AvlNode *, void *)

Functions
void	AvlTree_new (AvlTree *self, AvlComparator compare, void *compare_arg, AvlDeleter deleter, void *deleter_arg)
	Initializes an empty AvlTree. More...
void	AvlTree_drop (AvlTree *self)
	Drops an AvlTree, removing all members. More...
const AvlNode *	AvlTree_get (const AvlTree *self, const void *key, AvlHetComparator compare, void *arg)
AvlNode *	AvlTree_get_mut (AvlTree *self, const void *key, AvlHetComparator compare, void *arg)
AvlNode *	AvlTree_insert (AvlTree *self, AvlNode *node)
	Inserts an element into an AvlTree. More...
AvlNode *	AvlTree_get_or_insert (AvlTree *self, const void *key, AvlHetComparator compare, void *compare_arg, AvlNode *(*insert)(const void *, void *), void *insert_arg, int *inserted)
	Inserts an element into an AvlTree if no element with a matching key is found. More...
AvlNode *	AvlTree_remove (AvlTree *self, const void *key, AvlHetComparator compare, void *arg)
	Removes the node that compares equal to a key. More...
void	AvlTree_clear (AvlTree *self)
	Clears the tree, removing all members. More...

Detailed Description

C89 implementation of an AVL self-balancing binary search tree with intrusive nodes.

Function Documentation

void AvlTree_clear

(

AvlTree *

self

)

Clears the tree, removing all members.

Parameters

self	Must not be NULL. Must be initialized.

void AvlTree_drop

(

AvlTree *

self

)

Drops an AvlTree, removing all members.

Equivalent to AvlTree_clear.

Parameters

self	Must not be NULL. Must be initialized.

const AvlNode* AvlTree_get	(	const AvlTree *	self,
		const void *	key,
		AvlHetComparator	compare,
		void *	arg
	)

Parameters

self	Must not be NULL. Must be initialized.
compare	Must not be NULL. Must form the same total ordering over the contained elements as the one formed by one passed to AvlTree_new. Will be invoked by compare(key, node, arg).

Returns

A pointer to the node that compares equal to key, if there is one.

AvlNode* AvlTree_get_mut	(	AvlTree *	self,
		const void *	key,
		AvlHetComparator	compare,
		void *	arg
	)

Parameters

self	Must not be NULL. Must be initialized.
compare	Must not be NULL. Must form the same total ordering over the contained elements as the one formed by one passed to AvlTree_new. Will be invoked by compare(key, node, arg).

Returns

A mutable pointer to the node that compares equal to key, if there is one.

AvlNode* AvlTree_get_or_insert	(	AvlTree *	self,
		const void *	key,
		AvlHetComparator	compare,
		void *	compare_arg,
		AvlNode *(*)(const void *, void *)	insert,
		void *	insert_arg,
		int *	inserted
	)

Inserts an element into an AvlTree if no element with a matching key is found.

Parameters

self	Must not be NULL. Must be initialized.
compare	Must not be NULL. Must form the same total ordering over the contained elements as the one formed by one passed to AvlTree_new. Will be invoked by compare(key, node, compare_arg).
insert	Must not be NULL. If no element that compares equal to key is found, will be invoked by insert(key, insert_arg) to obtain a new node. Its return value must compare equal to key.
inserted	If not NULL, will be set to 1 if insert was called. Otherwise will be set to 0.

Returns

The element that compares equal to key or was just inserted.

AvlNode* AvlTree_insert	(	AvlTree *	self,
		AvlNode *	node
	)

Inserts an element into an AvlTree.

Parameters

self	Must not be NULL. Must be initialized.
node	Must not be NULL.

Returns

The previous element that compares equal to node, if there was one.

void AvlTree_new	(	AvlTree *	self,
		AvlComparator	compare,
		void *	compare_arg,
		AvlDeleter	deleter,
		void *	deleter_arg
	)

Initializes an empty AvlTree.

Parameters

self	Must not be NULL. Must not be initialized.
compare	Must not be NULL. Will be invoked to compare nodes by compare(lhs, rhs, compare_arg). Return values should have the same meaning as strcmp and should form a total ordering over the set of nodes.
deleter	Must not be NULL. Will be used to free nodes when they are no longer usable by the tree as if by deleter(node, deleter_arg).

AvlNode* AvlTree_remove	(	AvlTree *	self,
		const void *	key,
		AvlHetComparator	compare,
		void *	arg
	)

Removes the node that compares equal to a key.

Parameters

self	Must not be NULL.
compare	Must not be NULL. Must form the same total ordering over the set of nodes as the one passed to AvlTree_new. Will be invoked to compare the key to nodes by compare(key, node, arg).

Returns

The node that compared equal to key, if there was one.