From nobody Sun Feb 8 14:51:50 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 475A6C6FD20 for ; Sat, 25 Mar 2023 09:21:44 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232114AbjCYJRS (ORCPT ); Sat, 25 Mar 2023 05:17:18 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38206 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230192AbjCYJRP (ORCPT ); Sat, 25 Mar 2023 05:17:15 -0400 Received: from mail-pl1-x631.google.com (mail-pl1-x631.google.com [IPv6:2607:f8b0:4864:20::631]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 98664EC5B for ; Sat, 25 Mar 2023 02:17:14 -0700 (PDT) Received: by mail-pl1-x631.google.com with SMTP id w4so3933096plg.9 for ; Sat, 25 Mar 2023 02:17:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1679735834; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=LJpIXu9tlf2Gu4D95jY9X2YoHbkoJ6/PZq6kehT2lyI=; b=X5/UuRHfQcNqxm8pRv93hP3LY/wEcu/s/2KLDeXgpChaPWdVC6mtl6TNoGhXOfOHRI uL4/xxoaFT8dYHMld05dV2hcxyVHi5k6yOEDd3o15KzIvSBKtH921w4pjdQhomTp1Uoa 6J+VQvduvFX0vIlvxFYsj1dtb8+ggOWKDtUc5JZQCzzVOhRO+XxVyQoN2rim6c2hVkBC V35xCAeceVQqJ17cRoyDHH1XHd8lpekEPKXX8jy+MqdgU4xUDJOkoAYWWW7AfG/bkLub W4v98Z3hwNK290OLO4eHDKuheJA9e93nimomwC1WpBPx1qOOhm3lL0Irhf61f8XXqEDj 4v9g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679735834; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=LJpIXu9tlf2Gu4D95jY9X2YoHbkoJ6/PZq6kehT2lyI=; b=q9eEl9Mj56i3f1eDtsT4bLEiIbGzJm6uq82KQr9gWUPlpctuIJdISAfgqBs+oaUBw1 bzNFL2ZwP0+z8OguTxHG2aqLPxVBIl1atxPW+s7IZLo7uZElIMfZBOfh8itaeUyX4QOB rmmeTtvjHvhx6WLlWzPhLgP6d2iQ1P6hTICdQ5kILdOL0PfLTgAbEo5PgvzAC7LyKIGA ZJoZRSdLs04y7siZb3CsBe1OmXiNthswVJP43I96E+JSODqr8oluH6lUr7cfJytgN3eH 5jFSMiaYgpMDq0IIEQM5yuerMq/C2m6NQWpD3HOpk7AYffJoYV1hnMmX/gu6oioUgYXJ Nbgg== X-Gm-Message-State: AAQBX9d1ZC3hmgB9FZBFcSt1u/Rkt5w9VDtw6je1w2Shi+UyLxVv3HKP LmDKuzZ+k2wl1+F6oqKqayykmcytGbg= X-Google-Smtp-Source: AKy350YSY+yLrMXngrhU4OppEO85gGV+mQ3qhd9YLeT2ePtMLuAy4aTQwH4X/InP1Gm8KjCbAJdvJQ== X-Received: by 2002:a17:90b:1647:b0:237:50b6:7835 with SMTP id il7-20020a17090b164700b0023750b67835mr5913828pjb.20.1679735833700; Sat, 25 Mar 2023 02:17:13 -0700 (PDT) Received: from Dommie-Laptop.. ([180.217.16.141]) by smtp.gmail.com with ESMTPSA id a8-20020a170902900800b0019a88c1cf63sm15495670plp.180.2023.03.25.02.17.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 25 Mar 2023 02:17:12 -0700 (PDT) From: Yan-Jie Wang To: linux-kernel@vger.kernel.org Cc: Yan-Jie Wang Subject: [PATCH] lib/list_sort: reduce if-statements Date: Sat, 25 Mar 2023 17:16:54 +0800 Message-Id: <20230325091654.106040-1-yanjiewtw@gmail.com> X-Mailer: git-send-email 2.34.1 MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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 --- 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 =3D &head; + struct list_head *head, **tail =3D &head, **node; =20 - for (;;) { + for (node =3D NULL; a && b; *node =3D (*node)->next) { /* if equal, take 'a' -- important for sort stability */ - if (cmp(priv, a, b) <=3D 0) { - *tail =3D a; - tail =3D &a->next; - a =3D a->next; - if (!a) { - *tail =3D b; - break; - } - } else { - *tail =3D b; - tail =3D &b->next; - b =3D b->next; - if (!b) { - *tail =3D a; - break; - } - } + node =3D cmp(priv, a, b) <=3D 0 ? &a : &b; + *tail =3D *node; + tail =3D &(*node)->next; } + *tail =3D (struct list_head *) ((uintptr_t) a | (uintptr_t) b); return head; } =20 @@ -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 =3D head; + struct list_head *tail =3D head, **node; u8 count =3D 0; =20 - for (;;) { + for (node =3D NULL; a && b; *node =3D (*node)->next) { /* if equal, take 'a' -- important for sort stability */ - if (cmp(priv, a, b) <=3D 0) { - tail->next =3D a; - a->prev =3D tail; - tail =3D a; - a =3D a->next; - if (!a) - break; - } else { - tail->next =3D b; - b->prev =3D tail; - tail =3D b; - b =3D b->next; - if (!b) { - b =3D a; - break; - } - } + node =3D cmp(priv, a, b) <=3D 0 ? &a : &b; + tail->next =3D *node; + (*node)->prev =3D tail; + tail =3D *node; } + b =3D (struct list_head *) ((uintptr_t) a | (uintptr_t) b); =20 /* Finish linking remainder of list b on to tail */ tail->next =3D 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 =3D &head; + struct list_head *head, **tail =3D &head, **node; =20 - for (;;) { + for (node =3D NULL; a && b; *node =3D (*node)->next) { /* if equal, take 'a' -- important for sort stability */ - if (cmp(priv, a, b) <=3D 0) { - *tail =3D a; - tail =3D &a->next; - a =3D a->next; - if (!a) { - *tail =3D b; - break; - } - } else { - *tail =3D b; - tail =3D &b->next; - b =3D b->next; - if (!b) { - *tail =3D a; - break; - } - } + node =3D cmp(priv, a, b) <=3D 0 ? &a : &b; + *tail =3D *node; + tail =3D &(*node)->next; } + *tail =3D (struct list_head *) ((uintptr_t) a | (uintptr_t) b); return head; } =20 @@ -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 =3D head; + struct list_head *tail =3D head, **node; u8 count =3D 0; =20 - for (;;) { + for (node =3D NULL; a && b; *node =3D (*node)->next) { /* if equal, take 'a' -- important for sort stability */ - if (cmp(priv, a, b) <=3D 0) { - tail->next =3D a; - a->prev =3D tail; - tail =3D a; - a =3D a->next; - if (!a) - break; - } else { - tail->next =3D b; - b->prev =3D tail; - tail =3D b; - b =3D b->next; - if (!b) { - b =3D a; - break; - } - } + node =3D cmp(priv, a, b) <=3D 0 ? &a : &b; + tail->next =3D *node; + (*node)->prev =3D tail; + tail =3D *node; } + b =3D (struct list_head *) ((uintptr_t) a | (uintptr_t) b); =20 /* Finish linking remainder of list b on to tail */ tail->next =3D b; base-commit: 65aca32efdcb0965502d3db2f1fa33838c070952 --=20 2.34.1