git: b6ce129d24ff - main - rb_tree: optimize rb_insert

The branch main has been updated by dougm:

URL: https://cgit.FreeBSD.org/src/commit/?id=b6ce129d24ffe393c43378b1c922d1e56ea2be67

commit b6ce129d24ffe393c43378b1c922d1e56ea2be67
Author:     Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2022-08-25 07:26:04 +0000
Commit:     Doug Moore <dougm@FreeBSD.org>
CommitDate: 2022-08-25 07:26:04 +0000

    rb_tree: optimize rb_insert
    
    In searching for where to insert a new node, RB_INSERT discards the
    address of the pointer that will have to be modified, so that it must
    find it again from the values of 'parent' and 'comp'. Stop discarding
    that address, and so avoid having to recompute it.
    
    Reviewed by:    alc
    MFC after:      3 weeks
    Differential Revision:  https://reviews.freebsd.org/D36317
---
 sys/sys/tree.h | 21 ++++++++-------------
 1 file changed, 8 insertions(+), 13 deletions(-)

diff --git a/sys/sys/tree.h b/sys/sys/tree.h
index 1d4271c2144a..35c6b28be868 100644
--- a/sys/sys/tree.h
+++ b/sys/sys/tree.h
@@ -728,26 +728,21 @@ attr struct type *							\
 name##_RB_INSERT(struct name *head, struct type *elm)			\
 {									\
 	struct type *tmp;						\
+	struct type **tmpp = &RB_ROOT(head);				\
 	struct type *parent = NULL;					\
-	__typeof(cmp(NULL, NULL)) comp = 0;				\
-	tmp = RB_ROOT(head);						\
-	while (tmp) {							\
+									\
+	while ((tmp = *tmpp) != NULL) {					\
 		parent = tmp;						\
-		comp = (cmp)(elm, parent);				\
+		__typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent);	\
 		if (comp < 0)						\
-			tmp = RB_LEFT(tmp, field);			\
+			tmpp = &RB_LEFT(parent, field);			\
 		else if (comp > 0)					\
-			tmp = RB_RIGHT(tmp, field);			\
+			tmpp = &RB_RIGHT(parent, field);		\
 		else							\
-			return (tmp);					\
+			return (parent);				\
 	}								\
 	RB_SET(elm, parent, field);					\
-	if (parent == NULL)						\
-		RB_ROOT(head) = elm;					\
-	else if (comp < 0)						\
-		RB_LEFT(parent, field) = elm;				\
-	else								\
-		RB_RIGHT(parent, field) = elm;				\
+	*tmpp = elm;							\
 	name##_RB_INSERT_COLOR(head, elm);				\
 	RB_UPDATE_AUGMENT(elm, field);					\
 	return (NULL);							\