Skip to contentSkip to conversation

lib-list_sort-clarify-comparison-function-requirements-in-list_sort.patch removed from -mm tree

merged mm-nonmm-stable Andrew Morton 1 participant 1 message Jan 13, 2025

lore
Share & tools
lore

Andrew Morton

author tree notice Applied
#0 lore raw

The quilt patch titled
Subject: lib/list_sort: clarify comparison function requirements in list_sort()
has been removed from the -mm tree. Its filename was
lib-list_sort-clarify-comparison-function-requirements-in-list_sort.patch

This patch was dropped because it was merged into the mm-nonmm-stable branch of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm

------------------------------------------------------
From: Kuan-Wei Chiu <[email protected]>
Subject: lib/list_sort: clarify comparison function requirements in list_sort()
Date: Tue, 7 Jan 2025 01:01:04 +0800

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.

---

 lib/list_sort.c |    7 +++++++
 1 file changed, 7 insertions(+)
lib/list_sort.c renamed from lib/list_sort.c~lib-list_sort-clarify-comparison-function-requirements-in-list_sort +7 -0
@@ -108,6 +108,13 @@ static void merge_final(void *priv, list
  * and list_sort is a stable sort, so it is not necessary to distinguish
  * the @a < @b and @a == @b cases.
  *
+ * The comparison function must adhere to specific mathematical properties
+ * to ensure correct and stable sorting:
+ * - Antisymmetry: cmp(@a, @b) must return the opposite sign of
+ * cmp(@b, @a).
+ * - Transitivity: if cmp(@a, @b) <= 0 and cmp(@b, @c) <= 0, then
+ * cmp(@a, @c) <= 0.
+ *
  * This is compatible with two styles of @cmp function:
  * - The traditional style which returns <0 / =0 / >0, or
  * - Returning a boolean 0/1.

_

Patches currently in -mm which might be from [email protected] are