git: a5cac2e672a7 - main - LinuxKPI: Add rb_add_cached function

The branch main has been updated by wulf:

URL: https://cgit.FreeBSD.org/src/commit/?id=a5cac2e672a7d94c0391076e7452d6a487f7b5c1

commit a5cac2e672a7d94c0391076e7452d6a487f7b5c1
Author:     Vladimir Kondratyev <wulf@FreeBSD.org>
AuthorDate: 2024-06-26 20:43:16 +0000
Commit:     Vladimir Kondratyev <wulf@FreeBSD.org>
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 }