diff options
| author | Doug Moore <dougm@FreeBSD.org> | 2022-09-13 06:11:47 +0000 |
|---|---|---|
| committer | Doug Moore <dougm@FreeBSD.org> | 2022-10-12 02:42:55 +0000 |
| commit | deeaf9c4d85d937d3c935291e913ae614a28f824 (patch) | |
| tree | 296dcdddac7bc8ef3c1999dc8aebd5e905d54887 | |
| parent | 7e139187708a5171d441f1c828d581bda0ab9cdc (diff) | |
| download | src-deeaf9c4d85d937d3c935291e913ae614a28f824.tar.gz src-deeaf9c4d85d937d3c935291e913ae614a28f824.zip | |
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
(cherry picked from commit 4893472c9a18cd8ce3b68d0c54084ef6f0285d0f)
| -rw-r--r-- | sys/compat/linuxkpi/common/include/linux/rbtree.h | 11 | ||||
| -rw-r--r-- | 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 6a64498f6deb..c0cd65f41acb 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -422,7 +422,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 *) @@ -491,7 +492,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 \ @@ -503,12 +505,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; \ @@ -584,7 +585,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 @@ -774,7 +775,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); \ } |