Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/sys/external/bsd/drm2/include/linux Touch up the rbtree/inte...
details: https://anonhg.NetBSD.org/src/rev/75eb8e27d6c8
branches: trunk
changeset: 1028417:75eb8e27d6c8
user: riastradh <riastradh%NetBSD.org@localhost>
date: Sun Dec 19 11:00:18 2021 +0000
description:
Touch up the rbtree/intervaltree stubs.
Doesn't work at all yet, but maybe it will help.
diffstat:
sys/external/bsd/drm2/include/linux/interval_tree.h | 10 ++-
sys/external/bsd/drm2/include/linux/interval_tree_generic.h | 12 +-
sys/external/bsd/drm2/include/linux/rbtree.h | 40 ++++++++++++-
3 files changed, 54 insertions(+), 8 deletions(-)
diffs (152 lines):
diff -r e8ab9c950e34 -r 75eb8e27d6c8 sys/external/bsd/drm2/include/linux/interval_tree.h
--- a/sys/external/bsd/drm2/include/linux/interval_tree.h Sun Dec 19 11:00:10 2021 +0000
+++ b/sys/external/bsd/drm2/include/linux/interval_tree.h Sun Dec 19 11:00:18 2021 +0000
@@ -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_
diff -r e8ab9c950e34 -r 75eb8e27d6c8 sys/external/bsd/drm2/include/linux/interval_tree_generic.h
--- a/sys/external/bsd/drm2/include/linux/interval_tree_generic.h Sun Dec 19 11:00:10 2021 +0000
+++ b/sys/external/bsd/drm2/include/linux/interval_tree_generic.h Sun Dec 19 11:00:18 2021 +0000
@@ -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 @@
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 @@
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 @@
{ \
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 @@
{ \
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); \
diff -r e8ab9c950e34 -r 75eb8e27d6c8 sys/external/bsd/drm2/include/linux/rbtree.h
--- a/sys/external/bsd/drm2/include/linux/rbtree.h Sun Dec 19 11:00:10 2021 +0000
+++ b/sys/external/bsd/drm2/include/linux/rbtree.h Sun Dec 19 11:00:18 2021 +0000
@@ -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 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 @@
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(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
Home |
Main Index |
Thread Index |
Old Index