From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-pl1-f177.google.com (mail-pl1-f177.google.com [209.85.214.177]) (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 EBF201DED4A for ; Mon, 6 Jan 2025 17:01:19 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.177 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736182881; cv=none; b=pwO8nz8LNK9LCvmtwhaBAJB2vPYYpOVbXeZNrrj8KnFManvmf0wTamgf8EADHWGdi/0njipJn1T+ijBVu//OlZox9pIsVAT2L1IelpvkZHawmNhr0FpDDv0GxfPRm4vHZl+YiaBEAF0NQZ+xEEzKwG6mLR2lQuF5du7ywgqlKlA= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736182881; c=relaxed/simple; bh=/s7GG7fmRefmDjQyiYhI0kRTFg3yuxtTX3HAWzghcns=; h=From:To:Cc:Subject:Date:Message-Id:MIME-Version; b=cOGhRkLlWmSM1POZUT3ZFDy8VyAZGKU5p7aAdM97ZW9iKuv52WlNN2+uXJaG9EzEP5ZbBVbD2twQoKCzKYQvRvLBqWyPVz4GleWDdMEz+qvBfxMDXR4uUhPe4MIVkEmLCz3Mkclm9A02rUmOjbEukKWWftnqekmgh2wljImQJ5g= 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=cnBvOwCb; arc=none smtp.client-ip=209.85.214.177 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="cnBvOwCb" Received: by mail-pl1-f177.google.com with SMTP id d9443c01a7336-21675fd60feso11368985ad.2 for ; Mon, 06 Jan 2025 09:01:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1736182879; x=1736787679; 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=3fHQKTGtLS19Mv0lD9L4dKLcs05cfTx3cBzGyqE9wTQ=; b=cnBvOwCbmDyp1hViuygN2eTD8RD7m2ogmPldTda+IvYSZIOIrq9eXn6HXl6t40Qdty C1m7RbSZpUJfJmd673YvRw8v1xACYtK8ZWIpaGvlOSHmOJU1iU2h9nsvpC5PzRe5sQMM KGBp9FalW7gBwwMSTzAdPbVoZpwnN0SdCBD02BdAH3zDsBmXlUMLsxFwR7uqUANyGLqB CuQ8oDgJprXoDByJqda1EiQ+r6cxprdcaxb24HheDm0YgBQ3APaUZN/h4BoTk5g8/eVu cHQgf6SocYDVA0JFg739jtXrf/RltYA0cIpk/6II0YkuLleAu3a3NGpUqATgaCaPT3Ya u4dg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1736182879; x=1736787679; 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=3fHQKTGtLS19Mv0lD9L4dKLcs05cfTx3cBzGyqE9wTQ=; b=Z1T0gD/b4+m4mu1o4WPrMa5UX5/7YteBj/NOZ+4NDiLz9ISg7DTVXzECou2uZwd3Lz 0YtTzK2gzPapDhj9MjhS/h9aJxOTTneR2xnerAeslOD0pHcLHRP5GMndwTDdtwx+ZFmc wd8Y09mJojNIJNtf4NiucNZjKDvr504mbfs+/Td+fZDLyUotaaIVNv5Npl7FfNQttvXc 7T/dLRIjzh66XbyKLBIdXk08kCZJmkystc+Yci/BWYtxFNTi+8QS2L19urHGNIBmmMd1 +rZRww6LG1XwtFnQHF/mYCSmEgUoLBj9u7tTUaACodxEUKA5WcxxxcQVbWAQ6KZCYBt8 xWNw== X-Forwarded-Encrypted: i=1; AJvYcCXU8x6+B+oeIr+SJj/5HJ5n6gMiwKvGWkQJY4dl02YLkk1FqYTtHCCRwoo0aE8tf47wHouOUhxrRgmLzQM=@vger.kernel.org X-Gm-Message-State: AOJu0YwCeaNxqfqXrthGNjwnuxDELpwEkyBww1ZALxMJqAQXGRWaAyAY LRv8TxAVJxuV9AO5LisAD/UZL5IonLueS8Egg1c2saxNmiKn4He7 X-Gm-Gg: ASbGncuvT3h08dfYep532ZHAzs84tUgVxNKm3DOl04F7DCaB2zxmdJIU3x0xix9f5h7 SVsV8pZahank9qe+SZsLaGRAiAte2XSjfk3AwaGqc9gVHN828JLcdxZSuu8iNmA9vKvHpCCt1e/ RVCHvvND3h3pcNuXlWmQrFnjmttaQO0GzPWJEEpAKmR8+jUG+QYTlyZF/x8BVQPxR/9BUVi7IiT IgQKEjGpYkksyk3UPvLsXC7ilEY75eU3rk50KfUrVsp4s3pTlWRuOsv1yWJfM9bgEVQBHfIbuge Ib+AR1x1M7c= X-Google-Smtp-Source: AGHT+IGURgKLMoJkIMMznl+w7INe+2pwIrk56Aatlv12k78RYMBgXkiZF6Ye8AB0myLpYIxdLNeQ8A== X-Received: by 2002:a17:902:ec88:b0:216:57a6:28b5 with SMTP id d9443c01a7336-219e6f3ab09mr865061925ad.56.1736182878979; Mon, 06 Jan 2025 09:01:18 -0800 (PST) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-219dc9cdeabsm285196315ad.125.2025.01.06.09.01.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 06 Jan 2025 09:01:18 -0800 (PST) From: Kuan-Wei Chiu To: akpm@linux-foundation.org Cc: jserv@ccns.ncku.edu.tw, Chun-Ying Huang , linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v2 0/2] lib: clarify comparison function requirements Date: Tue, 7 Jan 2025 01:01:02 +0800 Message-Id: <20250106170104.3137845-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] 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/20250106174236.5a74e94e@canb.auug.org.au/ 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(+) -- 2.34.1