X-Git-Url: https://git.verplant.org/?a=blobdiff_plain;f=src%2Futils_avltree.c;h=830b711f8f9713d45bfe5b898995b2ac5f85b7ae;hb=f4c3e684850315991f0760e90f5d845af4615d5f;hp=f445e21e4b36fbe97f96409346980a0a3307e755;hpb=2a1ad78f89dce9c00ad7fc02b5cb4ce598bb1d48;p=collectd.git

diff --git a/src/utils_avltree.c b/src/utils_avltree.c
index f445e21e..830b711f 100644
--- a/src/utils_avltree.c
+++ b/src/utils_avltree.c
@@ -332,7 +332,7 @@ void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
 	}
 
 	return (r);
-}
+} /* void *avl_node_prev */
 
 static int _remove (avl_tree_t *t, avl_node_t *n)
 {
@@ -583,6 +583,44 @@ avl_iterator_t *avl_get_iterator (avl_tree_t *t)
 	return (avl_create_iterator (t, n));
 } /* avl_iterator_t *avl_get_iterator */
 
+int avl_pick (avl_tree_t *t, void **key, void **value)
+{
+	avl_node_t *n;
+	avl_node_t *p;
+
+	assert ((key != NULL) && (value != NULL));
+	if (t->root == NULL)
+		return (-1);
+
+	n = t->root;
+	while ((n->left != NULL) || (n->right != NULL))
+	{
+		int height_left  = (n->left  == NULL) ? 0 : n->left->height;
+		int height_right = (n->right == NULL) ? 0 : n->right->height;
+
+		if (height_left > height_right)
+			n = n->left;
+		else
+			n = n->right;
+	}
+
+	p = n->parent;
+	if (p == NULL)
+		t->root = NULL;
+	else if (p->left == n)
+		p->left = NULL;
+	else
+		p->right = NULL;
+
+	*key   = n->key;
+	*value = n->value;
+
+	free_node (n);
+	rebalance (t, p);
+
+	return (0);
+} /* int avl_pick */
+
 void *avl_iterator_next (avl_iterator_t *iter)
 {
 	avl_node_t *n;