git: 6f7a96cfe537 - stable/13 - rb_tree: optimize tree rotation

From: Doug Moore <dougm_at_FreeBSD.org>
Date: Mon, 01 Aug 2022 05:45:40 UTC
The branch stable/13 has been updated by dougm:

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

commit 6f7a96cfe53716cc65e6f2ac8eea4d8aeafd1e56
Author:     Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2022-06-25 07:40:16 +0000
Commit:     Doug Moore <dougm@FreeBSD.org>
CommitDate: 2022-08-01 05:43:08 +0000

    rb_tree: optimize tree rotation
    
    The RB_ROTATE macros begin with fetching a field via a pointer. In
    most cases, that value is one that has already been pulled into a
    register, and the compiler cannot infer that. So, to eliminate those
    needless fetches, have the caller of the RB_ROTATE macros present the
    data in the third macro parameter, rather than having the macro fetch
    it.
    
    Differential Revision:  https://reviews.freebsd.org/D35520
    
    (cherry picked from commit 61c74fb66f1bef776923cbd5b2a62fb06b003f0c)
---
 sys/sys/tree.h | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/sys/sys/tree.h b/sys/sys/tree.h
index 2206469db492..f6252ff7ac25 100644
--- a/sys/sys/tree.h
+++ b/sys/sys/tree.h
@@ -380,7 +380,6 @@ struct {								\
 } while (/*CONSTCOND*/ 0)
 
 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {			\
-	(tmp) = RB_RIGHT(elm, field);					\
 	if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {	\
 		RB_SET_PARENT(RB_RIGHT(elm, field), elm, field);	\
 	}								\
@@ -392,7 +391,6 @@ struct {								\
 } while (/*CONSTCOND*/ 0)
 
 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {			\
-	(tmp) = RB_LEFT(elm, field);					\
 	if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {	\
 		RB_SET_PARENT(RB_LEFT(elm, field), elm, field);		\
 	}								\
@@ -484,6 +482,7 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
 			}						\
 			RB_FLIP_RIGHT(parent, field);			\
 			if (RB_RED_RIGHT(parent, field)) {		\
+				child = elm;				\
 				elm = parent;				\
 				continue;				\
 			}						\
@@ -505,6 +504,7 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm)		\
 			}						\
 			RB_FLIP_LEFT(parent, field);			\
 			if (RB_RED_LEFT(parent, field)) {		\
+				child = elm;				\
 				elm = parent;				\
 				continue;				\
 			}						\
@@ -561,6 +561,7 @@ name##_RB_REMOVE_COLOR(struct name *head,				\
 				RB_FLIP_LEFT(parent, field);		\
 			else if (!RB_RED_RIGHT(sib, field)) {		\
 				RB_FLIP_LEFT(parent, field);		\
+				elm = RB_LEFT(sib, field);		\
 				RB_ROTATE_RIGHT(head, sib, elm, field);	\
 				if (RB_RED_RIGHT(elm, field))		\
 					RB_FLIP_LEFT(sib, field);	\
@@ -591,6 +592,7 @@ name##_RB_REMOVE_COLOR(struct name *head,				\
 				RB_FLIP_RIGHT(parent, field);		\
 			else if (!RB_RED_LEFT(sib, field)) {		\
 				RB_FLIP_RIGHT(parent, field);		\
+				elm = RB_RIGHT(sib, field);		\
 				RB_ROTATE_LEFT(head, sib, elm, field);	\
 				if (RB_RED_LEFT(elm, field))		\
 					RB_FLIP_RIGHT(sib, field);	\