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

[Vladimir Kondratyev]

The branch stable/13 has been updated by wulf:

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

commit c8ddc214cf76785e99358a92700f68c148d63365
Author:     Vladimir Kondratyev <w...@freebsd.org>
AuthorDate: 2021-11-05 11:43:31 +0000
Commit:     Vladimir Kondratyev <w...@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)