From patchwork Thu Jan 18 17:53:19 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella X-Patchwork-Id: 124999 Delivered-To: patch@linaro.org Received: by 10.46.64.27 with SMTP id n27csp228476lja; Thu, 18 Jan 2018 09:54:21 -0800 (PST) X-Google-Smtp-Source: ACJfBouK8U2kNuz+dSlPRKrmaJ7OUq8MVECzrKtSgvuzduPsXXyKLRUzMlcydw2RcGvzMHIdKcOD X-Received: by 10.101.89.3 with SMTP id f3mr25523422pgu.372.1516298060897; Thu, 18 Jan 2018 09:54:20 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1516298060; cv=none; d=google.com; s=arc-20160816; b=bmEevi7WqWNdf2fyMOP5UwwEoiW7b5V1twlGZpTSXVT1vud/MZOBv23ZTgKN30RdHk YU2P06ZlHESKT5yNmhFORvwwhH2rr/fdhS50/1HTAxku20NZ3oqUvd2fp3+0hqdnFz1T byIXT68UZo1bwqPMPlaRgMg+S8fkLM14DtZCDx9Z2bGdYhxbsYnnMQQ1mf9hojmMivij WCEP2tqw1jXI+INJI437JPwk8lbAcETAS4WonlUd8Cg2A2UmNh7FGMGLara3Ditq/5Dw IzjGDs+84yDAaetx0ul7Vhv+ZxkEkm+QoaiZbcqebulrbSiP61gUcG/UtwqVuu4SqFPa wvVA== 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: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=uqx+aF1SgpMl+64rQmiJEefbCQmc9yel89nbkbgspxo=; b=WiMg1Z8AzjUkbppYpdF/DesrvkUFCqs+kWKo7m8kranV0X64Gc31WI3UaHMhIOYwEM oOryqHOxWx/nWscpbUYLHN4yr3vYDxaQYVEWwU+geTdNc1lUUZPfGazT8J2k0UrlikG2 f08V6w1oDC+4jBm6a4kFg+YJ6oYHybQUcBsOrP/MpSIJJnvqLMms9TH139QGAOYEhDd1 2kmvKcOP66u2PWYp6XM4mRAusgZgWcAaX4gynTYdCdx9vaOSXp1eOdNmON68jX4TLwwt JtnIxz3fGnUfKVqkDcAJ4u8n//qPe0mmKi7ysUUQSa9Ah9IK5EvqeBbeQAUWlYJfLL/p 6t5A== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=K+FbnYtP; spf=pass (google.com: domain of libc-alpha-return-89326-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89326-patch=linaro.org@sourceware.org; dmarc=fail (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 k28si6533619pgf.251.2018.01.18.09.54.20 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 18 Jan 2018 09:54:20 -0800 (PST) Received-SPF: pass (google.com: domain of libc-alpha-return-89326-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=K+FbnYtP; spf=pass (google.com: domain of libc-alpha-return-89326-patch=linaro.org@sourceware.org designates 209.132.180.131 as permitted sender) smtp.mailfrom=libc-alpha-return-89326-patch=linaro.org@sourceware.org; dmarc=fail (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=ttFTF53r44OPEHzCMwn6EZaZmRxxkpR e7Cv/MzG0MEMNvYVdtV4FStf1gO7EMAl7oz+l1sjlG7vB4vYrMV8kpOypBTuSqXi 6quXgYhcoJYCjtCtA4YQH4/qk3w4qahNxIOc6HUvXQgfTZBY/Z/P114gJhjC/WvO TKBnGlIxwzgg= 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=z0pIBuRx1c6u+jdiZ9PKfpKAM74=; b=K+Fbn YtPjKFD2dD4PLWuc/ikYqNg3P2XTCALVkr9BhmXs9g11PtXXmtWdwiwD8bKjBiH0 eHGsnSOtx3iB5CX/clT6Obh9RYB7Z8NhpSFKfdjdK+kLwFw7UamNvJAYySLc135Y 1LbCArfR6tPZA13yhdywVovY5C0ugBQhymXtrw= Received: (qmail 79548 invoked by alias); 18 Jan 2018 17:53:40 -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 79422 invoked by uid 89); 18 Jan 2018 17:53:39 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.2 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, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mail-qt0-f172.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=uqx+aF1SgpMl+64rQmiJEefbCQmc9yel89nbkbgspxo=; b=qnyG0cidKCL0rRT3WA0bAfBu508uUQmirBBEA8vMa8Nimt0klo3Dy8ar2/Fq9j3eUu 0XXsFVJ9hYICjmN/6YbBqyiXMXDlfDI/tzQIbUztHA4Mv5D71hD4SGhkvxVge67I1h6+ xzQ1NrG2RQ/IOcOwOgOBS2jOSfP1RG8Ln3zk3k/xxCGU8YjYhOpCee3nvoEiiEHng19n CJ2Rh+hhb5fohVoVwpifvYE9LfEo1oPNFEfWJaFJb/cglaVlm4I9C2sIMPUXi67+hvlS 1Uq4yQnfp/anZ0tGlwlTarZju782qkmIfYXqpIPcGZUG1SAwyAby2ayoyObyFgnMaM5b e0zQ== X-Gm-Message-State: AKwxytf3TesmFQrvhubvAE2di7MGJygu/ynAZka+yIdYgirRWwf9nPqQ tFR9uk9RvZEeqr28HPDv7S4tTBDDSrg= X-Received: by 10.55.113.199 with SMTP id m190mr26532391qkc.320.1516298015202; Thu, 18 Jan 2018 09:53:35 -0800 (PST) From: Adhemerval Zanella To: libc-alpha@sourceware.org Subject: [PATCH 4/7] stdlib: Add more qsort{_r} coverage Date: Thu, 18 Jan 2018 15:53:19 -0200 Message-Id: <1516298002-4618-5-git-send-email-adhemerval.zanella@linaro.org> In-Reply-To: <1516298002-4618-1-git-send-email-adhemerval.zanella@linaro.org> References: <1516298002-4618-1-git-send-email-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 | 231 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 232 insertions(+), 1 deletion(-) create mode 100644 stdlib/tst-qsort3.c -- 2.7.4 diff --git a/stdlib/Makefile b/stdlib/Makefile index 7c363a6..6ef20a7 100644 --- a/stdlib/Makefile +++ b/stdlib/Makefile @@ -84,7 +84,7 @@ tests := tst-strtol tst-strtod testmb testrand testsort testdiv \ tst-cxa_atexit tst-on_exit test-atexit-race \ test-at_quick_exit-race test-cxa_atexit-race \ test-on_exit-race test-dlclose-exit-race \ - tst-makecontext-align + tst-makecontext-align 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 0000000..e6ddb60 --- /dev/null +++ b/stdlib/tst-qsort3.c @@ -0,0 +1,231 @@ +/* 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 + +/* 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 struct mt19937_32 mt; + +static void * +create_array (size_t nmemb, size_t type_size) +{ + size_t size = nmemb * type_size; + uint8_t *array = xmalloc (size); + + for (size_t i = 0; i < size; i++) + array[i] = uniform_uint32_distribution (mt32_rand (&mt), 0, UINT8_MAX); + + 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; + +#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; + } + break; + } +} + +#define CMDLINE_PROCESS cmdline_process_function + + +static int +do_test (void) +{ + mt32_seed (&mt, seed); + printf ("info: seed=0x%08x\n", seed); + + 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