git: c8ddc214cf76 - stable/13 - LinuxKPI: Import some linux/rbtree.h functions from OpenBSD

The branch stable/13 has been updated by wulf:

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

commit c8ddc214cf76785e99358a92700f68c148d63365
Author:     Vladimir Kondratyev <wulf@FreeBSD.org>
AuthorDate: 2021-11-05 11:43:31 +0000
Commit:     Vladimir Kondratyev <wulf@FreeBSD.org>
CommitDate: 2022-01-22 19:34:35 +0000

    LinuxKPI: Import some linux/rbtree.h functions from OpenBSD
    
    Required by drm-kmod
    
    Obtained from:  OpenBSD
    MFC after:      1 week
    
    (cherry picked from commit dd52763387abd18bb6ac510b1148632a13b945f0)
---
 sys/compat/linuxkpi/common/include/linux/rbtree.h | 40 ++++++++++++++++++++++-
 1 file changed, 39 insertions(+), 1 deletion(-)

diff --git a/sys/compat/linuxkpi/common/include/linux/rbtree.h b/sys/compat/linuxkpi/common/include/linux/rbtree.h
index 78da33ad2658..17d87f73ab75 100644
--- a/sys/compat/linuxkpi/common/include/linux/rbtree.h
+++ b/sys/compat/linuxkpi/common/include/linux/rbtree.h
@@ -59,9 +59,12 @@ int panic_cmp(struct rb_node *one, struct rb_node *two);
 RB_HEAD(linux_root, rb_node);
 RB_PROTOTYPE(linux_root, rb_node, __entry, panic_cmp);
 
+#define	rb_parent(r)	RB_PARENT(r, __entry)
 #define	rb_entry(ptr, type, member)	container_of(ptr, type, member)
+#define	rb_entry_safe(ptr, type, member) \
+	((ptr) != NULL ? rb_entry(ptr, type, member) : NULL)
 
-#define RB_EMPTY_ROOT(root)     RB_EMPTY((struct linux_root *)root)
+#define	RB_EMPTY_ROOT(root)	((root)->rb_node == NULL)
 #define RB_EMPTY_NODE(node)     (RB_PARENT(node, __entry) == node)
 #define RB_CLEAR_NODE(node)     RB_SET_PARENT(node, node, __entry)
 
@@ -74,6 +77,41 @@ RB_PROTOTYPE(linux_root, rb_node, __entry, panic_cmp);
 #define	rb_first(root)	RB_MIN(linux_root, (struct linux_root *)(root))
 #define	rb_last(root)	RB_MAX(linux_root, (struct linux_root *)(root))
 
+static inline struct rb_node *
+__rb_deepest_left(struct rb_node *node)
+{
+	struct rb_node *parent = NULL;
+	while (node != NULL) {
+		parent = node;
+		if (RB_LEFT(node, __entry))
+			node = RB_LEFT(node, __entry);
+		else
+			node = RB_RIGHT(node, __entry);
+	}
+	return (parent);
+}
+
+static inline struct rb_node *
+rb_next_postorder(const struct rb_node *node)
+{
+	struct rb_node *parent =
+	    RB_PARENT(__DECONST(struct rb_node *, node), __entry);
+	/* left -> right, right -> root */
+	if (parent != NULL &&
+	    (node == RB_LEFT(parent, __entry)) &&
+	    (RB_RIGHT(parent, __entry)))
+		return (__rb_deepest_left(RB_RIGHT(parent, __entry)));
+	else
+		return (parent);
+}
+
+#define	rbtree_postorder_for_each_entry_safe(x, y, head, member)	\
+	for ((x) = rb_entry_safe(__rb_deepest_left((head)->rb_node),	\
+	    __typeof(*x), member);					\
+	    ((x) != NULL) && ((y) =					\
+	    rb_entry_safe(rb_next_postorder(&x->member), typeof(*x), member), 1); \
+	    (x) = (y))
+
 static inline void
 rb_link_node(struct rb_node *node, struct rb_node *parent,
     struct rb_node **rb_link)