| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Sat, 25 Mar 2023 17:16:54 +0800
From: Yan-Jie Wang <yanjiewtw@...il.com>
To: linux-kernel@...r.kernel.org
Cc: Yan-Jie Wang <yanjiewtw@...il.com>
Subject: [PATCH] lib/list_sort: reduce if-statements
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@...il.com>
---
lib/list_sort.c | 51 +++++++++++--------------------------------
tools/lib/list_sort.c | 51 +++++++++++--------------------------------
2 files changed, 26 insertions(+), 76 deletions(-)
diff --git a/lib/list_sort.c b/lib/list_sort.c
index 0fb59e92ca2d..393fcb9948c5 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 (;;) {
+ for (node = NULL; a && b; *node = (*node)->next) {
/* 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;
}
+ *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 (;;) {
+ for (node = NULL; a && b; *node = (*node)->next) {
/* 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;
}
+ 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..5b1baa6a67d9 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 (;;) {
+ for (node = NULL; a && b; *node = (*node)->next) {
/* 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;
}
+ *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 (;;) {
+ for (node = NULL; a && b; *node = (*node)->next) {
/* 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;
}
+ 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
Powered by blists - more mailing lists