From 85998cb8be3db5e76f603bc2b70da8ae4e2e54bc Mon Sep 17 00:00:00 2001
From: Peter Wu <peter@lekensteyn.nl>
Date: Wed, 31 May 2017 23:04:43 +0200
Subject: [WIP] RB tree remove

Change-Id: Ie11f7a4bf4c0691b99ab386f8511db90ccfaf63f
---
 epan/wmem/wmem_interval_tree.c |  7 ++++-
 epan/wmem/wmem_test.c          |  1 +
 epan/wmem/wmem_tree-int.h      |  3 ++
 epan/wmem/wmem_tree.c          | 62 ++++++++++++++++++++++++++++++++++++++++--
 4 files changed, 69 insertions(+), 4 deletions(-)

diff --git a/epan/wmem/wmem_interval_tree.c b/epan/wmem/wmem_interval_tree.c
index 3bcd4d3d35..616ac780f3 100644
--- a/epan/wmem/wmem_interval_tree.c
+++ b/epan/wmem/wmem_interval_tree.c
@@ -284,11 +284,16 @@ wmem_itree_find_intervals(wmem_itree_t *tree, wmem_allocator_t *allocator, guint
     return results;
 }
 
+static void
+print_val(const void *value)
+{
+    ws_debug_printf("Value: %d\n", GPOINTER_TO_UINT(value));
+}
 
 void
 wmem_print_itree(wmem_tree_t *tree)
 {
-    wmem_print_tree(tree, &print_range, NULL);
+    wmem_print_tree(tree, &print_range, print_val);
 }
 
 /*
diff --git a/epan/wmem/wmem_test.c b/epan/wmem/wmem_test.c
index 7671261b4b..1fecf4afde 100644
--- a/epan/wmem/wmem_test.c
+++ b/epan/wmem/wmem_test.c
@@ -1507,6 +1507,7 @@ wmem_test_itree(void)
         g_assert(wmem_list_count(results) == userData.counter);
     }
 
+    /* */
     wmem_test_itree_insert_point(allocator);
 
     wmem_destroy_allocator(extra_allocator);
diff --git a/epan/wmem/wmem_tree-int.h b/epan/wmem/wmem_tree-int.h
index b53b9b889e..931c200158 100644
--- a/epan/wmem/wmem_tree-int.h
+++ b/epan/wmem/wmem_tree-int.h
@@ -71,6 +71,9 @@ typedef int (*compare_func)(const void *a, const void *b);
 wmem_tree_node_t *
 wmem_tree_insert(wmem_tree_t *tree, const void *key, void *data, compare_func cmp);
 
+void
+wmem_tree_remove(wmem_tree_t *tree, const void *key, compare_func cmp);
+
 typedef struct _wmem_range_t wmem_range_t;
 
 gboolean
diff --git a/epan/wmem/wmem_tree.c b/epan/wmem/wmem_tree.c
index 71815c7567..ee45c58695 100644
--- a/epan/wmem/wmem_tree.c
+++ b/epan/wmem/wmem_tree.c
@@ -206,6 +206,31 @@ rb_insert_case1(wmem_tree_t *tree, wmem_tree_node_t *node)
     }
 }
 
+static void
+rb_transplant(wmem_tree_t *tree, wmem_tree_node_t *node, wmem_tree_node_t *child)
+{
+    if (node->parent == NULL) {
+        tree->root = child;
+    } else if (node == node->parent->left) {
+        node->parent->left = child;
+    } else /* if (node == node->parent->right) */ {
+        node->parent->right = child;
+    }
+
+    if (child) {
+        child->parent = node->parent;
+    }
+}
+
+static wmem_tree_node_t *
+tree_minimum(wmem_tree_node_t *node)
+{
+    while (node->left) {
+        node = node->left;
+    }
+    return node;
+}
+
 wmem_tree_t *
 wmem_tree_new(wmem_allocator_t *allocator)
 {
@@ -423,7 +448,7 @@ lookup_or_insert32(wmem_tree_t *tree, guint32 key,
     return node->data;
 }
 
-static void *
+static wmem_tree_node_t *
 wmem_tree_lookup(wmem_tree_t *tree, const void *key, compare_func cmp)
 {
     wmem_tree_node_t *node;
@@ -437,7 +462,7 @@ wmem_tree_lookup(wmem_tree_t *tree, const void *key, compare_func cmp)
     while (node) {
         int result = cmp(key, node->key);
         if (result == 0) {
-            return node->data;
+            return node;
         }
         else if (result < 0) {
             node = node->left;
@@ -502,6 +527,35 @@ wmem_tree_insert(wmem_tree_t *tree, const void *key, void *data, compare_func cm
     return new_node;
 }
 
+void
+wmem_tree_remove(wmem_tree_t *tree, const void *key, compare_func cmp)
+{
+    wmem_tree_node_t *node, *movingNode;
+    wmem_node_color_t origColor;
+
+    node = wmem_tree_lookup(tree, key, cmp);
+    if (node == NULL) {
+        return;
+    }
+
+    /* node that will be removed (for at most one leaf node) or
+     * moved (for two leaf nodes). */
+    movingNode = node;
+    origColor = movingNode->color;
+
+    if (node->left == NULL) {
+        fixNode = node->right;
+        rb_transplant(tree, node, node->right);
+    } else if (node->right == NULL) {
+        fixNode = node->left;
+        rb_transplant(tree, node, node->left);
+    } else {
+        movingNode = tree_minimum(node->right);
+        origColor = movingNode->color;
+
+    }
+}
+
 void
 wmem_tree_insert32(wmem_tree_t *tree, guint32 key, void *data)
 {
@@ -622,6 +676,7 @@ void *
 wmem_tree_lookup_string(wmem_tree_t* tree, const gchar* k, guint32 flags)
 {
     compare_func cmp;
+    wmem_tree_node_t *node;
 
     if (flags & WMEM_TREE_STRING_NOCASE) {
         cmp = (compare_func)g_ascii_strcasecmp;
@@ -629,7 +684,8 @@ wmem_tree_lookup_string(wmem_tree_t* tree, const gchar* k, guint32 flags)
         cmp = (compare_func)strcmp;
     }
 
-    return wmem_tree_lookup(tree, k, cmp);
+    node = wmem_tree_lookup(tree, k, cmp);
+    return node ? node->data : NULL;
 }
 
 void *
-- 
cgit v1.2.1