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. 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.