summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPeter Wu <peter@lekensteyn.nl>2017-05-31 23:04:43 +0200
committerPeter Wu <peter@lekensteyn.nl>2017-05-31 23:04:43 +0200
commit85998cb8be3db5e76f603bc2b70da8ae4e2e54bc (patch)
tree830ed6b3584368517a5ebd2552031a1fbf6eb9d1
parent3d542e6d411cc2207c25f5f75f2b263d7a9ff0a4 (diff)
downloadwireshark-interval-tree-point-insert.tar.gz
[WIP] RB tree removeinterval-tree-point-insert
Change-Id: Ie11f7a4bf4c0691b99ab386f8511db90ccfaf63f
-rw-r--r--epan/wmem/wmem_interval_tree.c7
-rw-r--r--epan/wmem/wmem_test.c1
-rw-r--r--epan/wmem/wmem_tree-int.h3
-rw-r--r--epan/wmem/wmem_tree.c62
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;
@@ -503,6 +528,35 @@ wmem_tree_insert(wmem_tree_t *tree, const void *key, void *data, compare_func cm
}
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)
{
lookup_or_insert32(tree, key, NULL, data, FALSE, TRUE);
@@ -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 *