libavl: lookup can return the closest match

[plan9front.git] / sys / include / avl.h

diff --git a/sys/include/avl.h b/sys/include/avl.h
index 242ee1ba3bce0ca7ebb2cf85a698330e4ce44723..be7b18a5c8ac813c0f3f50017cbb434574962a7b 100644 (file)
--- a/sys/include/avl.h
+++ b/sys/include/avl.h
@@ -1,26 +1,24 @@
-#pragma        lib     "libavl.a"
+#pragma lib "libavl.a"
 #pragma src "/sys/src/libavl"
 
-typedef struct Avl     Avl;
-typedef struct Avltree Avltree;
-typedef struct Avlwalk Avlwalk;
+typedef struct Avl Avl;
+typedef struct Avltree Avltree;
 
-#pragma incomplete Avltree
-#pragma incomplete Avlwalk
+struct Avl {
+       Avl *c[2];
+       Avl *p;
+       schar balance;
+};
 
-struct Avl
-{
-       Avl     *p;             /* parent */
-       Avl     *n[2];          /* children */
-       int     bal;            /* balance bits */
+struct Avltree {
+       int (*cmp)(Avl*, Avl*);
+       Avl *root;
 };
 
-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);
-Avltree        *mkavltree(int(*cmp)(Avl*, Avl*));
-Avl*   searchavl(Avltree *tree, Avl *key, int neighbor);
+Avltree *avlinit(Avltree*, int(*)(Avl*, Avl*));
+Avltree *avlcreate(int(*)(Avl*, Avl*));
+Avl *avllookup(Avltree*, Avl*, int);
+Avl *avldelete(Avltree*, Avl*);
+Avl *avlinsert(Avltree*, Avl*);
+Avl *avlnext(Avl*);
+Avl *avlprev(Avl*);