wmem: add wmem_itree_insert_point function

The EPL dissector requires a data structure for mapping 8-bit integers
(subIndex) to information about a SubObject. As many (253) SubObjects
may have the same name, objectType and dataType, it would be nice if
those duplicates can be merged.

This patch works for matching based on the interval, but apparently EPL
should not match subIndexes where the name is different... so this patch
is useless anyway.

Besides, it is not optimal because the Red-Black tree implementation
does not have a remove method.

Change-Id: Icda566b8d36f7a86ae470d3101faed0fc62c7513

3 files changed, 270 insertions, 0 deletions

diff --git a/epan/wmem/wmem_interval_tree.c b/epan/wmem/wmem_interval_tree.c
index 1d89a06539..3bcd4d3d35 100644
--- a/epan/wmem/wmem_interval_tree.c
+++ b/epan/wmem/wmem_interval_tree.c
@@ -136,6 +136,119 @@ wmem_itree_insert(wmem_itree_t *tree, const guint64 low, const guint64 high, voi
     update_max_edge(node);
 }
 
+struct point_search_result {
+    wmem_tree_node_t *left;
+    wmem_tree_node_t *middle;
+    wmem_tree_node_t *right;
+};
+
+static void
+wmem_itree_find_points_in_subtree(wmem_tree_node_t *node, guint64 low, guint64 pos, guint64 high, struct point_search_result *result)
+{
+    const wmem_range_t *current;
+
+    if (!node) {
+        return;
+    }
+    current = (wmem_range_t *)node->key;
+
+    /* there is no child that can possibly match */
+    if (low > current->max_edge) {
+        return;
+    }
+
+    /* TODO implement a wmem_tree_remove method such that this check can be
+     * removed. */
+    if (!node->is_removed) {
+        if (current->low <= pos && pos <= current->high) {
+            /* overlap: point x overlaps the current interval. */
+            result->middle = node;
+        } else {
+            if (low != pos && current->high == low) {
+                /* current node is an interval at x-1 */
+                result->left = node;
+            }
+            if (high != pos && current->low == high) {
+                /* current node is an interval at x+1 */
+                result->right = node;
+            }
+        }
+    }
+
+    wmem_itree_find_points_in_subtree(node->left, low, pos, high, result);
+    wmem_itree_find_points_in_subtree(node->right, low, pos, high, result);
+}
+
+
+void
+wmem_itree_insert_point(wmem_itree_t *tree, const guint64 pos, wmem_itree_data_callback callback)
+{
+    const guint64 low = pos > 0 ? pos - 1 : pos;
+    const guint64 high = pos < G_MAXUINT64 ? pos + 1 : pos;
+    struct point_search_result result = { NULL, NULL, NULL };
+    wmem_range_t *leftKey, *rightKey;
+    void *leftData = NULL, *rightData = NULL;
+
+    /*
+     * Look for intervals overlapping at x-1, x or x+1.
+     * If an interval matches "x", then the interval range remains unmodified.
+     * Else if it is adjacent to both x-1 or x+1, merge those intervals.
+     * Else if it is adjacent to either x-1 or x+1, extend interval.
+     * Otherwise add a new interval.
+     */
+    wmem_itree_find_points_in_subtree(tree->root, low, pos, high, &result);
+    if (result.middle) {
+        /* interval exists, do not replace data. */
+        /* TODO maybe allow existing data to be replaced? Something like:
+         * result.middle->data = callback(result.middle->data, result.middle->data) */
+    } else if (result.left && result.right) {
+        /* need to merge the intervals. */
+        leftData = result.left->data;
+        rightData = result.right->data;
+
+        /* remove (insert NULL for) right key, it will be merged into left node. */
+        leftKey = (wmem_range_t *)result.left->key;
+        rightKey = (wmem_range_t *)result.right->key;
+        g_assert(leftKey->high + 1 == pos);
+        g_assert(rightKey->low - 1 == pos);
+        const wmem_range_t oldRightRange = *rightKey;
+        /* TODO use wmem_tree_remove when available. */
+        wmem_tree_insert(tree, rightKey, NULL, (compare_func)wmem_tree_compare_ranges);
+        leftKey->high = oldRightRange.high;
+        leftKey->max_edge = oldRightRange.max_edge;
+        update_max_edge(result.left);
+
+        result.left->data = callback(leftData, rightData);
+    } else if (result.left) {
+        /* Interval at x-1, simply extend left node. */
+        leftData = result.left->data;
+
+        leftKey = (wmem_range_t *)result.left->key;
+        g_assert(leftKey->high + 1 == pos);
+        leftKey->high = pos;
+        leftKey->max_edge = MAX(leftKey->max_edge, pos);
+        update_max_edge(result.left);
+
+        result.left->data = callback(leftData, NULL);
+    } else if (result.right) {
+        /* Interval at x+1. As tree is keyed by low, need to remove+insert. */
+        rightData = result.right->data;
+
+        rightKey = (wmem_range_t *)result.right->key;
+        g_assert(rightKey->low - 1 == pos);
+        const guint64 rightHigh = rightKey->high;
+        /* TODO use wmem_tree_remove when available. */
+        wmem_tree_insert(tree, rightKey, NULL, (compare_func)wmem_tree_compare_ranges);
+
+        rightData = callback(NULL, rightData);
+        wmem_itree_insert(tree, pos, rightHigh, rightData);
+    } else {
+        /* This is a new interval. */
+        leftData = callback(NULL, NULL);
+        wmem_itree_insert(tree, pos, pos, leftData);
+    }
+}
+
 
 static void
 wmem_itree_find_intervals_in_subtree(wmem_tree_node_t *node, wmem_range_t requested, wmem_list_t *results)
diff --git a/epan/wmem/wmem_interval_tree.h b/epan/wmem/wmem_interval_tree.h
index cf418cad9d..c4f903b126 100644
--- a/epan/wmem/wmem_interval_tree.h
+++ b/epan/wmem/wmem_interval_tree.h
@@ -54,6 +54,15 @@ struct _wmem_range_t {
     guint64 max_edge;   /* max value among subtrees */
 };
 
+/**
+ * Callback to provide the data for an interval. The original data that is
+ * replaced by the new data are passed as "oldData1" and "oldData2". If there
+ * was no previous interval, then these will be NULL. It is the responsibility
+ * of this callback to deallocate resources associated with the old data.
+ */
+typedef void *(*wmem_itree_data_callback)(void *oldData1, void *oldData2);
+
+
 WS_DLL_PUBLIC
 wmem_itree_t *
 wmem_itree_new(wmem_allocator_t *allocator)
@@ -74,6 +83,16 @@ WS_DLL_PUBLIC
 void
 wmem_itree_insert(wmem_itree_t *tree, const guint64 low, const guint64 high, void *data);
 
+/** Inserts a point indexed by "pos" in O(log(n)).
+ *
+ * Pre-condition: there must not be overlapping or directly adjacent intervals
+ * (guaranteed by using only wmem_itree_insert_point).
+ * If the point already exists, nothing is done. Otherwise an interval is
+ * created or updated, invoking the callback to obtain the new data.
+ */
+WS_DLL_PUBLIC
+void
+wmem_itree_insert_point(wmem_itree_t *tree, const guint64 pos, wmem_itree_data_callback callback);
 
 /*
  * Save results in a wmem_list with the scope passed as a parameter.
diff --git a/epan/wmem/wmem_test.c b/epan/wmem/wmem_test.c
index 067e32c808..7671261b4b 100644
--- a/epan/wmem/wmem_test.c
+++ b/epan/wmem/wmem_test.c
@@ -1306,6 +1306,142 @@ wmem_test_overlap(guint64 low, guint64 high, guint64 lowbis, guint64 highbis)
     return wmem_itree_range_overlap(&r1, &r2);
 }
 
+/* wmem_itree_insert_point tests {{{ */
+
+/* expected old data and new data for itree tests. */
+static guint64 expectedLeft, expectedRight, itreeNewData;
+static guint itree_data_callbacks_count;
+
+static void
+setup_itree_expectations(guint64 left, guint64 right, guint64 data)
+{
+    expectedLeft = left;
+    expectedRight = right;
+    itreeNewData = data;
+    itree_data_callbacks_count = 0;
+}
+
+typedef struct {
+    guint64 low;
+    guint64 high;
+    guint64 value;
+} wmem_test_itree_node_t;
+
+static gboolean
+wmem_test_itree_nodes_cb(const void *key, void *value, void *userData)
+{
+    wmem_array_t *arr = (wmem_array_t *)userData;
+    wmem_range_t *range = (wmem_range_t *)key;
+    wmem_test_itree_node_t val;
+
+    val.low = range->low;
+    val.high = range->high;
+    val.value = GPOINTER_TO_UINT(value);
+    wmem_array_append_one(arr, val);
+
+    return FALSE;
+}
+
+static wmem_test_itree_node_t *
+check_itree_nodes(wmem_allocator_t *allocator, wmem_itree_t *tree, guint expected_count)
+{
+    wmem_array_t *arr;
+
+    g_assert_cmpuint(wmem_tree_count(tree), ==, expected_count);
+    arr = wmem_array_sized_new(allocator, sizeof(wmem_test_itree_node_t), expected_count);
+    wmem_tree_foreach(tree, wmem_test_itree_nodes_cb, arr);
+    g_assert_cmpuint(wmem_array_get_count(arr), ==, expected_count);
+
+    return wmem_array_get_raw(arr);
+}
+
+static void
+check_itree_node(wmem_test_itree_node_t *actual, guint64 low, guint64 high, guint64 value)
+{
+    g_assert_cmpuint(actual->low, ==, low);
+    g_assert_cmpuint(actual->high, ==, high);
+    g_assert_cmpuint(actual->value, ==, value);
+}
+
+static void *
+itree_data_callback(void *oldData1, void *oldData2)
+{
+    g_assert_cmpuint(GPOINTER_TO_UINT(oldData1), ==, expectedLeft);
+    g_assert_cmpuint(GPOINTER_TO_UINT(oldData2), ==, expectedRight);
+    ++itree_data_callbacks_count;
+    return GUINT_TO_POINTER(itreeNewData);
+}
+
+static void *
+itree_data_unexpected_callback(void *oldData1 _U_, void *oldData2 _U_)
+{
+    g_assert_not_reached();
+    return NULL;
+}
+
+static void
+wmem_test_itree_insert_point(wmem_allocator_t *allocator)
+{
+    wmem_itree_t       *tree;
+    wmem_test_itree_node_t *nodes;
+
+    tree = wmem_itree_new(allocator);
+
+    /* new interval (3,3)=101 */
+    setup_itree_expectations(0, 0, 101);
+    wmem_itree_insert_point(tree, 3, itree_data_callback);
+    g_assert_cmpuint(itree_data_callbacks_count, ==, 1);
+    nodes = check_itree_nodes(allocator, tree, 1);
+    check_itree_node(&nodes[0], 3, 3, 101);
+
+    /* extend interval (3,3)=101 on the left to (2,3)=102 */
+    setup_itree_expectations(0, 101, 102);
+    wmem_itree_insert_point(tree, 2, itree_data_callback);
+    g_assert_cmpuint(itree_data_callbacks_count, ==, 1);
+    nodes = check_itree_nodes(allocator, tree, 1);
+    check_itree_node(&nodes[0], 2, 3, 102);
+
+    /* new interval (0,0)=103 at edge case (left) */
+    setup_itree_expectations(0, 0, 103);
+    wmem_itree_insert_point(tree, 0, itree_data_callback);
+    g_assert_cmpuint(itree_data_callbacks_count, ==, 1);
+    nodes = check_itree_nodes(allocator, tree, 2);
+    check_itree_node(&nodes[0], 0, 0, 103);
+    check_itree_node(&nodes[1], 2, 3, 102);
+
+    /* new interval (MAX,MAX)=104 at edge case (right) */
+    setup_itree_expectations(0, 0, 104);
+    wmem_itree_insert_point(tree, G_MAXUINT64, itree_data_callback);
+    g_assert_cmpuint(itree_data_callbacks_count, ==, 1);
+    nodes = check_itree_nodes(allocator, tree, 3);
+    check_itree_node(&nodes[0], 0, 0, 103);
+    check_itree_node(&nodes[1], 2, 3, 102);
+    check_itree_node(&nodes[2], G_MAXUINT64, G_MAXUINT64, 104);
+
+    /* must merge two intervals (0,0)=103 and (2,3)=102 into (0,3)=105 */
+    setup_itree_expectations(103, 102, 105);
+    wmem_itree_insert_point(tree, 1, itree_data_callback);
+    g_assert_cmpuint(itree_data_callbacks_count, ==, 1);
+    nodes = check_itree_nodes(allocator, tree, 2);
+    check_itree_node(&nodes[0], 0, 3, 105);
+    check_itree_node(&nodes[1], G_MAXUINT64, G_MAXUINT64, 104);
+
+    /* extend interval (0,3)=105 on the right to (0,4)=106 */
+    setup_itree_expectations(105, 0, 106);
+    wmem_itree_insert_point(tree, 4, itree_data_callback);
+    g_assert_cmpuint(itree_data_callbacks_count, ==, 1);
+    nodes = check_itree_nodes(allocator, tree, 2);
+    check_itree_node(&nodes[0], 0, 4, 106);
+    check_itree_node(&nodes[1], G_MAXUINT64, G_MAXUINT64, 104);
+
+    /* updating an existing interval (left, middle, right) should not have any effect */
+    wmem_itree_insert_point(tree, 0, itree_data_unexpected_callback);
+    wmem_itree_insert_point(tree, 1, itree_data_unexpected_callback);
+    wmem_itree_insert_point(tree, 4, itree_data_unexpected_callback);
+}
+
+/* }}} */
+
 static void
 wmem_test_itree(void)
 {
@@ -1371,6 +1507,8 @@ wmem_test_itree(void)
         g_assert(wmem_list_count(results) == userData.counter);
     }
 
+    wmem_test_itree_insert_point(allocator);
+
     wmem_destroy_allocator(extra_allocator);
     wmem_destroy_allocator(allocator);
 }