Module Name: src
Committed By: riastradh
Date: Sun Dec 19 11:00:18 UTC 2021
Modified Files:
src/sys/external/bsd/drm2/include/linux: interval_tree.h
interval_tree_generic.h rbtree.h
Log Message:
Touch up the rbtree/intervaltree stubs.
Doesn't work at all yet, but maybe it will help.
To generate a diff of this commit:
cvs rdiff -u -r1.11 -r1.12 \
src/sys/external/bsd/drm2/include/linux/interval_tree.h
cvs rdiff -u -r1.2 -r1.3 \
src/sys/external/bsd/drm2/include/linux/interval_tree_generic.h
cvs rdiff -u -r1.8 -r1.9 src/sys/external/bsd/drm2/include/linux/rbtree.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/sys/external/bsd/drm2/include/linux/interval_tree.h
diff -u src/sys/external/bsd/drm2/include/linux/interval_tree.h:1.11 src/sys/external/bsd/drm2/include/linux/interval_tree.h:1.12
--- src/sys/external/bsd/drm2/include/linux/interval_tree.h:1.11 Sun Dec 19 01:48:30 2021
+++ src/sys/external/bsd/drm2/include/linux/interval_tree.h Sun Dec 19 11:00:18 2021
@@ -1,4 +1,4 @@
-/* $NetBSD: interval_tree.h,v 1.11 2021/12/19 01:48:30 riastradh Exp $ */
+/* $NetBSD: interval_tree.h,v 1.12 2021/12/19 11:00:18 riastradh Exp $ */
/*-
* Copyright (c) 2018 The NetBSD Foundation, Inc.
@@ -29,6 +29,14 @@
* POSSIBILITY OF SUCH DAMAGE.
*/
+/*
+ * XXX WARNING: This does not actually implement interval trees -- it
+ * only implements trees of intervals. In particular, it does not
+ * support finding all intervals that contain a given point, or that
+ * intersect with a given interval. Another way to look at it is that
+ * this is an interval tree restricted to nonoverlapping intervals.
+ */
+
#ifndef _LINUX_INTERVAL_TREE_H_
#define _LINUX_INTERVAL_TREE_H_
Index: src/sys/external/bsd/drm2/include/linux/interval_tree_generic.h
diff -u src/sys/external/bsd/drm2/include/linux/interval_tree_generic.h:1.2 src/sys/external/bsd/drm2/include/linux/interval_tree_generic.h:1.3
--- src/sys/external/bsd/drm2/include/linux/interval_tree_generic.h:1.2 Sun Dec 19 01:51:27 2021
+++ src/sys/external/bsd/drm2/include/linux/interval_tree_generic.h Sun Dec 19 11:00:18 2021
@@ -1,4 +1,4 @@
-/* $NetBSD: interval_tree_generic.h,v 1.2 2021/12/19 01:51:27 riastradh Exp $ */
+/* $NetBSD: interval_tree_generic.h,v 1.3 2021/12/19 11:00:18 riastradh Exp $ */
/*-
* Copyright (c) 2018 The NetBSD Foundation, Inc.
@@ -57,7 +57,7 @@ static inline int \
PREFIX##__compare_key(void *__cookie, const void *__vn, const void *__vk) \
{ \
const T *__n = __vn; \
- const T *__k = __vk; \
+ const KT *__k = __vk; \
const KT __nstart = START(__n), __nlast = LAST(__n); \
\
if (__nlast < *__k) \
@@ -77,7 +77,7 @@ static const rb_tree_ops_t PREFIX##__rbt
QUAL void \
PREFIX##_init(struct rb_root_cached *__root) \
{ \
- rb_tree_init(&__root->rbrc_tree, &PREFIX##__rbtree_ops); \
+ rb_tree_init(&__root->rb_root.rbr_tree, &PREFIX##__rbtree_ops); \
} \
\
QUAL void \
@@ -85,14 +85,14 @@ PREFIX##_insert(T *__node, struct rb_roo
{ \
T *__collision __diagused; \
\
- __collision = rb_tree_insert_node(&__root->rbrc_tree, __node); \
+ __collision = rb_tree_insert_node(&__root->rb_root.rbr_tree, __node); \
KASSERT(__collision == __node); \
} \
\
QUAL void \
PREFIX##_remove(T *__node, struct rb_root_cached *__root) \
{ \
- rb_tree_remove_node(&__root->rbrc_tree, __node); \
+ rb_tree_remove_node(&__root->rb_root.rbr_tree, __node); \
} \
\
QUAL T * \
@@ -100,7 +100,7 @@ PREFIX##_iter_first(struct rb_root_cache
{ \
T *__node; \
\
- __node = rb_tree_find_node_geq(&__root->rbrc_tree, &__start); \
+ __node = rb_tree_find_node_geq(&__root->rb_root.rbr_tree, &__start); \
if (__node == NULL) \
return NULL; \
KASSERT(START(__node) <= __start); \
Index: src/sys/external/bsd/drm2/include/linux/rbtree.h
diff -u src/sys/external/bsd/drm2/include/linux/rbtree.h:1.8 src/sys/external/bsd/drm2/include/linux/rbtree.h:1.9
--- src/sys/external/bsd/drm2/include/linux/rbtree.h:1.8 Sun Dec 19 01:48:30 2021
+++ src/sys/external/bsd/drm2/include/linux/rbtree.h Sun Dec 19 11:00:18 2021
@@ -1,4 +1,4 @@
-/* $NetBSD: rbtree.h,v 1.8 2021/12/19 01:48:30 riastradh Exp $ */
+/* $NetBSD: rbtree.h,v 1.9 2021/12/19 11:00:18 riastradh Exp $ */
/*-
* Copyright (c) 2013 The NetBSD Foundation, Inc.
@@ -34,6 +34,8 @@
#include <sys/rbtree.h>
+#include <lib/libkern/libkern.h>
+
struct rb_root {
struct rb_tree rbr_tree;
};
@@ -42,6 +44,13 @@ struct rb_root_cached {
struct rb_root rb_root; /* Linux API name */
};
+#define rb_entry(P, T, F) container_of(P, T, F)
+#define rb_entry_safe(P, T, F) \
+({ \
+ __typeof__(P) __p = (P); \
+ __p ? container_of(__p, T, F) : NULL; \
+})
+
static inline bool
RB_EMPTY_ROOT(struct rb_root *root)
{
@@ -49,6 +58,16 @@ RB_EMPTY_ROOT(struct rb_root *root)
return RB_TREE_MIN(&root->rbr_tree) == NULL;
}
+static inline struct rb_node *
+rb_first_cached(struct rb_root_cached *root)
+{
+ char *vnode = RB_TREE_MIN(&root->rb_root.rbr_tree);
+
+ if (vnode)
+ vnode += root->rb_root.rbr_tree.rbt_ops->rbto_node_offset;
+ return (struct rb_node *)vnode;
+}
+
static inline void
rb_erase(struct rb_node *rbnode, struct rb_root *root)
{
@@ -64,6 +83,25 @@ rb_erase_cached(struct rb_node *rbnode,
rb_erase(rbnode, &root->rb_root);
}
+static inline void
+rb_replace_node(struct rb_node *old, struct rb_node *new, struct rb_root *root)
+{
+ void *vold = (char *)old - root->rbr_tree.rbt_ops->rbto_node_offset;
+ void *vnew = (char *)new - root->rbr_tree.rbt_ops->rbto_node_offset;
+ void *collision __diagused;
+
+ rb_tree_remove_node(&root->rbr_tree, vold);
+ collision = rb_tree_insert_node(&root->rbr_tree, vnew);
+ KASSERT(collision == vnew);
+}
+
+static inline void
+rb_replace_node_cached(struct rb_node *old, struct rb_node *new,
+ struct rb_root_cached *root)
+{
+ rb_replace_node(old, new, &root->rb_root);
+}
+
/*
* XXX This is not actually postorder, but I can't fathom why you would
* want postorder for an ordered tree; different insertion orders lead
