From patchwork Wed Oct 23 17:54:35 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Carlini X-Patchwork-Id: 285713 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id F25A52C0119 for ; Thu, 24 Oct 2013 04:54:58 +1100 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:references :in-reply-to:content-type; q=dns; s=default; b=L6VoIplkbY6Qd+LZf hQZKbGhu2VL5MpVfCBbN8NH44L871yRKVq1ijFhn1jsl/uAv6S95iZIPOJhUutOQ xLAuFaLcNzGZFis8oV4pMX1pyuQnl650xgbNN2YMB8zoUy44bq+0ILnbtfWm/q3J bXc4+sAJAn4QUdPHmkEz/smW2g= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:references :in-reply-to:content-type; s=default; bh=m+JYKVBDgjyzWmNPM9zMJMO WTxQ=; b=sWLlxUJLD9xxHBZ5h7c6lnTtjNzLiMm/q/VRxPg2O/rumBgk2uA0uj2 0lwe7mrwt6YQHM/OdZzzYcx3IUvLBhCmgsb6QzLJyHTEFUDxrFR/33Ttd7H+i2Zj VCXlxg2i/QNSoeHDf7U+EE+g6wecFai+yTOWtp5im5bsT8UK9VI8= Received: (qmail 15296 invoked by alias); 23 Oct 2013 17:54:52 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 15278 invoked by uid 89); 23 Oct 2013 17:54:51 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.9 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD, SPF_PASS, UNPARSEABLE_RELAY autolearn=ham version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients X-HELO: aserp1040.oracle.com Received: from aserp1040.oracle.com (HELO aserp1040.oracle.com) (141.146.126.69) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-SHA encrypted) ESMTPS; Wed, 23 Oct 2013 17:54:50 +0000 Received: from ucsinet21.oracle.com (ucsinet21.oracle.com [156.151.31.93]) by aserp1040.oracle.com (Sentrion-MTA-4.3.1/Sentrion-MTA-4.3.1) with ESMTP id r9NHshCI007461 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Wed, 23 Oct 2013 17:54:44 GMT Received: from aserz7021.oracle.com (aserz7021.oracle.com [141.146.126.230]) by ucsinet21.oracle.com (8.14.4+Sun/8.14.4) with ESMTP id r9NHsfZl019698 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Wed, 23 Oct 2013 17:54:42 GMT Received: from abhmt107.oracle.com (abhmt107.oracle.com [141.146.116.59]) by aserz7021.oracle.com (8.14.4+Sun/8.14.4) with ESMTP id r9NHsf82025491; Wed, 23 Oct 2013 17:54:41 GMT Received: from poldo4.casa (/79.52.234.117) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Wed, 23 Oct 2013 10:54:41 -0700 Message-ID: <52680D5B.9060007@oracle.com> Date: Wed, 23 Oct 2013 19:54:35 +0200 From: Paolo Carlini User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.0 MIME-Version: 1.0 To: Christopher Jefferson , libstdc++ , gcc-patches@gcc.gnu.org Subject: Re: libstdc++ Testsuite extension for sort, partial_sort, partial_sort_copy, nth_element References: <5264E9AE.8060800@oracle.com> In-Reply-To: <5264E9AE.8060800@oracle.com> X-IsSubscribed: yes --- Chris, I went ahead and applied to my local trees the various tweaks I mentioned. I tested the below make check, check-debug and again both -m32/-m64. See if you can spot something you don't like, otherwise I will commit it later today. Thanks, Paolo. //////////////////// Index: testsuite/25_algorithms/nth_element/random_test.cc =================================================================== --- testsuite/25_algorithms/nth_element/random_test.cc (revision 0) +++ testsuite/25_algorithms/nth_element/random_test.cc (working copy) @@ -0,0 +1,63 @@ +// Copyright (C) 2013 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++11" } +// { dg-options "-std=gnu++11 -DSIMULATOR_TEST" { target simulator } } +// { dg-require-cstdint "" } + +// 25.4.2 [lib.alg.nth.element] + +#include +#include +#include +#include +#include + +using __gnu_test::test_container; +using __gnu_test::random_access_iterator_wrapper; + +typedef test_container Container; + +struct testNthElement +{ + template + void operator()(Container con, RandomGen& rg) + { + bool test __attribute__((unused)) = true; + + const int size = con.end() - con.begin(); + auto dist = std::uniform_int_distribution<>(0, size); + const int element = dist(rg); + + std::nth_element(con.begin(), con.begin() + element, con.end()); + + if (element < size) + { + for (int i = 0; i < element; ++i) + VERIFY( con.val(i) <= con.val(element) ); + + for (int i = element + 1; i < size; ++i) + VERIFY( con.val(i) >= con.val(element) ); + } + } +}; + +int +main() +{ + __gnu_test::test_containers(testNthElement()); +} Index: testsuite/25_algorithms/partial_sort/random_test.cc =================================================================== --- testsuite/25_algorithms/partial_sort/random_test.cc (revision 0) +++ testsuite/25_algorithms/partial_sort/random_test.cc (working copy) @@ -0,0 +1,62 @@ +// Copyright (C) 2013 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++11" } +// { dg-options "-std=gnu++11 -DSIMULATOR_TEST" { target simulator } } +// { dg-require-cstdint "" } + +// 25.4.1.3 [lib.alg.partial.sort] + +#include +#include +#include +#include +#include + +using __gnu_test::test_container; +using __gnu_test::random_access_iterator_wrapper; + +typedef test_container Container; + +struct testPartialSort +{ + template + void operator()(Container con, RandomGen& rg) + { + bool test __attribute__((unused)) = true; + + const int size = con.end() - con.begin(); + auto dist = std::uniform_int_distribution<>(0, size); + const int element = dist(rg); + + std::partial_sort(con.begin(), con.begin() + element, con.end()); + + VERIFY( std::is_sorted(con.begin(), con.begin() + element) ); + + if (element > 0) + { + for (int i = element; i < size; ++i) + VERIFY( con.val(element - 1) <= con.val(i) ); + } + } +}; + +int +main() +{ + __gnu_test::test_containers(testPartialSort()); +} Index: testsuite/25_algorithms/partial_sort_copy/random_test.cc =================================================================== --- testsuite/25_algorithms/partial_sort_copy/random_test.cc (revision 0) +++ testsuite/25_algorithms/partial_sort_copy/random_test.cc (working copy) @@ -0,0 +1,67 @@ +// Copyright (C) 2013 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++11" } +// { dg-options "-std=gnu++11 -DSIMULATOR_TEST" { target simulator } } +// { dg-require-cstdint "" } + +// 25.4.1.4 [lib.alg.partial.sort.copy] + +#include +#include +#include +#include +#include +#include + +using __gnu_test::test_container; +using __gnu_test::random_access_iterator_wrapper; + +typedef test_container Container; + +struct testPartialSortCopy +{ + template + void operator()(Container con, RandomGen& rg) + { + bool test __attribute__((unused)) = true; + + const int size = con.end() - con.begin(); + auto dist = std::uniform_int_distribution<>(0, size); + const int element = dist(rg); + + std::vector outvec(element + 1); // add +1 to avoid empty issues + + Container out(outvec.data(), outvec.data() + element); + + std::partial_sort_copy(con.begin(), con.end(), + out.begin(), out.begin() + element); + + VERIFY( std::is_sorted(out.begin(), out.begin() + element) ); + + std::sort(con.begin(), con.end()); + + for (int i = 0; i < element; ++i) + VERIFY( con.val(i) == out.val(i) ); + } +}; + +int +main() +{ + __gnu_test::test_containers(testPartialSortCopy()); +} Index: testsuite/25_algorithms/sort/random_test.cc =================================================================== --- testsuite/25_algorithms/sort/random_test.cc (revision 0) +++ testsuite/25_algorithms/sort/random_test.cc (working copy) @@ -0,0 +1,51 @@ +// Copyright (C) 2013 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This 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 General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++11" } +// { dg-options "-std=gnu++11 -DSIMULATOR_TEST" { target simulator } } +// { dg-require-cstdint "" } + +// 25.4.1 [lib.alg.sort] + +#include +#include +#include +#include +#include + +using __gnu_test::test_container; +using __gnu_test::random_access_iterator_wrapper; + +typedef test_container Container; + +struct testSort +{ + template + void operator()(Container con, RandomGen&) + { + bool test __attribute__((unused)) = true; + + std::sort(con.begin(), con.end()); + VERIFY( std::is_sorted(con.begin(), con.end()) ); + } +}; + +int +main() +{ + __gnu_test::test_containers(testSort()); +} Index: testsuite/util/testsuite_containergen.h =================================================================== --- testsuite/util/testsuite_containergen.h (revision 0) +++ testsuite/util/testsuite_containergen.h (working copy) @@ -0,0 +1,97 @@ +// Copyright (C) 2013 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License as published by the Free Software +// Foundation; either version 3, or (at your option) any later +// version. + +// This 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 +// General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#ifndef _GLIBCXX_TESTSUITE_CONTAINER_GEN_H +#define _GLIBCXX_TESTSUITE_CONTAINER_GEN_H + +#include +#include + +namespace __gnu_test +{ + template + void + test_single_container(Tester test, RandomGen& rg, int length, int domain) + { + std::vector values; + auto dist = std::uniform_int_distribution<>(0, domain - 1); + + for(int i = 0; i < length; ++i) + values.push_back(dist(rg)); + + ContainerType con(values.data(), values.data() + length); + test(con, rg); + } + + template + void + test_special_containers(Tester test, RandomGen& rg, int length) + { + std::vector values(length); + ContainerType con(values.data(), values.data() + length); + + for(int i = 0; i < length; ++i) + values[i] = 0; + test(con, rg); + + for(int i = 0; i < length; ++i) + values[i] = i; + test(con, rg); + + for(int i = 0; i < length; ++i) + values[i] = -i; + test(con, rg); + } + + template + void + test_containers(Tester test) + { + std::mt19937_64 random_gen; + +#ifdef SIMULATOR_TEST + int loops = 10; +#else + int loops = 1000; +#endif + + for(int i = 0; i < loops; ++i) + test_special_containers(test, random_gen, i); + + for(int i = 1; i < 100; ++i) + for(int j = 0; j < loops; ++j) + test_single_container(test, random_gen, i, i); + + for(int i = 0; i < loops; ++i) + { + test_single_container(test, random_gen, 10, 10); + test_single_container(test, random_gen, 100, 10); + test_single_container(test, random_gen, 1000, 10); + test_single_container(test, random_gen, 10, 1000); + } + +#ifndef SIMULATOR_TEST + for(int i = 0; i < 1000; ++i) + { + test_single_container(test, random_gen, 10000, 10); + test_single_container(test, random_gen, 10000, 10000); + } +#endif + } +} // namespace __gnu_test + +#endif Index: testsuite/util/testsuite_iterators.h =================================================================== --- testsuite/util/testsuite_iterators.h (revision 203978) +++ testsuite/util/testsuite_iterators.h (working copy) @@ -539,6 +539,10 @@ return ItType(pos, &bounds); } + const T& + val(int pos) + { return (bounds.first)[pos]; } + ItType begin() { return it(bounds.first); }