Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Subject: Re: [PATCH 4/5] lib/list_sort: Simplify and remove
 MAX_LIST_LENGTH_BITS
To:     George Spelvin <lkml@sdf.org>, linux-kernel@vger.kernel.org
Cc:     Andrew Morton <akpm@linux-foundation.org>,
        Andrey Abramov <st5pub@yandex.ru>,
        Geert Uytterhoeven <geert@linux-m68k.org>,
        Daniel Wagner <daniel.wagner@siemens.com>,
        Rasmus Villemoes <linux@rasmusvillemoes.dk>,
        Don Mullis <don.mullis@gmail.com>,
        Dave Chinner <dchinner@redhat.com>,
        Andy Shevchenko <andriy.shevchenko@linux.intel.com>
References: <cover.1552097842.git.lkml@sdf.org>
 <dd447448384883bd42c41f0de6a83430b6435dc1.1552097842.git.lkml@sdf.org>
From:   Rasmus Villemoes <linux@rasmusvillemoes.dk>
Message-ID: <3194949c-6e04-da01-68df-60ae344db099@rasmusvillemoes.dk>
Date:   Sun, 10 Mar 2019 22:54:41 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
 Thunderbird/60.4.0
MIME-Version: 1.0
In-Reply-To: <dd447448384883bd42c41f0de6a83430b6435dc1.1552097842.git.lkml@sdf.org>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

On 05/03/2019 04.06, George Spelvin wrote:

>   * The comparison function @cmp must return a negative value if @a
>   * should sort before @b, and a positive value if @a should sort after
>   * @b. If @a and @b are equivalent, and their original relative
>   * ordering is to be preserved, @cmp must return 0.
> + *
> + * (Actually, it is always called with @a being the element which was
> + * originally first, so it is not necessary to to distinguish the @a < @b
> + * and @a == @b cases; the return value may be a simple boolean.  But if
> + * you ever *use* this freedom, be sure to update this comment to document
> + * that code now depends on preserving this property!)
>   */

This was and still is used at least by the block layer, and likely
others as well. While 3110fc79606fb introduced a bunch of if() return -1
else if () ... stuff, it still ends with a 0/1 result. Before
3110fc79606fb, it was even more obvious that this property was used. So
I agree that it is worth documenting this feature, both for users of
list_sort, but even more so for future refactorers of it - but you
probably want to change the wording somewhat.

Grepping around shows that this could probably be used in more places,
gaining a cycle or two per cmp callback, e.g. xfs_buf_cmp. But that's of
course outside the scope of this series.

Rasmus