git: f42139db6396 - stable/13 - rb_tree: optimize rb_insert

The branch stable/13 has been updated by dougm:

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

commit f42139db63963da134b9075382cac239a52fd940
Author:     Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2022-08-25 07:26:04 +0000
Commit:     Doug Moore <dougm@FreeBSD.org>
CommitDate: 2022-09-15 16:58:31 +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
    
    (cherry picked from commit b6ce129d24ffe393c43378b1c922d1e56ea2be67)
---
 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 1f0a260e25a7..88d15bda4177 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);							\