The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=b5b07c71e83637af8a2507ef96c32bc7e2d226c6
commit b5b07c71e83637af8a2507ef96c32bc7e2d226c6 Author: Doug Moore <[email protected]> AuthorDate: 2022-09-26 17:39:16 +0000 Commit: Doug Moore <[email protected]> CommitDate: 2022-09-26 17:39:16 +0000 rb_tree: add augmentation comments Add comments to better explain why augmentation is done in several places. Reviewed by: alc MFC after: 2 weeks Differential Revision: https://reviews.freebsd.org/D36646 --- sys/sys/tree.h | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) diff --git a/sys/sys/tree.h b/sys/sys/tree.h index d37e5a338f8b..460af08407b8 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -598,6 +598,10 @@ name##_RB_INSERT_COLOR(struct name *head, \ RB_ROTATE(parent, child, sibdir, field); \ _RB_UP(child, field) = gpar; \ RB_SWAP_CHILD(head, gpar, parent, child, field); \ + /* \ + * Elements rotated down have new, smaller subtrees, \ + * so update augmentation for them. \ + */ \ if (elm != child) \ RB_AUGMENT_CHECK(elm); \ RB_AUGMENT_CHECK(parent); \ @@ -724,6 +728,11 @@ name##_RB_REMOVE_COLOR(struct name *head, \ RB_ROTATE(parent, elm, elmdir, field); \ RB_SET_PARENT(elm, gpar, field); \ RB_SWAP_CHILD(head, gpar, parent, elm, field); \ + /* \ + * An element rotated down, but not into the search \ + * path has a new, smaller subtree, so update \ + * augmentation for it. \ + */ \ if (sib != elm) \ RB_AUGMENT_CHECK(sib); \ return (parent); \ @@ -779,6 +788,11 @@ name##_RB_REMOVE(struct name *head, struct type *out) \ } \ _RB_AUGMENT_WALK(parent, opar, field); \ if (opar != NULL) { \ + /* \ + * Elements rotated into the search path have \ + * changed subtrees, so update augmentation for \ + * them if AUGMENT_WALK didn't. \ + */ \ RB_AUGMENT_CHECK(opar); \ RB_AUGMENT_CHECK(RB_PARENT(opar, field)); \ } \ @@ -811,6 +825,11 @@ name##_RB_INSERT(struct name *head, struct type *elm) \ tmp = name##_RB_INSERT_COLOR(head, parent, elm); \ _RB_AUGMENT_WALK(elm, tmp, field); \ if (tmp != NULL) \ + /* \ + * An element rotated into the search path has a \ + * changed subtree, so update augmentation for it if \ + * AUGMENT_WALK didn't. \ + */ \ RB_AUGMENT_CHECK(tmp); \ return (NULL); \ }
