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

1 files changed, 138 insertions, 0 deletions

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);
 }