Messages in this thread Patch in this message | | | From | Yan-Jie Wang <> | Subject | [PATCH v3] lib/list_sort: reduce if-statements | Date | Sat, 25 Mar 2023 20:32:16 +0800 |
| |
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
| |