AVL(2)                                                     AVL(2)

          mkavltree, insertavl, lookupavl, deleteavl, avlwalk,
          avlnext, avlprev - AVL trees

          #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);

          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

     Page 1                       Plan 9            (printed 10/20/21)

     AVL(2)                                                     AVL(2)


          Lewis & Denenberg, Data Structures and Their Algorithms .

          These functions were extracted from replica(8) programs to
          be used also in repl(8) and other tools.

     Page 2                       Plan 9            (printed 10/20/21)