git: 871847f65312 - stable/13 - rb_tree: add augmentation comments
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Wed, 12 Oct 2022 03:00:27 UTC
The branch stable/13 has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=871847f653127d37626eebbc6f6d0980f540cf85 commit 871847f653127d37626eebbc6f6d0980f540cf85 Author: Doug Moore <dougm@FreeBSD.org> AuthorDate: 2022-09-26 17:39:16 +0000 Commit: Doug Moore <dougm@FreeBSD.org> CommitDate: 2022-10-12 02:47:06 +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 (cherry picked from commit b5b07c71e83637af8a2507ef96c32bc7e2d226c6) --- sys/sys/tree.h | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 51bf4211fea4..10f559f516d2 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); \ }