[src/trunk]: src/sys/external/bsd/drm2/include/linux Fill out interval tree a...

[riastradh <riastradh%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/71bfd0169ebb
branches:  trunk
changeset: 835191:71bfd0169ebb
user:      riastradh <riastradh%NetBSD.org@localhost>
date:      Mon Aug 27 07:51:59 2018 +0000

description:
Fill out interval tree a little bit including wacky linux rb stubs.

diffstat:

 sys/external/bsd/drm2/include/linux/interval_tree.h |  28 ++++++++++++++++++++-
 1 files changed, 27 insertions(+), 1 deletions(-)

diffs (54 lines):

diff -r 88418ceb205d -r 71bfd0169ebb sys/external/bsd/drm2/include/linux/interval_tree.h
--- a/sys/external/bsd/drm2/include/linux/interval_tree.h       Mon Aug 27 07:51:49 2018 +0000
+++ b/sys/external/bsd/drm2/include/linux/interval_tree.h       Mon Aug 27 07:51:59 2018 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: interval_tree.h,v 1.5 2018/08/27 06:42:28 riastradh Exp $      */
+/*     $NetBSD: interval_tree.h,v 1.6 2018/08/27 07:51:59 riastradh Exp $      */
 
 /*-
  * Copyright (c) 2018 The NetBSD Foundation, Inc.
@@ -38,6 +38,13 @@
        struct rb_tree  rbr_tree;
 };
 
+static inline bool
+RB_EMPTY_ROOT(struct rb_root *root)
+{
+
+       return RB_TREE_MIN(&root->rbr_tree) == NULL;
+}
+
 struct interval_tree_node {
        struct rb_node  itn_node;
        unsigned long   start;  /* inclusive */
@@ -81,6 +88,13 @@
 };
 
 static inline void
+interval_tree_init(struct rb_root *root)
+{
+
+       rb_tree_init(&root->rbr_tree, &interval_tree_ops);
+}
+
+static inline void
 interval_tree_insert(struct interval_tree_node *node, struct rb_root *root)
 {
        struct interval_tree_node *collision __diagused;
@@ -132,4 +146,16 @@
                return NULL;
 }
 
+/*
+ * XXX This is not actually postorder, but I can't fathom why you would
+ * want postorder for an ordered tree; different insertion orders lead
+ * to different traversal orders.
+ */
+#define        rbtree_postorder_for_each_entry_safe(NODE, TMP, ROOT, FIELD)          \
+       for ((NODE) = RB_TREE_MIN(&(ROOT)->rbr_tree);                         \
+               ((NODE) != NULL &&                                            \
+                   ((TMP) = rb_tree_iterate(&(ROOT)->rbr_tree, (NODE),       \
+                       RB_DIR_RIGHT)));                                      \
+               (NODE) = (TMP))
+
 #endif /* _LINUX_INTERVAL_TREE_H_ */