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 46908eee27b524877c583ad7b0ac15102f3e1e89 Author: Jonathan Wakely <jwak...@redhat.com> Date: Wed Oct 29 17:34:40 2014 +0000 Add <experimental/algorithm> and <experimental/functional>. * 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. </row> <row> - <?dbhtml bgcolor="#C8B0B0" ?> <entry> <link xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href=""> N3905 </link> </entry> <entry>Faster string searching (Boyer-Moore et al.)</entry> - <entry>N</entry> + <entry>Y</entry> <entry>Library Fundamentals TS</entry> </row> @@ -387,14 +386,13 @@ not in any particular release. </row> <row> - <?dbhtml bgcolor="#C8B0B0" ?> <entry> <link xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3925.pdf"> N3925 </link> </entry> <entry>A sample proposal</entry> - <entry>N</entry> + <entry>Y</entry> <entry>Library Fundamentals TS</entry> </row> 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 @@ +// <experimental/algorithm> -*- 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 +// <http://www.gnu.org/licenses/>. + +/** @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 <bits/c++14_warning.h> +#else + +#include <algorithm> +#include <random> + +namespace std _GLIBCXX_VISIBILITY(default) +{ +namespace experimental +{ +inline namespace fundamentals_v1 +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + template<typename _ForwardIterator, typename _Searcher> + inline _ForwardIterator + search(_ForwardIterator __first, _ForwardIterator __last, + const _Searcher& __searcher) + { return __searcher(__first, __last); } + +#define __cpp_lib_experimental_sample 201402 + + /// Reservoir sampling algorithm. + template<typename _InputIterator, typename _RandomAccessIterator, + typename _Size, typename _UniformRandomNumberGenerator> + _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<typename _ForwardIterator, typename _OutputIterator, typename _Cat, + typename _Size, typename _UniformRandomNumberGenerator> + _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<typename _PopulationIterator, typename _SampleIterator, + typename _Distance, typename _UniformRandomNumberGenerator> + _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<__pop_cat, forward_iterator_tag>, + 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 @@ +// <experimental/functional> -*- 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 +// <http://www.gnu.org/licenses/>. + +/** @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 <bits/c++14_warning.h> +#else + +#include <functional> +#include <tuple> +#include <iterator> +#include <unordered_map> +#include <vector> +#include <array> +#include <bits/stl_algo.h> + +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<typename _Tp> + constexpr bool is_bind_expression_v = std::is_bind_expression<_Tp>::value; + + /// Variable template for std::is_placeholder + template<typename _Tp> + constexpr int is_placeholder_v = std::is_placeholder<_Tp>::value; + +#define __cpp_lib_experimental_boyer_moore_searching 201402 + + // Searchers + + template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>> + 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<typename _ForwardIterator2> + _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<typename _Key, typename _Tp, typename _Hash, typename _Pred> + struct __boyer_moore_map_base + { + template<typename _RAIter> + __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<typename _Tp, size_t _Len, typename _Pred> + struct __boyer_moore_array_base + { + template<typename _RAIter, typename _Unused> + __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<decltype(__ch)>; + auto __uch = static_cast<_UCh>(__ch); + std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i; + } + } + + using __diff_type = _Tp; + + template<typename _Key> + __diff_type + _M_lookup(_Key __key, __diff_type __not_found) const + { + auto __ukey = static_cast<std::make_unsigned_t<_Key>>(__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<std::array<_Tp, _Len>, _Pred> _M_bad_char; + }; + + template<typename _Pred> + struct __is_std_equal_to : std::false_type { }; + + template<> + struct __is_std_equal_to<std::equal_to<void>> : std::true_type { }; + + // Use __boyer_moore_array_base when pattern consists of narrow characters + // and uses std::equal_to as the predicate. + template<typename _RAIter, typename _Hash, typename _Pred, + typename _Val = typename iterator_traits<_RAIter>::value_type, + typename _Diff = typename iterator_traits<_RAIter>::difference_type> + using __boyer_moore_base_t + = std::conditional_t<sizeof(_Val) == 1 && is_integral<_Val>::value + && __is_std_equal_to<_Pred>::value, + __boyer_moore_array_base<_Diff, 256, _Pred>, + __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>; + + template<typename _RAIter, typename _Hash + = std::hash<typename std::iterator_traits<_RAIter>::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<typename _RandomAccessIterator2> + _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<typename _Tp> + __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<typename _RAIter, typename _Hash + = std::hash<typename std::iterator_traits<_RAIter>::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<typename _RandomAccessIterator2> + _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<typename _Tp> + __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<typename _ForwardIterator, + typename _BinaryPredicate = std::equal_to<>> + 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<typename _RAIter, typename _Hash + = std::hash<typename std::iterator_traits<_RAIter>::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<typename _RAIter, typename _Hash + = std::hash<typename std::iterator_traits<_RAIter>::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<typename _RAIter, typename _Hash, typename _BinaryPredicate> + 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<typename _RAIter, typename _Hash, typename _BinaryPredicate> + template<typename _RandomAccessIterator2> + _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<typename _Fn> + struct _Not_fn + { + template<typename _Fn2> + 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<typename... _Args> + decltype(auto) + operator()(_Args&&... __args) + { return !_M_fn(std::forward<_Args>(__args)...); } + + template<typename... _Args> + decltype(auto) + operator()(_Args&&... __args) const + { return !_M_fn(std::forward<_Args>(__args)...); } + + template<typename... _Args> + decltype(auto) + operator()(_Args&&... __args) volatile + { return !_M_fn(std::forward<_Args>(__args)...); } + + template<typename... _Args> + 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 <class _Fn> + inline auto + not_fn(_Fn&& __fn) + { return _Not_fn<std::decay_t<_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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++14" } + +#include <experimental/algorithm> +#include <iterator> +#include <sstream> +#include <forward_list> +#include <vector> +#include <testsuite_hooks.h> + +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<int>{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<int> 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<int>{samp, " "}, 5, rng); + + // samp.rdbuf()->pubseekoff(0, std::ios::beg); + std::vector<int> v(istream_iterator<int>{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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++14" } + +#include <experimental/algorithm> +#include <testsuite_hooks.h> + +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 <experimental/optional> -#include <experimental/string_view> +#if !__has_include(<experimental/tuple>) +# error "<experimental/tuple>" +#endif + +#if !__has_include(<experimental/type_traits>) +# error "<experimental/type_traits>" +#endif + +#if !__has_include(<experimental/ratio>) +# error "<experimental/ratio>" +#endif + +#if !__has_include(<experimental/chrono>) +# error "<experimental/chrono>" +#endif + +#if !__has_include(<experimental/system_error>) +# error "<experimental/system_error>" +#endif + +#if !__has_include(<experimental/functional>) +# error "<experimental/functional>" +#endif #if !__has_include(<experimental/optional>) # error "<experimental/optional>" #endif -//#if !__has_include(<experimental/net>) -//# error "<experimental/net>" -//#endif - #if !__has_include(<experimental/any>) # error "<experimental/any>" #endif +#if !__has_include(<experimental/string_view>) +# error "<experimental/string_view>" +#endif + +//#if !__has_include(<experimental/memory>) +//# error "<experimental/memory>" +//#endif + //#if !__has_include(<experimental/memory_resource>) //# error "<experimental/memory_resource>" //#endif -#if !__has_include(<experimental/string_view>) -# error "<experimental/string_view>" -#endif +//#if !__has_include(<experimental/future>) +//# error "<experimental/future>" +//#endif -#if !__has_include(<experimental/tuple>) -# error "<experimental/tuple>" +#if !__has_include(<experimental/algorithm>) +# error "<experimental/algorithm>" #endif + +//#if !__has_include(<experimental/net>) +//# error "<experimental/net>" +//#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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++14" } + +#include <experimental/functional> +#include <testsuite_hooks.h> + +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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++14" } + +#include <experimental/functional> +#include <cstring> +#ifdef _GLIBCXX_USE_WCHAR_T +# include <cwchar> +#endif +#include <testsuite_hooks.h> + +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<char>{}(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 +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++14" } +// { dg-do compile } + +#include <experimental/functional> + +// 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<int> + && !std::is_bind_expression<int>::value, ""); + +static_assert(std::experimental::is_bind_expression_v<B> + && std::is_bind_expression<B>::value, ""); + +using PH = decltype(std::placeholders::_1); + +static_assert(!std::experimental::is_placeholder_v<int> + && !std::is_placeholder<int>::value, ""); + +static_assert(std::experimental::is_placeholder_v<PH> + && std::is_placeholder<PH>::value, "");
commit 9604253d1a5fc0c42848613d445d6c61f33390b9 Author: Jonathan Wakely <jwak...@redhat.com> 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 <experimental/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 <typename _Tp> constexpr size_t tuple_size_v = tuple_size<_Tp>::value; +#define __cpp_lib_experimental_tuple 201402 + template <typename _Fn, typename _Tuple, std::size_t... _Idx> 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 <typename _Tp> 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<int&>(y); // { dg-error "qualifiers" "" { target { *-*-* } } 380 } + any_cast<int&>(y); // { dg-error "qualifiers" "" { target { *-*-* } } 382 } }