Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/910046/?format=api
{ "id": 910046, "url": "http://patchwork.ozlabs.org/api/patches/910046/?format=api", "web_url": "http://patchwork.ozlabs.org/project/qemu-devel/patch/20180508072907.18959-1-peterx@redhat.com/", "project": { "id": 14, "url": "http://patchwork.ozlabs.org/api/projects/14/?format=api", "name": "QEMU Development", "link_name": "qemu-devel", "list_id": "qemu-devel.nongnu.org", "list_email": "qemu-devel@nongnu.org", "web_url": "", "scm_url": "", "webscm_url": "", "list_archive_url": "", "list_archive_url_format": "", "commit_url_format": "" }, "msgid": "<20180508072907.18959-1-peterx@redhat.com>", "list_archive_url": null, "date": "2018-05-08T07:29:07", "name": "[v2,11/10] tests: add interval tree unit test", "commit_ref": null, "pull_url": null, "state": "new", "archived": false, "hash": "233139fd95bf935806fc35f1bca4960228262b27", "submitter": { "id": 67717, "url": "http://patchwork.ozlabs.org/api/people/67717/?format=api", "name": "Peter Xu", "email": "peterx@redhat.com" }, "delegate": null, "mbox": "http://patchwork.ozlabs.org/project/qemu-devel/patch/20180508072907.18959-1-peterx@redhat.com/mbox/", "series": [ { "id": 42502, "url": "http://patchwork.ozlabs.org/api/series/42502/?format=api", "web_url": "http://patchwork.ozlabs.org/project/qemu-devel/list/?series=42502", "date": "2018-05-04T03:08:01", "name": "intel-iommu: nested vIOMMU, cleanups, bug fixes", "version": 2, "mbox": "http://patchwork.ozlabs.org/series/42502/mbox/" } ], "comments": "http://patchwork.ozlabs.org/api/patches/910046/comments/", "check": "pending", "checks": "http://patchwork.ozlabs.org/api/patches/910046/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org>", "X-Original-To": "incoming@patchwork.ozlabs.org", "Delivered-To": "patchwork-incoming@bilbo.ozlabs.org", "Authentication-Results": [ "ozlabs.org;\n\tspf=pass (mailfrom) smtp.mailfrom=nongnu.org\n\t(client-ip=2001:4830:134:3::11; helo=lists.gnu.org;\n\tenvelope-from=qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org;\n\treceiver=<UNKNOWN>)", "ozlabs.org;\n\tdmarc=fail (p=none dis=none) header.from=redhat.com" ], "Received": [ "from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11])\n\t(using TLSv1 with cipher AES256-SHA (256/256 bits))\n\t(No client certificate requested)\n\tby ozlabs.org (Postfix) with ESMTPS id 40gB2l5DFWz9rxs\n\tfor <incoming@patchwork.ozlabs.org>;\n\tTue, 8 May 2018 17:29:50 +1000 (AEST)", "from localhost ([::1]:49734 helo=lists.gnu.org)\n\tby lists.gnu.org with esmtp (Exim 4.71) (envelope-from\n\t<qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org>)\n\tid 1fFx4E-0003TJ-SV\n\tfor incoming@patchwork.ozlabs.org; Tue, 08 May 2018 03:29:46 -0400", "from eggs.gnu.org ([2001:4830:134:3::10]:34272)\n\tby lists.gnu.org with esmtp (Exim 4.71)\n\t(envelope-from <peterx@redhat.com>) id 1fFx3t-0003RF-8a\n\tfor qemu-devel@nongnu.org; Tue, 08 May 2018 03:29:26 -0400", "from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)\n\t(envelope-from <peterx@redhat.com>) id 1fFx3q-000799-3b\n\tfor qemu-devel@nongnu.org; Tue, 08 May 2018 03:29:25 -0400", "from mx3-rdu2.redhat.com ([66.187.233.73]:49242\n\thelo=mx1.redhat.com)\n\tby eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32)\n\t(Exim 4.71) (envelope-from <peterx@redhat.com>) id 1fFx3p-00078d-R1\n\tfor qemu-devel@nongnu.org; Tue, 08 May 2018 03:29:22 -0400", "from smtp.corp.redhat.com\n\t(int-mx04.intmail.prod.int.rdu2.redhat.com [10.11.54.4])\n\t(using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits))\n\t(No client certificate requested)\n\tby mx1.redhat.com (Postfix) with ESMTPS id 60E65818F6E5;\n\tTue, 8 May 2018 07:29:15 +0000 (UTC)", "from xz-mi.nay.redhat.com (dhcp-14-151.nay.redhat.com\n\t[10.66.14.151])\n\tby smtp.corp.redhat.com (Postfix) with ESMTP id 7AEB52022EE0;\n\tTue, 8 May 2018 07:29:08 +0000 (UTC)" ], "From": "Peter Xu <peterx@redhat.com>", "To": "qemu-devel@nongnu.org", "Date": "Tue, 8 May 2018 15:29:07 +0800", "Message-Id": "<20180508072907.18959-1-peterx@redhat.com>", "In-Reply-To": "<20180504030811.28111-1-peterx@redhat.com>", "X-Scanned-By": "MIMEDefang 2.78 on 10.11.54.4", "X-Greylist": [ "Sender IP whitelisted, not delayed by milter-greylist-4.5.16\n\t(mx1.redhat.com [10.11.55.8]);\n\tTue, 08 May 2018 07:29:15 +0000 (UTC)", "inspected by milter-greylist-4.5.16 (mx1.redhat.com\n\t[10.11.55.8]); \n\tTue, 08 May 2018 07:29:15 +0000 (UTC) for IP:'10.11.54.4'\n\tDOMAIN:'int-mx04.intmail.prod.int.rdu2.redhat.com'\n\tHELO:'smtp.corp.redhat.com' FROM:'peterx@redhat.com' RCPT:''" ], "X-detected-operating-system": "by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic]\n\t[fuzzy]", "X-Received-From": "66.187.233.73", "Subject": "[Qemu-devel] [PATCH v2 11/10] tests: add interval tree unit test", "X-BeenThere": "qemu-devel@nongnu.org", "X-Mailman-Version": "2.1.21", "Precedence": "list", "List-Id": "<qemu-devel.nongnu.org>", "List-Unsubscribe": "<https://lists.nongnu.org/mailman/options/qemu-devel>,\n\t<mailto:qemu-devel-request@nongnu.org?subject=unsubscribe>", "List-Archive": "<http://lists.nongnu.org/archive/html/qemu-devel/>", "List-Post": "<mailto:qemu-devel@nongnu.org>", "List-Help": "<mailto:qemu-devel-request@nongnu.org?subject=help>", "List-Subscribe": "<https://lists.nongnu.org/mailman/listinfo/qemu-devel>,\n\t<mailto:qemu-devel-request@nongnu.org?subject=subscribe>", "Cc": "Tian Kevin <kevin.tian@intel.com>, \"Michael S . Tsirkin\" <mst@redhat.com>,\n\tJason Wang <jasowang@redhat.com>, Peter Xu <peterx@redhat.com>,\n\tAlex Williamson <alex.williamson@redhat.com>,\n\tJintack Lim <jintack@cs.columbia.edu>", "Errors-To": "qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org", "Sender": "\"Qemu-devel\"\n\t<qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org>" }, "content": "Signed-off-by: Peter Xu <peterx@redhat.com>\n---\n tests/test-interval-tree.c | 190 +++++++++++++++++++++++++++++++++++++\n tests/Makefile.include | 2 +\n 2 files changed, 192 insertions(+)\n create mode 100644 tests/test-interval-tree.c", "diff": "diff --git a/tests/test-interval-tree.c b/tests/test-interval-tree.c\nnew file mode 100644\nindex 0000000000..a0e3decca0\n--- /dev/null\n+++ b/tests/test-interval-tree.c\n@@ -0,0 +1,190 @@\n+/*\n+ * Interval tree tests\n+ *\n+ * Copyright Red Hat, Inc. 2018\n+ *\n+ * Authors:\n+ * Peter Xu <peterx@redhat.com>,\n+ *\n+ * This work is licensed under the terms of the GNU LGPL, version 2 or later.\n+ * See the COPYING.LIB file in the top-level directory.\n+ */\n+\n+#include \"qemu/osdep.h\"\n+#include \"qemu/interval-tree.h\"\n+\n+static ITRange ranges[2];\n+static int range_i;\n+\n+static void ranges_reset(void)\n+{\n+ memset(&ranges, 0, sizeof(ranges));\n+ range_i = 0;\n+}\n+\n+static gboolean ranges_iterate(ITValue start, ITValue end)\n+{\n+ g_assert(range_i < ARRAY_SIZE(ranges));\n+ ranges[range_i].start = start;\n+ ranges[range_i].end = end;\n+ range_i++;\n+ return FALSE;\n+}\n+\n+static void ranges_check(void)\n+{\n+ g_assert(range_i == 2);\n+ g_assert(ranges[0].start == 10 && ranges[0].end == 19);\n+ g_assert(ranges[1].start == 30 && ranges[1].end == 39);\n+}\n+\n+static void test_interval_tree_common(void)\n+{\n+ int ret;\n+ ITTree *tree = it_tree_new();\n+ ITRange *range;\n+\n+ g_assert(tree);\n+\n+ /* Test insertion */\n+ ret = it_tree_insert(tree, 10, 19);\n+ g_assert(ret == 0);\n+ ret = it_tree_insert(tree, 30, 39);\n+ g_assert(ret == 0);\n+ ret = it_tree_insert(tree, 15, 19);\n+ g_assert(ret == IT_ERR_OVERLAP);\n+ ret = it_tree_insert(tree, 0, 99);\n+ g_assert(ret == IT_ERR_OVERLAP);\n+\n+ /* Test searching */\n+ range = it_tree_find(tree, 0, 9);\n+ g_assert(range == NULL);\n+ range = it_tree_find(tree, 10, 19);\n+ g_assert(range->start == 10 && range->end == 19);\n+ range = it_tree_find_value(tree, 15);\n+ g_assert(range->start == 10 && range->end == 19);\n+ range = it_tree_find(tree, 15, 99);\n+ g_assert(range->start == 10 && range->end == 19);\n+ range = it_tree_find_value(tree, 35);\n+ g_assert(range->start == 30 && range->end == 39);\n+\n+ /* Test iterations */\n+ ranges_reset();\n+ it_tree_foreach(tree, ranges_iterate);\n+ ranges_check();\n+\n+ /* Remove one of them */\n+ ret = it_tree_remove(tree, 10, 19);\n+ g_assert(ret == 0);\n+ g_assert(!it_tree_find(tree, 10, 19));\n+ g_assert(it_tree_find(tree, 30, 39));\n+\n+ it_tree_destroy(tree);\n+}\n+\n+static void test_interval_tree_merging(void)\n+{\n+ int ret;\n+ ITTree *tree = it_tree_new();\n+ ITRange *range;\n+\n+ g_assert(tree);\n+\n+ ret = it_tree_insert(tree, 10, 19);\n+ g_assert(ret == 0);\n+ ret = it_tree_insert(tree, 30, 39);\n+ g_assert(ret == 0);\n+\n+ /* Test left side merging */\n+ ret = it_tree_insert(tree, 40, 59);\n+ g_assert(ret == 0);\n+ range = it_tree_find(tree, 30, 39);\n+ g_assert(range->start == 30 && range->end == 59);\n+\n+ /* Test right side merging */\n+ ret = it_tree_insert(tree, 0, 9);\n+ g_assert(ret == 0);\n+ range = it_tree_find(tree, 10, 19);\n+ g_assert(range->start == 0 && range->end == 19);\n+\n+ /* Test bidirectional merging */\n+ ret = it_tree_insert(tree, 20, 29);\n+ g_assert(ret == 0);\n+ range = it_tree_find(tree, 20, 29);\n+ g_assert(range->start == 0 && range->end == 59);\n+ range = it_tree_find(tree, 0, 29);\n+ g_assert(range->start == 0 && range->end == 59);\n+ range = it_tree_find(tree, 40, 45);\n+ g_assert(range->start == 0 && range->end == 59);\n+\n+ it_tree_destroy(tree);\n+}\n+\n+static void test_interval_tree_removal(void)\n+{\n+ int ret;\n+ ITTree *tree = it_tree_new();\n+ ITRange *range;\n+\n+ g_assert(tree);\n+\n+ ret = it_tree_insert(tree, 10, 19);\n+ g_assert(ret == 0);\n+ ret = it_tree_insert(tree, 30, 39);\n+ g_assert(ret == 0);\n+\n+ /*\n+ * Remove some useless areas, which should not remove any existing\n+ * ranges in the tree\n+ */\n+ ret = it_tree_remove(tree, 0, 9);\n+ g_assert(ret == 0);\n+ ret = it_tree_remove(tree, 50, 99);\n+ g_assert(ret == 0);\n+ ret = it_tree_remove(tree, 20, 29);\n+ g_assert(ret == 0);\n+ /* Make sure the elements are not removed */\n+ g_assert(it_tree_find(tree, 10, 19));\n+ g_assert(it_tree_find(tree, 30, 39));\n+\n+ /* Remove left subset of a range */\n+ ret = it_tree_remove(tree, 0, 14);\n+ g_assert(ret == 0);\n+ range = it_tree_find(tree, 10, 19);\n+ g_assert(range->start == 15 && range->end == 19);\n+ it_tree_insert(tree, 10, 15);\n+\n+ /* Remove right subset of a range */\n+ ret = it_tree_remove(tree, 35, 45);\n+ g_assert(ret == 0);\n+ range = it_tree_find(tree, 30, 39);\n+ g_assert(range->start == 30 && range->end == 34);\n+ it_tree_insert(tree, 35, 39);\n+\n+ /* Remove covers more than one range */\n+ ret = it_tree_remove(tree, 0, 40);\n+ g_assert(ret == 0);\n+ g_assert(!it_tree_find(tree, 10, 19));\n+ g_assert(!it_tree_find(tree, 30, 39));\n+ it_tree_insert(tree, 10, 19);\n+ it_tree_insert(tree, 30, 39);\n+\n+ /* Remove in the middle */\n+ ret = it_tree_remove(tree, 12, 16);\n+ g_assert(ret == 0);\n+ range = it_tree_find_value(tree, 10);\n+ g_assert(range->start == 10 && range->end == 11);\n+ range = it_tree_find_value(tree, 17);\n+ g_assert(range->start == 17 && range->end == 19);\n+\n+ it_tree_destroy(tree);\n+}\n+\n+int main(int argc, char *argv[])\n+{\n+ g_test_init(&argc, &argv, NULL);\n+ g_test_add_func(\"/interval-tree/common\", test_interval_tree_common);\n+ g_test_add_func(\"/interval-tree/merging\", test_interval_tree_merging);\n+ g_test_add_func(\"/interval-tree/removal\", test_interval_tree_removal);\n+ return g_test_run();\n+}\ndiff --git a/tests/Makefile.include b/tests/Makefile.include\nindex 3b9a5e31a2..db1e6c93db 100644\n--- a/tests/Makefile.include\n+++ b/tests/Makefile.include\n@@ -169,6 +169,7 @@ check-unit-y += tests/ptimer-test$(EXESUF)\n gcov-files-ptimer-test-y = hw/core/ptimer.c\n check-unit-y += tests/test-qapi-util$(EXESUF)\n gcov-files-test-qapi-util-y = qapi/qapi-util.c\n+check-unit-y += tests/test-interval-tree$(EXESUF)\n \n check-block-$(CONFIG_POSIX) += tests/qemu-iotests-quick.sh\n \n@@ -642,6 +643,7 @@ tests/test-qht-par$(EXESUF): tests/test-qht-par.o tests/qht-bench$(EXESUF) $(tes\n tests/qht-bench$(EXESUF): tests/qht-bench.o $(test-util-obj-y)\n tests/test-bufferiszero$(EXESUF): tests/test-bufferiszero.o $(test-util-obj-y)\n tests/atomic_add-bench$(EXESUF): tests/atomic_add-bench.o $(test-util-obj-y)\n+tests/test-interval-tree$(EXESUF): tests/test-interval-tree.o $(test-util-obj-y)\n \n tests/test-qdev-global-props$(EXESUF): tests/test-qdev-global-props.o \\\n \thw/core/qdev.o hw/core/qdev-properties.o hw/core/hotplug.o\\\n", "prefixes": [ "v2", "11/10" ] }