* [PATCH 0/2] stdlib: Fix and verify heapsort for two-element cases
@ 2024-01-16 2:16 Kuan-Wei Chiu
2024-01-16 2:16 ` [PATCH 1/2] stdlib: Fix heapsort for cases with exactly two elements Kuan-Wei Chiu
` (2 more replies)
0 siblings, 3 replies; 6+ messages in thread
From: Kuan-Wei Chiu @ 2024-01-16 2:16 UTC (permalink / raw)
To: libc-alpha; +Cc: adhemerval.zanella, fweimer, Kuan-Wei Chiu
Ensure correct behavior in cases with exactly two elements, and malloc
fails when allocating a buffer. Additionally, adjust the testing
approach to validate the correctness of heapsort for such cases.
Thanks,
Kuan-Wei
Kuan-Wei Chiu (2):
stdlib: Fix heapsort for cases with exactly two elements
stdlib: Verify heapsort for two-element cases
stdlib/qsort.c | 2 +-
stdlib/tst-qsort4.c | 4 +---
2 files changed, 2 insertions(+), 4 deletions(-)
--
2.25.1
^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH 1/2] stdlib: Fix heapsort for cases with exactly two elements
2024-01-16 2:16 [PATCH 0/2] stdlib: Fix and verify heapsort for two-element cases Kuan-Wei Chiu
@ 2024-01-16 2:16 ` Kuan-Wei Chiu
2024-01-16 10:46 ` Adhemerval Zanella Netto
2024-01-16 2:16 ` [PATCH 2/2] stdlib: Verify heapsort for two-element cases Kuan-Wei Chiu
2024-01-17 20:06 ` [PATCH 0/2] stdlib: Fix and verify " Andreas K. Huettel
2 siblings, 1 reply; 6+ messages in thread
From: Kuan-Wei Chiu @ 2024-01-16 2:16 UTC (permalink / raw)
To: libc-alpha; +Cc: adhemerval.zanella, fweimer, Kuan-Wei Chiu
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 <visitorckw@gmail.com>
---
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);
--
2.25.1
^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH 2/2] stdlib: Verify heapsort for two-element cases
2024-01-16 2:16 [PATCH 0/2] stdlib: Fix and verify heapsort for two-element cases Kuan-Wei Chiu
2024-01-16 2:16 ` [PATCH 1/2] stdlib: Fix heapsort for cases with exactly two elements Kuan-Wei Chiu
@ 2024-01-16 2:16 ` Kuan-Wei Chiu
2024-01-16 10:47 ` Adhemerval Zanella Netto
2024-01-17 20:06 ` [PATCH 0/2] stdlib: Fix and verify " Andreas K. Huettel
2 siblings, 1 reply; 6+ messages in thread
From: Kuan-Wei Chiu @ 2024-01-16 2:16 UTC (permalink / raw)
To: libc-alpha; +Cc: adhemerval.zanella, fweimer, Kuan-Wei Chiu
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 <visitorckw@gmail.com>
---
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);
--
2.25.1
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 1/2] stdlib: Fix heapsort for cases with exactly two elements
2024-01-16 2:16 ` [PATCH 1/2] stdlib: Fix heapsort for cases with exactly two elements Kuan-Wei Chiu
@ 2024-01-16 10:46 ` Adhemerval Zanella Netto
0 siblings, 0 replies; 6+ messages in thread
From: Adhemerval Zanella Netto @ 2024-01-16 10:46 UTC (permalink / raw)
To: Kuan-Wei Chiu, libc-alpha; +Cc: fweimer
On 15/01/24 23:16, Kuan-Wei Chiu wrote:
> 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 <visitorckw@gmail.com>
LGTM, thanks.
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
> ---
> 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);
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 2/2] stdlib: Verify heapsort for two-element cases
2024-01-16 2:16 ` [PATCH 2/2] stdlib: Verify heapsort for two-element cases Kuan-Wei Chiu
@ 2024-01-16 10:47 ` Adhemerval Zanella Netto
0 siblings, 0 replies; 6+ messages in thread
From: Adhemerval Zanella Netto @ 2024-01-16 10:47 UTC (permalink / raw)
To: Kuan-Wei Chiu, libc-alpha; +Cc: fweimer
On 15/01/24 23:16, Kuan-Wei Chiu wrote:
> 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 <visitorckw@gmail.com>
LGTM, thanks.
Reviewed-by: Adhemerval Zanella <adhemerval.zanella@linaro.org>
> ---
> 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);
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 0/2] stdlib: Fix and verify heapsort for two-element cases
2024-01-16 2:16 [PATCH 0/2] stdlib: Fix and verify heapsort for two-element cases Kuan-Wei Chiu
2024-01-16 2:16 ` [PATCH 1/2] stdlib: Fix heapsort for cases with exactly two elements Kuan-Wei Chiu
2024-01-16 2:16 ` [PATCH 2/2] stdlib: Verify heapsort for two-element cases Kuan-Wei Chiu
@ 2024-01-17 20:06 ` Andreas K. Huettel
2 siblings, 0 replies; 6+ messages in thread
From: Andreas K. Huettel @ 2024-01-17 20:06 UTC (permalink / raw)
To: libc-alpha; +Cc: adhemerval.zanella, fweimer, Kuan-Wei Chiu, Kuan-Wei Chiu
[-- Attachment #1: Type: text/plain, Size: 750 bytes --]
Am Dienstag, 16. Januar 2024, 03:16:55 CET schrieb Kuan-Wei Chiu:
> Ensure correct behavior in cases with exactly two elements, and malloc
> fails when allocating a buffer. Additionally, adjust the testing
> approach to validate the correctness of heapsort for such cases.
>
> Thanks,
> Kuan-Wei
>
> Kuan-Wei Chiu (2):
> stdlib: Fix heapsort for cases with exactly two elements
> stdlib: Verify heapsort for two-element cases
>
> stdlib/qsort.c | 2 +-
> stdlib/tst-qsort4.c | 4 +---
> 2 files changed, 2 insertions(+), 4 deletions(-)
OK
--
Andreas K. Hüttel
dilfridge@gentoo.org
Gentoo Linux developer
(council, comrel, toolchain, base-system, perl, libreoffice)
https://wiki.gentoo.org/wiki/User:Dilfridge
[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 833 bytes --]
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2024-01-17 20:06 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-01-16 2:16 [PATCH 0/2] stdlib: Fix and verify heapsort for two-element cases Kuan-Wei Chiu
2024-01-16 2:16 ` [PATCH 1/2] stdlib: Fix heapsort for cases with exactly two elements Kuan-Wei Chiu
2024-01-16 10:46 ` Adhemerval Zanella Netto
2024-01-16 2:16 ` [PATCH 2/2] stdlib: Verify heapsort for two-element cases Kuan-Wei Chiu
2024-01-16 10:47 ` Adhemerval Zanella Netto
2024-01-17 20:06 ` [PATCH 0/2] stdlib: Fix and verify " Andreas K. Huettel
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).