From nobody Tue Sep 13 06:14:08 2022 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4MRY805Lgnz4cbJ7; Tue, 13 Sep 2022 06:14:08 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4MRY804hrNz3L0L; Tue, 13 Sep 2022 06:14:08 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1663049648; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=nxI8huao+INC4V+PNVoiA+AlzOW+t/wM1NPszifsnLw=; b=ERJIjMicyoWDZ33YLNAjO4TqUdwfDR5UU/QpQsWh3zkykYVs+pZIElo4Le/IYumrFSV6S9 N9NnvxLirawkzNjCvB5mwTP2R02viZz1RsiUiHswcogoUMha74G2R1qFWBQYX24ZoPY/3F TDkFaWjXGT6VYeVYJxlyWm2bJwcghHvPX77FyFfs3U/VDE1CUvHmzAWuvGPmoGN4ogaAum zhryNYVSo+gXKB/xjYvGdnVGQESGXLmwrpwKi2VXYHS5tsj0fUC5MAof7vN9wWkS6Yo72J QjKuANxXK5rpGSmtbrq/xEcupq2rwAsSJxPj8T7s3GZ1mAKRqlYG52kmk73iUA== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4MRY803lKYzFPT; Tue, 13 Sep 2022 06:14:08 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 28D6E8cj096640; Tue, 13 Sep 2022 06:14:08 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 28D6E8Vb096639; Tue, 13 Sep 2022 06:14:08 GMT (envelope-from git) Date: Tue, 13 Sep 2022 06:14:08 GMT Message-Id: <202209130614.28D6E8Vb096639@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Doug Moore Subject: git: 4893472c9a18 - main - rb_tree: pass parent to RB_INSERT_COLOR List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: dougm X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 4893472c9a18cd8ce3b68d0c54084ef6f0285d0f Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1663049648; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=nxI8huao+INC4V+PNVoiA+AlzOW+t/wM1NPszifsnLw=; b=LXgsa6i38rApt6X4gJr+qpkIhOvsnWP/zqCbLY/lCt9X2lmQZNvxWlJKK2gjnLvhCoBzqt GVKsqeBImen3YNZwYJcxnRY0bQFA+Z5EODakMf2EjvIA1EV1ukc0i3skSX5fs3YIElxnR8 6e+5abd/1x89/inOvAPWzStdcc3nziSqbw4UNrEdKjPjUbwn7uywS32D/HCu8URgxLtKRK bmmJeydzco0KxdECw8vW/vL0O/LKLHtk3jtYBVBcV1CR38GFsjXMNc6sD7uh5f8KZfs4YB 65ksEpVCisg+304d9T3784KmcFfeit7DQcZ61qlVqSe+igQUY36Ux+lIHoIMRg== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1663049648; a=rsa-sha256; cv=none; b=sf3BoKhyH7oSpczH7jVjGgG5K2jlBj0V6mr1oJuv+RR0wgfygFeMyAM0GlO28Eitn2gq1t UzXCQ79RjawGPXdZ4yaRCqrUoWV87xsEdvHNB+SUxxG8iQ0scsWFUUaybTXJBcL7/UIAF/ fCiKzeQsi8ZN3omUoMAiUiFPrD4E3oOZVMEMWE8E/apmwWyUcMUdvR4uWCq67qO4Cg83i1 3fMZ0Uow/5fuSYCrhfLwexN7SqHZL/ndngquk6bK0YPldPtOCi8mt7q7TrYuA3TteEnqou p73UY/gRoXM82X8xgshXpLboKBbBXc2762yB8s3/RcX7KEz4f6DsTuiDHOGFvA== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=4893472c9a18cd8ce3b68d0c54084ef6f0285d0f commit 4893472c9a18cd8ce3b68d0c54084ef6f0285d0f Author: Doug Moore AuthorDate: 2022-09-13 06:11:47 +0000 Commit: Doug Moore CommitDate: 2022-09-13 06:11:47 +0000 rb_tree: pass parent to RB_INSERT_COLOR Change RB_COLOR_INSERT to take a parent parameter, to avoid looking up a value already available. Make adjustments to a linux rbtree header, which invokes it. Reviewed by: alc, hselasky Differential Revision: https://reviews.freebsd.org/D36114 --- sys/compat/linuxkpi/common/include/linux/rbtree.h | 11 ++++++++--- sys/sys/tree.h | 18 ++++++++++-------- 2 files changed, 18 insertions(+), 11 deletions(-) diff --git a/sys/compat/linuxkpi/common/include/linux/rbtree.h b/sys/compat/linuxkpi/common/include/linux/rbtree.h index 1f337d59545c..37537d4b2724 100644 --- a/sys/compat/linuxkpi/common/include/linux/rbtree.h +++ b/sys/compat/linuxkpi/common/include/linux/rbtree.h @@ -74,8 +74,11 @@ RB_PROTOTYPE(linux_root, rb_node, __entry, panic_cmp); #define RB_EMPTY_NODE(node) (RB_PARENT(node, __entry) == node) #define RB_CLEAR_NODE(node) RB_SET_PARENT(node, node, __entry) -#define rb_insert_color(node, root) \ - linux_root_RB_INSERT_COLOR((struct linux_root *)(root), (node)) +#define rb_insert_color(node, root) do { \ + if (rb_parent(node)) \ + linux_root_RB_INSERT_COLOR((struct linux_root *)(root), \ + rb_parent(node), (node)); \ +} while (0) #define rb_erase(node, root) \ linux_root_RB_REMOVE((struct linux_root *)(root), (node)) #define rb_next(node) RB_NEXT(linux_root, NULL, (node)) @@ -145,7 +148,9 @@ static inline void rb_insert_color_cached(struct rb_node *node, struct rb_root_cached *root, bool leftmost) { - linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root, node); + if (rb_parent(node)) + linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root, + rb_parent(node), node); if (leftmost) root->rb_leftmost = node; } diff --git a/sys/sys/tree.h b/sys/sys/tree.h index e0ab4449bd35..7a574eff3aea 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -426,7 +426,8 @@ struct { \ #define RB_PROTOTYPE_RANK(name, type, attr) #endif #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ - attr void name##_RB_INSERT_COLOR(struct name *, struct type *) + attr void name##_RB_INSERT_COLOR(struct name *, \ + struct type *, struct type *) #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ attr void name##_RB_REMOVE_COLOR(struct name *, \ struct type *, struct type *) @@ -495,7 +496,8 @@ name##_RB_RANK(struct type *elm) \ #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ attr void \ -name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ +name##_RB_INSERT_COLOR(struct name *head, \ + struct type *parent, struct type *elm) \ { \ /* \ * Initially, elm is a leaf. Either its parent was previously \ @@ -507,12 +509,11 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ * uninitialized 'child', and a later iteration can only happen \ * when a value has been assigned to 'child' in the previous \ * one. \ - */ \ - struct type *child, *child_up, *gpar, *parent; \ + */ \ + struct type *child, *child_up, *gpar; \ __uintptr_t elmdir, sibdir; \ \ - gpar = _RB_UP(elm, field); \ - while ((parent = gpar) != NULL) { \ + do { \ /* the rank of the tree rooted at elm grew */ \ gpar = _RB_UP(parent, field); \ elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \ @@ -588,7 +589,7 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ RB_AUGMENT(elm); \ RB_AUGMENT(parent); \ break; \ - } \ + } while ((parent = gpar) != NULL); \ } #ifndef RB_STRICT_HST @@ -778,7 +779,8 @@ name##_RB_INSERT(struct name *head, struct type *elm) \ } \ RB_SET(elm, parent, field); \ *tmpp = elm; \ - name##_RB_INSERT_COLOR(head, elm); \ + if (parent != NULL) \ + name##_RB_INSERT_COLOR(head, parent, elm); \ RB_UPDATE_AUGMENT(elm, field); \ return (NULL); \ }