AVL(2) AVL(2)
NAME
mkavltree, insertavl, lookupavl, deleteavl, avlwalk,
avlnext, avlprev - AVL trees
SYNOPSIS
#include <u.h>
#include <libc.h>
#include <avl.h>
typedef struct Avl Avl;
typedef struct Avltree Avltree;
typedef struct Avlwalk Avlwalk;
Avltree *mkavltree(int(*cmp)(Avl*, Avl*));
void insertavl(Avltree *tree, Avl *new, Avl **oldp);
Avl *lookupavl(Avltree *tree, Avl *key);
void deleteavl(Avltree *tree, Avl *key, Avl **oldp);
Avlwalk *avlwalk(Avltree *tree);
Avl *avlnext(Avlwalk *walk);
Avl *avlprev(Avlwalk *walk);
void endwalk(Avlwalk *walk);
DESCRIPTION
These routines manage in-memory databasea stored as self-
balancing AVL trees. Each node in the tree is supposed to
contain a Avl structure. The tree is created by a call to
mkavltree supplying a function to compare two nodes.
Nodes can be added to the tree by calling insertavl using
the Avltree returned by mkavltree and the node to insert.
They are removed by deleteavl and giving as key a node used
as a key to locate the node to be deleted. The routine
returns in oldp a node to be released by the user.
Entries can be searched by calling lookupavl and giving a
example node that is used as the search key.
Iteration over the nodes is provided by avlwalk (which cre-
ates a new iterator), avlnext (which returns a new node, in
order, each time called), and endwalk (which releases the
iterator). The function avlprev moves backwards in the iter-
ation order, determined by the compare function given to
mkavltree.
Page 1 Plan 9 (printed 12/22/24)
AVL(2) AVL(2)
SOURCE
/sys/src/libavl
SEE ALSO
Lewis & Denenberg, Data Structures and Their Algorithms .
HISTORY
These functions were extracted from replica(8) programs to
be used also in repl(8) and other tools.
Page 2 Plan 9 (printed 12/22/24)