From patchwork Fri Aug 31 20:42:34 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella Netto X-Patchwork-Id: 145693 Delivered-To: patch@linaro.org Received: by 2002:a2e:1648:0:0:0:0:0 with SMTP id 8-v6csp1210605ljw; Fri, 31 Aug 2018 13:43:32 -0700 (PDT) X-Google-Smtp-Source: ANB0VdZMLdbkjjdGglL6Wi2NiyPyyfKbJzKtzVI4rIvC8KOuQcIWRdRSNp0QTg1+SgKYR2aToZ6s X-Received: by 2002:a63:6881:: with SMTP id d123-v6mr1427378pgc.298.1535748212476; Fri, 31 Aug 2018 13:43:32 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1535748212; cv=none; d=google.com; s=arc-20160816; b=Hgkjy/2uG8HpyQTAtqpevOliAABDMGY/iNTvZ7/hSGF0jbYP2jvrKtuAwe9o7oXO/I o+xJ+FGkNTh1byJAhKMtLa0y1m5g3XhedpLvaZ+2Q4eH8nLWI8yU4crGAlDHkNCRqK6D 5MxLuFvNHteNyizDqyp5zYCaxNe/fCCbJaGTllHJat39F+p616qRLl6nlStzKPHSn6OU HuSFHZiSonIGnD2Sfzc9Tp+p/Uwq1B/JkIYvKH4C/EtpoUDSSMnYKq45/Q9DZc2SIdfL uVRZAZukQf0ZQ+XcMgWkSmqaNlzGwisYAYDbl8/n19bc822xMyqHyiBn++bM7q8mOflH JQmg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:to:from :dkim-signature:delivered-to:sender:list-help:list-post:list-archive :list-subscribe:list-unsubscribe:list-id:precedence:mailing-list :dkim-signature:domainkey-signature:arc-authentication-results; bh=Paz/YzMnHGsRPUgnAJSqcZ82axddFW42Aewr1lAuDGw=; b=LcuN4NmW2tgFn9sMVS9Utp4FjR2kxcGb+q85LW/UexB3d3V3SXhLw15+3zvCSy1ZG5 I9RIbHLtpRpqYn/Ai1QEOilUtaH+poX/rPflc9CoceXLcOivrDT/zlprXm71yMPzlncZ Bn4nrrisgUO2o9yKSWoKwgS0lPTlkSD7GWRpuNtuJk1GSFDJcoJQWRAj7+YMIRVZA39l NkytteYhJL/tGgGSny0KR7KhlETPdxtbzdYxBZbsnCokUKCw/7HN796WNZ3pKu8ah1JD 8SiqFCBLDT30sYZTuC0/2Nto60QZbR3WVsSGqnRP9GAHdubmwgevpxGxr+BvDDv2+6C0 r8DQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=kTyzttjo; dkim=pass header.i=@linaro.org header.s=google header.b=XjJ6c0KX; spf=pass (google.com: domain of libc-alpha-return-95625-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95625-patch=linaro.org@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id w5-v6si9791120pge.395.2018.08.31.13.43.32 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 31 Aug 2018 13:43:32 -0700 (PDT) Received-SPF: pass (google.com: domain of libc-alpha-return-95625-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=kTyzttjo; dkim=pass header.i=@linaro.org header.s=google header.b=XjJ6c0KX; spf=pass (google.com: domain of libc-alpha-return-95625-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="libc-alpha-return-95625-patch=linaro.org@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; q=dns; s=default; b=m1K7cJ5lzVoYMdzFKVTzyu1mi15xpwj b62hBqSo9e2hkpRfz89DD5DNvExx74NtNcwctnV1S3M5toooHbEfGyk7qWvkmhUo 6lgpbxaVPbzBkwNVWiPQwZw32yxuoii+4zPvUroCtDFaG3lXGWAcY8l7y7TqA0pf aTmGdvjbKIyo= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; s=default; bh=JwiJ1if+dtkU/+4St5UARrDmNRs=; b=kTyzt tjoQu5L1yDHMDd3DT/odRJrW//ZGtmLJWnJN/TNHFea86srnEAecYt4djSuEKorG CWLfIYsjHvvMuJifnV07mmTvStlFtALY24l74BUgtx9p7uDNz7lNdRF2vSaarKKG 1voxkC4hITyHZcHi3Cf2a08jintJVdqBfH0cu0= Received: (qmail 54488 invoked by alias); 31 Aug 2018 20:42:55 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 54385 invoked by uid 89); 31 Aug 2018 20:42:54 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.6 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, RCVD_IN_DNSWL_NONE, SEM_URI, SEM_URIRED, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mail-qt0-f170.google.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:subject:date:message-id:in-reply-to:references; bh=Paz/YzMnHGsRPUgnAJSqcZ82axddFW42Aewr1lAuDGw=; b=XjJ6c0KX9iQNc4Hwu66JbyHM+cuJ5+bAIYNQxtqmp5y0EBd4ePz6Fm9FE3RIe9XuPA Prr/j3YjrP50G7VSxx/6CjpeW1M1FCiMVyIV7APtU3A9VUx6E3nt5V+e2qM+19qptUtN sA2FHkhCsLI4a5hJBoN25nYTaR0PU+oOkDUMI= Return-Path: From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH v2 3/7] stdlib: Add more qsort{_r} coverage Date: Fri, 31 Aug 2018 17:42:34 -0300 Message-Id: <20180831204238.10626-4-adhemerval.zanella@linaro.org> In-Reply-To: <20180831204238.10626-1-adhemerval.zanella@linaro.org> References: <20180831204238.10626-1-adhemerval.zanella@linaro.org> This patch adds a qsort and qsort_t (which glibc current lacks coverage). The test check with random input (created using support random) with different internal types (uint8_t, uint16_t, uint32_t, and uint64_t) and with different set of element numbers (from 0 to 262144). Checked on x86_64-linux-gnu. * stdlib/tst-qsort3.c: New file. * stdlib/Makefile (tests): Add tst-qsort3. --- stdlib/Makefile | 2 +- stdlib/tst-qsort3.c | 235 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 236 insertions(+), 1 deletion(-) create mode 100644 stdlib/tst-qsort3.c -- 2.17.1 diff --git a/stdlib/Makefile b/stdlib/Makefile index 01194bbf7c..4e012a865a 100644 --- a/stdlib/Makefile +++ b/stdlib/Makefile @@ -87,7 +87,7 @@ tests := tst-strtol tst-strtod testmb testrand testsort testdiv \ tst-makecontext-align test-bz22786 tst-strtod-nan-sign \ tst-swapcontext1 tst-setcontext4 tst-setcontext5 \ tst-setcontext6 tst-setcontext7 tst-setcontext8 \ - tst-setcontext9 + tst-setcontext9 tst-qsort3 tests-internal := tst-strtod1i tst-strtod3 tst-strtod4 tst-strtod5i \ tst-tls-atexit tst-tls-atexit-nodelete diff --git a/stdlib/tst-qsort3.c b/stdlib/tst-qsort3.c new file mode 100644 index 0000000000..26db0c2da6 --- /dev/null +++ b/stdlib/tst-qsort3.c @@ -0,0 +1,235 @@ +/* qsort(_r) generic tests. + Copyright (C) 2017 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#include +#include +#include +#include +#include +#include + +#include +#include +#include +#include + +/* Functions used to check qsort. */ +static int +uint8_t_cmp (const void *a, const void *b) +{ + uint8_t ia = *(uint8_t*)a; + uint8_t ib = *(uint8_t*)b; + return (ia > ib) - (ia < ib); +} + +static int +uint16_t_cmp (const void *a, const void *b) +{ + uint16_t ia = *(uint16_t*)a; + uint16_t ib = *(uint16_t*)b; + return (ia > ib) - (ia < ib); +} + +static int +uint32_t_cmp (const void *a, const void *b) +{ + uint32_t ia = *(uint32_t*)a; + uint32_t ib = *(uint32_t*)b; + return (ia > ib) - (ia < ib); +} + +static int +uint64_t_cmp (const void *a, const void *b) +{ + uint64_t ia = *(uint64_t*)a; + uint64_t ib = *(uint64_t*)b; + return (ia > ib) - (ia < ib); +} + +/* Function used to check qsort_r. */ + +enum type_cmp_t +{ + UINT8_CMP_T = 0, + UINT16_CMP_T = 1, + UINT32_CMP_T = 2, + UINT64_CMP_T = 3, +}; + +static enum type_cmp_t +uint_t_cmp_type (size_t sz) +{ + switch (sz) + { + case sizeof (uint8_t): return UINT8_CMP_T; + case sizeof (uint16_t): return UINT16_CMP_T; + case sizeof (uint64_t): return UINT64_CMP_T; + case sizeof (uint32_t): + default: return UINT32_CMP_T; + } +} + +static int +uint_t_cmp (const void *a, const void *b, void *arg) +{ + enum type_cmp_t type = *(enum type_cmp_t*) arg; + switch (type) + { + case UINT8_CMP_T: return uint8_t_cmp (a, b); + case UINT16_CMP_T: return uint16_t_cmp (a, b); + case UINT64_CMP_T: return uint64_t_cmp (a, b); + case UINT32_CMP_T: + default: return uint32_t_cmp (a, b); + } +} + +static support_random_state rand_state; + +static void * +create_array (size_t nmemb, size_t type_size) +{ + size_t size = nmemb * type_size; + uint8_t *array = xmalloc (size); + support_random_buf (&rand_state, array, size); + return array; +} + +typedef int (*cmpfunc_t)(const void *, const void *); + +static void +check_array (void *array, size_t nmemb, size_t type_size, + cmpfunc_t cmpfunc) +{ + for (size_t i = 1; i < nmemb; i++) + { + void *array_i = (void*)((uintptr_t)array + i * type_size); + void *array_i_1 = (void*)((uintptr_t)array + (i-1) * type_size); + int ret; + TEST_VERIFY ((ret = cmpfunc (array_i, array_i_1)) >= 0); + if (ret < 0) + break; + } +} + +static uint32_t seed; +static bool seed_set = false; + +#define OPT_SEED 10000 +#define CMDLINE_OPTIONS \ + { "seed", required_argument, NULL, OPT_SEED }, + +static void __attribute__ ((used)) +cmdline_process_function (int c) +{ + switch (c) + { + case OPT_SEED: + { + unsigned long int value = strtoul (optarg, NULL, 0); + if (errno == ERANGE || value > UINT32_MAX) + { + printf ("error: seed should be a value in range of " + "[0, UINT32_MAX]\n"); + exit (EXIT_FAILURE); + } + seed = value; + seed_set = true; + } + break; + } +} + +#define CMDLINE_PROCESS cmdline_process_function + + +static int +do_test (void) +{ + if (test_verbose > 0) + printf ("info: seed=0x%08x\n", seed); + if (seed_set) + support_random_seed (&rand_state, seed); + else + support_random_rseed (&rand_state); + + const size_t elem[] = { 0, 1, 64, 128, 4096, 16384, 262144 }; + const size_t nelem = sizeof (elem) / sizeof (elem[0]); + + struct test_t + { + size_t type_size; + cmpfunc_t cmpfunc; + } + tests[] = + { + { sizeof (uint8_t), uint8_t_cmp }, + { sizeof (uint16_t), uint16_t_cmp }, + { sizeof (uint32_t), uint32_t_cmp }, + { sizeof (uint64_t), uint64_t_cmp }, + /* Test swap with large elements. */ + { 32, uint32_t_cmp }, + }; + size_t ntests = sizeof (tests) / sizeof (tests[0]); + + for (size_t i = 0; i < ntests; i++) + { + size_t ts = tests[i].type_size; + if (test_verbose > 0) + printf ("info: testing qsort with type_size=%zu\n", ts); + for (size_t n = 0; n < nelem; n++) + { + size_t nmemb = elem[n]; + if (test_verbose > 0) + printf (" nmemb=%zu, total size=%zu\n", nmemb, nmemb * ts); + + void *array = create_array (nmemb, ts); + + qsort (array, nmemb, ts, tests[i].cmpfunc); + + check_array (array, nmemb, ts, tests[i].cmpfunc); + + free (array); + } + } + + for (size_t i = 0; i < ntests; i++) + { + size_t ts = tests[i].type_size; + if (test_verbose > 0) + printf ("info: testing qsort_r type_size=%zu\n", ts); + for (size_t n = 0; n < nelem; n++) + { + size_t nmemb = elem[n]; + if (test_verbose > 0) + printf (" nmemb=%zu, total size=%zu\n", nmemb, nmemb * ts); + + void *array = create_array (nmemb, ts); + + enum type_cmp_t type = uint_t_cmp_type (ts); + qsort_r (array, nmemb, ts, uint_t_cmp, &type); + + check_array (array, nmemb, ts, tests[i].cmpfunc); + + free (array); + } + } + + return 0; +} + +#include