diff options
| author | Vladimir Kondratyev <wulf@FreeBSD.org> | 2021-11-05 11:43:31 +0000 |
|---|---|---|
| committer | Vladimir Kondratyev <wulf@FreeBSD.org> | 2022-01-22 19:34:35 +0000 |
| commit | c8ddc214cf76785e99358a92700f68c148d63365 (patch) | |
| tree | b34820a22bfc54263851b9c1581e2a7dabe393ef | |
| parent | 7a6364ac7733bb3225285cdbd3119d124a56a802 (diff) | |
| download | src-c8ddc214cf76785e99358a92700f68c148d63365.tar.gz src-c8ddc214cf76785e99358a92700f68c148d63365.zip | |
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)
| -rw-r--r-- | sys/compat/linuxkpi/common/include/linux/rbtree.h | 40 |
1 files changed, 39 insertions, 1 deletions
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) |