gp_avl_tree.h File Reference

AVL tree implementation. More...

#include <core/gp_compiler.h>

Go to the source code of this file.

Data Structures
struct	gp_avl_node
	AVL tree node. More...

Typedefs
typedef struct gp_avl_node	gp_avl_node
	AVL tree node.

Functions
static unsigned int	gp_avl_tree_depth (gp_avl_node *root)
	Returns AVL tree depth.
static gp_avl_node *	gp_avl_tree_ins (gp_avl_node *root, gp_avl_node *node, int(*cmp)(gp_avl_node *a, gp_avl_node *b))
	Inserts a node into an AVL tree.
static gp_avl_node *	gp_avl_tree_del_min (gp_avl_node *root, gp_avl_node **min)
	Removes a minimal node from an AVL tree.
static gp_avl_node *	gp_avl_tree_del_max (gp_avl_node *root, gp_avl_node **max)
	Removes a maximal node from an AVL tree.
static gp_avl_node *	gp_avl_tree_del (gp_avl_node *root, const void *key, gp_avl_node **del, int(*cmp)(gp_avl_node *a, const void *key))
	Removes a node by a key from an AVL tree.
static gp_avl_node *	gp_avl_tree_lookup (gp_avl_node *root, const void *key, int(*cmp)(gp_avl_node *a, const void *key))
	Looks up a node by a key.

Detailed Description

AVL tree implementation.

Definition in file gp_avl_tree.h.

Typedef Documentation

gp_avl_node

typedef struct gp_avl_node gp_avl_node

AVL tree node.

The node is supposed to be embedded in a user structure.

Function Documentation

gp_avl_tree_del()

static gp_avl_node * gp_avl_tree_del ( gp_avl_node * root, const void * key, gp_avl_node ** del, int(* cmp )(gp_avl_node *a, const void *key) )

inlinestatic

Removes a node by a key from an AVL tree.

Parameters

root	An AVL tree root.
key	A key to look the node by.
del	A pointer to store the removed node to.
cmp	A node comparsion callback.

Returns

A new tree root.

Definition at line 229 of file gp_avl_tree.h.

References gp_avl_tree_del(), gp_avl_tree_del_min(), gp_avl_node::left, and gp_avl_node::right.

Referenced by gp_avl_tree_del().

gp_avl_tree_del_max()

static gp_avl_node * gp_avl_tree_del_max ( gp_avl_node * root, gp_avl_node ** max )

inlinestatic

Removes a maximal node from an AVL tree.

Parameters

root	An AVL tree root.
max	A pointer to store the maximal node to.

Returns

A new tree root.

Definition at line 200 of file gp_avl_tree.h.

References gp_avl_tree_del_max(), gp_avl_node::left, and gp_avl_node::right.

Referenced by gp_avl_tree_del_max().

gp_avl_tree_del_min()

static gp_avl_node * gp_avl_tree_del_min ( gp_avl_node * root, gp_avl_node ** min )

inlinestatic

Removes a minimal node from an AVL tree.

Parameters

root	An AVL tree root.
min	A pointer to store the minimal node to.

Returns

A new tree root.

Definition at line 173 of file gp_avl_tree.h.

References gp_avl_tree_del_min(), gp_avl_node::left, and gp_avl_node::right.

Referenced by gp_avl_tree_del(), and gp_avl_tree_del_min().

gp_avl_tree_depth()

static unsigned int gp_avl_tree_depth ( gp_avl_node * root )

inlinestatic

Returns AVL tree depth.

Parameters

root	An AVL tree root.

Returns

An AVL tree depth.

Definition at line 39 of file gp_avl_tree.h.

References gp_avl_node::depth.

gp_avl_tree_ins()

static gp_avl_node * gp_avl_tree_ins ( gp_avl_node * root, gp_avl_node * node, int(* cmp )(gp_avl_node *a, gp_avl_node *b) )

inlinestatic

Inserts a node into an AVL tree.

Parameters

root	An AVL tree root.
node	A node to be insterted.
cmp	A node comparsion callback.

Returns

A new tree root.

Definition at line 157 of file gp_avl_tree.h.

References gp_avl_node::depth, gp_avl_node::left, and gp_avl_node::right.

gp_avl_tree_lookup()

static gp_avl_node * gp_avl_tree_lookup ( gp_avl_node * root, const void * key, int(* cmp )(gp_avl_node *a, const void *key) )

inlinestatic

Looks up a node by a key.

Parameters

root	An AVL tree root.
key	A key to look the node by.
cmp	A node comparsion callback.

Returns

A looked up node or NULL if not found.

Definition at line 278 of file gp_avl_tree.h.

References gp_avl_tree_lookup(), gp_avl_node::left, and gp_avl_node::right.

Referenced by gp_avl_tree_lookup().