Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   Yan-Jie Wang <yanjiewtw@gmail.com>
To:     linux-kernel@vger.kernel.org
Cc:     Yan-Jie Wang <yanjiewtw@gmail.com>
Subject: [PATCH v3] lib/list_sort: reduce if-statements
Date:   Sat, 25 Mar 2023 20:32:16 +0800
Message-Id: <20230325123216.226120-1-yanjiewtw@gmail.com>
In-Reply-To: <20230325091654.106040-1-yanjiewtw@gmail.com>
References: <20230325091654.106040-1-yanjiewtw@gmail.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Precedence: bulk

Reduce if-statements in merge and merge_final functions by using
indirect pointers and bitwise operations.

This will make the code more elegant and reduce the number of branch
instructions in compiled code.

Signed-off-by: Yan-Jie Wang <yanjiewtw@gmail.com>
---
Changes since v2:
 * Remove unnecessory assignments to the variable, node.

Changes since v1:
 * Use do-while instead of for-loop to avoid an unnecessory check at
   the beginning of the loop.
 * After moving *node to the next node, just check whether *node is
   NULL or not instead of checking both a && b to determine whether to
   continue.
 * Above changes further reduces the compiled code size and branch
   instructions.

 lib/list_sort.c       | 55 ++++++++++++-------------------------------
 tools/lib/list_sort.c | 55 ++++++++++++-------------------------------
 2 files changed, 30 insertions(+), 80 deletions(-)

diff --git a/lib/list_sort.c b/lib/list_sort.c
index 0fb59e92ca2d..9a2745a1a44b 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -16,28 +16,15 @@ __attribute__((nonnull(2,3,4)))
 static struct list_head *merge(void *priv, list_cmp_func_t cmp,
 				struct list_head *a, struct list_head *b)
 {
-	struct list_head *head, **tail = &head;
+	struct list_head *head, **tail = &head, **node;
 
-	for (;;) {
+	do {
 		/* if equal, take 'a' -- important for sort stability */
-		if (cmp(priv, a, b) <= 0) {
-			*tail = a;
-			tail = &a->next;
-			a = a->next;
-			if (!a) {
-				*tail = b;
-				break;
-			}
-		} else {
-			*tail = b;
-			tail = &b->next;
-			b = b->next;
-			if (!b) {
-				*tail = a;
-				break;
-			}
-		}
-	}
+		node = cmp(priv, a, b) <= 0 ? &a : &b;
+		*tail = *node;
+		tail = &(*node)->next;
+	} while ((*node = (*node)->next));
+	*tail = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
 	return head;
 }
 
@@ -52,29 +39,17 @@ __attribute__((nonnull(2,3,4,5)))
 static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
 			struct list_head *a, struct list_head *b)
 {
-	struct list_head *tail = head;
+	struct list_head *tail = head, **node;
 	u8 count = 0;
 
-	for (;;) {
+	do {
 		/* if equal, take 'a' -- important for sort stability */
-		if (cmp(priv, a, b) <= 0) {
-			tail->next = a;
-			a->prev = tail;
-			tail = a;
-			a = a->next;
-			if (!a)
-				break;
-		} else {
-			tail->next = b;
-			b->prev = tail;
-			tail = b;
-			b = b->next;
-			if (!b) {
-				b = a;
-				break;
-			}
-		}
-	}
+		node = cmp(priv, a, b) <= 0 ? &a : &b;
+		tail->next = *node;
+		(*node)->prev = tail;
+		tail = *node;
+	} while ((*node = (*node)->next));
+	b = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
 
 	/* Finish linking remainder of list b on to tail */
 	tail->next = b;
diff --git a/tools/lib/list_sort.c b/tools/lib/list_sort.c
index 10c067e3a8d2..5054b2196981 100644
--- a/tools/lib/list_sort.c
+++ b/tools/lib/list_sort.c
@@ -15,28 +15,15 @@ __attribute__((nonnull(2,3,4)))
 static struct list_head *merge(void *priv, list_cmp_func_t cmp,
 				struct list_head *a, struct list_head *b)
 {
-	struct list_head *head, **tail = &head;
+	struct list_head *head, **tail = &head, **node;
 
-	for (;;) {
+	do {
 		/* if equal, take 'a' -- important for sort stability */
-		if (cmp(priv, a, b) <= 0) {
-			*tail = a;
-			tail = &a->next;
-			a = a->next;
-			if (!a) {
-				*tail = b;
-				break;
-			}
-		} else {
-			*tail = b;
-			tail = &b->next;
-			b = b->next;
-			if (!b) {
-				*tail = a;
-				break;
-			}
-		}
-	}
+		node = cmp(priv, a, b) <= 0 ? &a : &b;
+		*tail = *node;
+		tail = &(*node)->next;
+	} while ((*node = (*node)->next));
+	*tail = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
 	return head;
 }
 
@@ -51,29 +38,17 @@ __attribute__((nonnull(2,3,4,5)))
 static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
 			struct list_head *a, struct list_head *b)
 {
-	struct list_head *tail = head;
+	struct list_head *tail = head, **node;
 	u8 count = 0;
 
-	for (;;) {
+	do {
 		/* if equal, take 'a' -- important for sort stability */
-		if (cmp(priv, a, b) <= 0) {
-			tail->next = a;
-			a->prev = tail;
-			tail = a;
-			a = a->next;
-			if (!a)
-				break;
-		} else {
-			tail->next = b;
-			b->prev = tail;
-			tail = b;
-			b = b->next;
-			if (!b) {
-				b = a;
-				break;
-			}
-		}
-	}
+		node = cmp(priv, a, b) <= 0 ? &a : &b;
+		tail->next = *node;
+		(*node)->prev = tail;
+		tail = *node;
+	} while ((*node = (*node)->next));
+	b = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
 
 	/* Finish linking remainder of list b on to tail */
 	tail->next = b;

base-commit: 65aca32efdcb0965502d3db2f1fa33838c070952
-- 
2.34.1