]> www.infradead.org Git - users/jedix/linux-maple.git/commit
lib/list_sort: clarify comparison function requirements in list_sort()
authorKuan-Wei Chiu <visitorckw@gmail.com>
Mon, 6 Jan 2025 17:01:04 +0000 (01:01 +0800)
committerAndrew Morton <akpm@linux-foundation.org>
Sat, 25 Jan 2025 06:47:23 +0000 (22:47 -0800)
commite420460ba443e8ad1cd71568c50b6e09d13fb106
treeb94129ad6948ce39a2381aee24cc140f5586414d
parent4e0a15f8b4bd47548032acccdbeb5b9083b3675e
lib/list_sort: clarify comparison function requirements in list_sort()

Add a detailed explanation in the list_sort() kernel doc comment
specifying that the comparison function must satisfy antisymmetry and
transitivity.  These properties are essential for the sorting algorithm to
produce correct results.

Issues have arisen in the past [1][2][3][4] where comparison functions
violated the transitivity property, causing sorting algorithms to fail to
correctly order elements.  While these requirements may seem
straightforward, they are commonly misunderstood or overlooked, leading to
bugs.  Highlighting these properties in the documentation will help
prevent such mistakes in the future.

Link: https://lore.kernel.org/lkml/20240701205639.117194-1-visitorckw@gmail.com
Link: https://lore.kernel.org/lkml/20241203202228.1274403-1-visitorckw@gmail.com
Link: https://lore.kernel.org/lkml/20241209134226.1939163-1-visitorckw@gmail.com
Link: https://lore.kernel.org/lkml/20241209145728.1975311-1-visitorckw@gmail.com
Link: https://lkml.kernel.org/r/20250106170104.3137845-3-visitorckw@gmail.com
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
Cc: Ching-Chun (Jim) Huang <jserv@ccns.ncku.edu.tw>
Cc: <chuang@cs.nycu.edu.tw>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
lib/list_sort.c