From 6b95d15beca00fb69dd4eaceeb101ea49f9fcb04 Mon Sep 17 00:00:00 2001
From: Florian Forster <octo@leeloo.lan.home.verplant.org>
Date: Sat, 25 Nov 2006 11:21:19 +0100
Subject: [PATCH] src/utils_avltree.[ch]: Changed the interface to return the
 key upon deletion.

The idea behind this is, that the calling routing may not have a pointer to
it's location, and possibly can't deallocate the memory.
---
 src/utils_avltree.c | 29 +++++++++++++++++------------
 src/utils_avltree.h | 10 ++++++++--
 2 files changed, 25 insertions(+), 14 deletions(-)

diff --git a/src/utils_avltree.c b/src/utils_avltree.c
index 3665760b..275cb9b3 100644
--- a/src/utils_avltree.c
+++ b/src/utils_avltree.c
@@ -49,7 +49,7 @@ static void free_node (avl_node_t *n)
 	free (n);
 }
 
-static avl_node_t *search (avl_tree_t *t, void *key)
+static avl_node_t *search (avl_tree_t *t, const void *key)
 {
 	avl_node_t *n;
 	int cmp;
@@ -234,14 +234,10 @@ void *avl_node_prev (avl_tree_t *t, avl_node_t *n)
 	return (r);
 }
 
-static void *_remove (avl_tree_t *t, avl_node_t *n)
+static int _remove (avl_tree_t *t, avl_node_t *n)
 {
-	void *ret;
-
 	assert ((t != NULL) && (n != NULL));
 
-	ret = n->value;
-
 	if ((n->left == NULL) && (n->right == NULL))
 	{
 		/* Deleting a leave is easy */
@@ -283,7 +279,7 @@ static void *_remove (avl_tree_t *t, avl_node_t *n)
 		_remove (t, r);
 	}
 
-	return (ret);
+	return (0);
 } /* void *_remove */
 
 /*
@@ -378,7 +374,7 @@ int avl_insert (avl_tree_t *t, void *key, void *value)
 	return (0);
 } /* int avl_insert */
 
-void *avl_remove (avl_tree_t *t, void *key)
+int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue)
 {
 	avl_node_t *n;
 
@@ -386,20 +382,29 @@ void *avl_remove (avl_tree_t *t, void *key)
 
 	n = search (t, key);
 	if (n == NULL)
-		return (NULL);
+		return (-1);
+
+	if (rkey != NULL)
+		*rkey = n->key;
+	if (rvalue != NULL)
+		*rvalue = n->value;
 
 	return (_remove (t, n));
 } /* void *avl_remove */
 
-void *avl_get (avl_tree_t *t, void *key)
+int avl_get (avl_tree_t *t, const void *key, void **value)
 {
 	avl_node_t *n;
 
+	assert (value != NULL);
+
 	n = search (t, key);
 	if (n == NULL)
-		return (NULL);
+		return (-1);
 
-	return (n->value);
+	*value = n->value;
+
+	return (0);
 }
 
 avl_iterator_t *avl_get_iterator (avl_tree_t *t)
diff --git a/src/utils_avltree.h b/src/utils_avltree.h
index 5ffa696e..7875e0b2 100644
--- a/src/utils_avltree.h
+++ b/src/utils_avltree.h
@@ -7,13 +7,19 @@ typedef struct avl_tree_s avl_tree_t;
 struct avl_iterator_s;
 typedef struct avl_iterator_s avl_iterator_t;
 
+struct avl_keyval_s
+{
+	void *key;
+	void *value;
+};
+
 avl_tree_t *avl_create (int (*compare) (const void *, const void *));
 void avl_destroy (avl_tree_t *t);
 
 int avl_insert (avl_tree_t *t, void *key, void *value);
-void *avl_remove (avl_tree_t *t, void *key);
+int avl_remove (avl_tree_t *t, void *key, void **rkey, void **rvalue);
 
-void *avl_get (avl_tree_t *t, void *key);
+int avl_get (avl_tree_t *t, const void *key, void **value);
 
 avl_iterator_t *avl_get_iterator (avl_tree_t *t);
 void *avl_iterator_next (avl_iterator_t *iter);
-- 
2.11.0