From: Johannes Berg <johannes@sipsolutions.net>
To: backports@vger.kernel.org
Cc: Johannes Berg <johannes.berg@intel.com>
Subject: [PATCH] backports: add rb_tree_cached
Date: Thu, 15 Jul 2021 18:00:46 +0200 [thread overview]
Message-ID: <20210715180046.6635727a182b.Id747625a81c1c87ae14145eff93436b94a122980@changeid> (raw)
From: Johannes Berg <johannes.berg@intel.com>
We just map them to the normal rb_tree, losing the efficiency
gain in this case.
ticket=none
Signed-off-by: Johannes Berg <johannes.berg@intel.com>
---
backport/backport-include/linux/rbtree.h | 25 ++++++++++++++++++++++++
patches/0104-rb-tree-cached.cocci | 5 +++++
2 files changed, 30 insertions(+)
create mode 100644 backport/backport-include/linux/rbtree.h
create mode 100644 patches/0104-rb-tree-cached.cocci
diff --git a/backport/backport-include/linux/rbtree.h b/backport/backport-include/linux/rbtree.h
new file mode 100644
index 000000000000..feccff36e7dd
--- /dev/null
+++ b/backport/backport-include/linux/rbtree.h
@@ -0,0 +1,25 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+/*
+ * Copyright (C) 2021 Intel Corporation
+ */
+#ifndef __BACKPORT_RBTREE_H
+#define __BACKPORT_RBTREE_H
+#include_next <linux/rbtree.h>
+
+#if LINUX_VERSION_IS_LESS(4,14,0)
+#define rb_root_cached rb_root
+#define rb_first_cached rb_first
+static inline void rb_insert_color_cached(struct rb_node *node,
+ struct rb_root_cached *root,
+ bool leftmost)
+{
+ rb_insert_color(node, root);
+}
+#define rb_erase_cached rb_erase
+#define RB_ROOT_CACHED RB_ROOT
+#define rb_root_node(root) (root)->rb_node
+#else
+#define rb_root_node(root) (root)->rb_root.rb_node
+#endif
+
+#endif /* __BACKPORT_RBTREE_H */
diff --git a/patches/0104-rb-tree-cached.cocci b/patches/0104-rb-tree-cached.cocci
new file mode 100644
index 000000000000..a8388c847a5a
--- /dev/null
+++ b/patches/0104-rb-tree-cached.cocci
@@ -0,0 +1,5 @@
+@@
+struct rb_root_cached *root;
+@@
+-root->rb_root.rb_node
++rb_root_node(root)
--
2.31.1
--
To unsubscribe from this list: send the line "unsubscribe backports" in
next reply other threads:[~2021-07-15 16:01 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-07-15 16:00 Johannes Berg [this message]
2021-10-16 12:06 ` [PATCH] backports: add rb_tree_cached Hauke Mehrtens
2021-10-16 12:11 ` Johannes Berg
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20210715180046.6635727a182b.Id747625a81c1c87ae14145eff93436b94a122980@changeid \
--to=johannes@sipsolutions.net \
--cc=backports@vger.kernel.org \
--cc=johannes.berg@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).