git: 871847f65312 - stable/13 - rb_tree: add augmentation comments

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);							\
 }