[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [PATCH v2 11/10] tests: add interval tree unit test
From: |
Peter Xu |
Subject: |
[Qemu-devel] [PATCH v2 11/10] tests: add interval tree unit test |
Date: |
Tue, 8 May 2018 15:29:07 +0800 |
Signed-off-by: Peter Xu <address@hidden>
---
tests/test-interval-tree.c | 190 +++++++++++++++++++++++++++++++++++++
tests/Makefile.include | 2 +
2 files changed, 192 insertions(+)
create mode 100644 tests/test-interval-tree.c
diff --git a/tests/test-interval-tree.c b/tests/test-interval-tree.c
new file mode 100644
index 0000000000..a0e3decca0
--- /dev/null
+++ b/tests/test-interval-tree.c
@@ -0,0 +1,190 @@
+/*
+ * Interval tree tests
+ *
+ * Copyright Red Hat, Inc. 2018
+ *
+ * Authors:
+ * Peter Xu <address@hidden>,
+ *
+ * This work is licensed under the terms of the GNU LGPL, version 2 or later.
+ * See the COPYING.LIB file in the top-level directory.
+ */
+
+#include "qemu/osdep.h"
+#include "qemu/interval-tree.h"
+
+static ITRange ranges[2];
+static int range_i;
+
+static void ranges_reset(void)
+{
+ memset(&ranges, 0, sizeof(ranges));
+ range_i = 0;
+}
+
+static gboolean ranges_iterate(ITValue start, ITValue end)
+{
+ g_assert(range_i < ARRAY_SIZE(ranges));
+ ranges[range_i].start = start;
+ ranges[range_i].end = end;
+ range_i++;
+ return FALSE;
+}
+
+static void ranges_check(void)
+{
+ g_assert(range_i == 2);
+ g_assert(ranges[0].start == 10 && ranges[0].end == 19);
+ g_assert(ranges[1].start == 30 && ranges[1].end == 39);
+}
+
+static void test_interval_tree_common(void)
+{
+ int ret;
+ ITTree *tree = it_tree_new();
+ ITRange *range;
+
+ g_assert(tree);
+
+ /* Test insertion */
+ ret = it_tree_insert(tree, 10, 19);
+ g_assert(ret == 0);
+ ret = it_tree_insert(tree, 30, 39);
+ g_assert(ret == 0);
+ ret = it_tree_insert(tree, 15, 19);
+ g_assert(ret == IT_ERR_OVERLAP);
+ ret = it_tree_insert(tree, 0, 99);
+ g_assert(ret == IT_ERR_OVERLAP);
+
+ /* Test searching */
+ range = it_tree_find(tree, 0, 9);
+ g_assert(range == NULL);
+ range = it_tree_find(tree, 10, 19);
+ g_assert(range->start == 10 && range->end == 19);
+ range = it_tree_find_value(tree, 15);
+ g_assert(range->start == 10 && range->end == 19);
+ range = it_tree_find(tree, 15, 99);
+ g_assert(range->start == 10 && range->end == 19);
+ range = it_tree_find_value(tree, 35);
+ g_assert(range->start == 30 && range->end == 39);
+
+ /* Test iterations */
+ ranges_reset();
+ it_tree_foreach(tree, ranges_iterate);
+ ranges_check();
+
+ /* Remove one of them */
+ ret = it_tree_remove(tree, 10, 19);
+ g_assert(ret == 0);
+ g_assert(!it_tree_find(tree, 10, 19));
+ g_assert(it_tree_find(tree, 30, 39));
+
+ it_tree_destroy(tree);
+}
+
+static void test_interval_tree_merging(void)
+{
+ int ret;
+ ITTree *tree = it_tree_new();
+ ITRange *range;
+
+ g_assert(tree);
+
+ ret = it_tree_insert(tree, 10, 19);
+ g_assert(ret == 0);
+ ret = it_tree_insert(tree, 30, 39);
+ g_assert(ret == 0);
+
+ /* Test left side merging */
+ ret = it_tree_insert(tree, 40, 59);
+ g_assert(ret == 0);
+ range = it_tree_find(tree, 30, 39);
+ g_assert(range->start == 30 && range->end == 59);
+
+ /* Test right side merging */
+ ret = it_tree_insert(tree, 0, 9);
+ g_assert(ret == 0);
+ range = it_tree_find(tree, 10, 19);
+ g_assert(range->start == 0 && range->end == 19);
+
+ /* Test bidirectional merging */
+ ret = it_tree_insert(tree, 20, 29);
+ g_assert(ret == 0);
+ range = it_tree_find(tree, 20, 29);
+ g_assert(range->start == 0 && range->end == 59);
+ range = it_tree_find(tree, 0, 29);
+ g_assert(range->start == 0 && range->end == 59);
+ range = it_tree_find(tree, 40, 45);
+ g_assert(range->start == 0 && range->end == 59);
+
+ it_tree_destroy(tree);
+}
+
+static void test_interval_tree_removal(void)
+{
+ int ret;
+ ITTree *tree = it_tree_new();
+ ITRange *range;
+
+ g_assert(tree);
+
+ ret = it_tree_insert(tree, 10, 19);
+ g_assert(ret == 0);
+ ret = it_tree_insert(tree, 30, 39);
+ g_assert(ret == 0);
+
+ /*
+ * Remove some useless areas, which should not remove any existing
+ * ranges in the tree
+ */
+ ret = it_tree_remove(tree, 0, 9);
+ g_assert(ret == 0);
+ ret = it_tree_remove(tree, 50, 99);
+ g_assert(ret == 0);
+ ret = it_tree_remove(tree, 20, 29);
+ g_assert(ret == 0);
+ /* Make sure the elements are not removed */
+ g_assert(it_tree_find(tree, 10, 19));
+ g_assert(it_tree_find(tree, 30, 39));
+
+ /* Remove left subset of a range */
+ ret = it_tree_remove(tree, 0, 14);
+ g_assert(ret == 0);
+ range = it_tree_find(tree, 10, 19);
+ g_assert(range->start == 15 && range->end == 19);
+ it_tree_insert(tree, 10, 15);
+
+ /* Remove right subset of a range */
+ ret = it_tree_remove(tree, 35, 45);
+ g_assert(ret == 0);
+ range = it_tree_find(tree, 30, 39);
+ g_assert(range->start == 30 && range->end == 34);
+ it_tree_insert(tree, 35, 39);
+
+ /* Remove covers more than one range */
+ ret = it_tree_remove(tree, 0, 40);
+ g_assert(ret == 0);
+ g_assert(!it_tree_find(tree, 10, 19));
+ g_assert(!it_tree_find(tree, 30, 39));
+ it_tree_insert(tree, 10, 19);
+ it_tree_insert(tree, 30, 39);
+
+ /* Remove in the middle */
+ ret = it_tree_remove(tree, 12, 16);
+ g_assert(ret == 0);
+ range = it_tree_find_value(tree, 10);
+ g_assert(range->start == 10 && range->end == 11);
+ range = it_tree_find_value(tree, 17);
+ g_assert(range->start == 17 && range->end == 19);
+
+ it_tree_destroy(tree);
+}
+
+int main(int argc, char *argv[])
+{
+ g_test_init(&argc, &argv, NULL);
+ g_test_add_func("/interval-tree/common", test_interval_tree_common);
+ g_test_add_func("/interval-tree/merging", test_interval_tree_merging);
+ g_test_add_func("/interval-tree/removal", test_interval_tree_removal);
+ return g_test_run();
+}
diff --git a/tests/Makefile.include b/tests/Makefile.include
index 3b9a5e31a2..db1e6c93db 100644
--- a/tests/Makefile.include
+++ b/tests/Makefile.include
@@ -169,6 +169,7 @@ check-unit-y += tests/ptimer-test$(EXESUF)
gcov-files-ptimer-test-y = hw/core/ptimer.c
check-unit-y += tests/test-qapi-util$(EXESUF)
gcov-files-test-qapi-util-y = qapi/qapi-util.c
+check-unit-y += tests/test-interval-tree$(EXESUF)
check-block-$(CONFIG_POSIX) += tests/qemu-iotests-quick.sh
@@ -642,6 +643,7 @@ tests/test-qht-par$(EXESUF): tests/test-qht-par.o
tests/qht-bench$(EXESUF) $(tes
tests/qht-bench$(EXESUF): tests/qht-bench.o $(test-util-obj-y)
tests/test-bufferiszero$(EXESUF): tests/test-bufferiszero.o $(test-util-obj-y)
tests/atomic_add-bench$(EXESUF): tests/atomic_add-bench.o $(test-util-obj-y)
+tests/test-interval-tree$(EXESUF): tests/test-interval-tree.o
$(test-util-obj-y)
tests/test-qdev-global-props$(EXESUF): tests/test-qdev-global-props.o \
hw/core/qdev.o hw/core/qdev-properties.o hw/core/hotplug.o\
--
2.17.0
- [Qemu-devel] [PATCH v2 04/10] intel-iommu: only do page walk for MAP notifiers, (continued)
- [Qemu-devel] [PATCH v2 04/10] intel-iommu: only do page walk for MAP notifiers, Peter Xu, 2018/05/03
- [Qemu-devel] [PATCH v2 03/10] intel-iommu: add iommu lock, Peter Xu, 2018/05/03
- [Qemu-devel] [PATCH v2 05/10] intel-iommu: introduce vtd_page_walk_info, Peter Xu, 2018/05/03
- [Qemu-devel] [PATCH v2 06/10] intel-iommu: pass in address space when page walk, Peter Xu, 2018/05/03
- [Qemu-devel] [PATCH v2 07/10] util: implement simple interval tree logic, Peter Xu, 2018/05/03
- [Qemu-devel] [PATCH v2 08/10] intel-iommu: maintain per-device iova ranges, Peter Xu, 2018/05/03
- [Qemu-devel] [PATCH v2 09/10] intel-iommu: don't unmap all for shadow page table, Peter Xu, 2018/05/03
- [Qemu-devel] [PATCH v2 10/10] intel-iommu: remove notify_unmap for page walk, Peter Xu, 2018/05/03
- Re: [Qemu-devel] [PATCH v2 00/10] intel-iommu: nested vIOMMU, cleanups, bug fixes, no-reply, 2018/05/03
- [Qemu-devel] [PATCH v2 11/10] tests: add interval tree unit test,
Peter Xu <=
- Re: [Qemu-devel] [PATCH v2 00/10] intel-iommu: nested vIOMMU, cleanups, bug fixes, Peter Xu, 2018/05/16
- Re: [Qemu-devel] [PATCH v2 00/10] intel-iommu: nested vIOMMU, cleanups, bug fixes, Jason Wang, 2018/05/16
- Re: [Qemu-devel] [PATCH v2 00/10] intel-iommu: nested vIOMMU, cleanups, bug fixes, Peter Xu, 2018/05/16
- Re: [Qemu-devel] [PATCH v2 00/10] intel-iommu: nested vIOMMU, cleanups, bug fixes, Alex Williamson, 2018/05/16
- Re: [Qemu-devel] [PATCH v2 00/10] intel-iommu: nested vIOMMU, cleanups, bug fixes, Peter Xu, 2018/05/17