From patchwork Thu Aug 10 07:10:56 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: tip-bot2 for Thomas Gleixner X-Patchwork-Id: 133738 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b824:0:b0:3f2:4152:657d with SMTP id z4csp255097vqi; Thu, 10 Aug 2023 00:56:33 -0700 (PDT) X-Google-Smtp-Source: AGHT+IEiBZwoplakQAF9F+fGk87EdHurOVOhGayzh+PjyLiMGhohHjsHtTxUl5c+vWrG+e7fE3DE X-Received: by 2002:a05:6808:1789:b0:3a5:a4b4:f93e with SMTP id bg9-20020a056808178900b003a5a4b4f93emr2232560oib.7.1691654193506; Thu, 10 Aug 2023 00:56:33 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1691654193; cv=none; d=google.com; s=arc-20160816; b=EKvcDf0LLgb9CT0hDA7bPiTCAwav1OJSR4O1MoAoOlW/tktiHZ5tzYbhsdklfNoyhX dRiYtxAJLpCrt+mDHuePJhJ+u+q/MU+FZH2crOGJW97BKbFAIVO+/8wXuiPbVaw4c6cR TQ5lOh8y2hJeCFvJeUrXT+06ajQkG58aZ/bTH5aywzWfokCxMTk6x+8hykGC0iuoZd4M RSEnBg05T3aJUacJN/Xd9HSrRLwgcPQmrkjQKbn6PhyMZJ13bveqK+eZmCY8Z8FmwKHK CVdzal+JFbvh9CWq2mxjHlPKL+6Je6T3pYAAalGZCfmRaRZ2y8aLABI9WL6yn/hZPEHD cbFw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:robot-unsubscribe :robot-id:message-id:mime-version:references:in-reply-to:cc:subject :to:reply-to:sender:from:dkim-signature:dkim-signature:date; bh=D4ibZomJJGs831EnKckgDLHRDE5xgjYSDrjS2GgTZOc=; fh=vkqUiGzLB1kYJlh6VK0MMfK5N8EB/xst0EWTlb2LqmA=; b=ivW5OPR3EEl8H4Bh5YJe+qdk0rhti3ezBa56cP59xiSHhjK9xCN6rnbbm7YKdDlmgT wmX+fAqESyWFuEXvZNbg+OWXE9+09qtBCOo95wcDkIOz6N+DdpBQfW7FCi/w3Mv9J8Io tKfDz3O6xJDynZL5PVPiJVq5rqarBz4bG151Jlr+USf03yTTnQeJ6k8S4rBDEUA1zjpM VlcyZOvEyPz9JFa3rNvrG28nRpwODIaY+WVe1BF7tZAWBstdRPAFXFUiIcgYZIg6Rgml 0PfJ6HD8Crvm8NtvL9R37L32xit1Jafof2lpuyNNsiWBIlMtTG5Mgf8odeFk5bxO2KPm Sx0w== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linutronix.de header.s=2020 header.b=ChK2bCCy; dkim=neutral (no key) header.i=@linutronix.de header.s=2020e; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=linutronix.de Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id q22-20020a17090aa01600b00268178130a2si1113641pjp.60.2023.08.10.00.56.20; Thu, 10 Aug 2023 00:56:33 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@linutronix.de header.s=2020 header.b=ChK2bCCy; dkim=neutral (no key) header.i=@linutronix.de header.s=2020e; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=linutronix.de Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233743AbjHJHLL (ORCPT + 99 others); Thu, 10 Aug 2023 03:11:11 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:54302 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233721AbjHJHK7 (ORCPT ); Thu, 10 Aug 2023 03:10:59 -0400 Received: from galois.linutronix.de (Galois.linutronix.de [193.142.43.55]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 52A5CF3; Thu, 10 Aug 2023 00:10:59 -0700 (PDT) Date: Thu, 10 Aug 2023 07:10:56 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020; t=1691651458; h=from:from:sender:sender:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=D4ibZomJJGs831EnKckgDLHRDE5xgjYSDrjS2GgTZOc=; b=ChK2bCCyrflE1GGL07pj+xPHQwKAdeoMQ0NCY87FuucsZ5ckuU6BaO4fiuVCPq/beL9KB7 PdgfWpKbcInD+Fikqd5tGXT754E9bAz88lFMt1c0oWXPaH/NA4mB3Rn4YJJAM5cDXDzRPm a4xajPmGkgXDKTDyzv+pxe1MRDAlJGosN45B4eh61o0eKPr/HC/IjtVeEAuvDlnGFSnLx8 gFoD5FH/zkCWoEzeh4HvpSTbUt39BR08dSYduzLRCtaSCbPI2XDvZylanKcDoIyfR0Dlsg D2OrzS/00aIQ0s1wu8qcgE3D+e6sM9zuk6HScBP08RGJMJfzbbtyqe3aEcBRqQ== DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=linutronix.de; s=2020e; t=1691651458; h=from:from:sender:sender:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=D4ibZomJJGs831EnKckgDLHRDE5xgjYSDrjS2GgTZOc=; b=nNATIig822xMthvlsQoWHtly4LNjI7jrDb5ueX9P7Vru4vXxfcoY0XVipph4Hi0r2cYP3A D0dlwNJ9hIRpWbAw== From: "tip-bot2 for Peter Zijlstra" Sender: tip-bot2@linutronix.de Reply-to: linux-kernel@vger.kernel.org To: linux-tip-commits@vger.kernel.org Subject: [tip: sched/core] rbtree: Add rb_add_augmented_cached() helper Cc: "Peter Zijlstra (Intel)" , Ingo Molnar , x86@kernel.org, linux-kernel@vger.kernel.org In-Reply-To: <20230531124603.862983648@infradead.org> References: <20230531124603.862983648@infradead.org> MIME-Version: 1.0 Message-ID: <169165145631.27769.14339276495833528763.tip-bot2@tip-bot2> Robot-ID: Robot-Unsubscribe: Contact to get blacklisted from these emails X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_BLOCKED, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1767414543574262451 X-GMAIL-MSGID: 1773827987305292369 The following commit has been merged into the sched/core branch of tip: Commit-ID: 99d4d26551b56f4e523dd04e4970b94aa796a64e Gitweb: https://git.kernel.org/tip/99d4d26551b56f4e523dd04e4970b94aa796a64e Author: Peter Zijlstra AuthorDate: Wed, 31 May 2023 13:58:43 +02:00 Committer: Ingo Molnar CommitterDate: Wed, 19 Jul 2023 09:43:58 +02:00 rbtree: Add rb_add_augmented_cached() helper While slightly sub-optimal, updating the augmented data while going down the tree during lookup would be faster -- alas the augment interface does not currently allow for that, provide a generic helper to add a node to an augmented cached tree. Signed-off-by: Peter Zijlstra (Intel) Signed-off-by: Ingo Molnar Link: https://lore.kernel.org/r/20230531124603.862983648@infradead.org --- include/linux/rbtree_augmented.h | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h index 7ee7ed5..6dbc5a1 100644 --- a/include/linux/rbtree_augmented.h +++ b/include/linux/rbtree_augmented.h @@ -60,6 +60,32 @@ rb_insert_augmented_cached(struct rb_node *node, rb_insert_augmented(node, &root->rb_root, augment); } +static __always_inline struct rb_node * +rb_add_augmented_cached(struct rb_node *node, struct rb_root_cached *tree, + bool (*less)(struct rb_node *, const struct rb_node *), + const struct rb_augment_callbacks *augment) +{ + struct rb_node **link = &tree->rb_root.rb_node; + struct rb_node *parent = NULL; + bool leftmost = true; + + while (*link) { + parent = *link; + if (less(node, parent)) { + link = &parent->rb_left; + } else { + link = &parent->rb_right; + leftmost = false; + } + } + + rb_link_node(node, parent, link); + augment->propagate(parent, NULL); /* suboptimal */ + rb_insert_augmented_cached(node, tree, leftmost, augment); + + return leftmost ? node : NULL; +} + /* * Template for declaring augmented rbtree callbacks (generic case) *