Skip to content

lib: clarify comparison function requirements

Kuan-Wei Chiu lkml 2 versions – Applied

Status from this message: [merged mm-nonmm-stable] lib-list_sort-clarify-comparison-function-requirements-in-list_sort.patch removed from -mm tree

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v2 Latest2 patches 0 repliesApplied 2/2
  2. v12 patches 0 repliesSuperseded

Changes in v2 from the cover letter

- Cc @lkml

Patches in v2 All 2 applied

#Subject and filesSizeRepliesApplied
1/2lib/sort: clarify comparison function requirements in sort_r()lib/sort.c+7 -00 repliesApplied
2/2lib/list_sort: clarify comparison function requirements in list_sort()lib/list_sort.c+7 -00 repliesApplied

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v2 yet.

Read the v2 thread

Cover letter [RESEND PATCH v2 0/2] lib: clarify comparison function requirements

Add a detailed explanation in the sort_r/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.

Changes in resend v2:
- Cc @lkml

Changes in v2:
- Fix typo in patch 2: sort_r() -> list_sort()
- Fix htmldocs build warnings reported by Stephen [5]

[5]: https://lore.kernel.org/all/[email protected]/

Kuan-Wei Chiu (2):
lib/sort: clarify comparison function requirements in sort_r() lib/list_sort: clarify comparison function requirements in list_sort()

 lib/list_sort.c | 7 +++++++
 lib/sort.c      | 7 +++++++
 2 files changed, 14 insertions(+)
Signature · 1 line
2.34.1