From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-pl1-f179.google.com (mail-pl1-f179.google.com [209.85.214.179]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 4BEEF211A3A for ; Tue, 24 Dec 2024 16:39:35 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.179 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1735058376; cv=none; b=CadDTabzYltMzkmLKlZlT+Rt/lGag85DVomAPulTBIrIdHyPNoY8yMqVY6LdptMhEC8XcMcVR5X90hfmepKKWz9nTH8agvDBLQVP3GsHeevgUnVPduxc6kB7kn/WwZ8mtjUvUACPKg549OfoiUQrFRfOEM5AerYo/SBoTsemDAA= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1735058376; c=relaxed/simple; bh=M1kJGXD5mCZCiDJ20JfE5o6BkcEv25iQK/00zARP0fg=; h=From:To:Cc:Subject:Date:Message-Id:MIME-Version; b=dOfAtQXB8MeBh2ArKxIv+uj+LsETLYXrXdfC3RUS74qaKF1Bi1KpmgpMDrbNdOY9PSrLuDOgQKB5LDBmJPRqpR8zeKmBq5r3AbAImkdQjBVuBg/oHBpW/d5JM0vjbEcXEv/ki8Xd30hRxwPLkqvOP8Gwkf06E5kF3yCKk+842B8= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=KNGZzECd; arc=none smtp.client-ip=209.85.214.179 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="KNGZzECd" Received: by mail-pl1-f179.google.com with SMTP id d9443c01a7336-2164b662090so49531455ad.1 for ; Tue, 24 Dec 2024 08:39:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1735058374; x=1735663174; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=mIoILHzC0XEMy2cdzCc1fIAievzG0nUjmmEhaJgCdzA=; b=KNGZzECdSuhHr8gQNPMqFq/Wz5QDcGh0c+aj0ywprmf07QqmQVrqnx2n3x7OsNV5zd jlPKrHmms8iQDNQ0QqJIEJOINw8nmjwerJEjIwJ0p1ROucBUIylj0vHx6CqvkvVLkDgE W5WAghNQkyBMHU19ubMiruW2nqPnQCS+OzYEB4PGOpHMJzJI+LNZvtiat1qK9uS3TbJO zU8p/vygZeCGWJV0OrRSTSPHo2rE3ax1fWk08FZA/Ptk01m93BArrJ//2MxnttYiCU4u 1F2Y3b6SBHADIoD+nWzP8/88D6seKj/3UB3zxgiSNmYjRoQIAZzFCoqVy7JNjMgIiksd tPrQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1735058374; x=1735663174; 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=mIoILHzC0XEMy2cdzCc1fIAievzG0nUjmmEhaJgCdzA=; b=Zu8kNYuC0qS4sP0ruyXK5LlNBpk4LTyM4lcXno7lP1tjMkpKGOIbDlgAxJ//AKZ7nJ IoDF09ClPrOQ+yxf77IVHfjqdWKqvk8SzDdP/yy7hH023kn32odEHx4j44RvHAxx73me /E/9bt6O3kjhDgha1sX/GYxLg0kSKRAHpSq+LguSWoz0QbFBwR3PYu6+36KiG9VzJydl 1ZssofP5oPupuyKg43hSbT9QaCMXyiKJ15SUEKE9a6AVnVKEvqSMXmeSETu6io+muYOS oJWMxxVggLj851tVhXtcfdvrtRzoNzs8+DOSqFUX6O9zSodbhpXEtrdeXgfYoifkAA9A P4wg== X-Forwarded-Encrypted: i=1; AJvYcCWZ3LEwGWl4K6k/GopIv1cecCu5/1NUZ4+YRvFZDt9B38r159pzzrzAULeroGSF9Zh820ULhWOcZlWqGJ0=@vger.kernel.org X-Gm-Message-State: AOJu0Yw+9h0wcXfmViD8II4GX5PCXEwzGuQUwL8wEcOdU+SNSgMaQ1Te 45t249I0JtjEHwqLKlyGawmO3dUpvZb4F3kDxEVVKY7xMuCdzMGhEv941GhS X-Gm-Gg: ASbGncskeVA2vpJ2saZTHhfYgqcUQ9s4nqwpEyXfrbzKHKN5maOSNRv5vY2Bjxyg9Ou 8aJ0P9FWujoBqt5Fnj1cboglthwALNcRIvu19gvL1imdWDlDIgI+J9RTQ+knBugeD0r4QdMy6e9 Bw24lFr+ckLo8RzJhwFr/E8H6GFwJaf4jhMBSIQ8QkWgjCV9gQjG5RURjgEkhPlcdn5V7gSseAl XCRJWJEf588KMwsFXxQNfSkEu/7BTCU4ylDMYkIyPU0JK7N9hv58jR+NsXpo98cwu2MFxWh01c/ 9mOER37YBmw= X-Google-Smtp-Source: AGHT+IEFWJvpRxgd7bhweZkc2uw6JYeYQC3CaEDked7/a3vyeqTdL3Dn4D3JCeWJTYR4K8GmtDrgbA== X-Received: by 2002:a05:6a20:7487:b0:1e1:b404:d854 with SMTP id adf61e73a8af0-1e5e04a2becmr29139066637.23.1735058374490; Tue, 24 Dec 2024 08:39:34 -0800 (PST) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-72aad8309f3sm9864895b3a.55.2024.12.24.08.39.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Dec 2024 08:39:33 -0800 (PST) From: Kuan-Wei Chiu To: akpm@linux-foundation.org Cc: jserv@ccns.ncku.edu.tw, chuang@cs.nycu.edu.tw, linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 0/2] lib: clarify comparison function requirements Date: Wed, 25 Dec 2024 00:39:25 +0800 Message-Id: <20241224163927.2558195-1-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit 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. Link: https://lore.kernel.org/lkml/20240701205639.117194-1-visitorckw@gmail.com [1] Link: https://lore.kernel.org/lkml/20241203202228.1274403-1-visitorckw@gmail.com [2] Link: https://lore.kernel.org/lkml/20241209134226.1939163-1-visitorckw@gmail.com [3] Link: https://lore.kernel.org/lkml/20241209145728.1975311-1-visitorckw@gmail.com [4] Kuan-Wei Chiu (2): lib/sort: clarify comparison function requirements in sort_r() lib/list_sort: clarify comparison function requirements in sort_r() lib/list_sort.c | 7 +++++++ lib/sort.c | 7 +++++++ 2 files changed, 14 insertions(+) -- 2.34.1