Page MenuHomeFreeBSD
Files F98096623

D37716.diff
No OneTemporary
Actions

D37716.diff
View Options

diff --git a/sys/compat/linuxkpi/common/include/linux/rbtree.h b/sys/compat/linuxkpi/common/include/linux/rbtree.h
--- a/sys/compat/linuxkpi/common/include/linux/rbtree.h
+++ b/sys/compat/linuxkpi/common/include/linux/rbtree.h
@@ -74,11 +74,8 @@
#define RB_EMPTY_NODE(node) (RB_PARENT(node, __entry) == node)
#define RB_CLEAR_NODE(node) RB_SET_PARENT(node, node, __entry)
-#define rb_insert_color(node, root) do { \
- if (rb_parent(node)) \
- linux_root_RB_INSERT_COLOR((struct linux_root *)(root), \
- rb_parent(node), (node)); \
-} while (0)
+#define rb_insert_color(node, root) \
+ linux_root_RB_INSERT_COLOR((struct linux_root *)(root), (node))
#define rb_erase(node, root) \
linux_root_RB_REMOVE((struct linux_root *)(root), (node))
#define rb_next(node) RB_NEXT(linux_root, NULL, (node))
@@ -148,9 +145,7 @@
rb_insert_color_cached(struct rb_node *node, struct rb_root_cached *root,
bool leftmost)
{
- if (rb_parent(node))
- linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root,
- rb_parent(node), node);
+ linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root, node);
if (leftmost)
root->rb_leftmost = node;
}
diff --git a/sys/sys/tree.h b/sys/sys/tree.h
--- a/sys/sys/tree.h
+++ b/sys/sys/tree.h
@@ -331,7 +331,7 @@
* that the left or right child of the tree node is "red".
*/
#define _RB_LINK(elm, dir, field) (elm)->field.rbe_link[dir]
-#define _RB_UP(elm, field) _RB_LINK(elm, 0, field)
+#define _RB_UP(elm, field) _RB_LINK(elm, 2, field)
#define _RB_L ((__uintptr_t)1)
#define _RB_R ((__uintptr_t)2)
#define _RB_LR ((__uintptr_t)3)
@@ -341,8 +341,8 @@
((__uintptr_t)elm & ~_RB_LR)
#define RB_PARENT(elm, field) _RB_PTR(_RB_UP(elm, field))
-#define RB_LEFT(elm, field) _RB_LINK(elm, _RB_L, field)
-#define RB_RIGHT(elm, field) _RB_LINK(elm, _RB_R, field)
+#define RB_LEFT(elm, field) _RB_LINK(elm, _RB_L-1, field)
+#define RB_RIGHT(elm, field) _RB_LINK(elm, _RB_R-1, field)
#define RB_ROOT(head) (head)->rbh_root
#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
@@ -398,10 +398,10 @@
* update the same pair of pointer fields with distinct values.
*/
#define RB_ROTATE(elm, tmp, dir, field) do { \
- if ((_RB_LINK(elm, dir ^ _RB_LR, field) = \
- _RB_LINK(tmp, dir, field)) != NULL) \
- RB_SET_PARENT(_RB_LINK(tmp, dir, field), elm, field); \
- _RB_LINK(tmp, dir, field) = (elm); \
+ if ((_RB_LINK(elm, (dir ^ _RB_LR)-1, field) = \
+ _RB_LINK(tmp, dir-1, field)) != NULL) \
+ RB_SET_PARENT(_RB_LINK(tmp, dir-1, field), elm, field); \
+ _RB_LINK(tmp, dir-1, field) = (elm); \
RB_SET_PARENT(elm, tmp, field); \
} while (/*CONSTCOND*/ 0)
@@ -412,6 +412,7 @@
RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
RB_PROTOTYPE_RANK(name, type, attr) \
+ RB_PROTOTYPE_DO_INSERT_COLOR(name, type, attr); \
RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \
RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
RB_PROTOTYPE_INSERT_FINISH(name, type, attr); \
@@ -431,9 +432,11 @@
#else
#define RB_PROTOTYPE_RANK(name, type, attr)
#endif
-#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
- attr struct type *name##_RB_INSERT_COLOR(struct name *, \
+#define RB_PROTOTYPE_DO_INSERT_COLOR(name, type, attr) \
+ attr struct type *name##_RB_DO_INSERT_COLOR(struct name *, \
struct type *, struct type *)
+#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
+ attr struct type *name##_RB_INSERT_COLOR(struct name *, struct type *)
#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
attr struct type *name##_RB_REMOVE_COLOR(struct name *, \
struct type *, struct type *)
@@ -472,6 +475,7 @@
RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
RB_GENERATE_RANK(name, type, field, attr) \
+ RB_GENERATE_DO_INSERT_COLOR(name, type, field, attr) \
RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
RB_GENERATE_INSERT_FINISH(name, type, field, attr) \
@@ -522,9 +526,9 @@
#define RB_GENERATE_RANK(name, type, field, attr)
#endif
-#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
+#define RB_GENERATE_DO_INSERT_COLOR(name, type, field, attr) \
attr struct type * \
-name##_RB_INSERT_COLOR(struct name *head, \
+name##_RB_DO_INSERT_COLOR(struct name *head, \
struct type *parent, struct type *elm) \
{ \
/* \
@@ -625,6 +629,20 @@
return (NULL); \
}
+#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
+attr struct type * \
+name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
+{ \
+ struct type *parent, *tmp; \
+ \
+ parent = RB_PARENT(elm, field); \
+ if (parent != NULL) \
+ tmp = name##_RB_DO_INSERT_COLOR(head, parent, elm); \
+ else \
+ tmp = NULL; \
+ return (tmp); \
+}
+
#ifndef RB_STRICT_HST
/*
* In REMOVE_COLOR, the HST paper, in figure 3, in the single-rotate case, has
@@ -671,7 +689,7 @@
continue; \
} \
sibdir = elmdir ^ _RB_LR; \
- sib = _RB_LINK(parent, sibdir, field); \
+ sib = _RB_LINK(parent, sibdir-1, field); \
up = _RB_UP(sib, field); \
_RB_BITS(up) ^= _RB_LR; \
if ((_RB_BITS(up) & _RB_LR) == 0) { \
@@ -700,7 +718,7 @@
* / z \
* y \
*/ \
- elm = _RB_LINK(sib, elmdir, field); \
+ elm = _RB_LINK(sib, elmdir-1, field); \
/* elm is a 1-child. First rotate at elm. */ \
RB_ROTATE(sib, elm, sibdir, field); \
up = _RB_UP(elm, field); \
@@ -826,7 +844,7 @@
RB_SET(elm, parent, field); \
*pptr = elm; \
if (parent != NULL) \
- tmp = name##_RB_INSERT_COLOR(head, parent, elm); \
+ tmp = name##_RB_DO_INSERT_COLOR(head, parent, elm); \
_RB_AUGMENT_WALK(elm, tmp, field); \
if (tmp != NULL) \
/* \

File Metadata

Mime Type
text/plain
Expires
Thu, Oct 3, 8:16 AM (21 h, 45 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
13436246
Default Alt Text
D37716.diff (5 KB)

Event Timeline