From nobody Wed Sep 07 07:14:10 2022 X-Original-To: dev-commits-src-main@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4MMtm903R9z4bmhN; Wed, 7 Sep 2022 07:14:17 +0000 (UTC) (envelope-from hps@selasky.org) Received: from mail.turbocat.net (turbocat.net [88.99.82.50]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 4MMtm75yXVz3jbL; Wed, 7 Sep 2022 07:14:15 +0000 (UTC) (envelope-from hps@selasky.org) Received: from [10.36.2.165] (unknown [178.232.223.95]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits)) (No client certificate requested) by mail.turbocat.net (Postfix) with ESMTPSA id 6919526007D; Wed, 7 Sep 2022 09:14:14 +0200 (CEST) Message-ID: <3796054f-03b0-8016-ed07-ef346c3b78cd@selasky.org> Date: Wed, 7 Sep 2022 09:14:10 +0200 List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-main@freebsd.org X-BeenThere: dev-commits-src-main@freebsd.org MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:91.0) Gecko/20100101 Thunderbird/91.13.0 Subject: Re: git: c65e42dbde41 - main - libc: add test case for qsort_b(3) Content-Language: en-US From: Hans Petter Selasky To: Xin LI , src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org References: <202209070612.2876C6ko054410@gitrepo.freebsd.org> In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 4MMtm75yXVz3jbL X-Spamd-Bar: --- Authentication-Results: mx1.freebsd.org; dkim=none; dmarc=none; spf=pass (mx1.freebsd.org: domain of hps@selasky.org designates 88.99.82.50 as permitted sender) smtp.mailfrom=hps@selasky.org X-Spamd-Result: default: False [-3.30 / 15.00]; NEURAL_HAM_LONG(-1.00)[-1.000]; NEURAL_HAM_SHORT(-1.00)[-1.000]; NEURAL_HAM_MEDIUM(-1.00)[-0.999]; R_SPF_ALLOW(-0.20)[+a:mail.turbocat.net:c]; MIME_GOOD(-0.10)[text/plain]; ASN(0.00)[asn:24940, ipnet:88.99.0.0/16, country:DE]; R_DKIM_NA(0.00)[]; FROM_EQ_ENVFROM(0.00)[]; MIME_TRACE(0.00)[0:+]; MLMMJ_DEST(0.00)[dev-commits-src-all@FreeBSD.org,dev-commits-src-main@FreeBSD.org]; TO_DN_SOME(0.00)[]; ARC_NA(0.00)[]; DMARC_NA(0.00)[selasky.org]; MID_RHS_MATCH_FROM(0.00)[]; RCVD_VIA_SMTP_AUTH(0.00)[]; RCVD_COUNT_TWO(0.00)[2]; FROM_HAS_DN(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; RCPT_COUNT_THREE(0.00)[4]; RCVD_TLS_ALL(0.00)[] X-ThisMailContainsUnwantedMimeParts: N 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 >> AuthorDate: 2022-09-07 06:11:46 +0000 >> Commit:     Xin LI >> 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 >> + * 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 >> +#include >> +#include >> + >> +#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