From patchwork Wed Oct 29 18:22:26 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 404753 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.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4175A14007D for ; Thu, 30 Oct 2014 05:22:51 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type :content-transfer-encoding; q=dns; s=default; b=ZUP4LG82rIVv8C+d hasGqWJR0YIm5kPDsob7adqSPglLjlwP/22hx1rAzutKlygvEbzy5tAvMJRLaUh1 IweFWJ2R6eEMgcEfkxHBoJC0NxBS6zqCj3/FlkV4WJwf001XVHWrGtPJclL0MFKW J3/q3O5uCJwcR0L1XrFxODhYGjM= 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:date :from:to:subject:message-id:mime-version:content-type :content-transfer-encoding; s=default; bh=RDdinc+U4vSYo1elxOWmkF i2aWk=; b=UCpLlKgvIh8NHWXRNcnAZ+KKDBQippBqkI8zmg2bvThOhovXUKEkYK RKNIJQYjrswB76TyUUaunbe70YegKnwvodtieFf81wl8+uCvrejX73qrXrJkdR9j RVmwg+8cUSmS3auNg/jA1GG0RGEXb4kNpvwSk6c/iJLQCTdZQU+Zc= Received: (qmail 28845 invoked by alias); 29 Oct 2014 18:22:37 -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 28781 invoked by uid 89); 29 Oct 2014 18:22:37 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.0 required=5.0 tests=AWL, BAYES_50, RP_MATCHES_RCVD, SPF_HELO_PASS, SPF_PASS autolearn=ham version=3.3.2 X-Spam-User: qpsmtpd, 2 recipients X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Wed, 29 Oct 2014 18:22:31 +0000 Received: from int-mx14.intmail.prod.int.phx2.redhat.com (int-mx14.intmail.prod.int.phx2.redhat.com [10.5.11.27]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id s9TIMSfA030177 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL); Wed, 29 Oct 2014 14:22:29 -0400 Received: from localhost (ovpn-116-112.ams2.redhat.com [10.36.116.112]) by int-mx14.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id s9TIMRXB027972; Wed, 29 Oct 2014 14:22:27 -0400 Date: Wed, 29 Oct 2014 18:22:26 +0000 From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: Add Library Fundamentals and Message-ID: <20141029182226.GG3033@redhat.com> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.23 (2014-03-12) The first patch adds the following from Library Fundamentals v1: std::experimental::sample std::experimental::search std::experimental::default_searcher std::experimental::make_default_searcher std::experimental::boyer_moore_searcher std::experimental::make_boyer_moore_searcher std::experimental::boyer_moore_horspool_searcher std::experimental::make_boyer_moore_horspool_searcher std::experimental::is_bind_expression_v std::experimental::is_placeholder_v And from v2: std::experimental::not_fn The second patch adds the feature-testing macros recommended by the TS. Tested x86_64-linux, committed to trunk. commit 9604253d1a5fc0c42848613d445d6c61f33390b9 Author: Jonathan Wakely Date: Wed Oct 29 17:37:56 2014 +0000 * include/experimental/any: Add feature-testing macro. * include/experimental/optional: Likewise. * include/experimental/string_view: Likewise. * include/experimental/tuple: Likewise. * include/experimental/type_traits: Likewise. * testsuite/experimental/any/misc/any_cast_neg.cc: Adjust dg-error. diff --git a/libstdc++-v3/include/experimental/any b/libstdc++-v3/include/experimental/any index a4ac983..1de467c 100644 --- a/libstdc++-v3/include/experimental/any +++ b/libstdc++-v3/include/experimental/any @@ -60,6 +60,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * @{ */ +#define __cpp_lib_experimental_any 201402 + /** * @brief Exception class thrown by a failed @c any_cast * @ingroup exceptions diff --git a/libstdc++-v3/include/experimental/optional b/libstdc++-v3/include/experimental/optional index c68d7ea..973775b 100644 --- a/libstdc++-v3/include/experimental/optional +++ b/libstdc++-v3/include/experimental/optional @@ -67,6 +67,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * @{ */ +#define __cpp_lib_experimental_optional 201406 + // All subsequent [X.Y.n] references are against n3793. // [X.Y.4] diff --git a/libstdc++-v3/include/experimental/string_view b/libstdc++-v3/include/experimental/string_view index 041f748..320d72d 100644 --- a/libstdc++-v3/include/experimental/string_view +++ b/libstdc++-v3/include/experimental/string_view @@ -50,6 +50,8 @@ inline namespace fundamentals_v1 { _GLIBCXX_BEGIN_NAMESPACE_VERSION +#define __cpp_lib_experimental_string_view 201402 + /** * @class basic_string_view * @brief A non-owning reference to a string. diff --git a/libstdc++-v3/include/experimental/tuple b/libstdc++-v3/include/experimental/tuple index da756b8..5cf02d3 100644 --- a/libstdc++-v3/include/experimental/tuple +++ b/libstdc++-v3/include/experimental/tuple @@ -44,10 +44,13 @@ namespace experimental inline namespace fundamentals_v1 { _GLIBCXX_BEGIN_NAMESPACE_VERSION + // See C++14 §20.4.2.5, tuple helper classes template constexpr size_t tuple_size_v = tuple_size<_Tp>::value; +#define __cpp_lib_experimental_tuple 201402 + template constexpr decltype(auto) __apply_impl(_Fn&& f, _Tuple&& t, std::index_sequence<_Idx...>) diff --git a/libstdc++-v3/include/experimental/type_traits b/libstdc++-v3/include/experimental/type_traits index 93dd8ce..72aadbe 100644 --- a/libstdc++-v3/include/experimental/type_traits +++ b/libstdc++-v3/include/experimental/type_traits @@ -50,6 +50,8 @@ inline namespace fundamentals_v1 { _GLIBCXX_BEGIN_NAMESPACE_VERSION +#define __cpp_lib_experimental_type_trait_variable_templates 201402 + // See C++14 §20.10.4.1, primary type categories template constexpr bool is_void_v = is_void<_Tp>::value; diff --git a/libstdc++-v3/testsuite/experimental/any/misc/any_cast_neg.cc b/libstdc++-v3/testsuite/experimental/any/misc/any_cast_neg.cc index 9a12ec3..9ef7194 100644 --- a/libstdc++-v3/testsuite/experimental/any/misc/any_cast_neg.cc +++ b/libstdc++-v3/testsuite/experimental/any/misc/any_cast_neg.cc @@ -26,5 +26,5 @@ void test01() using std::experimental::any_cast; const any y(1); - any_cast(y); // { dg-error "qualifiers" "" { target { *-*-* } } 380 } + any_cast(y); // { dg-error "qualifiers" "" { target { *-*-* } } 382 } } commit 46908eee27b524877c583ad7b0ac15102f3e1e89 Author: Jonathan Wakely Date: Wed Oct 29 17:34:40 2014 +0000 Add and . * doc/xml/manual/status_cxx2014.xml: Update TS status. * include/Makefile.am: Add new headers. * include/Makefile.in: Regenerate. * include/experimental/algorithm: New. * include/experimental/functional: New. * testsuite/experimental/algorithm/sample.cc: New. * testsuite/experimental/algorithm/search.cc: New. * testsuite/experimental/functional/not_fn.cc: New. * testsuite/experimental/functional/searchers.cc: New. * testsuite/experimental/functional/value.cc: New. * testsuite/experimental/feat-lib-fund.cc: Add headers and reorder. diff --git a/libstdc++-v3/doc/xml/manual/status_cxx2014.xml b/libstdc++-v3/doc/xml/manual/status_cxx2014.xml index e2a2d94..f7d18a2 100644 --- a/libstdc++-v3/doc/xml/manual/status_cxx2014.xml +++ b/libstdc++-v3/doc/xml/manual/status_cxx2014.xml @@ -329,14 +329,13 @@ not in any particular release. - N3905 Faster string searching (Boyer-Moore et al.) - N + Y Library Fundamentals TS @@ -387,14 +386,13 @@ not in any particular release. - N3925 A sample proposal - N + Y Library Fundamentals TS diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 89fa436..5fa243b 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -639,8 +639,10 @@ decimal_headers = \ experimental_srcdir = ${glibcxx_srcdir}/include/experimental experimental_builddir = ./experimental experimental_headers = \ + ${experimental_srcdir}/algorithm \ ${experimental_srcdir}/any \ ${experimental_srcdir}/chrono \ + ${experimental_srcdir}/functional \ ${experimental_srcdir}/optional \ ${experimental_srcdir}/ratio \ ${experimental_srcdir}/string_view \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index bf10d6f..4ae4e41 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -905,8 +905,10 @@ decimal_headers = \ experimental_srcdir = ${glibcxx_srcdir}/include/experimental experimental_builddir = ./experimental experimental_headers = \ + ${experimental_srcdir}/algorithm \ ${experimental_srcdir}/any \ ${experimental_srcdir}/chrono \ + ${experimental_srcdir}/functional \ ${experimental_srcdir}/optional \ ${experimental_srcdir}/ratio \ ${experimental_srcdir}/string_view \ diff --git a/libstdc++-v3/include/experimental/algorithm b/libstdc++-v3/include/experimental/algorithm new file mode 100644 index 0000000..3d669b0 --- /dev/null +++ b/libstdc++-v3/include/experimental/algorithm @@ -0,0 +1,137 @@ +// -*- C++ -*- + +// Copyright (C) 2014 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file experimental/algorithm + * This is a TS C++ Library header. + */ + +#ifndef _GLIBCXX_EXPERIMENTAL_ALGORITHM +#define _GLIBCXX_EXPERIMENTAL_ALGORITHM 1 + +#pragma GCC system_header + +#if __cplusplus <= 201103L +# include +#else + +#include +#include + +namespace std _GLIBCXX_VISIBILITY(default) +{ +namespace experimental +{ +inline namespace fundamentals_v1 +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + template + inline _ForwardIterator + search(_ForwardIterator __first, _ForwardIterator __last, + const _Searcher& __searcher) + { return __searcher(__first, __last); } + +#define __cpp_lib_experimental_sample 201402 + + /// Reservoir sampling algorithm. + template + _RandomAccessIterator + __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, + _RandomAccessIterator __out, random_access_iterator_tag, + _Size __n, _UniformRandomNumberGenerator&& __g) + { + using __distrib_type = std::uniform_int_distribution<_Size>; + using __param_type = typename __distrib_type::param_type; + __distrib_type __d{}; + _Size __sample_sz = 0; + while (__first != __last && __sample_sz != __n) + __out[__sample_sz++] = *__first++; + for (auto __pop_sz = __sample_sz; __first != __last; + ++__first, ++__pop_sz) + { + const auto __k = __d(__g, __param_type{0, __pop_sz}); + if (__k < __n) + __out[__k] = *__first; + } + return __out + __sample_sz; + } + + /// Selection sampling algorithm. + template + _OutputIterator + __sample(_ForwardIterator __first, _ForwardIterator __last, + forward_iterator_tag, + _OutputIterator __out, _Cat, + _Size __n, _UniformRandomNumberGenerator&& __g) + { + using __distrib_type = std::uniform_int_distribution<_Size>; + using __param_type = typename __distrib_type::param_type; + __distrib_type __d{}; + _Size __unsampled_sz = std::distance(__first, __last); + for (__n = std::min(__n, __unsampled_sz); __n != 0; ++__first) + if (__d(__g, __param_type{0, --__unsampled_sz}) < __n) + { + *__out++ = *__first; + --__n; + } + return __out; + } + + /// Take a random sample from a population. + template + _SampleIterator + sample(_PopulationIterator __first, _PopulationIterator __last, + _SampleIterator __out, _Distance __n, + _UniformRandomNumberGenerator&& __g) + { + using __pop_cat = typename + std::iterator_traits<_PopulationIterator>::iterator_category; + using __samp_cat = typename + std::iterator_traits<_SampleIterator>::iterator_category; + + static_assert( + __or_, + is_convertible<__samp_cat, random_access_iterator_tag>>::value, + "output range must use a RandomAccessIterator when input range" + " does not meet the ForwardIterator requirements"); + + static_assert(is_integral<_Distance>::value, + "sample size must be an integer type"); + + return std::experimental::__sample( + __first, __last, __pop_cat{}, __out, __samp_cat{}, + __n, std::forward<_UniformRandomNumberGenerator>(__g)); + } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace fundamentals_v1 +} // namespace experimental +} // namespace std + +#endif // C++14 + +#endif // _GLIBCXX_EXPERIMENTAL_ALGORITHM diff --git a/libstdc++-v3/include/experimental/functional b/libstdc++-v3/include/experimental/functional new file mode 100644 index 0000000..4ecc6a5 --- /dev/null +++ b/libstdc++-v3/include/experimental/functional @@ -0,0 +1,428 @@ +// -*- C++ -*- + +// Copyright (C) 2014 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. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// . + +/** @file experimental/functional + * This is a TS C++ Library header. + */ + +#ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL +#define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1 + +#pragma GCC system_header + +#if __cplusplus <= 201103L +# include +#else + +#include +#include +#include +#include +#include +#include +#include + +namespace std _GLIBCXX_VISIBILITY(default) +{ +namespace experimental +{ +inline namespace fundamentals_v1 +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + // See C++14 ??20.9.9, Function object binders + + /// Variable template for std::is_bind_expression + template + constexpr bool is_bind_expression_v = std::is_bind_expression<_Tp>::value; + + /// Variable template for std::is_placeholder + template + constexpr int is_placeholder_v = std::is_placeholder<_Tp>::value; + +#define __cpp_lib_experimental_boyer_moore_searching 201402 + + // Searchers + + template> + class default_searcher + { + public: + default_searcher(_ForwardIterator1 __pat_first, + _ForwardIterator1 __pat_last, + _BinaryPredicate __pred = _BinaryPredicate()) + : _M_m(__pat_first, __pat_last, std::move(__pred)) + { } + + template + _ForwardIterator2 + operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const + { + return std::search(__first, __last, + std::get<0>(_M_m), std::get<1>(_M_m), + std::get<2>(_M_m)); + } + + private: + std::tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m; + }; + + template + struct __boyer_moore_map_base + { + template + __boyer_moore_map_base(_RAIter __pat, size_t __patlen, + _Hash&& __hf, _Pred&& __pred) + : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) } + { + if (__patlen > 0) + for (__diff_type __i = 0; __i < __patlen - 1; ++__i) + _M_bad_char[__pat[__i]] = __patlen - 1 - __i; + } + + using __diff_type = _Tp; + + __diff_type + _M_lookup(_Key __key, __diff_type __not_found) const + { + auto __iter = _M_bad_char.find(__key); + if (__iter == _M_bad_char.end()) + return __not_found; + return __iter->second; + } + + _Pred + _M_pred() const { return _M_bad_char.key_eq(); } + + std::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char; + }; + + template + struct __boyer_moore_array_base + { + template + __boyer_moore_array_base(_RAIter __pat, size_t __patlen, + _Unused&&, _Pred&& __pred) + : _M_bad_char{ {}, std::move(__pred) } + { + std::get<0>(_M_bad_char).fill(__patlen); + if (__patlen > 0) + for (__diff_type __i = 0; __i < __patlen - 1; ++__i) + { + auto __ch = __pat[__i]; + using _UCh = std::make_unsigned_t; + auto __uch = static_cast<_UCh>(__ch); + std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i; + } + } + + using __diff_type = _Tp; + + template + __diff_type + _M_lookup(_Key __key, __diff_type __not_found) const + { + auto __ukey = static_cast>(__key); + if (__ukey >= _Len) + return __not_found; + return std::get<0>(_M_bad_char)[__ukey]; + } + + const _Pred& + _M_pred() const { return std::get<1>(_M_bad_char); } + + std::tuple, _Pred> _M_bad_char; + }; + + template + struct __is_std_equal_to : std::false_type { }; + + template<> + struct __is_std_equal_to> : std::true_type { }; + + // Use __boyer_moore_array_base when pattern consists of narrow characters + // and uses std::equal_to as the predicate. + template::value_type, + typename _Diff = typename iterator_traits<_RAIter>::difference_type> + using __boyer_moore_base_t + = std::conditional_t::value + && __is_std_equal_to<_Pred>::value, + __boyer_moore_array_base<_Diff, 256, _Pred>, + __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>; + + template::value_type>, + typename _BinaryPredicate = std::equal_to<>> + class boyer_moore_searcher + : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> + { + using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>; + using typename _Base::__diff_type; + + public: + boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, + _Hash __hf = _Hash(), + _BinaryPredicate __pred = _BinaryPredicate()); + + template + _RandomAccessIterator2 + operator()(_RandomAccessIterator2 __first, + _RandomAccessIterator2 __last) const; + + private: + bool + _M_is_prefix(_RAIter __word, __diff_type __len, + __diff_type __pos) + { + const auto& __pred = this->_M_pred(); + __diff_type __suffixlen = __len - __pos; + for (__diff_type __i = 0; __i < __suffixlen; ++__i) + if (!__pred(__word[__i], __word[__pos + __i])) + return false; + return true; + } + + __diff_type + _M_suffix_length(_RAIter __word, __diff_type __len, + __diff_type __pos) + { + const auto& __pred = this->_M_pred(); + __diff_type __i = 0; + while (__pred(__word[__pos - __i], __word[__len - 1 - __i]) + && __i < __pos) + { + ++__i; + } + return __i; + } + + template + __diff_type + _M_bad_char_shift(_Tp __c) const + { return this->_M_lookup(__c, _M_pat_end - _M_pat); } + + _RAIter _M_pat; + _RAIter _M_pat_end; + std::vector<__diff_type> _M_good_suffix; + }; + + template::value_type>, + typename _BinaryPredicate = std::equal_to<>> + class boyer_moore_horspool_searcher + : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> + { + using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>; + using typename _Base::__diff_type; + + public: + boyer_moore_horspool_searcher(_RAIter __pat, + _RAIter __pat_end, + _Hash __hf = _Hash(), + _BinaryPredicate __pred + = _BinaryPredicate()) + : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)), + _M_pat(__pat), _M_pat_end(__pat_end) + { } + + template + _RandomAccessIterator2 + operator()(_RandomAccessIterator2 __first, + _RandomAccessIterator2 __last) const + { + const auto& __pred = this->_M_pred(); + auto __patlen = _M_pat_end - _M_pat; + if (__patlen == 0) + return __first; + auto __len = __last - __first; + while (__len >= __patlen) + { + for (auto __scan = __patlen - 1; + __pred(__first[__scan], _M_pat[__scan]); --__scan) + if (__scan == 0) + return __first; + auto __shift = _M_bad_char_shift(__first[__patlen - 1]); + __len -= __shift; + __first += __shift; + } + return __last; + } + + private: + template + __diff_type + _M_bad_char_shift(_Tp __c) const + { return this->_M_lookup(__c, _M_pat_end - _M_pat); } + + _RAIter _M_pat; + _RAIter _M_pat_end; + }; + + /// Generator function for default_searcher + template> + inline default_searcher<_ForwardIterator, _BinaryPredicate> + make_default_searcher(_ForwardIterator __pat_first, + _ForwardIterator __pat_last, + _BinaryPredicate __pred = _BinaryPredicate()) + { return { __pat_first, __pat_last, __pred }; } + + /// Generator function for boyer_moore_searcher + template::value_type>, + typename _BinaryPredicate = equal_to<>> + inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate> + make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last, + _Hash __hf = _Hash(), + _BinaryPredicate __pred = _BinaryPredicate()) + { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; } + + /// Generator function for boyer_moore_horspool_searcher + template::value_type>, + typename _BinaryPredicate = equal_to<>> + inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate> + make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last, + _Hash __hf = _Hash(), + _BinaryPredicate __pred + = _BinaryPredicate()) + { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; } + + template + boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>:: + boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end, + _Hash __hf, _BinaryPredicate __pred) + : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)), + _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat) + { + auto __patlen = __pat_end - __pat; + if (__patlen == 0) + return; + __diff_type __last_prefix = __patlen - 1; + for (__diff_type __p = __patlen - 1; __p >= 0; --__p) + { + if (_M_is_prefix(__pat, __patlen, __p + 1)) + __last_prefix = __p + 1; + _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p); + } + for (__diff_type __p = 0; __p < __patlen - 1; ++__p) + { + auto __slen = _M_suffix_length(__pat, __patlen, __p); + auto __pos = __patlen - 1 - __slen; + if (!__pred(__pat[__p - __slen], __pat[__pos])) + _M_good_suffix[__pos] = __patlen - 1 - __p + __slen; + } + } + + template + template + _RandomAccessIterator2 + boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>:: + operator()(_RandomAccessIterator2 __first, + _RandomAccessIterator2 __last) const + { + auto __patlen = _M_pat_end - _M_pat; + if (__patlen == 0) + return __first; + const auto& __pred = this->_M_pred(); + __diff_type __i = __patlen - 1; + auto __stringlen = __last - __first; + while (__i < __stringlen) + { + __diff_type __j = __patlen - 1; + while (__j >= 0 && __pred(__first[__i], _M_pat[__j])) + { + --__i; + --__j; + } + if (__j < 0) + return __first + __i + 1; + __i += std::max(_M_bad_char_shift(__first[__i]), + _M_good_suffix[__j]); + } + return __last; + } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace fundamentals_v1 + +inline namespace fundamentals_v2 +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + +#define __cpp_lib_experimental_not_fn 201406 + + /// Generalized negator. + template + struct _Not_fn + { + template + explicit + _Not_fn(_Fn2&& __fn) : _M_fn(std::forward<_Fn2>(__fn)) { } + + _Not_fn(const _Not_fn& __fn) = default; + _Not_fn(_Not_fn&& __fn) = default; + _Not_fn& operator=(const _Not_fn& __fn) = default; + _Not_fn& operator=(_Not_fn&& __fn) = default; + ~_Not_fn() = default; + + template + decltype(auto) + operator()(_Args&&... __args) + { return !_M_fn(std::forward<_Args>(__args)...); } + + template + decltype(auto) + operator()(_Args&&... __args) const + { return !_M_fn(std::forward<_Args>(__args)...); } + + template + decltype(auto) + operator()(_Args&&... __args) volatile + { return !_M_fn(std::forward<_Args>(__args)...); } + + template + decltype(auto) + operator()(_Args&&... __args) const volatile + { return !_M_fn(std::forward<_Args>(__args)...); } + + private: + _Fn _M_fn; + }; + + /// [func.not_fn] Function template not_fn + template + inline auto + not_fn(_Fn&& __fn) + { return _Not_fn>{std::forward<_Fn>(__fn)}; } + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace fundamentals_v2 +} // namespace experimental +} // namespace std + +#endif // C++14 + +#endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL diff --git a/libstdc++-v3/testsuite/experimental/algorithm/sample.cc b/libstdc++-v3/testsuite/experimental/algorithm/sample.cc new file mode 100644 index 0000000..b1d3efe --- /dev/null +++ b/libstdc++-v3/testsuite/experimental/algorithm/sample.cc @@ -0,0 +1,99 @@ +// Copyright (C) 2014 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++14" } + +#include +#include +#include +#include +#include +#include + +std::mt19937 rng; + +using std::experimental::sample; +using std::istream_iterator; +using std::ostream_iterator; + +void +test01() +{ + const int pop[] = { 1, 2 }; + int samp[10] = { }; + + // population smaller than desired sample size + auto it = sample(pop, pop + 2, samp, 10, rng); + VERIFY( it == samp + 2 ); + VERIFY( std::accumulate(samp, samp + 10, 0) == 3 ); +} + +void +test02() +{ + const int pop[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; + int samp[10] = { }; + + auto it = sample(pop, std::end(pop), samp, 10, rng); + VERIFY( it == samp + 10 ); + + std::sort(samp, it); + auto it2 = std::unique(samp, it); + VERIFY( it2 == it ); +} + +void +test03() +{ + std::istringstream pop("0 1 2 3 4 5 6 7 8 9"); + int samp[5] = { }; + + // input iterator for population + auto it = sample(istream_iterator{pop}, {}, samp, 5, rng); + VERIFY( it == samp + 5 ); + + std::sort(samp, it); + auto it2 = std::unique(samp, it); + VERIFY( it2 == it ); +} + +void +test04() +{ + std::forward_list pop{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; + std::stringstream samp; + + // forward iterator for population and output iterator for result + sample(pop.begin(), pop.end(), ostream_iterator{samp, " "}, 5, rng); + + // samp.rdbuf()->pubseekoff(0, std::ios::beg); + std::vector v(istream_iterator{samp}, {}); + VERIFY( v.size() == 5 ); + + std::sort(v.begin(), v.end()); + auto it = std::unique(v.begin(), v.end()); + VERIFY( it == v.end() ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +} diff --git a/libstdc++-v3/testsuite/experimental/algorithm/search.cc b/libstdc++-v3/testsuite/experimental/algorithm/search.cc new file mode 100644 index 0000000..3ec7ed1 --- /dev/null +++ b/libstdc++-v3/testsuite/experimental/algorithm/search.cc @@ -0,0 +1,44 @@ +// Copyright (C) 2014 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++14" } + +#include +#include + +struct nocopy +{ + nocopy() = default; + nocopy(const nocopy&) = delete; + nocopy& operator=(const nocopy&) = delete; + + int* operator()(int* f, int* l) const { return f; } +}; + +void +test01() +{ + int i[] = { 1, 2 }; + auto res = std::experimental::search(i, i + 2, nocopy{}); + VERIFY( res == i ); +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/experimental/feat-lib-fund.cc b/libstdc++-v3/testsuite/experimental/feat-lib-fund.cc index 0c73f09..fbc3744 100644 --- a/libstdc++-v3/testsuite/experimental/feat-lib-fund.cc +++ b/libstdc++-v3/testsuite/experimental/feat-lib-fund.cc @@ -1,29 +1,58 @@ // { dg-options "-std=gnu++14" } // { dg-do compile } -#include -#include +#if !__has_include() +# error "" +#endif + +#if !__has_include() +# error "" +#endif + +#if !__has_include() +# error "" +#endif + +#if !__has_include() +# error "" +#endif + +#if !__has_include() +# error "" +#endif + +#if !__has_include() +# error "" +#endif #if !__has_include() # error "" #endif -//#if !__has_include() -//# error "" -//#endif - #if !__has_include() # error "" #endif +#if !__has_include() +# error "" +#endif + +//#if !__has_include() +//# error "" +//#endif + //#if !__has_include() //# error "" //#endif -#if !__has_include() -# error "" -#endif +//#if !__has_include() +//# error "" +//#endif -#if !__has_include() -# error "" +#if !__has_include() +# error "" #endif + +//#if !__has_include() +//# error "" +//#endif diff --git a/libstdc++-v3/testsuite/experimental/functional/not_fn.cc b/libstdc++-v3/testsuite/experimental/functional/not_fn.cc new file mode 100644 index 0000000..d4c8ed9 --- /dev/null +++ b/libstdc++-v3/testsuite/experimental/functional/not_fn.cc @@ -0,0 +1,57 @@ +// Copyright (C) 2014 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++14" } + +#include +#include + +int func(int, char) { return 0; } + +struct F +{ + bool operator()() { return false; } + bool operator()() const { return true; } + bool operator()(int) { return false; } + bool operator()(int) volatile { return true; } +}; + +void +test01() +{ + using std::experimental::not_fn; + + auto f1 = not_fn(func); + VERIFY( f1(1, '2') == true ); + + auto f2 = not_fn( [] { return true; } ); + VERIFY( f2() == false ); + + auto f3 = not_fn( F{} ); + VERIFY( f3() == true ); + VERIFY( f3(1) == true ); + const auto f4 = f3; + VERIFY( f4() == false ); + volatile auto f5 = f3; + VERIFY( f5(1) == false ); +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/experimental/functional/searchers.cc b/libstdc++-v3/testsuite/experimental/functional/searchers.cc new file mode 100644 index 0000000..ae04f6f --- /dev/null +++ b/libstdc++-v3/testsuite/experimental/functional/searchers.cc @@ -0,0 +1,137 @@ +// Copyright (C) 2014 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++14" } + +#include +#include +#ifdef _GLIBCXX_USE_WCHAR_T +# include +#endif +#include + +using std::experimental::make_default_searcher; +using std::experimental::make_boyer_moore_searcher; +using std::experimental::make_boyer_moore_horspool_searcher; + +void +test01() +{ + const char s[] = { 'a', (char)-97, 'a', '\0' }; + const char* needles[] = { + s, "", "a", "aa", "aaa", "ab", "cd", "abcd", "abcdabcd", "abcabcd" + }; + const char* haystacks[] = { + s, "", "a", "aa", "aaa", "ab", "cd", "abcd", "abcdabcd", "abcabcd", + "aaaaaaa", "aabaa", "aaacab", "cdabcdab", "abcdabcd", "xyzabcdxyz" + }; + + for (auto n : needles) + { + auto ne = n + std::strlen(n); + auto d = make_default_searcher(n, ne); + auto bm = make_boyer_moore_searcher(n, ne); + auto bmh = make_boyer_moore_horspool_searcher(n, ne); + for (auto h : haystacks) + { + auto he = h + std::strlen(h); + auto res = std::search(h, he, n, ne); + auto d_res = d(h, he); + VERIFY( d_res == res ); + auto bm_res = bm(h, he); + VERIFY( bm_res == res ); + auto bmh_res = bmh(h, he); + VERIFY( bmh_res == res ); + } + } +} + +void +test02() +{ +#ifdef _GLIBCXX_USE_WCHAR_T + const wchar_t s[] = { L'a', (wchar_t)-97, L'a', L'\0' }; + const wchar_t* needles[] = { + s, L"", L"a", L"aa", L"aaa", L"ab", L"cd", L"abcd", L"abcdabcd", L"abcabcd" + }; + const wchar_t* haystacks[] = { + s, L"", L"a", L"aa", L"aaa", L"ab", L"cd", L"abcd", L"abcdabcd", L"abcabcd", + L"aaaaaaa", L"aabaa", L"aaacab", L"cdabcdab", L"abcdabcd", L"xyzabcdxyz" + }; + + for (auto n : needles) + { + auto ne = n + std::wcslen(n); + auto d = make_default_searcher(n, ne); + auto bm = make_boyer_moore_searcher(n, ne); + auto bmh = make_boyer_moore_horspool_searcher(n, ne); + for (auto h : haystacks) + { + auto he = h + std::wcslen(h); + auto res = std::search(h, he, n, ne); + auto d_res = d(h, he); + VERIFY( d_res == res ); + auto bm_res = bm(h, he); + VERIFY( bm_res == res ); + auto bmh_res = bmh(h, he); + VERIFY( bmh_res == res ); + } + } +#endif +} + +void +test03() +{ + // custom predicate + struct + { + static unsigned char + norm(unsigned char c) { return std::isalnum(c) ? c : '#'; } + + // equality + bool operator()(char l, char r) const { return norm(l) == norm(r); } + + // hash + std::size_t operator()(char c) const { return std::hash{}(norm(c)); } + } eq; + + const char* needle = " foo 123 "; + const char* haystack = "*****foo*123******"; + const char* ne = needle + std::strlen(needle); + const char* he = haystack + std::strlen(haystack); + + auto d = make_default_searcher(needle, ne, eq); + auto bm = make_boyer_moore_searcher(needle, ne, eq, eq); + auto bmh = make_boyer_moore_horspool_searcher(needle, ne, eq, eq); + + auto res = std::search(haystack, he, needle, ne, eq); + auto d_res = d(haystack, he); + VERIFY( d_res == res ); + auto bm_res = bm(haystack, he); + VERIFY( bm_res == res ); + auto bmh_res = bmh(haystack, he); + VERIFY( bmh_res == res ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/experimental/functional/value.cc b/libstdc++-v3/testsuite/experimental/functional/value.cc new file mode 100644 index 0000000..8136e7c --- /dev/null +++ b/libstdc++-v3/testsuite/experimental/functional/value.cc @@ -0,0 +1,43 @@ +// Copyright (C) 2014 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++14" } +// { dg-do compile } + +#include + +// These tests are rather simple, the front-end tests already test +// variable templates, and the library tests for the underlying +// traits are more elaborate. These are just simple sanity tests. + +int f(int); + +using B = decltype(std::bind(f, std::placeholders::_1)); + +static_assert(!std::experimental::is_bind_expression_v + && !std::is_bind_expression::value, ""); + +static_assert(std::experimental::is_bind_expression_v + && std::is_bind_expression::value, ""); + +using PH = decltype(std::placeholders::_1); + +static_assert(!std::experimental::is_placeholder_v + && !std::is_placeholder::value, ""); + +static_assert(std::experimental::is_placeholder_v + && std::is_placeholder::value, "");