From nobody Wed Jun 26 20:54:38 2024 X-Original-To: dev-commits-src-main@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 4W8Yq24RR3z5QCt5; Wed, 26 Jun 2024 20:54:38 +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 4W8Yq23tKmz4LlL; Wed, 26 Jun 2024 20:54:38 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1719435278; 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=nWR6F7dZd8hRLMkU9aUVCQ/Hvf+NSxBhIKZJvgTNcqw=; b=D++14FoMbDYImj+WpDJB9f6amFtYDdTTD4w+4mbo+COVhdnVGaN1xkQ4jigP4g4fulhhX9 x2WyKwgfPOqwY6CFWawjNFNnRGd/cSNsL3/ufNd6uHpef3Ko25u83Tbz3HIryWedSo9ooH nPShZ+oFe2qsILDfjkLXjiAlyzzaa/UB4z6Djxs+u0RQVdXpQWfrXfTSO4+0h6vw5jdk8B 0xeu+RJUFRsr4rAHxRQvbuHBQcCuoyNDpKvz+y7t7UjB9tic7TgVc/zYvHYWxmCJQj2KQw AKMyVclgpgEuh415jkYv0PrHWwjeFxIKjNPLEZrwXn5EDODf/QTlHY/g1OEcDg== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1719435278; a=rsa-sha256; cv=none; b=JGQxVNMU7hhbA1HPCQjmtzwjs8GAq/mLJS/nqwDasIeii3QoMR2rBAlg4l6+qB4DYJwv+7 9cSs9sl30vEaL9DG4v0TWiiqrRMedFoolQQsUOYCfuVAQgFVWrsCJ+1Uyzu+ywb9+EJtbx a1pElo5KIWJ3sGL8vGzlVtZ9TsGE9r6SmsrNbIuE6ZYeSqlCTQaWwfhdAg7ztZKakbDyA9 sb2xAVkbkISCEv7dYRm0/C9NhvI+Yqh1CXs57pF5F9tywqqC6ZIaeq/dxNLplWoaGY1AfV 1z/P17TxIBpCQO9wGmuwATwxj1HLxGSptVVTToKn40rqUucyXJkDiwnNGApO6Q== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1719435278; 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=nWR6F7dZd8hRLMkU9aUVCQ/Hvf+NSxBhIKZJvgTNcqw=; b=C7t7sV/jFCTvxCuRLXvaTX8eM0MEwbTuAbtBhnuV5Ky2jeJkxuw0O3IFfF3vFZkH6SXWBR XlllCdA8+VejNvKaHUAx1oeP9mEmsm/giPmkAsyLQBTuJ0rr9yXG0e3+Vvct0pCndfJvBy xtbsyHJKbQBw0tFfBMw++K6PDwSAH4PXh551mgEM6WgpgQivUFulNnLAAKz00REKu6JX7D T6+eHRrQQZ5R827p04KCt4C3/26nnNnkViHEr2q9ra4HWfuVXqWHBAiDhKhXWiASLyWaVW VFjCfqXXDwtmNX/nOPjOao0gZl0Lf0AwmdSGH/WAGpz9kpfGsxHwRVmKFozDbw== 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 4W8Yq23VKLz10X0; Wed, 26 Jun 2024 20:54:38 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.17.1/8.17.1) with ESMTP id 45QKscDw092294; Wed, 26 Jun 2024 20:54:38 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.17.1/8.17.1/Submit) id 45QKscIw092291; Wed, 26 Jun 2024 20:54:38 GMT (envelope-from git) Date: Wed, 26 Jun 2024 20:54:38 GMT Message-Id: <202406262054.45QKscIw092291@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Vladimir Kondratyev Subject: git: a5cac2e672a7 - main - LinuxKPI: Add rb_add_cached function List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: X-BeenThere: dev-commits-src-main@freebsd.org Sender: owner-dev-commits-src-main@FreeBSD.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: wulf X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: a5cac2e672a7d94c0391076e7452d6a487f7b5c1 Auto-Submitted: auto-generated The branch main has been updated by wulf: URL: https://cgit.FreeBSD.org/src/commit/?id=a5cac2e672a7d94c0391076e7452d6a487f7b5c1 commit a5cac2e672a7d94c0391076e7452d6a487f7b5c1 Author: Vladimir Kondratyev AuthorDate: 2024-06-26 20:43:16 +0000 Commit: Vladimir Kondratyev CommitDate: 2024-06-26 20:43:16 +0000 LinuxKPI: Add rb_add_cached function rb_add_cached inserts node into the leftmost cached tree Sponsored by: Serenity CyberSecurity, LLC MFC after: 1 week Reviewed by: manu Differential Revision: https://reviews.freebsd.org/D45608 --- sys/compat/linuxkpi/common/include/linux/rbtree.h | 24 +++++++++++++++++++++++ 1 file changed, 24 insertions(+) diff --git a/sys/compat/linuxkpi/common/include/linux/rbtree.h b/sys/compat/linuxkpi/common/include/linux/rbtree.h index 78bf938eb000..e6033cfd760d 100644 --- a/sys/compat/linuxkpi/common/include/linux/rbtree.h +++ b/sys/compat/linuxkpi/common/include/linux/rbtree.h @@ -175,6 +175,30 @@ rb_replace_node_cached(struct rb_node *old, struct rb_node *new, root->rb_leftmost = new; } +static inline struct rb_node * +rb_add_cached(struct rb_node *node, struct rb_root_cached *tree, + bool (*less)(struct rb_node *, const struct rb_node *)) +{ + struct rb_node **link = &tree->rb_root.rb_node; + struct rb_node *parent = NULL; + bool leftmost = true; + + while (*link != NULL) { + parent = *link; + if (less(node, parent)) { + link = &RB_LEFT(parent, __entry); + } else { + link = &RB_RIGHT(parent, __entry); + leftmost = false; + } + } + + rb_link_node(node, parent, link); + rb_insert_color_cached(node, tree, leftmost); + + return (leftmost ? node : NULL); +} + #undef RB_ROOT #define RB_ROOT (struct rb_root) { NULL } #define RB_ROOT_CACHED (struct rb_root_cached) { RB_ROOT, NULL }