NAME

SYNOPSIS

#include <u.h>
#include <libc.h>
#include <avl.h>

typedef struct Avl Avl;
struct Avl
{
	Avl	*p;		/* parent */
	Avl	*n[2];		/* children */
	int	bal;		/* balance bits */
};

Avl	*avlnext(Avlwalk *walk);
Avl	*avlprev(Avlwalk *walk);
Avlwalk	*avlwalk(Avltree *tree);
void	deleteavl(Avltree *tree, Avl *key, Avl **oldp);
void	endwalk(Avlwalk *walk);
void	insertavl(Avltree *tree, Avl *new, Avl **oldp);
Avl	*lookupavl(Avltree *tree, Avl *key);
Avl	*searchavl(Avltree *tree, Avl *key, int neighbor);
Avltree	*mkavltree(int(*cmp)(Avl*, Avl*));

DESCRIPTION

An empty AVL tree is created by calling mkavltree with a comparison function as argument. This function should take two pointers to Avl objects and return -1, 0 or 1 as the first is respectively less than, equal to, or greater than, the second. Insertavl adds a new tree node into tree. If oldp is non-nil upon return, it points to storage for an old node with the same key that may now be freed. Lookupavl returns the tree node that matches key by tree's comparison function, or nil if none.

Searchavl returns the tree node that matches key by tree's comparison function, if it exists. If it does not, and neighbor is positive, it returns the nearest node whose key is greater or nil if there is none and, if neighbor is negative, it returns the nearest node whose key is less or nil if there is none. It is an error to set neighbor to values other than -1, 0, or +1.

Deleteavl removes the node matching key from tree; oldp is handled as per insertavl.

Avlwalk returns a pointer to a newly-allocated Avlwalk object. Endwalk frees such an object. Avlnext and avlprev walk the tree associated with walk, returning the next (respectively, previous) tree node in the comparison order defined by the comparison function associated with the tree associated with walk.

EXAMPLES

typedef struct Node {
	Avl;
	uchar	score[VtScoreSize];
	int	type;
} Node;

Avltree *tree;
Avl *res;
Node *np;
...
	res = lookupavl(tree, np);
    

SOURCE

SEE ALSO

DIAGNOSTICS