Re: git: c65e42dbde41 - main - libc: add test case for qsort_b(3)
- In reply to: Hans Petter Selasky : "Re: git: c65e42dbde41 - main - libc: add test case for qsort_b(3)"
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Wed, 07 Sep 2022 07:14:10 UTC
On 9/7/22 08:58, Hans Petter Selasky wrote:
> On 9/7/22 08:12, Xin LI wrote:
>> The branch main has been updated by delphij:
>>
>> URL:
>> https://cgit.FreeBSD.org/src/commit/?id=c65e42dbde4198ce46aef7ddac061390abe672dc
>>
>>
>> commit c65e42dbde4198ce46aef7ddac061390abe672dc
>> Author: Xin LI <delphij@FreeBSD.org>
>> AuthorDate: 2022-09-07 06:11:46 +0000
>> Commit: Xin LI <delphij@FreeBSD.org>
>> CommitDate: 2022-09-07 06:11:46 +0000
>>
>> libc: add test case for qsort_b(3)
>> Reviewed by: markj
>> MFC after: 2 weeks
>> Differential Revision: https://reviews.freebsd.org/D36463
>> ---
>> lib/libc/tests/stdlib/Makefile | 7 ++++
>> lib/libc/tests/stdlib/qsort_b_test.c | 76
>> ++++++++++++++++++++++++++++++++++++
>> share/mk/src.libnames.mk | 1 +
>> 3 files changed, 84 insertions(+)
>>
>> diff --git a/lib/libc/tests/stdlib/Makefile
>> b/lib/libc/tests/stdlib/Makefile
>> index ffba83443a9e..47841a92ba32 100644
>> --- a/lib/libc/tests/stdlib/Makefile
>> +++ b/lib/libc/tests/stdlib/Makefile
>> @@ -7,6 +7,7 @@ ATF_TESTS_C+= dynthr_test
>> ATF_TESTS_C+= heapsort_test
>> ATF_TESTS_C+= mergesort_test
>> ATF_TESTS_C+= qsort_test
>> +ATF_TESTS_C+= qsort_b_test
>> ATF_TESTS_C+= qsort_r_test
>> ATF_TESTS_C+= qsort_s_test
>> ATF_TESTS_C+= set_constraint_handler_s_test
>> @@ -59,6 +60,12 @@ CXXSTD.cxa_thread_atexit_test= c++11
>> CXXSTD.cxa_thread_atexit_nothr_test= c++11
>> LIBADD.cxa_thread_atexit_test+= pthread
>> +# Tests that requires Blocks feature
>> +.for t in qsort_b_test
>> +CFLAGS.${t}.c+= -fblocks
>> +LIBADD.${t}+= BlocksRuntime
>> +.endfor
>> +
>> .for t in h_getopt h_getopt_long
>> CFLAGS.$t+= -I${LIBNETBSD_SRCDIR} -I${SRCTOP}/contrib/netbsd-tests
>> LDFLAGS.$t+= -L${LIBNETBSD_OBJDIR}
>> diff --git a/lib/libc/tests/stdlib/qsort_b_test.c
>> b/lib/libc/tests/stdlib/qsort_b_test.c
>> new file mode 100644
>> index 000000000000..60cd30ac222a
>> --- /dev/null
>> +++ b/lib/libc/tests/stdlib/qsort_b_test.c
>> @@ -0,0 +1,76 @@
>> +/*-
>> + * Copyright (C) 2004 Maxim Sobolev <sobomax@FreeBSD.org>
>> + * All rights reserved.
>> + *
>> + * Redistribution and use in source and binary forms, with or without
>> + * modification, are permitted provided that the following conditions
>> + * are met:
>> + * 1. Redistributions of source code must retain the above copyright
>> + * notice, this list of conditions and the following disclaimer.
>> + * 2. Redistributions in binary form must reproduce the above copyright
>> + * notice, this list of conditions and the following disclaimer in
>> the
>> + * documentation and/or other materials provided with the
>> distribution.
>> + *
>> + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
>> AND
>> + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
>> + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
>> PURPOSE
>> + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
>> LIABLE
>> + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
>> CONSEQUENTIAL
>> + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
>> GOODS
>> + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
>> + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
>> CONTRACT, STRICT
>> + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
>> ANY WAY
>> + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
>> POSSIBILITY OF
>> + * SUCH DAMAGE.
>> + */
>> +
>> +/*
>> + * Test for qsort_b() routine.
>> + */
>> +
>> +#include <assert.h>
>> +#include <stdio.h>
>> +#include <stdlib.h>
>> +
>> +#include "test-sort.h"
>> +
>> +ATF_TC_WITHOUT_HEAD(qsort_b_test);
>> +ATF_TC_BODY(qsort_b_test, tc)
>> +{
>> + int testvector[IVEC_LEN];
>> + int sresvector[IVEC_LEN];
>> + int i, j;
>> +
>> + for (j = 2; j < IVEC_LEN; j++) {
>> + /* Populate test vectors */
>> + for (i = 0; i < j; i++)
>> + testvector[i] = sresvector[i] = initvector[i];
>> +
>> + /* Sort using qsort_b(3) */
>> + qsort_b(testvector, j, sizeof(testvector[0]),
>> + ^(const void* a, const void* b) {
>> + if (*(int *)a > *(int *)b)
>> + return (1);
>> + else if (*(int *)a < *(int *)b)
>> + return (-1);
>> + else
>> + return (0);
>> + });
>> + /* Sort using reference slow sorting routine */
>> + ssort(sresvector, j);
>> +
>> + /* Compare results */
>> + for (i = 0; i < j; i++)
>> + ATF_CHECK_MSG(testvector[i] == sresvector[i],
>> + "item at index %d didn't match: %d != %d",
>> + i, testvector[i], sresvector[i]);
>> + }
>> +}
>> +
>> +ATF_TP_ADD_TCS(tp)
>> +{
>> +
>> + ATF_TP_ADD_TC(tp, qsort_b_test);
>> +
>> + return (atf_no_error());
>> +}
>> diff --git a/share/mk/src.libnames.mk b/share/mk/src.libnames.mk
>> index 50eb5f1bf915..53b1937f7a79 100644
>> --- a/share/mk/src.libnames.mk
>> +++ b/share/mk/src.libnames.mk
>> @@ -97,6 +97,7 @@ _LIBRARIES= \
>> archive \
>> asn1 \
>> avl \
>> + BlocksRuntime \
>> be \
>> begemot \
>> bluetooth \
>
> Hi,
>
> Could we also have a test that qsort_b() is not sensitive to the sort
> pattern it is given? You are aware about how qsort() works?
>
> In my opinion, qsort() should be removed from the kernel. It does
> sorting, but is not reliable for all kinds of unsorted data! And can
> explode into stack usage ...
>
> --HPS
If you really need an inline sorting algorithm, here is one solution,
that uses a bit more CPU, but needs no serious memory or stack:
https://github.com/hselasky/libmbin/blob/main/mbin_sort.c
--HPS