From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.0 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY,SPF_PASS,URIBL_BLOCKED, USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 18365C43387 for ; Thu, 20 Dec 2018 09:23:10 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id DEB2420656 for ; Thu, 20 Dec 2018 09:23:09 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=default; t=1545297789; bh=4p5U0+rqfqrDYVPf1w5FV/UPHdhIy8HNdLBIX0GuEbE=; h=From:To:Cc:Subject:Date:In-Reply-To:References:List-ID:From; b=TPmz8GYtHwDkitI/qRKTfcne3bw1S1qzmx9+zvzpDe4MsmOFLejtnSCfCelsw0X68 FeVOfyuk9Df69RUvcLsDTc3jqed0sbG8os7RWpTgFQqIiEphp20xS4aXDP0GDqTw6J IVOMiLxqdWVNE8hkt1CkpzGO4XlAvzSCNgIYgnk4= Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1731482AbeLTJXI (ORCPT ); Thu, 20 Dec 2018 04:23:08 -0500 Received: from mail.kernel.org ([198.145.29.99]:50178 "EHLO mail.kernel.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1731442AbeLTJXF (ORCPT ); Thu, 20 Dec 2018 04:23:05 -0500 Received: from localhost (5356596B.cm-6-7b.dynamic.ziggo.nl [83.86.89.107]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPSA id A03B2217D7; Thu, 20 Dec 2018 09:23:04 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=default; t=1545297785; bh=4p5U0+rqfqrDYVPf1w5FV/UPHdhIy8HNdLBIX0GuEbE=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=ASykYtdUXW0AenNOfEwS7kOzaiIA5EgxypYOWhd1Oe+gJVIrq9KcFGxoEvukznENa Ku9sa+TIffp2wSTIEsjIGGE2ECcyetYTwi0P4fW7aPBGcV2Agetz70t9qxP1pSAzMC rzT924atTNTSPOz51JHH86kqODedYKpBdFswGxlo= From: Greg Kroah-Hartman To: linux-kernel@vger.kernel.org Cc: Greg Kroah-Hartman , stable@vger.kernel.org, Davidlohr Bueso , Andrew Morton , Linus Torvalds , Sasha Levin Subject: [PATCH 4.9 03/61] lib/interval_tree_test.c: allow full tree search Date: Thu, 20 Dec 2018 10:18:03 +0100 Message-Id: <20181220085843.876085484@linuxfoundation.org> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20181220085843.743900603@linuxfoundation.org> References: <20181220085843.743900603@linuxfoundation.org> User-Agent: quilt/0.65 X-stable: review X-Patchwork-Hint: ignore MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 4.9-stable review patch. If anyone has any objections, please let me know. ------------------ [ Upstream commit c46ecce431ebe6b1a9551d1f530eb432dae5c39b ] ... such that a user can specify visiting all the nodes in the tree (intersects with the world). This is a nice opposite from the very basic default query which is a single point. Link: http://lkml.kernel.org/r/20170518174936.20265-5-dave@stgolabs.net Signed-off-by: Davidlohr Bueso Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds Signed-off-by: Sasha Levin --- lib/interval_tree_test.c | 15 ++++++++++----- 1 file changed, 10 insertions(+), 5 deletions(-) diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c index 1093f0496d5e..409383463879 100644 --- a/lib/interval_tree_test.c +++ b/lib/interval_tree_test.c @@ -15,6 +15,7 @@ __param(int, perf_loops, 100000, "Number of iterations modifying the tree"); __param(int, nsearches, 100, "Number of searches to the interval tree"); __param(int, search_loops, 10000, "Number of iterations searching the tree"); +__param(bool, search_all, false, "Searches will iterate all nodes in the tree"); static struct rb_root root = RB_ROOT; @@ -24,13 +25,13 @@ static u32 *queries = NULL; static struct rnd_state rnd; static inline unsigned long -search(unsigned long query, struct rb_root *root) +search(struct rb_root *root, unsigned long start, unsigned long last) { struct interval_tree_node *node; unsigned long results = 0; - for (node = interval_tree_iter_first(root, query, query); node; - node = interval_tree_iter_next(node, query, query)) + for (node = interval_tree_iter_first(root, start, last); node; + node = interval_tree_iter_next(node, start, last)) results++; return results; } @@ -99,8 +100,12 @@ static int interval_tree_test_init(void) results = 0; for (i = 0; i < search_loops; i++) - for (j = 0; j < nsearches; j++) - results += search(queries[j], &root); + for (j = 0; j < nsearches; j++) { + unsigned long start = search_all ? 0 : queries[j]; + unsigned long last = search_all ? max_endpoint : queries[j]; + + results += search(&root, start, last); + } time2 = get_cycles(); time = time2 - time1; -- 2.19.1