headers: Add rbtree cached

This copies the version of the rbtree which caches the left most
element. This only needs extensions to the header files.

The cached version was initially integrated in kernel 4.14, but it was
changed to a header only extension in kernel 5.3, which is used here.

Signed-off-by: Hauke Mehrtens <hauke@hauke-m.de>

1 files changed, 59 insertions, 0 deletions

diff --git a/backport/backport-include/linux/rbtree.h b/backport/backport-include/linux/rbtree.h
new file mode 100644
index 00000000..a364f07b
--- /dev/null
+++ b/backport/backport-include/linux/rbtree.h
@@ -0,0 +1,59 @@
+#ifndef __BACKPORT_LINUX_RBTREE_H
+#define __BACKPORT_LINUX_RBTREE_H
+#include_next <linux/rbtree.h>
+
+#if LINUX_VERSION_IS_LESS(4,14,0)
+/*
+ * Leftmost-cached rbtrees.
+ *
+ * We do not cache the rightmost node based on footprint
+ * size vs number of potential users that could benefit
+ * from O(1) rb_last(). Just not worth it, users that want
+ * this feature can always implement the logic explicitly.
+ * Furthermore, users that want to cache both pointers may
+ * find it a bit asymmetric, but that's ok.
+ */
+struct rb_root_cached {
+	struct rb_root rb_root;
+	struct rb_node *rb_leftmost;
+};
+
+#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
+
+/* Same as rb_first(), but O(1) */
+#define rb_first_cached(root) (root)->rb_leftmost
+
+static inline void rb_insert_color_cached(struct rb_node *node,
+					  struct rb_root_cached *root,
+					  bool leftmost)
+{
+	if (leftmost)
+		root->rb_leftmost = node;
+	rb_insert_color(node, &root->rb_root);
+}
+
+
+static inline struct rb_node *
+rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)
+{
+	struct rb_node *leftmost = NULL;
+
+	if (root->rb_leftmost == node)
+		leftmost = root->rb_leftmost = rb_next(node);
+
+	rb_erase(node, &root->rb_root);
+
+	return leftmost;
+}
+
+static inline void rb_replace_node_cached(struct rb_node *victim,
+					  struct rb_node *new,
+					  struct rb_root_cached *root)
+{
+	if (root->rb_leftmost == victim)
+		root->rb_leftmost = new;
+	rb_replace_node(victim, new, &root->rb_root);
+}
+#endif
+
+#endif /* __BACKPORT_LINUX_RBTREE_H */