Temporarily move taskq+util to libzpool until that directory is broken in to lib...

[zfs.git] / zfs / lib / libavl / avl.c

diff --git a/zfs/lib/libavl/avl.c b/zfs/lib/libavl/avl.c
index ff3ad52..c9727c6 100644 (file)
--- a/zfs/lib/libavl/avl.c
+++ b/zfs/lib/libavl/avl.c
@@ -19,11 +19,11 @@
  * CDDL HEADER END
  */
 /*
- * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
+ * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  * Use is subject to license terms.
  */
 
-
+#pragma ident  "%Z%%M% %I%     %E% SMI"
 
 
 /*
@@ -808,6 +808,64 @@ avl_remove(avl_tree_t *tree, void *data)
        } while (parent != NULL);
 }
 
+#define        AVL_REINSERT(tree, obj)         \
+       avl_remove((tree), (obj));      \
+       avl_add((tree), (obj))
+
+boolean_t
+avl_update_lt(avl_tree_t *t, void *obj)
+{
+       void *neighbor;
+
+       ASSERT(((neighbor = AVL_NEXT(t, obj)) == NULL) ||
+           (t->avl_compar(obj, neighbor) <= 0));
+
+       neighbor = AVL_PREV(t, obj);
+       if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) {
+               AVL_REINSERT(t, obj);
+               return (B_TRUE);
+       }
+
+       return (B_FALSE);
+}
+
+boolean_t
+avl_update_gt(avl_tree_t *t, void *obj)
+{
+       void *neighbor;
+
+       ASSERT(((neighbor = AVL_PREV(t, obj)) == NULL) ||
+           (t->avl_compar(obj, neighbor) >= 0));
+
+       neighbor = AVL_NEXT(t, obj);
+       if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) {
+               AVL_REINSERT(t, obj);
+               return (B_TRUE);
+       }
+
+       return (B_FALSE);
+}
+
+boolean_t
+avl_update(avl_tree_t *t, void *obj)
+{
+       void *neighbor;
+
+       neighbor = AVL_PREV(t, obj);
+       if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) {
+               AVL_REINSERT(t, obj);
+               return (B_TRUE);
+       }
+
+       neighbor = AVL_NEXT(t, obj);
+       if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) {
+               AVL_REINSERT(t, obj);
+               return (B_TRUE);
+       }
+
+       return (B_FALSE);
+}
+
 /*
  * initialize a new AVL tree
  */
@@ -853,6 +911,12 @@ avl_numnodes(avl_tree_t *tree)
        return (tree->avl_numnodes);
 }
 
+boolean_t
+avl_is_empty(avl_tree_t *tree)
+{
+       ASSERT(tree);
+       return (tree->avl_numnodes == 0);
+}
 
 #define        CHILDBIT        (1L)