usual/aatree.h File Reference

AA-Tree - Binary tree with embeddable nodes. More...

Data Structures
struct	AATree
	Tree header, for storing helper functions. More...
struct	AANode
	Tree node. More...
Typedefs
typedef int(*	aatree_cmp_f )(uintptr_t, struct AANode *node)
	Callback for node comparision against value.
typedef void(*	aatree_walker_f )(struct AANode *n, void *arg)
	Callback for walking the tree.
Enumerations
enum	AATreeWalkType
	Walk order types. More...
Functions
void	aatree_init (struct AATree *tree, aatree_cmp_f cmpfn, aatree_walker_f release_cb)
	Initialize structure.
struct AANode *	aatree_search (struct AATree *tree, uintptr_t value)
	Search for node.
void	aatree_insert (struct AATree *tree, uintptr_t value, struct AANode *node)
	Insert new node.
void	aatree_remove (struct AATree *tree, uintptr_t value)
	Remote node.
void	aatree_walk (struct AATree *tree, enum AATreeWalkType wtype, aatree_walker_f walker, void *arg)
	Walk over all nodes.
void	aatree_destroy (struct AATree *tree)
	Free.
static int	aatree_is_nil_node (const struct AANode *node)
	Check if terminal node.

---

Detailed Description

AA-Tree - Binary tree with embeddable nodes.

AA-Tree (Arne Andersson tree) is a simplified Red-Black tree.

---

Typedef Documentation

typedef int(* aatree_cmp_f)(uintptr_t, struct AANode *node)

Callback for node comparision against value.

typedef void(* aatree_walker_f)(struct AANode *n, void *arg)

Callback for walking the tree.

---

Enumeration Type Documentation

enum AATreeWalkType

Walk order types.

---

Function Documentation

void aatree_init	(	struct AATree *	tree,
		aatree_cmp_f	cmpfn,
		aatree_walker_f	release_cb
	)

Initialize structure.

struct AANode* aatree_search	(	struct AATree *	tree,
		uintptr_t	value
	)		[read]

Search for node.

void aatree_insert	(	struct AATree *	tree,
		uintptr_t	value,
		struct AANode *	node
	)

Insert new node.

void aatree_remove	(	struct AATree *	tree,
		uintptr_t	value
	)

Remote node.

void aatree_walk	(	struct AATree *	tree,
		enum AATreeWalkType	wtype,
		aatree_walker_f	walker,
		void *	arg
	)

Walk over all nodes.

void aatree_destroy

(

struct AATree *

tree

)

Free.

static int aatree_is_nil_node

(

const struct AANode *

node

)

[inline, static]

Check if terminal node.

References AANode::left.