diff options
| -rw-r--r-- | epan/wmem/wmem_interval_tree.c | 113 | ||||
| -rw-r--r-- | epan/wmem/wmem_interval_tree.h | 19 | ||||
| -rw-r--r-- | epan/wmem/wmem_test.c | 138 |
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); } |