From patchwork Tue Jan 16 02:16:56 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 1886902 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=dsE2jvkj; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4TDXhp2XDbz1yPV for ; Tue, 16 Jan 2024 13:17:30 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id A16B53858432 for ; Tue, 16 Jan 2024 02:17:27 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-pl1-x629.google.com (mail-pl1-x629.google.com [IPv6:2607:f8b0:4864:20::629]) by sourceware.org (Postfix) with ESMTPS id 568F8385842C for ; Tue, 16 Jan 2024 02:17:09 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 568F8385842C Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 568F8385842C Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::629 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705371431; cv=none; b=Mbj3SwMw0CO3DtVxJPUvcVoV5o5Qy7hdOg6nwMJ3GiMrWVLoifYwuC6Grkwqrk6POBFig4JV+b0ygxTh5Kw6p6q0Tiiz/dbq7gdZo+X9XSOQ4pVFEJ/Evkd3G4Y8vfxr2dfTst4hQCxev5aTOWGwd32kjXm6pOhPXxQp0ftPYM4= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705371431; c=relaxed/simple; bh=/c18FlqViJUzZCeG/PZ4LSkqOUopxzx2kUS9gYabRcg=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=g9XBYkwzaLLoYIZwoGiJ47aUrLj4Iy3oJh/0H5XCttvw2ewTF6qJPvcZNHZPTHeWfF9JELv12Cb2VCW7zhGtucKUf+gAe20iUYxtKd7bLlUmu1w8VQogNAAWtjVlR6lEsK+SLluKx2gHTkAntEr1VxEyK5AZR+ay/+SWGm71Vp0= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pl1-x629.google.com with SMTP id d9443c01a7336-1d5595997ffso16010275ad.1 for ; Mon, 15 Jan 2024 18:17:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1705371427; x=1705976227; darn=sourceware.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=o+jTE8JMJL2KicNejY/DqXKQDdjS2pv3OAGAV3u2MSw=; b=dsE2jvkjJU+kGPqGD2b8F9w7LpLYJqI/0u4tsHeBZmTZq9wYmCZLKcwkgEaXRlm9h9 +jPf40AhBPp6P5hnailH5dmGg2WdfCil3FRAFWWJBXc+YoQFwgs8B2vMuApv2Z0dzNt8 q7Rv4fCZuKfgXPTJtDaaPkhoRGdFbCNjoX/u9ThipH6akFd1ceErJcJX7EMra8yTU/uj Uo3Wt43q6RnJRT/ROFlGo0MQu1l+agX+DP5LsJM3hn/YKkt2z+FSdYJ4UpN7LELD14dA 9cx68jnesMimzhPdoq/NcTF60mReSW6QdlBolGDCi5MxX6ihCn2YC6ovRXdI0WGfy0sb 4wGw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705371427; x=1705976227; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=o+jTE8JMJL2KicNejY/DqXKQDdjS2pv3OAGAV3u2MSw=; b=Vy8WECSiKGa5gdZbQb8soGj3N/B3aa2uzo1ocG1moYTidKFpZ7t1qDks3JZ/7+lFCX 6uQOE2evZ5AH0aaNCSvfRhAEIhGbCnorWrAQkxgyj4XULN6JjS41q7wR+hrf6VbGhIhr tMG/CEaCvWCciDJvoqnv3p6Q+7yd9m+j3jHNk06OModSnEvTgTZjL4sJd6WABNqhO75r tDwBX38vCy46WBMLZbZwVbYdnSqmYb6a0c3nFYyKAJByny116+AFccbiMuQiusVNOqkl A8Pp7XJ9GtR4RUd3+T6nniJf2qoT2TWpVQYe4vw9p3G7SadpUmuzLtcGYdHDrhJYnsIR qJZA== X-Gm-Message-State: AOJu0YwOsGfAqEQLASq7kwFRw7VjoM0mtzHYDYOCXjUHneSsFIncNkKL K8OEXDRL6HR8Mhs5Tb5vQyTf87nUvjA= X-Google-Smtp-Source: AGHT+IGs6JvEyDD18lqtzjUqdrr4X6VEGQfnKuxbF+O0Gzpt0ktSjn0/TyeQjYMH7UtQoCQzywpT1w== X-Received: by 2002:a17:902:d50e:b0:1d4:e2bc:891c with SMTP id b14-20020a170902d50e00b001d4e2bc891cmr12702448plg.5.1705371427251; Mon, 15 Jan 2024 18:17:07 -0800 (PST) Received: from localhost.localdomain ([140.116.154.65]) by smtp.gmail.com with ESMTPSA id s14-20020a170902b18e00b001d491db286dsm8234762plr.259.2024.01.15.18.17.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 15 Jan 2024 18:17:06 -0800 (PST) From: Kuan-Wei Chiu To: libc-alpha@sourceware.org Cc: adhemerval.zanella@linaro.org, fweimer@redhat.com, Kuan-Wei Chiu Subject: [PATCH 1/2] stdlib: Fix heapsort for cases with exactly two elements Date: Tue, 16 Jan 2024 10:16:56 +0800 Message-Id: <20240116021657.2553198-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20240116021657.2553198-1-visitorckw@gmail.com> References: <20240116021657.2553198-1-visitorckw@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org When malloc fails to allocate a buffer and falls back to heapsort, the current heapsort implementation does not perform sorting when there are exactly two elements. Heapsort is now skipped only when there is exactly one element. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Adhemerval Zanella --- stdlib/qsort.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/stdlib/qsort.c b/stdlib/qsort.c index b29882388e..45af8da80c 100644 --- a/stdlib/qsort.c +++ b/stdlib/qsort.c @@ -162,7 +162,7 @@ get_swap_type (void *const pbase, size_t size) static void heapsort_r (void *base, size_t n, size_t size, __compar_d_fn_t cmp, void *arg) { - if (n <= 1) + if (n == 0) return; enum swap_type_t swap_type = get_swap_type (base, size); From patchwork Tue Jan 16 02:16:57 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 1886903 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20230601 header.b=feMYnQkb; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=8.43.85.97; helo=server2.sourceware.org; envelope-from=libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4TDXhs1GcNz1yPV for ; Tue, 16 Jan 2024 13:17:33 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2EB0438582A1 for ; Tue, 16 Jan 2024 02:17:31 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-pl1-x62a.google.com (mail-pl1-x62a.google.com [IPv6:2607:f8b0:4864:20::62a]) by sourceware.org (Postfix) with ESMTPS id E76703858437 for ; Tue, 16 Jan 2024 02:17:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org E76703858437 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org E76703858437 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::62a ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705371434; cv=none; b=MlYJ4dvQIxE+Tb6a4/oYUC5gI93KBsmYizbJ1aZqXWqgVRV+Hu8AdqEa/0LggRCEUoGs1thqSL7+6kBHsdk1eQUhDfEfZFC/voM9eOMysHaZJcCgRMUxjyjY4N+fdBjGKrxCEDsuyuw9jJ+yvhvCbymVyV2n/26c6msEILkSKM0= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1705371434; c=relaxed/simple; bh=c3ZRJvF4Ybad6SxY7VHa9TyF9JobGmaLEJtosRts7kI=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=BwehAsljnIYze8MgpFDjBUlHjMmzqfO5q8gCzAgOW5WGs09wyzB3OM11G3c3WYfxRSu7Q9EnStQGV0elS1XuvhshaNxUc+5inqfD8Pf5LvrYdZEDXvyS+2twMmYRykxk9H7G0BjH+MfH52bTKJGC+GjQt7iFNNQvhwiVaK11r0w= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pl1-x62a.google.com with SMTP id d9443c01a7336-1d5595997ffso16010325ad.1 for ; Mon, 15 Jan 2024 18:17:11 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1705371430; x=1705976230; darn=sourceware.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=OO2qbjKQgOGNtxHzIyoav6d87an25Ai+r8yotl1jGTA=; b=feMYnQkbTs22huIcVJxJ2Z5i1qr8rmq2XfnqOJUQCbtovYjfSScE++GYb/Uk2ymkZS DsXQI9X4DCRQMj4BQ7o3tLQGWp6iphodsZ0fBei3ubOnKSXtrg7cszf4dKJ6zBnlL1zi VhIvNB8uIc7EY53RHchG+HKo3WLeNLkvgMDa2p5U5w8EFSL2MQn8CsvG0AIQlONt5Osn Zs2F1lEe+jZlUSHD1c1FL3B6Xi5m9mr7C5Dz0k0iHqjW5seJp6XznVQUGAJ5G7getcQ3 72JXqyM+/IKcliUZzYlbbnO97cykRhyZlLc6KzyHhj68s0MpBt4rt7vyvhq9aE8kyjdr md7A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1705371430; x=1705976230; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=OO2qbjKQgOGNtxHzIyoav6d87an25Ai+r8yotl1jGTA=; b=oYmRQbxPAzh9qYNhksDGYpvAPsczJZXgG0vYFEqBKhqwFKDcdewSlGIaXh1n46KhZP fPyMse+NPMhosGIQAv80fhDyHAAIDDM+0nR52nH4EuLqLejpzc3YkYREguP/CTh0cZH3 rp4J8/wM/kYfnkWg2d4ZZc2kh7ULf16wGSPY8qvsB1ldk5NxevBkdRWYYRAQlWd1n3Rn wYsA9LatwFVr7nwwVQFg6qvyteU1N5im1jWngBYaHtZWXNbGcNCJhDajGn9mpuQcrW+E JearIR7vGsxZszubkJXhMbVhuraGYpJTyQKgViVOuXhRvwsuNA67byyRJrPwILuQ99yw EUqg== X-Gm-Message-State: AOJu0Yw1mO1E8kf/TdgsAOlhQDGH+IENRbZ5jMl6pYzgS3u0OGpJrmWE TJzQteA81rvkxIFVT8B5U18IhNG0ccY= X-Google-Smtp-Source: AGHT+IHgELqQDoCrhB7QF1p1yAdOnoPv05KzxArqYt8+Kfl1pmWezCH+tlt7qp1iLt3zwnqVq7sHMg== X-Received: by 2002:a17:902:d50e:b0:1d4:e2bc:891c with SMTP id b14-20020a170902d50e00b001d4e2bc891cmr12702533plg.5.1705371429915; Mon, 15 Jan 2024 18:17:09 -0800 (PST) Received: from localhost.localdomain ([140.116.154.65]) by smtp.gmail.com with ESMTPSA id s14-20020a170902b18e00b001d491db286dsm8234762plr.259.2024.01.15.18.17.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 15 Jan 2024 18:17:09 -0800 (PST) From: Kuan-Wei Chiu To: libc-alpha@sourceware.org Cc: adhemerval.zanella@linaro.org, fweimer@redhat.com, Kuan-Wei Chiu Subject: [PATCH 2/2] stdlib: Verify heapsort for two-element cases Date: Tue, 16 Jan 2024 10:16:57 +0800 Message-Id: <20240116021657.2553198-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.25.1 In-Reply-To: <20240116021657.2553198-1-visitorckw@gmail.com> References: <20240116021657.2553198-1-visitorckw@gmail.com> MIME-Version: 1.0 X-Spam-Status: No, score=-10.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org Adjust the testing approach to start from scenarios with only 2 elements, as insertion sort no longer handles such cases. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Adhemerval Zanella --- stdlib/tst-qsort4.c | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) diff --git a/stdlib/tst-qsort4.c b/stdlib/tst-qsort4.c index 4635275419..247917b454 100644 --- a/stdlib/tst-qsort4.c +++ b/stdlib/tst-qsort4.c @@ -96,9 +96,7 @@ do_test (void) check_one_sort ((signed char[16]) {15, 3, 4, 2, 1, 0, 8, 7, 6, 5, 14, 13, 12, 11, 10, 9}, 16); - /* Array lengths 2 and less are not handled by heapsort_r and - deferred to insertion sort. */ - for (int i = 3; i <= 8; ++i) + for (int i = 2; i <= 8; ++i) { signed char *buf = xmalloc (i); check_combinations (i, buf, 0);