The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=4893472c9a18cd8ce3b68d0c54084ef6f0285d0f
commit 4893472c9a18cd8ce3b68d0c54084ef6f0285d0f Author: Doug Moore <[email protected]> AuthorDate: 2022-09-13 06:11:47 +0000 Commit: Doug Moore <[email protected]> CommitDate: 2022-09-13 06:11:47 +0000 rb_tree: pass parent to RB_INSERT_COLOR Change RB_COLOR_INSERT to take a parent parameter, to avoid looking up a value already available. Make adjustments to a linux rbtree header, which invokes it. Reviewed by: alc, hselasky Differential Revision: https://reviews.freebsd.org/D36114 --- sys/compat/linuxkpi/common/include/linux/rbtree.h | 11 ++++++++--- sys/sys/tree.h | 18 ++++++++++-------- 2 files changed, 18 insertions(+), 11 deletions(-) diff --git a/sys/compat/linuxkpi/common/include/linux/rbtree.h b/sys/compat/linuxkpi/common/include/linux/rbtree.h index 1f337d59545c..37537d4b2724 100644 --- a/sys/compat/linuxkpi/common/include/linux/rbtree.h +++ b/sys/compat/linuxkpi/common/include/linux/rbtree.h @@ -74,8 +74,11 @@ RB_PROTOTYPE(linux_root, rb_node, __entry, panic_cmp); #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) \ - linux_root_RB_INSERT_COLOR((struct linux_root *)(root), (node)) +#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_erase(node, root) \ linux_root_RB_REMOVE((struct linux_root *)(root), (node)) #define rb_next(node) RB_NEXT(linux_root, NULL, (node)) @@ -145,7 +148,9 @@ static inline void rb_insert_color_cached(struct rb_node *node, struct rb_root_cached *root, bool leftmost) { - linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root, node); + if (rb_parent(node)) + linux_root_RB_INSERT_COLOR((struct linux_root *)&root->rb_root, + rb_parent(node), node); if (leftmost) root->rb_leftmost = node; } diff --git a/sys/sys/tree.h b/sys/sys/tree.h index e0ab4449bd35..7a574eff3aea 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -426,7 +426,8 @@ struct { \ #define RB_PROTOTYPE_RANK(name, type, attr) #endif #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ - attr void name##_RB_INSERT_COLOR(struct name *, struct type *) + attr void name##_RB_INSERT_COLOR(struct name *, \ + struct type *, struct type *) #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ attr void name##_RB_REMOVE_COLOR(struct name *, \ struct type *, struct type *) @@ -495,7 +496,8 @@ name##_RB_RANK(struct type *elm) \ #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ attr void \ -name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ +name##_RB_INSERT_COLOR(struct name *head, \ + struct type *parent, struct type *elm) \ { \ /* \ * Initially, elm is a leaf. Either its parent was previously \ @@ -507,12 +509,11 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ * uninitialized 'child', and a later iteration can only happen \ * when a value has been assigned to 'child' in the previous \ * one. \ - */ \ - struct type *child, *child_up, *gpar, *parent; \ + */ \ + struct type *child, *child_up, *gpar; \ __uintptr_t elmdir, sibdir; \ \ - gpar = _RB_UP(elm, field); \ - while ((parent = gpar) != NULL) { \ + do { \ /* the rank of the tree rooted at elm grew */ \ gpar = _RB_UP(parent, field); \ elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \ @@ -588,7 +589,7 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ RB_AUGMENT(elm); \ RB_AUGMENT(parent); \ break; \ - } \ + } while ((parent = gpar) != NULL); \ } #ifndef RB_STRICT_HST @@ -778,7 +779,8 @@ name##_RB_INSERT(struct name *head, struct type *elm) \ } \ RB_SET(elm, parent, field); \ *tmpp = elm; \ - name##_RB_INSERT_COLOR(head, elm); \ + if (parent != NULL) \ + name##_RB_INSERT_COLOR(head, parent, elm); \ RB_UPDATE_AUGMENT(elm, field); \ return (NULL); \ }
