aboutsummaryrefslogtreecommitdiff
path: root/cddl/contrib/opensolaris/common
diff options
context:
space:
mode:
authorRui Paulo <rpaulo@FreeBSD.org>2010-08-02 13:40:53 +0000
committerRui Paulo <rpaulo@FreeBSD.org>2010-08-02 13:40:53 +0000
commit1670a1c2a47d10ecccd001970b859caf93cd3b6e (patch)
tree3fd229f631527cecfed36a148a8b8d4077b143b5 /cddl/contrib/opensolaris/common
parent46514c778360a66b0715d4df1e2b752b06bb49ff (diff)
parente0ea83ebb1a4b194c927cb114766e8781676380b (diff)
downloadsrc-1670a1c2a47d10ecccd001970b859caf93cd3b6e.tar.gz
src-1670a1c2a47d10ecccd001970b859caf93cd3b6e.zip
MFV OpenSolaris DTrace userland bits.
Notes
Notes: svn path=/head/; revision=210767
Diffstat (limited to 'cddl/contrib/opensolaris/common')
-rw-r--r--cddl/contrib/opensolaris/common/avl/avl.c71
1 files changed, 66 insertions, 5 deletions
diff --git a/cddl/contrib/opensolaris/common/avl/avl.c b/cddl/contrib/opensolaris/common/avl/avl.c
index 7403e813014c..dd39c12d215e 100644
--- a/cddl/contrib/opensolaris/common/avl/avl.c
+++ b/cddl/contrib/opensolaris/common/avl/avl.c
@@ -19,13 +19,10 @@
* CDDL HEADER END
*/
/*
- * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
+ * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
-#pragma ident "%Z%%M% %I% %E% SMI"
-
-
/*
* AVL - generic AVL tree implementation for kernel use
*
@@ -243,7 +240,7 @@ avl_nearest(avl_tree_t *tree, avl_index_t where, int direction)
* "void *" of the found tree node
*/
void *
-avl_find(avl_tree_t *tree, void *value, avl_index_t *where)
+avl_find(avl_tree_t *tree, const void *value, avl_index_t *where)
{
avl_node_t *node;
avl_node_t *prev = NULL;
@@ -808,6 +805,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 +908,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)