From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx0a-001b2d01.pphosted.com (mx0a-001b2d01.pphosted.com [148.163.156.1]) by sourceware.org (Postfix) with ESMTPS id D8D3E383820D for ; Thu, 2 Jun 2022 13:36:17 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D8D3E383820D Received: from pps.filterd (m0098404.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.17.1.5/8.17.1.5) with ESMTP id 252DGXT7004961; Thu, 2 Jun 2022 13:36:15 GMT Received: from pps.reinject (localhost [127.0.0.1]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 3gewxg8c07-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 02 Jun 2022 13:36:15 +0000 Received: from m0098404.ppops.net (m0098404.ppops.net [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 252DKlLk029561; Thu, 2 Jun 2022 13:36:14 GMT Received: from ppma03ams.nl.ibm.com (62.31.33a9.ip4.static.sl-reverse.com [169.51.49.98]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 3gewxg8byj-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 02 Jun 2022 13:36:14 +0000 Received: from pps.filterd (ppma03ams.nl.ibm.com [127.0.0.1]) by ppma03ams.nl.ibm.com (8.16.1.2/8.16.1.2) with SMTP id 252DZCpx005312; Thu, 2 Jun 2022 13:36:12 GMT Received: from b06avi18626390.portsmouth.uk.ibm.com (b06avi18626390.portsmouth.uk.ibm.com [9.149.26.192]) by ppma03ams.nl.ibm.com with ESMTP id 3gbc7h74fk-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 02 Jun 2022 13:36:12 +0000 Received: from d06av23.portsmouth.uk.ibm.com (d06av23.portsmouth.uk.ibm.com [9.149.105.59]) by b06avi18626390.portsmouth.uk.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 252Da5o820578784 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 2 Jun 2022 13:36:05 GMT Received: from d06av23.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 39ABAA4053; Thu, 2 Jun 2022 13:36:09 +0000 (GMT) Received: from d06av23.portsmouth.uk.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id D50E2A404D; Thu, 2 Jun 2022 13:36:08 +0000 (GMT) Received: from heavy.ibmuc.com (unknown [9.171.42.87]) by d06av23.portsmouth.uk.ibm.com (Postfix) with ESMTP; Thu, 2 Jun 2022 13:36:08 +0000 (GMT) From: Ilya Leoshkevich To: Tom Tromey , Andrew Burgess , Pedro Alves Cc: Andreas Arnez , gdb-patches@sourceware.org, Ilya Leoshkevich Subject: [PATCH 3/5] gdbsupport: Add interval_tree unit tests Date: Thu, 2 Jun 2022 15:35:44 +0200 Message-Id: <20220602133546.2948282-4-iii@linux.ibm.com> X-Mailer: git-send-email 2.35.3 In-Reply-To: <20220602133546.2948282-1-iii@linux.ibm.com> References: <20220602133546.2948282-1-iii@linux.ibm.com> X-TM-AS-GCONF: 00 X-Proofpoint-GUID: a2O5TFhZoIXAXTB_-KardkP97_vx9Cnu X-Proofpoint-ORIG-GUID: Mem2girza1lySdlwUJW_MLNnUkl-ADQk Content-Transfer-Encoding: 8bit X-Proofpoint-UnRewURL: 0 URL was un-rewritten MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.205,Aquarius:18.0.874,Hydra:6.0.517,FMLib:17.11.64.514 definitions=2022-06-02_03,2022-06-02_01,2022-02-23_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 phishscore=0 impostorscore=0 suspectscore=0 mlxlogscore=949 lowpriorityscore=0 adultscore=0 mlxscore=0 spamscore=0 bulkscore=0 malwarescore=0 priorityscore=1501 clxscore=1015 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2204290000 definitions=main-2206020059 X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 02 Jun 2022 13:36:20 -0000 Test small corner cases as well as a large tree. --- gdb/Makefile.in | 1 + gdb/unittests/interval_tree-selftests.c | 263 ++++++++++++++++++++++++ 2 files changed, 264 insertions(+) create mode 100644 gdb/unittests/interval_tree-selftests.c diff --git a/gdb/Makefile.in b/gdb/Makefile.in index d80087749de..8d848add1e3 100644 --- a/gdb/Makefile.in +++ b/gdb/Makefile.in @@ -456,6 +456,7 @@ SELFTESTS_SRCS = \ unittests/function-view-selftests.c \ unittests/gdb_tilde_expand-selftests.c \ unittests/gmp-utils-selftests.c \ + unittests/interval_tree-selftests.c \ unittests/intrusive_list-selftests.c \ unittests/lookup_name_info-selftests.c \ unittests/memory-map-selftests.c \ diff --git a/gdb/unittests/interval_tree-selftests.c b/gdb/unittests/interval_tree-selftests.c new file mode 100644 index 00000000000..98a3f4c15bd --- /dev/null +++ b/gdb/unittests/interval_tree-selftests.c @@ -0,0 +1,263 @@ +/* Tests interval tree for GDB, the GNU debugger. + Copyright (C) 2022 Free Software Foundation, Inc. + + This file is part of GDB. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . */ + +#include "defs.h" + +#include "gdbsupport/selftest.h" +#include +#include +#include + +#include "gdbsupport/interval_tree.h" + +/* A test type for storing in an interval tree. Interval tree must be able to + handle types without a default constructor, nonmoveable types, and + noncopyable types. */ + +struct test_interval +{ + test_interval (int low, int high) : low (low), high (high) {} + + test_interval () = delete; + test_interval (const test_interval &) = delete; + test_interval &operator= (const test_interval &) = delete; + test_interval (test_interval &&) = delete; + test_interval &operator= (test_interval &&) = delete; + + typedef int endpoint_type; + const int low; + const int high; +}; + +/* An expected ordering within an interval tree. */ + +struct cmp_test_interval +{ + bool + operator() (const test_interval &lhs, const test_interval &rhs) const + { + if (lhs.low != rhs.low) + return lhs.low < rhs.low; + return lhs.high < rhs.high; + } +}; + +/* Insert an interval into a tree and verify its integrity. */ + +static interval_tree::iterator +check_emplace (interval_tree &t, int low, int high) +{ + auto it = t.emplace (low, high); + std::ostringstream () << t; + return it; +} + +/* Check that iterator range has specific content. */ + +template +static void +check_iterator (Iterator it, EndIterator end) +{ + gdb_assert (it == end); +} + +template +static void +check_iterator (Iterator it, EndIterator end, int low, int high, + Args &&...args) +{ + gdb_assert (it != end); + gdb_assert (it->low == low && it->high == high); + ++it; + check_iterator (it, end, std::forward (args)...); +} + +/* Remove an interval from a tree and verify its integrity. */ + +static void +check_erase (interval_tree &t, + interval_tree::iterator it) +{ + t.erase (it); + std::ostringstream () << t; +} + +/* Small tests for various corner cases. */ + +static void +test_interval_tree_1 () +{ + interval_tree t; + check_iterator (t.find (0, 1), t.end ()); + auto it0 = check_emplace (t, 0, 1); + check_iterator (t.find (0, 1), t.end (), 0, 1); + check_erase (t, it0); + check_iterator (t.find (0, 1), t.end ()); +} + +static void +test_interval_tree_2 () +{ + interval_tree t; + check_emplace (t, -16119041, -1); + check_emplace (t, -1, 184549375); + check_emplace (t, 0, 0); + check_iterator (t.find (0, 0), t.end (), -1, 184549375, 0, 0); +} + +static void +test_interval_tree_3 () +{ + interval_tree t; + check_emplace (t, 0, 65536); + check_emplace (t, -1978987776, 10); + check_iterator (t.find (0, 239), t.end (), -1978987776, 10, 0, 65536); +} + +static void +test_interval_tree_4 () +{ + interval_tree t; + check_emplace (t, 0, 59); + check_emplace (t, 0, 0); + check_iterator (t.find (0, 0), t.end (), 0, 0, 0, 59); +} + +static void +test_interval_tree_5 () +{ + interval_tree t; + check_emplace (t, -16777216, -16711936); + check_emplace (t, 0, 0); +} + +static void +test_interval_tree_6 () +{ + interval_tree t; + check_emplace (t, -167772160, -33554186); + check_emplace (t, -16908034, -16712192); + check_emplace (t, -1, -1); + check_emplace (t, 0, 0); +} + +static void +test_interval_tree_7 () +{ + interval_tree t; + check_emplace (t, 621897471, 983770623); + check_emplace (t, 0, 0); + check_emplace (t, 0, 0); + check_emplace (t, 0, 8061696); + check_iterator (t.find (0, 0), t.end (), 0, 0, 0, 0, 0, 8061696); +} + +static void +test_interval_tree_8 () +{ + interval_tree t; + auto it0 = check_emplace (t, 1795875964, 1796149007); + check_emplace (t, 3855, 252371968); + check_erase (t, it0); +} + +static void +test_interval_tree_9 () +{ + interval_tree t; + check_emplace (t, 0, 0); + auto it1 = check_emplace (t, -603979523, 853292838); + check_erase (t, it1); +} + +static void +test_interval_tree_10 () +{ + interval_tree t; + auto it0 = check_emplace (t, 0, 6); + check_emplace (t, -65527, 65280); + check_emplace (t, 5636352, 26411009); + check_erase (t, it0); +} + +static void +test_interval_tree_11 () +{ + interval_tree t; + auto it0 = check_emplace (t, 62652437, 454794924); + check_emplace (t, -188, 1145351340); + check_emplace (t, 352332868, 1140916191); + check_erase (t, it0); +} + +static void +test_interval_tree_12 () +{ + interval_tree t; + auto it0 = check_emplace (t, -366592, 1389189); + auto it1 = check_emplace (t, 16128, 29702); + check_emplace (t, 2713716, 1946157056); + check_emplace (t, 393215, 1962868736); + check_erase (t, it0); + check_emplace (t, 2560, 4128768); + check_emplace (t, 0, 4128768); + check_emplace (t, 0, 125042688); + check_erase (t, it1); +} + +/* Performance test: add and lookup 1M intervals. */ + +static void +test_interval_tree_perf () +{ + interval_tree t; + const int count = 1000000; + for (int i = 0; i < count; i++) + t.emplace (i * 5, i * 5 + 5); + std::ostringstream () << t; + for (int i = 1; i < count; i++) + check_iterator (t.find (i * 5 - 2, i * 5 + 2), t.end (), i * 5 - 5, i * 5, + i * 5, i * 5 + 5); +} + +/* Test registration. */ + +static void +test_interval_tree () +{ + test_interval_tree_1 (); + test_interval_tree_2 (); + test_interval_tree_3 (); + test_interval_tree_4 (); + test_interval_tree_5 (); + test_interval_tree_6 (); + test_interval_tree_7 (); + test_interval_tree_8 (); + test_interval_tree_9 (); + test_interval_tree_10 (); + test_interval_tree_11 (); + test_interval_tree_12 (); + test_interval_tree_perf (); +} + +void _initialize_interval_tree_selftests (); +void +_initialize_interval_tree_selftests () +{ + selftests::register_test ("interval_tree", test_interval_tree); +} -- 2.35.3