diff options
Diffstat (limited to 'libstdc++-v3')
59 files changed, 2798 insertions, 1705 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 9bd426812e7..6ad664509b3 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,246 @@ +2012-04-22 Paolo Carlini <paolo.carlini@oracle.com> + + PR libstdc++/53067 + * include/bits/hashtable_policy.h: Change inheritances to public. + * testsuite/23_containers/unordered_map/requirements/53067.cc: New. + * testsuite/23_containers/unordered_set/requirements/53067.cc: Likewise. + +2012-04-22 Jonathan Wakely <jwakely.gcc@gmail.com> + + * include/ext/alloc_traits.h (__alloc_traits::difference_type): + Define. + +2012-04-22 Jonathan Wakely <jwakely.gcc@gmail.com> + + PR libstdc++/53027 + * include/bits/ptr_traits.h (pointer_traits::rebind): Make public. + * testsuite/20_util/pointer_traits/requirements/typedefs.cc: Check + rebind works. + +2012-04-22 Jonathan Wakely <jwakely.gcc@gmail.com> + + * include/debug/forward_list (forward_list::splice_after): Check + allocators are equal. + * src/c++11/debug.cc: Fix spelling. + * testsuite/23_containers/forward_list/debug/splice_after5_neg.cc: + New. + * testsuite/23_containers/forward_list/debug/splice_after6_neg.cc: + Likewise. + * testsuite/23_containers/forward_list/debug/splice_after7_neg.cc: + Likewise. + +2012-04-20 Paolo Carlini <paolo.carlini@oracle.com> + + PR libstdc++/53052 + * include/std/type_traits (is_explicitly_convertible): Remove. + * testsuite/20_util/is_explicitly_convertible: Likewise. + * testsuite/20_util/make_signed/requirements/typedefs_neg.cc: + Adjust dg-error line numbers. + * testsuite/20_util/make_unsigned/requirements/typedefs_neg.cc: + Likewise. + * testsuite/20_util/declval/requirements/1_neg.cc: Likewise. + +2012-04-17 Benjamin Kosnik <bkoz@redhat.com> + + * testsuite/20_util/specialized_algorithms/uninitialized_copy/ + 808590.cc: New. + +2012-04-17 Rainer Orth <ro@CeBiTec.Uni-Bielefeld.DE> + + * testsuite/util/testsuite_abi.cc (compare_symbols): Change + summary header to avoid confusion with DejaGnu header. + +2012-04-15 Paolo Carlini <paolo.carlini@oracle.com> + + PR libstdc++/52702 + * include/std/type_traits (is_trivially_destructible): Add. + (has_trivial_destructor): Remove. + * testsuite/util/testsuite_common_types.h: Adjust. + * testsuite/20_util/tuple/requirements/dr801.cc: Likewise. + * testsuite/20_util/pair/requirements/dr801.cc: Likewise. + * testsuite/20_util/is_trivially_destructible/value.cc: New. + * testsuite/20_util/is_trivially_destructible/requirements/ + typedefs.cc: Likewise. + * testsuite/20_util/is_trivially_destructible/requirements/ + explicit_instantiation.cc: Likewise. + * testsuite/20_util/make_signed/requirements/typedefs_neg.cc: + Adjust dg-error line numbers. + * testsuite/20_util/make_unsigned/requirements/typedefs_neg.cc: + Likewise. + * testsuite/20_util/declval/requirements/1_neg.cc: Likewise. + +2012-04-14 Paolo Carlini <paolo.carlini@oracle.com> + + PR libstdc++/52699 + * include/bits/random.tcc (independent_bits_engine<>::operator()()) + Avoid various overflows; use common_type on result_type and + _RandomNumberEngine::result_type; avoid floating point computations; + other smaller tweaks. + + * include/bits/random.tcc (uniform_int_distribution<>::operator()) + Use common_type; assume _UniformRandomNumberGenerator::result_type + unsigned; tidy. + + * include/bits/stl_algobase.h (__lg(unsigned), __lg(unsigned long), + __lg(unsigned long long)): Add. + +2012-04-14 Alan Modra <amodra@gmail.com> + + PR libstdc++/52839 + * acinclude.m4 (_GLIBCXX_ATOMIC_BUILTINS): Do not depend on + glibcxx_cv_atomic_long_long. + * configure: Regenerate. + +2012-04-13 Paolo Carlini <paolo.carlini@oracle.com> + + * testsuite/26_numerics/cmath/51083.cc: Move... + * testsuite/26_numerics/headers/cmath/51083.cc: ... here. + +2012-04-13 Laurent Alfonsi <laurent.alfonsi@st.com> + + PR libstdc++/52604 + * src/c++98/mt_allocator.cc: (__freelist::~__freelist): Reset pointer. + +2012-04-13 Paolo Carlini <paolo.carlini@oracle.com> + + * include/debug/safe_iterator.h (_BeforeBeginHelper<>:: + _S_Is_Beginnest): Add. + * include/debug/forward_list (_BeforeBeginHelper<>:: + _S_Is_Beginnest): Likewise. + (_Safe_iterator<>::_M_is_beginnest): Add. + * include/debug/safe_iterator.tcc (_Safe_iterator<>::_M_valid_range): + Use the latter. + * testsuite/23_containers/forward_list/debug/splice_after.cc: + Add test. + +2012-04-12 Benjamin Kosnik <bkoz@redhat.com> + + * include/bits/unordered_map.h (__unordered_map): Remove. + (__unordered_multimap): Remove. + Add aliases for __umap_traits, __umap_hashtable, __ummap_traits, + __ummap_hashtable. + (unordered_map): Derive from __umap_hashtable. + (unordered_multimap): Derive from __ummap_hashtable. + * include/bits/unordered_set.h (__unordered_set): Remove. + (__unordered_multiset): Remove. + Add aliases for __uset_traits, __uset_hashtable, __umset_traits, + __umset_hashtable. + (unordered_set): Derive from __uset_hashtable. + (unordered_multiset): Derive from __umset_hashtable. + * include/bits/hashtable.h (__cache_default): New, consolidated + cache defaults for _Hashtable. Adjust comments for doxygen. + (_Hashtable): Consolidate bool template parameters into new, + _Traits class. Inherited base classes synthesize _Hashtable in + CRTP via original 10 parameters. Prefer using declarations to + typedefs, add __node_type, __bucket_type, etc. Push many nested + types down hierarchy to _Hashtable_base. Add constructors + necessary for top-level unordered_containers. Consolidate insert + member functions and logic in new base class, __detail::_Insert + and __detail::_Insert_base. + (_Hashtable::operator=(initializer_list)): Add. + * include/bits/hashtable_policy.h: Convert to doxygen markup. + (_Hashtable_traits) New. Consolidate bool template parameters here. + (_Insert, _Insert_base): New, consolidated insert member functions. + (_Map_base, _Equality, _Rehash_base): Adjust template parameters, + use base types. + (_Hashtable_base): Move type declarations useful to other base + classes into this class. + * python/libstdcxx/v6/printers.py (Tr1HashtableIterator): Update. + * testsuite/23_containers/unordered_set/instantiation_neg.cc: + Adjust traits, line numbers. + +2012-04-12 Jeffrey Yasskin <jyasskin@google.com> + + PR libstdc++/52822 + * include/bits/stl_algo.h (__find_if_not): Expose in C++98 mode. + (__find_if_not_n): Like __find_if_not, but works on and updates a + counted range instead of a bounded range. + (stable_partition): Guarantee !__pred(*__first) in call to + __stable_partition_adaptive() or __inplace_stable_partition(). + (__stable_partition_adaptive): Use new precondition to avoid + moving/copying objects onto themselves. Guarantee new + precondition to recursive calls. + (__inplace_stable_partition): Use new precondition to simplify + base case, remove __last parameter. Guarantee new precondition to + recursive calls. + * testsuite/25_algorithms/stable_partition/moveable.cc (test02): + Test a sequence that starts with a value matching the predicate. + * testsuite/25_algorithms/stable_partition/pr52822.cc: Test + vectors, which have a destructive self-move-assignment. + +2012-04-12 Andreas Schwab <schwab@linux-m68k.org> + + * testsuite/Makefile.am (check_DEJAGNUnormal0): Run + prettyprinters.exp. + * testsuite/Makefile.in: Regenerated. + +2012-04-12 Paolo Carlini <paolo.carlini@oracle.com> + + PR libstdc++/52942 + * include/bits/stl_function.h (_Identity, _Select1st, _Select2nd): + In C++11 mode do not derive from std::unary_function. + * include/ext/functional (identity, select1st, select2nd): Adjust. + * testsuite/23_containers/unordered_map/requirements/52942.cc: New. + * testsuite/23_containers/unordered_set/requirements/52942.cc: Likewise. + +2012-04-11 Jonathan Wakely <jwakely.gcc@gmail.com> + + PR libstdc++/52924 + * include/bits/shared_ptr_base.h (_Sp_counted_deleter): Add + user-defined destructor. + (_Sp_counted_inplace): Likewise. + * testsuite/20_util/shared_ptr/cons/52924.cc: New. + * testsuite/20_util/shared_ptr/cons/43820_neg.cc: Adjust dg-error + line numbers. + +2012-04-11 Jonathan Wakely <jwakely.gcc@gmail.com> + + * doc/xml/manual/debug.xml (Debug Versions of Library Binary Files): + Re-arrange text slightly. + +2012-04-11 Jonathan Wakely <jwakely.gcc@gmail.com> + + * testsuite/performance/30_threads/future/polling.cc: Adjust. + +2012-04-11 Paolo Carlini <paolo.carlini@oracle.com> + + * include/bits/forward_list.h (splice_after(const_iterator, + forward_list&), splice_after(const_iterator, forward_list&, + const_iterator), splice_after(const_iterator, forward_list&, + const_iterator, const_iterator), merge(forward_list&), + merge(forward_list&, _Comp)): Add per C++11 as published (and + LWG 1310). + * include/debug/forward_list: Adjust. + + * include/bits/forward_list.h (splice_after(const_iterator, + forward_list&&, const_iterator)): Only declare. + (_M_transfer_after): Remove. + (_M_splice_after(const_iterator, forward_list&&)): Change signature. + (splice_after(const_iterator, forward_list&&, const_iterator, + const_iterator)): Use the latter. + * include/bits/forward_list.tcc (splice_after(const_iterator, + forward_list&&, const_iterator)): Define here. + (_M_splice_after): Define, use throughout. + + * include/bits/forward_list.h (insert_after(const_iterator, + std::initializer_list<_Tp>)): Forward to insert_after(const_iterator, + _InputIterator, _InputIterator). + * include/bits/forward_list.tcc: Remove definition. + + * testsuite/23_containers/forward_list/modifiers/6.cc: New. + * testsuite/23_containers/forward_list/operations/1.cc: Adjust. + +2012-04-11 Paolo Carlini <paolo.carlini@oracle.com> + + PR libstdc++/52931 + * include/bits/functional_hash.h (struct hash): Remove definition. + * testsuite/20_util/hash/52931.cc: New. + +2012-04-11 Manuel López-Ibáñez <manu@gcc.gnu.org> + + PR 24985 + * testsuite/lib/prune.exp: Handle caret. + 2012-04-05 Rainer Orth <ro@CeBiTec.Uni-Bielefeld.DE> Partially revert: diff --git a/libstdc++-v3/acinclude.m4 b/libstdc++-v3/acinclude.m4 index 01b06e490d7..6632725b7ec 100644 --- a/libstdc++-v3/acinclude.m4 +++ b/libstdc++-v3/acinclude.m4 @@ -2861,11 +2861,10 @@ EOF CXXFLAGS="$old_CXXFLAGS" AC_LANG_RESTORE - # Set atomicity_dir to builtins if all of above tests pass. + # Set atomicity_dir to builtins if all but the long long test above passes. if test $glibcxx_cv_atomic_bool = yes \ && test $glibcxx_cv_atomic_short = yes \ - && test $glibcxx_cv_atomic_int = yes \ - && test $glibcxx_cv_atomic_long_long = yes ; then + && test $glibcxx_cv_atomic_int = yes; then AC_DEFINE(_GLIBCXX_ATOMIC_BUILTINS, 1, [Define if the compiler supports C++11 atomics.]) atomicity_dir=cpu/generic/atomicity_builtins diff --git a/libstdc++-v3/configure b/libstdc++-v3/configure index e8fb5d37b22..a545eda2eec 100755 --- a/libstdc++-v3/configure +++ b/libstdc++-v3/configure @@ -15446,11 +15446,10 @@ ac_link='$CC -o conftest$ac_exeext $CFLAGS $CPPFLAGS $LDFLAGS conftest.$ac_ext $ ac_compiler_gnu=$ac_cv_c_compiler_gnu - # Set atomicity_dir to builtins if all of above tests pass. + # Set atomicity_dir to builtins if all but the long long test above passes. if test $glibcxx_cv_atomic_bool = yes \ && test $glibcxx_cv_atomic_short = yes \ - && test $glibcxx_cv_atomic_int = yes \ - && test $glibcxx_cv_atomic_long_long = yes ; then + && test $glibcxx_cv_atomic_int = yes; then $as_echo "#define _GLIBCXX_ATOMIC_BUILTINS 1" >>confdefs.h @@ -15482,7 +15481,7 @@ $as_echo "$as_me: WARNING: Performance of certain classes will degrade as a resu # unnecessary for this test. cat > conftest.$ac_ext << EOF -#line 15485 "configure" +#line 15484 "configure" int main() { _Decimal32 d1; @@ -15524,7 +15523,7 @@ ac_compiler_gnu=$ac_cv_cxx_compiler_gnu # unnecessary for this test. cat > conftest.$ac_ext << EOF -#line 15527 "configure" +#line 15526 "configure" template<typename T1, typename T2> struct same { typedef T2 type; }; @@ -15558,7 +15557,7 @@ $as_echo "$enable_int128" >&6; } rm -f conftest* cat > conftest.$ac_ext << EOF -#line 15561 "configure" +#line 15560 "configure" template<typename T1, typename T2> struct same { typedef T2 type; }; diff --git a/libstdc++-v3/doc/xml/manual/debug.xml b/libstdc++-v3/doc/xml/manual/debug.xml index 7ee2abf6988..0a24c960211 100644 --- a/libstdc++-v3/doc/xml/manual/debug.xml +++ b/libstdc++-v3/doc/xml/manual/debug.xml @@ -64,8 +64,9 @@ <para> If you would like debug symbols in libstdc++, there are two ways to - build libstdc++ with debug flags. The first is to run make from the - toplevel in a freshly-configured tree with + build libstdc++ with debug flags. The first is to create a separate + debug build by running make from the top-level of a tree + freshly-configured with </para> <programlisting> --enable-libstdcxx-debug @@ -75,11 +76,11 @@ --enable-libstdcxx-debug-flags='...' </programlisting> <para> - to create a separate debug build. Both the normal build and the - debug build will persist, without having to specify - <code>CXXFLAGS</code>, and the debug library will be installed in a - separate directory tree, in <code>(prefix)/lib/debug</code>. For - more information, look at the <link linkend="manual.intro.setup.configure">configuration</link> section. + Both the normal build and the debug build will persist, without + having to specify <code>CXXFLAGS</code>, and the debug library will + be installed in a separate directory tree, in <code>(prefix)/lib/debug</code>. + For more information, look at the + <link linkend="manual.intro.setup.configure">configuration</link> section. </para> <para> diff --git a/libstdc++-v3/include/bits/forward_list.h b/libstdc++-v3/include/bits/forward_list.h index 01020c5e933..76c3e3303cc 100644 --- a/libstdc++-v3/include/bits/forward_list.h +++ b/libstdc++-v3/include/bits/forward_list.h @@ -53,15 +53,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _Fwd_list_node_base* _M_next; _Fwd_list_node_base* - _M_transfer_after(_Fwd_list_node_base* __begin) - { - _Fwd_list_node_base* __end = __begin; - while (__end && __end->_M_next) - __end = __end->_M_next; - return _M_transfer_after(__begin, __end); - } - - _Fwd_list_node_base* _M_transfer_after(_Fwd_list_node_base* __begin, _Fwd_list_node_base* __end) { @@ -925,7 +916,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * does not invalidate iterators and references. */ iterator - insert_after(const_iterator __pos, std::initializer_list<_Tp> __il); + insert_after(const_iterator __pos, std::initializer_list<_Tp> __il) + { return insert_after(__pos, __il.begin(), __il.end()); } /** * @brief Removes the element pointed to by the iterator following @@ -1047,9 +1039,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER splice_after(const_iterator __pos, forward_list&& __list) { if (!__list.empty()) - _M_splice_after(__pos, std::move(__list)); + _M_splice_after(__pos, __list.before_begin(), __list.end()); } + void + splice_after(const_iterator __pos, forward_list& __list) + { splice_after(__pos, std::move(__list)); } + /** * @brief Insert element from another %forward_list. * @param __pos Iterator referencing the element to insert after. @@ -1062,15 +1058,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ void splice_after(const_iterator __pos, forward_list&& __list, - const_iterator __i) - { - const_iterator __j = __i; - ++__j; - if (__pos == __i || __pos == __j) - return; + const_iterator __i); - splice_after(__pos, std::move(__list), __i, __j); - } + void + splice_after(const_iterator __pos, forward_list& __list, + const_iterator __i) + { splice_after(__pos, std::move(__list), __i); } /** * @brief Insert range from another %forward_list. @@ -1086,8 +1079,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * Undefined if @a __pos is in (__before,__last). */ void - splice_after(const_iterator __pos, forward_list&& __list, - const_iterator __before, const_iterator __last); + splice_after(const_iterator __pos, forward_list&&, + const_iterator __before, const_iterator __last) + { _M_splice_after(__pos, __before, __last); } + + void + splice_after(const_iterator __pos, forward_list&, + const_iterator __before, const_iterator __last) + { _M_splice_after(__pos, __before, __last); } /** * @brief Remove all elements equal to value. @@ -1130,7 +1129,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ void unique() - { this->unique(std::equal_to<_Tp>()); } + { unique(std::equal_to<_Tp>()); } /** * @brief Remove consecutive elements satisfying a predicate. @@ -1159,7 +1158,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ void merge(forward_list&& __list) - { this->merge(std::move(__list), std::less<_Tp>()); } + { merge(std::move(__list), std::less<_Tp>()); } + + void + merge(forward_list& __list) + { merge(std::move(__list)); } /** * @brief Merge sorted lists according to comparison function. @@ -1176,6 +1179,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void merge(forward_list&& __list, _Comp __comp); + template<typename _Comp> + void + merge(forward_list& __list, _Comp __comp) + { merge(std::move(__list), __comp); } + /** * @brief Sort the elements of the list. * @@ -1184,7 +1192,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ void sort() - { this->sort(std::less<_Tp>()); } + { sort(std::less<_Tp>()); } /** * @brief Sort the forward_list using a comparison function. @@ -1218,7 +1226,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER // Called by splice_after and insert_after. iterator - _M_splice_after(const_iterator __pos, forward_list&& __list); + _M_splice_after(const_iterator __pos, const_iterator __before, + const_iterator __last); // Called by forward_list(n). void diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc index 99fa3a01609..3c9f2380b27 100644 --- a/libstdc++-v3/include/bits/forward_list.tcc +++ b/libstdc++-v3/include/bits/forward_list.tcc @@ -223,22 +223,37 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _Tp, typename _Alloc> typename forward_list<_Tp, _Alloc>::iterator forward_list<_Tp, _Alloc>:: - _M_splice_after(const_iterator __pos, forward_list&& __list) + _M_splice_after(const_iterator __pos, + const_iterator __before, const_iterator __last) { _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node); - iterator __before = __list.before_begin(); - return iterator(__tmp->_M_transfer_after(__before._M_node)); + _Node_base* __b = const_cast<_Node_base*>(__before._M_node); + _Node_base* __end = __b; + + while (__end && __end->_M_next != __last._M_node) + __end = __end->_M_next; + + if (__b != __end) + return iterator(__tmp->_M_transfer_after(__b, __end)); + else + return iterator(__tmp); } template<typename _Tp, typename _Alloc> void forward_list<_Tp, _Alloc>:: splice_after(const_iterator __pos, forward_list&&, - const_iterator __before, const_iterator __last) + const_iterator __i) { + const_iterator __j = __i; + ++__j; + + if (__pos == __i || __pos == __j) + return; + _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node); - __tmp->_M_transfer_after(const_cast<_Node_base*>(__before._M_node), - const_cast<_Node_base*>(__last._M_node)); + __tmp->_M_transfer_after(const_cast<_Node_base*>(__i._M_node), + const_cast<_Node_base*>(__j._M_node)); } template<typename _Tp, typename _Alloc> @@ -249,7 +264,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER if (__n) { forward_list __tmp(__n, __val, get_allocator()); - return _M_splice_after(__pos, std::move(__tmp)); + return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end()); } else return iterator(const_cast<_Node_base*>(__pos._M_node)); @@ -264,26 +279,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { forward_list __tmp(__first, __last, get_allocator()); if (!__tmp.empty()) - return _M_splice_after(__pos, std::move(__tmp)); + return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end()); else return iterator(const_cast<_Node_base*>(__pos._M_node)); } template<typename _Tp, typename _Alloc> - typename forward_list<_Tp, _Alloc>::iterator - forward_list<_Tp, _Alloc>:: - insert_after(const_iterator __pos, std::initializer_list<_Tp> __il) - { - if (__il.size()) - { - forward_list __tmp(__il, get_allocator()); - return _M_splice_after(__pos, std::move(__tmp)); - } - else - return iterator(const_cast<_Node_base*>(__pos._M_node)); - } - - template<typename _Tp, typename _Alloc> void forward_list<_Tp, _Alloc>:: remove(const _Tp& __val) diff --git a/libstdc++-v3/include/bits/functional_hash.h b/libstdc++-v3/include/bits/functional_hash.h index e892159d449..69c186c5795 100644 --- a/libstdc++-v3/include/bits/functional_hash.h +++ b/libstdc++-v3/include/bits/functional_hash.h @@ -1,6 +1,7 @@ // functional_hash.h header -*- C++ -*- -// Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. +// Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012 +// 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 @@ -55,12 +56,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// Primary class template hash. template<typename _Tp> - struct hash : public __hash_base<size_t, _Tp> - { - static_assert(sizeof(_Tp) < 0, - "std::hash is not specialized for this type"); - size_t operator()(const _Tp&) const noexcept; - }; + struct hash; /// Partial specializations for pointer types. template<typename _Tp> diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 41418a8a509..8c17035b5c8 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -1,6 +1,7 @@ // hashtable.h header -*- C++ -*- -// Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. +// Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012 +// 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 @@ -38,254 +39,305 @@ namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION - // Class template _Hashtable, class definition. + template<typename _Tp, typename _Hash> + using __cache_default = __not_<__and_<is_integral<_Tp>, + is_empty<_Hash>, + integral_constant<bool, !__is_final(_Hash)>, + __detail::__is_noexcept_hash<_Tp, _Hash> >>; - // Meaning of class template _Hashtable's template parameters - - // _Key and _Value: arbitrary CopyConstructible types. - - // _Allocator: an allocator type ([lib.allocator.requirements]) whose - // value type is Value. As a conforming extension, we allow for - // value type != Value. - - // _ExtractKey: function object that takes an object of type Value - // and returns a value of type _Key. - - // _Equal: function object that takes two objects of type k and returns - // a bool-like value that is true if the two objects are considered equal. - - // _H1: the hash function. A unary function object with argument type - // Key and result type size_t. Return values should be distributed - // over the entire range [0, numeric_limits<size_t>:::max()]. - - // _H2: the range-hashing function (in the terminology of Tavori and - // Dreizin). A binary function object whose argument types and result - // type are all size_t. Given arguments r and N, the return value is - // in the range [0, N). - - // _Hash: the ranged hash function (Tavori and Dreizin). A binary function - // whose argument types are _Key and size_t and whose result type is - // size_t. Given arguments k and N, the return value is in the range - // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other - // than the default, _H1 and _H2 are ignored. - - // _RehashPolicy: Policy class with three members, all of which govern - // the bucket count. _M_next_bkt(n) returns a bucket count no smaller - // than n. _M_bkt_for_elements(n) returns a bucket count appropriate - // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) - // determines whether, if the current bucket count is n_bkt and the - // current element count is n_elt, we need to increase the bucket - // count. If so, returns make_pair(true, n), where n is the new - // bucket count. If not, returns make_pair(false, <anything>). - - // __cache_hash_code: bool. true if we store the value of the hash - // function along with the value. This is a time-space tradeoff. - // Storing it may improve lookup speed by reducing the number of times - // we need to call the Equal function. - - // __constant_iterators: bool. true if iterator and const_iterator are - // both constant iterator types. This is true for unordered_set and - // unordered_multiset, false for unordered_map and unordered_multimap. - - // __unique_keys: bool. true if the return value of _Hashtable::count(k) - // is always at most one, false if it may be an arbitrary number. This - // true for unordered_set and unordered_map, false for unordered_multiset - // and unordered_multimap. /** - * Here's _Hashtable data structure, each _Hashtable has: - * - _Bucket[] _M_buckets - * - _Hash_node_base _M_before_begin - * - size_type _M_bucket_count - * - size_type _M_element_count + * Primary class template _Hashtable. + * + * @ingroup hashtable-detail + * + * @tparam _Value CopyConstructible type. + * + * @tparam _Key CopyConstructible type. + * + * @tparam _Alloc An allocator type + * ([lib.allocator.requirements]) whose _Alloc::value_type is + * _Value. As a conforming extension, we allow for + * _Alloc::value_type != _Value. + * + * @tparam _ExtractKey Function object that takes an object of type + * _Value and returns a value of type _Key. + * + * @tparam _Equal Function object that takes two objects of type k + * and returns a bool-like value that is true if the two objects + * are considered equal. + * + * @tparam _H1 The hash function. A unary function object with + * argument type _Key and result type size_t. Return values should + * be distributed over the entire range [0, numeric_limits<size_t>:::max()]. + * + * @tparam _H2 The range-hashing function (in the terminology of + * Tavori and Dreizin). A binary function object whose argument + * types and result type are all size_t. Given arguments r and N, + * the return value is in the range [0, N). + * + * @tparam _Hash The ranged hash function (Tavori and Dreizin). A + * binary function whose argument types are _Key and size_t and + * whose result type is size_t. Given arguments k and N, the + * return value is in the range [0, N). Default: hash(k, N) = + * h2(h1(k), N). If _Hash is anything other than the default, _H1 + * and _H2 are ignored. + * + * @tparam _RehashPolicy Policy class with three members, all of + * which govern the bucket count. _M_next_bkt(n) returns a bucket + * count no smaller than n. _M_bkt_for_elements(n) returns a + * bucket count appropriate for an element count of n. + * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the + * current bucket count is n_bkt and the current element count is + * n_elt, we need to increase the bucket count. If so, returns + * make_pair(true, n), where n is the new bucket count. If not, + * returns make_pair(false, <anything>) + * + * @tparam _Traits Compile-time class with three boolean + * std::integral_constant members: __cache_hash_code, __constant_iterators, + * __unique_keys. * - * with _Bucket being _Hash_node* and _Hash_node constaining: - * - _Hash_node* _M_next - * - Tp _M_value - * - size_t _M_code if cache_hash_code is true + * Each _Hashtable data structure has: * - * In terms of Standard containers the hastable is like the aggregation of: - * - std::forward_list<_Node> containing the elements - * - std::vector<std::forward_list<_Node>::iterator> representing the buckets + * - _Bucket[] _M_buckets + * - _Hash_node_base _M_before_begin + * - size_type _M_bucket_count + * - size_type _M_element_count * - * The non-empty buckets contain the node before the first bucket node. This - * design allow to implement something like a std::forward_list::insert_after - * on container insertion and std::forward_list::erase_after on container - * erase calls. _M_before_begin is equivalent to - * std::foward_list::before_begin. Empty buckets are containing nullptr. - * Note that one of the non-empty bucket contains &_M_before_begin which is - * not a derefenrenceable node so the node pointers in buckets shall never be - * derefenrenced, only its next node can be. - * - * Walk through a bucket nodes require a check on the hash code to see if the - * node is still in the bucket. Such a design impose a quite efficient hash - * functor and is one of the reasons it is highly advise to set - * __cache_hash_code to true. + * with _Bucket being _Hash_node* and _Hash_node constaining: * - * The container iterators are simply built from nodes. This way incrementing - * the iterator is perfectly efficient independent of how many empty buckets - * there are in the container. + * - _Hash_node* _M_next + * - Tp _M_value + * - size_t _M_code if cache_hash_code is true * - * On insert we compute element hash code and thanks to it find the bucket - * index. If the element must be inserted on an empty bucket we add it at the - * beginning of the singly linked list and make the bucket point to - * _M_before_begin. The bucket that used to point to _M_before_begin, if any, - * is updated to point to its new before begin node. + * In terms of Standard containers the hastable is like the aggregation of: * - * On erase, the simple iterator design impose to use the hash functor to get - * the index of the bucket to update. For this reason, when __cache_hash_code - * is set to false, there is a static assertion that the hash functor cannot - * throw. + * - std::forward_list<_Node> containing the elements + * - std::vector<std::forward_list<_Node>::iterator> representing the buckets + * + * The non-empty buckets contain the node before the first bucket + * node. This design allow to implement something like a + * std::forward_list::insert_after on container insertion and + * std::forward_list::erase_after on container erase + * calls. _M_before_begin is equivalent to + * std::foward_list::before_begin. Empty buckets are containing + * nullptr. Note that one of the non-empty bucket contains + * &_M_before_begin which is not a derefenrenceable node so the + * node pointers in buckets shall never be derefenrenced, only its + * next node can be. + * + * Walk through a bucket nodes require a check on the hash code to + * see if the node is still in the bucket. Such a design impose a + * quite efficient hash functor and is one of the reasons it is + * highly advise to set __cache_hash_code to true. + * + * The container iterators are simply built from nodes. This way + * incrementing the iterator is perfectly efficient independent of + * how many empty buckets there are in the container. + * + * On insert we compute element hash code and thanks to it find the + * bucket index. If the element must be inserted on an empty bucket + * we add it at the beginning of the singly linked list and make the + * bucket point to _M_before_begin. The bucket that used to point to + * _M_before_begin, if any, is updated to point to its new before + * begin node. + * + * On erase, the simple iterator design impose to use the hash + * functor to get the index of the bucket to update. For this + * reason, when __cache_hash_code is set to false, there is a static + * assertion that the hash functor cannot throw. + * + * Functionality is implemented by decomposition into base classes, + * where the derived _Hashtable class is used in _Map_base, + * _Insert, _Rehash_base, and _Equality base classes to access the + * "this" pointer. _Hashtable_base is used in the base classes as a + * non-recursive, fully-completed-type so that detailed nested type + * information, such as iterator type and node type, can be + * used. This is similar to the "Curiously Recurring Template + * Pattern" (CRTP) technique, but uses a reconstructed, not + * explicitly passed, template pattern. + * + * Base class templates are: + * __detail::_Hashtable_base + * __detail::_Map_base + * __detail::_Insert + * __detail::_Rehash_base + * __detail::_Equality */ - - template<typename _Key, typename _Value, typename _Allocator, + template<typename _Key, typename _Value, typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, - typename _RehashPolicy, - bool __cache_hash_code, - bool __constant_iterators, - bool __unique_keys> + typename _RehashPolicy, typename _Traits> class _Hashtable - : public __detail::_Rehash_base<_RehashPolicy, - _Hashtable<_Key, _Value, _Allocator, - _ExtractKey, - _Equal, _H1, _H2, _Hash, - _RehashPolicy, - __cache_hash_code, - __constant_iterators, - __unique_keys> >, - public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, - _H1, _H2, _Hash, __cache_hash_code>, - public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys, - _Hashtable<_Key, _Value, _Allocator, - _ExtractKey, - _Equal, _H1, _H2, _Hash, - _RehashPolicy, - __cache_hash_code, - __constant_iterators, - __unique_keys> >, - public __detail::_Equality_base<_ExtractKey, __unique_keys, - _Hashtable<_Key, _Value, _Allocator, - _ExtractKey, - _Equal, _H1, _H2, _Hash, - _RehashPolicy, - __cache_hash_code, - __constant_iterators, - __unique_keys> > + : public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, _Traits>, + public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>, + public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>, + public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>, + public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits> { + public: + typedef _Key key_type; + typedef _Value value_type; + typedef _Alloc allocator_type; + typedef _Equal key_equal; + + // mapped_type, if present, comes from _Map_base. + // hasher, if present, comes from _Hash_code_base/_Hashtable_base. + typedef typename _Alloc::pointer pointer; + typedef typename _Alloc::const_pointer const_pointer; + typedef typename _Alloc::reference reference; + typedef typename _Alloc::const_reference const_reference; + + private: + using __rehash_type = _RehashPolicy; + using __rehash_state = typename __rehash_type::_State; + + using __traits_type = _Traits; + using __hash_cached = typename __traits_type::__hash_cached; + using __constant_iterators = typename __traits_type::__constant_iterators; + using __unique_keys = typename __traits_type::__unique_keys; + + using __key_extract = typename std::conditional< + __constant_iterators::value, + std::_Identity<value_type>, + std::_Select1st<value_type>>::type; + + using __hashtable_base = __detail:: + _Hashtable_base<_Key, _Value, _ExtractKey, + _Equal, _H1, _H2, _Hash, _Traits>; + + using __hash_code_base = typename __hashtable_base::__hash_code_base; + using __hash_code = typename __hashtable_base::__hash_code; + using __node_type = typename __hashtable_base::__node_type; + using __node_base = typename __hashtable_base::__node_base; + using __bucket_type = typename __hashtable_base::__bucket_type; + using __ireturn_type = typename __hashtable_base::__ireturn_type; + using __iconv_type = typename __hashtable_base::__iconv_type; + + using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits>; + + using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc, + _ExtractKey, _Equal, + _H1, _H2, _Hash, + _RehashPolicy, _Traits>; + + using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits>; + + // Metaprogramming for picking apart hash caching. + using __hash_noexcept = __detail::__is_noexcept_hash<_Key, _H1>; + template<typename _Cond> - using __if_hash_code_cached - = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>; + using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>; template<typename _Cond> - using __if_hash_code_not_cached - = __or_<integral_constant<bool, __cache_hash_code>, _Cond>; - - // When hash codes are not cached the hash functor shall not throw - // because it is used in methods (erase, swap...) that shall not throw. - static_assert(__if_hash_code_not_cached<__detail::__is_noexcept_hash<_Key, - _H1>>::value, - "Cache the hash code or qualify your hash functor with noexcept"); - - // Following two static assertions are necessary to guarantee that - // swapping two hashtable instances won't invalidate associated local - // iterators. - - // When hash codes are cached local iterator only uses H2 which must then - // be empty. - static_assert(__if_hash_code_cached<is_empty<_H2>>::value, - "Functor used to map hash code to bucket index must be empty"); - - typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, - __cache_hash_code> _HCBase; - - // When hash codes are not cached local iterator is going to use _HCBase - // above to compute node bucket index so it has to be empty. - static_assert(__if_hash_code_not_cached<is_empty<_HCBase>>::value, - "Cache the hash code or make functors involved in hash code" - " and bucket index computation empty"); + using __if_hash_not_cached = __or_<__hash_cached, _Cond>; + + // Compile-time diagnostics. + + // When hash codes are not cached the hash functor shall not + // throw because it is used in methods (erase, swap...) that + // shall not throw. + static_assert(__if_hash_not_cached<__hash_noexcept>::value, + "Cache the hash code" + " or qualify your hash functor with noexcept"); + + // Following two static assertions are necessary to guarantee + // that swapping two hashtable instances won't invalidate + // associated local iterators. + + // When hash codes are cached local iterator only uses H2 which + // must then be empty. + static_assert(__if_hash_cached<is_empty<_H2>>::value, + "Functor used to map hash code to bucket index" + " must be empty"); + + // When hash codes are not cached local iterator is going to use + // __hash_code_base above to compute node bucket index so it has + // to be empty. + static_assert(__if_hash_not_cached<is_empty<__hash_code_base>>::value, + "Cache the hash code or make functors involved in hash code" + " and bucket index computation empty"); public: - typedef _Allocator allocator_type; - typedef _Value value_type; - typedef _Key key_type; - typedef _Equal key_equal; - // mapped_type, if present, comes from _Map_base. - // hasher, if present, comes from _Hash_code_base. - typedef typename _Allocator::pointer pointer; - typedef typename _Allocator::const_pointer const_pointer; - typedef typename _Allocator::reference reference; - typedef typename _Allocator::const_reference const_reference; - - typedef std::size_t size_type; - typedef std::ptrdiff_t difference_type; - typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey, - _H1, _H2, _Hash, - __constant_iterators, - __cache_hash_code> - local_iterator; - typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey, - _H1, _H2, _Hash, - __constant_iterators, - __cache_hash_code> - const_local_iterator; - typedef __detail::_Node_iterator<value_type, __constant_iterators, - __cache_hash_code> - iterator; - typedef __detail::_Node_const_iterator<value_type, - __constant_iterators, - __cache_hash_code> - const_iterator; - - template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2, - typename _Hashtable2> + template<typename _Keya, typename _Valuea, typename _Alloca, + typename _ExtractKeya, typename _Equala, + typename _H1a, typename _H2a, typename _Hasha, + typename _RehashPolicya, typename _Traitsa, + bool _Unique_keysa> friend struct __detail::_Map_base; + template<typename _Keya, typename _Valuea, typename _Alloca, + typename _ExtractKeya, typename _Equala, + typename _H1a, typename _H2a, typename _Hasha, + typename _RehashPolicya, typename _Traitsa> + friend struct __detail::_Insert_base; + + template<typename _Keya, typename _Valuea, typename _Alloca, + typename _ExtractKeya, typename _Equala, + typename _H1a, typename _H2a, typename _Hasha, + typename _RehashPolicya, typename _Traitsa, + bool _Constant_iteratorsa, bool _Unique_keysa> + friend struct __detail::_Insert; + + using size_type = typename __hashtable_base::size_type; + using difference_type = typename __hashtable_base::difference_type; + + using iterator = typename __hashtable_base::iterator; + using const_iterator = typename __hashtable_base::const_iterator; + + using local_iterator = typename __hashtable_base::local_iterator; + using const_local_iterator = typename __hashtable_base:: + const_local_iterator; + private: - typedef typename _RehashPolicy::_State _RehashPolicyState; - typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node; - typedef typename _Allocator::template rebind<_Node>::other + typedef typename _Alloc::template rebind<__node_type>::other _Node_allocator_type; - typedef __detail::_Hash_node_base _BaseNode; - typedef _BaseNode* _Bucket; - typedef typename _Allocator::template rebind<_Bucket>::other + typedef typename _Alloc::template rebind<__bucket_type>::other _Bucket_allocator_type; - - typedef typename _Allocator::template rebind<_Value>::other + typedef typename _Alloc::template rebind<value_type>::other _Value_allocator_type; + _Node_allocator_type _M_node_allocator; - _Bucket* _M_buckets; + __bucket_type* _M_buckets; size_type _M_bucket_count; - _BaseNode _M_before_begin; + __node_base _M_before_begin; size_type _M_element_count; _RehashPolicy _M_rehash_policy; template<typename... _Args> - _Node* + __node_type* _M_allocate_node(_Args&&... __args); void - _M_deallocate_node(_Node* __n); + _M_deallocate_node(__node_type* __n); // Deallocate the linked list of nodes pointed to by __n void - _M_deallocate_nodes(_Node* __n); + _M_deallocate_nodes(__node_type* __n); - _Bucket* + __bucket_type* _M_allocate_buckets(size_type __n); void - _M_deallocate_buckets(_Bucket*, size_type __n); + _M_deallocate_buckets(__bucket_type*, size_type __n); // Gets bucket begin, deals with the fact that non-empty buckets contain // their before begin node. - _Node* + __node_type* _M_bucket_begin(size_type __bkt) const; - _Node* + __node_type* _M_begin() const - { return static_cast<_Node*>(_M_before_begin._M_nxt); } + { return static_cast<__node_type*>(_M_before_begin._M_nxt); } public: // Constructor, destructor, assignment, swap @@ -305,6 +357,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hashtable(_Hashtable&&); + // Use delegating construtors. + explicit + _Hashtable(size_type __n = 10, + const _H1& __hf = _H1(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Hashtable(__n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + __key_extract(), __a) + { } + + template<typename _InputIterator> + _Hashtable(_InputIterator __f, _InputIterator __l, + size_type __n = 0, + const _H1& __hf = _H1(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Hashtable(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + __key_extract(), __a) + { } + + _Hashtable(initializer_list<value_type> __l, + size_type __n = 0, + const _H1& __hf = _H1(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Hashtable(__l.begin(), __l.end(), __n, __hf, + __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + __key_extract(), __a) + { } + _Hashtable& operator=(const _Hashtable& __ht) { @@ -323,6 +408,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return *this; } + _Hashtable& + operator=(initializer_list<value_type> __l) + { + this->clear(); + this->insert(__l.begin(), __l.end()); + return *this; + } + ~_Hashtable() noexcept; void swap(_Hashtable&); @@ -394,8 +487,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION local_iterator begin(size_type __n) - { return local_iterator(_M_bucket_begin(__n), __n, - _M_bucket_count); } + { return local_iterator(_M_bucket_begin(__n), __n, _M_bucket_count); } local_iterator end(size_type __n) @@ -428,8 +520,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // max_load_factor, if present, comes from _Rehash_base. - // Generalization of max_load_factor. Extension, not found in TR1. Only - // useful if _RehashPolicy is something other than the default. + // Generalization of max_load_factor. Extension, not found in + // TR1. Only useful if _RehashPolicy is something other than + // the default. const _RehashPolicy& __rehash_policy() const { return _M_rehash_policy; } @@ -453,63 +546,49 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const; - private: + protected: // Bucket index computation helpers. size_type - _M_bucket_index(_Node* __n) const - { return _HCBase::_M_bucket_index(__n, _M_bucket_count); } + _M_bucket_index(__node_type* __n) const + { return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); } size_type - _M_bucket_index(const key_type& __k, - typename _Hashtable::_Hash_code_type __c) const - { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); } + _M_bucket_index(const key_type& __k, __hash_code __c) const + { return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); } // Find and insert helper functions and types // Find the node before the one matching the criteria. - _BaseNode* - _M_find_before_node(size_type, const key_type&, - typename _Hashtable::_Hash_code_type) const; + __node_base* + _M_find_before_node(size_type, const key_type&, __hash_code) const; - _Node* + __node_type* _M_find_node(size_type __bkt, const key_type& __key, - typename _Hashtable::_Hash_code_type __c) const + __hash_code __c) const { - _BaseNode* __before_n = _M_find_before_node(__bkt, __key, __c); + __node_base* __before_n = _M_find_before_node(__bkt, __key, __c); if (__before_n) - return static_cast<_Node*>(__before_n->_M_nxt); + return static_cast<__node_type*>(__before_n->_M_nxt); return nullptr; } // Insert a node at the beginning of a bucket. void - _M_insert_bucket_begin(size_type, _Node*); + _M_insert_bucket_begin(size_type, __node_type*); // Remove the bucket first node void - _M_remove_bucket_begin(size_type __bkt, _Node* __next_n, + _M_remove_bucket_begin(size_type __bkt, __node_type* __next_n, size_type __next_bkt); // Get the node before __n in the bucket __bkt - _BaseNode* - _M_get_previous_node(size_type __bkt, _BaseNode* __n); + __node_base* + _M_get_previous_node(size_type __bkt, __node_base* __n); template<typename _Arg> iterator - _M_insert_bucket(_Arg&&, size_type, - typename _Hashtable::_Hash_code_type); + _M_insert_bucket(_Arg&&, size_type, __hash_code); - typedef typename std::conditional<__unique_keys, - std::pair<iterator, bool>, - iterator>::type - _Insert_Return_Type; - typedef typename std::conditional<__unique_keys, - std::_Select1st<_Insert_Return_Type>, - std::_Identity<_Insert_Return_Type> - >::type - _Insert_Conv_Type; - - protected: template<typename... _Args> std::pair<iterator, bool> _M_emplace(std::true_type, _Args&&... __args); @@ -527,51 +606,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_insert(_Arg&&, std::false_type); public: - // Emplace, insert and erase + // Emplace template<typename... _Args> - _Insert_Return_Type + __ireturn_type emplace(_Args&&... __args) - { return _M_emplace(integral_constant<bool, __unique_keys>(), - std::forward<_Args>(__args)...); } + { return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); } template<typename... _Args> iterator emplace_hint(const_iterator, _Args&&... __args) - { return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); } + { return __iconv_type()(emplace(std::forward<_Args>(__args)...)); } - _Insert_Return_Type - insert(const value_type& __v) - { return _M_insert(__v, integral_constant<bool, __unique_keys>()); } - - iterator - insert(const_iterator, const value_type& __v) - { return _Insert_Conv_Type()(insert(__v)); } - - template<typename _Pair, typename = typename - std::enable_if<__and_<integral_constant<bool, !__constant_iterators>, - std::is_convertible<_Pair, - value_type>>::value>::type> - _Insert_Return_Type - insert(_Pair&& __v) - { return _M_insert(std::forward<_Pair>(__v), - integral_constant<bool, __unique_keys>()); } - - template<typename _Pair, typename = typename - std::enable_if<__and_<integral_constant<bool, !__constant_iterators>, - std::is_convertible<_Pair, - value_type>>::value>::type> - iterator - insert(const_iterator, _Pair&& __v) - { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); } - - template<typename _InputIterator> - void - insert(_InputIterator __first, _InputIterator __last); - - void - insert(initializer_list<value_type> __l) - { this->insert(__l.begin(), __l.end()); } + // Insert member functions via inheritance. + // Erase iterator erase(const_iterator); @@ -602,26 +650,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Helper rehash method used when keys can be non-unique. void _M_rehash_aux(size_type __n, std::false_type); - // Unconditionally change size of bucket array to n, restore hash policy - // state to __state on exception. - void _M_rehash(size_type __n, const _RehashPolicyState& __state); + // Unconditionally change size of bucket array to n, restore + // hash policy state to __state on exception. + void _M_rehash(size_type __n, const __rehash_state& __state); }; // Definitions of class template _Hashtable's out-of-line member functions. template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> template<typename... _Args> - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::_Node* - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>::__node_type* + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_allocate_node(_Args&&... __args) { - _Node* __n = _M_node_allocator.allocate(1); + __node_type* __n = _M_node_allocator.allocate(1); __try { _M_node_allocator.construct(__n, std::forward<_Args>(__args)...); @@ -635,125 +682,122 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_deallocate_node(_Node* __n) + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_deallocate_node(__node_type* __n) { _M_node_allocator.destroy(__n); _M_node_allocator.deallocate(__n, 1); } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_deallocate_nodes(_Node* __n) + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_deallocate_nodes(__node_type* __n) { while (__n) { - _Node* __tmp = __n; + __node_type* __tmp = __n; __n = __n->_M_next(); _M_deallocate_node(__tmp); } } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::_Bucket* - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>::__bucket_type* + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_allocate_buckets(size_type __n) { _Bucket_allocator_type __alloc(_M_node_allocator); - _Bucket* __p = __alloc.allocate(__n); - __builtin_memset(__p, 0, __n * sizeof(_Bucket)); + __bucket_type* __p = __alloc.allocate(__n); + __builtin_memset(__p, 0, __n * sizeof(__bucket_type)); return __p; } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_deallocate_buckets(_Bucket* __p, size_type __n) + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_deallocate_buckets(__bucket_type* __p, size_type __n) { _Bucket_allocator_type __alloc(_M_node_allocator); __alloc.deallocate(__p, __n); } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::_Node* - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::__node_type* + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_bucket_begin(size_type __bkt) const { - _BaseNode* __n = _M_buckets[__bkt]; - return __n ? static_cast<_Node*>(__n->_M_nxt) : nullptr; + __node_base* __n = _M_buckets[__bkt]; + return __n ? static_cast<__node_type*>(__n->_M_nxt) : nullptr; } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + typename _Traits> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _Hashtable(size_type __bucket_hint, const _H1& __h1, const _H2& __h2, const _Hash& __h, const _Equal& __eq, const _ExtractKey& __exk, const allocator_type& __a) - : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), - __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, - _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h, - __eq), - __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), + : __hashtable_base(__exk, __h1, __h2, __h, __eq), + __map_base(), + __rehash_base(), _M_node_allocator(__a), _M_bucket_count(0), _M_element_count(0), _M_rehash_policy() { _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); - // We don't want the rehash policy to ask for the hashtable to shrink - // on the first insertion so we need to reset its previous resize level. + + // We don't want the rehash policy to ask for the hashtable to + // shrink on the first insertion so we need to reset its + // previous resize level. _M_rehash_policy._M_prev_resize = 0; _M_buckets = _M_allocate_buckets(_M_bucket_count); } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> template<typename _InputIterator> - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _Hashtable(_InputIterator __f, _InputIterator __l, size_type __bucket_hint, const _H1& __h1, const _H2& __h2, const _Hash& __h, const _Equal& __eq, const _ExtractKey& __exk, const allocator_type& __a) - : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), - __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, - _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h, - __eq), - __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), + : __hashtable_base(__exk, __h1, __h2, __h, __eq), + __map_base(), + __rehash_base(), _M_node_allocator(__a), _M_bucket_count(0), _M_element_count(0), @@ -764,9 +808,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_bkt_for_elements(__detail:: __distance_fw(__f, __l))); - // We don't want the rehash policy to ask for the hashtable to shrink - // on the first insertion so we need to reset its previous resize - // level. + + // We don't want the rehash policy to ask for the hashtable to + // shrink on the first insertion so we need to reset its + // previous resize level. _M_rehash_policy._M_prev_resize = 0; _M_buckets = _M_allocate_buckets(_M_bucket_count); __try @@ -783,16 +828,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + typename _Traits> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _Hashtable(const _Hashtable& __ht) - : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), - __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, - _H1, _H2, _Hash, __chc>(__ht), - __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), + : __hashtable_base(__ht), + __map_base(__ht), + __rehash_base(__ht), _M_node_allocator(__ht._M_node_allocator), _M_bucket_count(__ht._M_bucket_count), _M_element_count(__ht._M_element_count), @@ -806,14 +850,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // First deal with the special first node pointed to by // _M_before_begin. - const _Node* __ht_n = __ht._M_begin(); - _Node* __this_n = _M_allocate_node(__ht_n->_M_v); + const __node_type* __ht_n = __ht._M_begin(); + __node_type* __this_n = _M_allocate_node(__ht_n->_M_v); this->_M_copy_code(__this_n, __ht_n); _M_before_begin._M_nxt = __this_n; _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin; // Then deal with other nodes. - _BaseNode* __prev_n = __this_n; + __node_base* __prev_n = __this_n; for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next()) { __this_n = _M_allocate_node(__ht_n->_M_v); @@ -834,16 +878,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + typename _Traits> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _Hashtable(_Hashtable&& __ht) - : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), - __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, - _H1, _H2, _Hash, __chc>(__ht), - __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), + : __hashtable_base(__ht), + __map_base(__ht), + __rehash_base(__ht), _M_node_allocator(std::move(__ht._M_node_allocator)), _M_buckets(__ht._M_buckets), _M_bucket_count(__ht._M_bucket_count), @@ -862,11 +905,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + typename _Traits> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: ~_Hashtable() noexcept { clear(); @@ -874,17 +917,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: swap(_Hashtable& __x) { - // The only base class with member variables is hash_code_base. We - // define _Hash_code_base::_M_swap because different specializations - // have different members. + // The only base class with member variables is hash_code_base. + // We define _Hash_code_base::_M_swap because different + // specializations have different members. this->_M_swap(__x); // _GLIBCXX_RESOLVE_LIB_DEFECTS @@ -897,8 +940,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::swap(_M_bucket_count, __x._M_bucket_count); std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt); std::swap(_M_element_count, __x._M_element_count); - // Fix buckets containing the _M_before_begin pointers that can't be - // swapped. + + // Fix buckets containing the _M_before_begin pointers that + // can't be swapped. if (_M_begin()) _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin; if (__x._M_begin()) @@ -907,12 +951,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: __rehash_policy(const _RehashPolicy& __pol) { size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); @@ -922,53 +966,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: find(const key_type& __k) { - typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); - _Node* __p = _M_find_node(__n, __k, __code); + __node_type* __p = _M_find_node(__n, __k, __code); return __p ? iterator(__p) : this->end(); } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::const_iterator - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::const_iterator + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: find(const key_type& __k) const { - typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); - _Node* __p = _M_find_node(__n, __k, __code); + __node_type* __p = _M_find_node(__n, __k, __code); return __p ? const_iterator(__p) : this->end(); } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::size_type - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::size_type + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: count(const key_type& __k) const { - typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); - _Node* __p = _M_bucket_begin(__n); + __node_type* __p = _M_bucket_begin(__n); if (!__p) return 0; @@ -978,9 +1022,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (this->_M_equals(__k, __code, __p)) ++__result; else if (__result) - // All equivalent values are next to each other, if we found a not - // equivalent value after an equivalent one it means that we won't - // find anymore an equivalent value. + // All equivalent values are next to each other, if we + // found a not equivalent value after an equivalent one it + // means that we won't find anymore an equivalent value. break; if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n) break; @@ -989,28 +1033,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - std::pair<typename _Hashtable<_Key, _Value, _Allocator, + typename _Traits> + std::pair<typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator, - typename _Hashtable<_Key, _Value, _Allocator, + _Traits>::iterator, + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator> - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: equal_range(const key_type& __k) { - typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); - _Node* __p = _M_find_node(__n, __k, __code); + __node_type* __p = _M_find_node(__n, __k, __code); if (__p) { - _Node* __p1 = __p->_M_next(); + __node_type* __p1 = __p->_M_next(); while (__p1 && _M_bucket_index(__p1) == __n && this->_M_equals(__k, __code, __p1)) __p1 = __p1->_M_next(); @@ -1022,28 +1066,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - std::pair<typename _Hashtable<_Key, _Value, _Allocator, + typename _Traits> + std::pair<typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::const_iterator, - typename _Hashtable<_Key, _Value, _Allocator, + _Traits>::const_iterator, + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::const_iterator> - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::const_iterator> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: equal_range(const key_type& __k) const { - typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + __hash_code __code = this->_M_hash_code(__k); std::size_t __n = _M_bucket_index(__k, __code); - _Node* __p = _M_find_node(__n, __k, __code); + __node_type* __p = _M_find_node(__n, __k, __code); if (__p) { - _Node* __p1 = __p->_M_next(); + __node_type* __p1 = __p->_M_next(); while (__p1 && _M_bucket_index(__p1) == __n && this->_M_equals(__k, __code, __p1)) __p1 = __p1->_M_next(); @@ -1054,24 +1098,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return std::make_pair(this->end(), this->end()); } - // Find the node whose key compares equal to k in the bucket n. Return nullptr - // if no node is found. + // Find the node whose key compares equal to k in the bucket n. + // Return nullptr if no node is found. template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::_BaseNode* - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::__node_base* + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_find_before_node(size_type __n, const key_type& __k, - typename _Hashtable::_Hash_code_type __code) const + __hash_code __code) const { - _BaseNode* __prev_p = _M_buckets[__n]; + __node_base* __prev_p = _M_buckets[__n]; if (!__prev_p) return nullptr; - _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt); + __node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt); for (;; __p = __p->_M_next()) { if (this->_M_equals(__k, __code, __p)) @@ -1084,44 +1128,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_insert_bucket_begin(size_type __bkt, _Node* __new_node) + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_insert_bucket_begin(size_type __bkt, __node_type* __node) { if (_M_buckets[__bkt]) { - // Bucket is not empty, we just need to insert the new node after the - // bucket before begin. - __new_node->_M_nxt = _M_buckets[__bkt]->_M_nxt; - _M_buckets[__bkt]->_M_nxt = __new_node; + // Bucket is not empty, we just need to insert the new node + // after the bucket before begin. + __node->_M_nxt = _M_buckets[__bkt]->_M_nxt; + _M_buckets[__bkt]->_M_nxt = __node; } else { - // The bucket is empty, the new node is inserted at the beginning of - // the singly linked list and the bucket will contain _M_before_begin - // pointer. - __new_node->_M_nxt = _M_before_begin._M_nxt; - _M_before_begin._M_nxt = __new_node; - if (__new_node->_M_nxt) + // The bucket is empty, the new node is inserted at the + // beginning of the singly linked list and the bucket will + // contain _M_before_begin pointer. + __node->_M_nxt = _M_before_begin._M_nxt; + _M_before_begin._M_nxt = __node; + if (__node->_M_nxt) // We must update former begin bucket that is pointing to // _M_before_begin. - _M_buckets[_M_bucket_index(__new_node->_M_next())] = __new_node; + _M_buckets[_M_bucket_index(__node->_M_next())] = __node; _M_buckets[__bkt] = &_M_before_begin; } } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_remove_bucket_begin(size_type __bkt, _Node* __next, size_type __next_bkt) + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_remove_bucket_begin(size_type __bkt, __node_type* __next, + size_type __next_bkt) { if (!__next || __next_bkt != __bkt) { @@ -1129,6 +1174,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // First update next bucket if any if (__next) _M_buckets[__next_bkt] = _M_buckets[__bkt]; + // Second update before begin node if necessary if (&_M_before_begin == _M_buckets[__bkt]) _M_before_begin._M_nxt = __next; @@ -1137,54 +1183,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::_BaseNode* - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_get_previous_node(size_type __bkt, _BaseNode* __n) + _Traits>::__node_base* + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_get_previous_node(size_type __bkt, __node_base* __n) { - _BaseNode* __prev_n = _M_buckets[__bkt]; + __node_base* __prev_n = _M_buckets[__bkt]; while (__prev_n->_M_nxt != __n) __prev_n = __prev_n->_M_nxt; return __prev_n; } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> template<typename... _Args> - std::pair<typename _Hashtable<_Key, _Value, _Allocator, + std::pair<typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator, bool> - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator, bool> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_emplace(std::true_type, _Args&&... __args) { // First build the node to get access to the hash code - _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...); + __node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...); __try { - const key_type& __k = this->_M_extract()(__new_node->_M_v); - typename _Hashtable::_Hash_code_type __code - = this->_M_hash_code(__k); + const key_type& __k = this->_M_extract()(__node->_M_v); + __hash_code __code = this->_M_hash_code(__k); size_type __bkt = _M_bucket_index(__k, __code); - if (_Node* __p = _M_find_node(__bkt, __k, __code)) + if (__node_type* __p = _M_find_node(__bkt, __k, __code)) { // There is already an equivalent node, no insertion - _M_deallocate_node(__new_node); + _M_deallocate_node(__node); return std::make_pair(iterator(__p), false); } // We are going to insert this node - this->_M_store_code(__new_node, __code); - const _RehashPolicyState& __saved_state + this->_M_store_code(__node, __code); + const __rehash_state& __saved_state = _M_rehash_policy._M_state(); std::pair<bool, std::size_t> __do_rehash = _M_rehash_policy._M_need_rehash(_M_bucket_count, @@ -1196,42 +1241,41 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __bkt = _M_bucket_index(__k, __code); } - _M_insert_bucket_begin(__bkt, __new_node); + _M_insert_bucket_begin(__bkt, __node); ++_M_element_count; - return std::make_pair(iterator(__new_node), true); + return std::make_pair(iterator(__node), true); } __catch(...) { - _M_deallocate_node(__new_node); + _M_deallocate_node(__node); __throw_exception_again; } } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> template<typename... _Args> - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_emplace(std::false_type, _Args&&... __args) { - const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); + const __rehash_state& __saved_state = _M_rehash_policy._M_state(); std::pair<bool, std::size_t> __do_rehash = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); // First build the node to get its hash code. - _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...); + __node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...); __try { - const key_type& __k = this->_M_extract()(__new_node->_M_v); - typename _Hashtable::_Hash_code_type __code - = this->_M_hash_code(__k); - this->_M_store_code(__new_node, __code); + const key_type& __k = this->_M_extract()(__node->_M_v); + __hash_code __code = this->_M_hash_code(__k); + this->_M_store_code(__node, __code); // Second, do rehash if necessary. if (__do_rehash.first) @@ -1239,44 +1283,44 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Third, find the node before an equivalent one. size_type __bkt = _M_bucket_index(__k, __code); - _BaseNode* __prev = _M_find_before_node(__bkt, __k, __code); - + __node_base* __prev = _M_find_before_node(__bkt, __k, __code); + if (__prev) { // Insert after the node before the equivalent one. - __new_node->_M_nxt = __prev->_M_nxt; - __prev->_M_nxt = __new_node; + __node->_M_nxt = __prev->_M_nxt; + __prev->_M_nxt = __node; } else - // The inserted node has no equivalent in the hashtable. We must - // insert the new node at the beginning of the bucket to preserve - // equivalent elements relative positions. - _M_insert_bucket_begin(__bkt, __new_node); + // The inserted node has no equivalent in the + // hashtable. We must insert the new node at the + // beginning of the bucket to preserve equivalent + // elements relative positions. + _M_insert_bucket_begin(__bkt, __node); ++_M_element_count; - return iterator(__new_node); + return iterator(__node); } __catch(...) { - _M_deallocate_node(__new_node); + _M_deallocate_node(__node); __throw_exception_again; } } // Insert v in bucket n (assumes no element with its key already present). template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> template<typename _Arg> - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_insert_bucket(_Arg&& __v, size_type __n, - typename _Hashtable::_Hash_code_type __code) + _Traits>::iterator + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_insert_bucket(_Arg&& __v, size_type __n, __hash_code __code) { - const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); + const __rehash_state& __saved_state = _M_rehash_policy._M_state(); std::pair<bool, std::size_t> __do_rehash = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); @@ -1284,52 +1328,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__do_rehash.first) { const key_type& __k = this->_M_extract()(__v); - __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second); + __n = __hash_code_base::_M_bucket_index(__k, __code, + __do_rehash.second); } - _Node* __new_node = nullptr; + __node_type* __node = nullptr; __try { // Allocate the new node before doing the rehash so that we // don't do a rehash if the allocation throws. - __new_node = _M_allocate_node(std::forward<_Arg>(__v)); - this->_M_store_code(__new_node, __code); + __node = _M_allocate_node(std::forward<_Arg>(__v)); + this->_M_store_code(__node, __code); if (__do_rehash.first) _M_rehash(__do_rehash.second, __saved_state); - _M_insert_bucket_begin(__n, __new_node); + _M_insert_bucket_begin(__n, __node); ++_M_element_count; - return iterator(__new_node); + return iterator(__node); } __catch(...) { - if (!__new_node) + if (!__node) _M_rehash_policy._M_reset(__saved_state); else - _M_deallocate_node(__new_node); + _M_deallocate_node(__node); __throw_exception_again; } } // Insert v if no element with its key is already present. template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> template<typename _Arg> - std::pair<typename _Hashtable<_Key, _Value, _Allocator, + std::pair<typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator, bool> - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator, bool> + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_insert(_Arg&& __v, std::true_type) { const key_type& __k = this->_M_extract()(__v); - typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + __hash_code __code = this->_M_hash_code(__k); size_type __n = _M_bucket_index(__k, __code); - if (_Node* __p = _M_find_node(__n, __k, __code)) + if (__node_type* __p = _M_find_node(__n, __k, __code)) return std::make_pair(iterator(__p), false); return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v), __n, __code), true); @@ -1337,103 +1382,84 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Insert v unconditionally. template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> template<typename _Arg> - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_insert(_Arg&& __v, std::false_type) { - const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); + const __rehash_state& __saved_state = _M_rehash_policy._M_state(); std::pair<bool, std::size_t> __do_rehash = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); - // First compute the hash code so that we don't do anything if it throws. - typename _Hashtable::_Hash_code_type __code - = this->_M_hash_code(this->_M_extract()(__v)); + // First compute the hash code so that we don't do anything if + // it throws. + __hash_code __code = this->_M_hash_code(this->_M_extract()(__v)); - _Node* __new_node = nullptr; + __node_type* __node = nullptr; __try { // Second allocate new node so that we don't rehash if it throws. - __new_node = _M_allocate_node(std::forward<_Arg>(__v)); - this->_M_store_code(__new_node, __code); + __node = _M_allocate_node(std::forward<_Arg>(__v)); + this->_M_store_code(__node, __code); if (__do_rehash.first) _M_rehash(__do_rehash.second, __saved_state); // Third, find the node before an equivalent one. - size_type __bkt = _M_bucket_index(__new_node); - _BaseNode* __prev - = _M_find_before_node(__bkt, this->_M_extract()(__new_node->_M_v), + size_type __bkt = _M_bucket_index(__node); + __node_base* __prev + = _M_find_before_node(__bkt, this->_M_extract()(__node->_M_v), __code); if (__prev) { // Insert after the node before the equivalent one. - __new_node->_M_nxt = __prev->_M_nxt; - __prev->_M_nxt = __new_node; + __node->_M_nxt = __prev->_M_nxt; + __prev->_M_nxt = __node; } else - // The inserted node has no equivalent in the hashtable. We must - // insert the new node at the beginning of the bucket to preserve - // equivalent elements relative positions. - _M_insert_bucket_begin(__bkt, __new_node); + // The inserted node has no equivalent in the + // hashtable. We must insert the new node at the + // beginning of the bucket to preserve equivalent + // elements relative positions. + _M_insert_bucket_begin(__bkt, __node); ++_M_element_count; - return iterator(__new_node); + return iterator(__node); } __catch(...) { - if (!__new_node) + if (!__node) _M_rehash_policy._M_reset(__saved_state); else - _M_deallocate_node(__new_node); + _M_deallocate_node(__node); __throw_exception_again; } } - template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - template<typename _InputIterator> - void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - insert(_InputIterator __first, _InputIterator __last) - { - size_type __n_elt = __detail::__distance_fw(__first, __last); - const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); - std::pair<bool, std::size_t> __do_rehash - = _M_rehash_policy._M_need_rehash(_M_bucket_count, - _M_element_count, __n_elt); - if (__do_rehash.first) - _M_rehash(__do_rehash.second, __saved_state); - - for (; __first != __last; ++__first) - this->insert(*__first); - } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: erase(const_iterator __it) { - _Node* __n = __it._M_cur; + __node_type* __n = __it._M_cur; std::size_t __bkt = _M_bucket_index(__n); - // Look for previous node to unlink it from the erased one, this is why - // we need buckets to contain the before begin to make this research fast. - _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n); + // Look for previous node to unlink it from the erased one, this + // is why we need buckets to contain the before begin to make + // this research fast. + __node_base* __prev_n = _M_get_previous_node(__bkt, __n); if (__n == _M_bucket_begin(__bkt)) _M_remove_bucket_begin(__bkt, __n->_M_next(), __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0); @@ -1453,34 +1479,36 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::size_type - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::size_type + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: erase(const key_type& __k) { - typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + __hash_code __code = this->_M_hash_code(__k); std::size_t __bkt = _M_bucket_index(__k, __code); + // Look for the node before the first matching node. - _BaseNode* __prev_n = _M_find_before_node(__bkt, __k, __code); + __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code); if (!__prev_n) return 0; - _Node* __n = static_cast<_Node*>(__prev_n->_M_nxt); + __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt); bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n; // We found a matching node, start deallocation loop from it std::size_t __next_bkt = __bkt; - _Node* __next_n = __n; + __node_type* __next_n = __n; size_type __result = 0; - _Node* __saved_n = nullptr; + __node_type* __saved_n = nullptr; do { - _Node* __p = __next_n; + __node_type* __p = __next_n; __next_n = __p->_M_next(); + // _GLIBCXX_RESOLVE_LIB_DEFECTS // 526. Is it undefined if a function in the standard changes // in parameters? @@ -1509,31 +1537,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> - typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + typename _Traits> + typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::iterator - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Traits>::iterator + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: erase(const_iterator __first, const_iterator __last) { - _Node* __n = __first._M_cur; - _Node* __last_n = __last._M_cur; + __node_type* __n = __first._M_cur; + __node_type* __last_n = __last._M_cur; if (__n == __last_n) return iterator(__n); std::size_t __bkt = _M_bucket_index(__n); - _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n); + __node_base* __prev_n = _M_get_previous_node(__bkt, __n); bool __is_bucket_begin = __n == _M_bucket_begin(__bkt); std::size_t __n_bkt = __bkt; for (;;) { do { - _Node* __tmp = __n; + __node_type* __tmp = __n; __n = __n->_M_next(); _M_deallocate_node(__tmp); --_M_element_count; @@ -1557,30 +1585,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: clear() noexcept { _M_deallocate_nodes(_M_begin()); - __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(_Bucket)); + __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(__bucket_type)); _M_element_count = 0; _M_before_begin._M_nxt = nullptr; } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: rehash(size_type __n) { - const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state(); + const __rehash_state& __saved_state = _M_rehash_policy._M_state(); _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n), _M_rehash_policy._M_bkt_for_elements(_M_element_count + 1)), @@ -1588,17 +1616,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_rehash(size_type __n, const _RehashPolicyState& __state) + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: + _M_rehash(size_type __n, const __rehash_state& __state) { __try { - _M_rehash_aux(__n, integral_constant<bool, __uk>()); + _M_rehash_aux(__n, __unique_keys()); } __catch(...) { @@ -1611,22 +1639,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Rehash when there is no equivalent elements. template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_rehash_aux(size_type __n, std::true_type) { - _Bucket* __new_buckets = _M_allocate_buckets(__n); - _Node* __p = _M_begin(); + __bucket_type* __new_buckets = _M_allocate_buckets(__n); + __node_type* __p = _M_begin(); _M_before_begin._M_nxt = nullptr; std::size_t __bbegin_bkt; while (__p) { - _Node* __next = __p->_M_next(); - std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n); + __node_type* __next = __p->_M_next(); + std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n); if (!__new_buckets[__bkt]) { __p->_M_nxt = _M_before_begin._M_nxt; @@ -1651,28 +1679,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Rehash when there can be equivalent elements, preserve their relative // order. template<typename _Key, typename _Value, - typename _Allocator, typename _ExtractKey, typename _Equal, + typename _Alloc, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, - bool __chc, bool __cit, bool __uk> + typename _Traits> void - _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, - _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>:: _M_rehash_aux(size_type __n, std::false_type) { - _Bucket* __new_buckets = _M_allocate_buckets(__n); + __bucket_type* __new_buckets = _M_allocate_buckets(__n); - _Node* __p = _M_begin(); + __node_type* __p = _M_begin(); _M_before_begin._M_nxt = nullptr; std::size_t __bbegin_bkt; std::size_t __prev_bkt; - _Node* __prev_p = nullptr; + __node_type* __prev_p = nullptr; bool __check_bucket = false; while (__p) { bool __check_now = true; - _Node* __next = __p->_M_next(); - std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n); + __node_type* __next = __p->_M_next(); + std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n); if (!__new_buckets[__bkt]) { @@ -1707,7 +1735,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __new_buckets[__bkt]->_M_nxt = __p; } } - + if (__check_now && __check_bucket) { // Check if we shall update the next bucket because of insertions @@ -1715,7 +1743,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__prev_p->_M_nxt) { std::size_t __next_bkt - = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n); + = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), + __n); if (__next_bkt != __prev_bkt) __new_buckets[__next_bkt] = __prev_p; } @@ -1729,7 +1758,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (__check_bucket && __prev_p->_M_nxt) { std::size_t __next_bkt - = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n); + = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n); if (__next_bkt != __prev_bkt) __new_buckets[__next_bkt] = __prev_p; } diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index b585d23a970..160a6ce1724 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -33,10 +33,26 @@ namespace std _GLIBCXX_VISIBILITY(default) { + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> + class _Hashtable; + namespace __detail { _GLIBCXX_BEGIN_NAMESPACE_VERSION + /** + * @defgroup hashtable-detail Base and Implementation Classes + * @ingroup unordered_associative_containers + * @{ + */ + template<typename _Key, typename _Value, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _Traits> + struct _Hashtable_base; + // Helper function: return distance(first, last) for forward // iterators, or 0 for input iterators. template<class _Iterator> @@ -64,28 +80,68 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template <typename _Key, typename _Hash> struct __is_noexcept_hash : std::integral_constant<bool, noexcept(declval<const _Hash&>()(declval<const _Key&>()))> - {}; + { }; - // Auxiliary types used for all instantiations of _Hashtable: nodes + // Auxiliary types used for all instantiations of _Hashtable nodes // and iterators. - // Nodes, used to wrap elements stored in the hash table. A policy - // template parameter of class template _Hashtable controls whether - // nodes also store a hash code. In some cases (e.g. strings) this - // may be a performance win. + /** + * struct _Hashtable_traits + * + * Important traits for hash tables. + * + * @tparam __cache_hash_code Boolean value. True if the value of + * the hash function is stored along with the value. This is a + * time-space tradeoff. Storing it may improve lookup speed by + * reducing the number of times we need to call the _Equal + * function. + * + * @tparam __constant_iterators Boolean value. True if iterator and + * const_iterator are both constant iterator types. This is true + * for unordered_set and unordered_multiset, false for + * unordered_map and unordered_multimap. + * + * @tparam __unique_keys Boolean value. True if the return value + * of _Hashtable::count(k) is always at most one, false if it may + * be an arbitrary number. This true for unordered_set and + * unordered_map, false for unordered_multiset and + * unordered_multimap. + */ + template<bool _Cache_hash_code, bool _Constant_iterators, bool _Unique_keys> + struct _Hashtable_traits + { + template<bool _Cond> + using __bool_constant = integral_constant<bool, _Cond>; + + using __hash_cached = __bool_constant<_Cache_hash_code>; + using __constant_iterators = __bool_constant<_Constant_iterators>; + using __unique_keys = __bool_constant<_Unique_keys>; + }; + + /** + * struct _Hash_node_base + * + * Nodes, used to wrap elements stored in the hash table. A policy + * template parameter of class template _Hashtable controls whether + * nodes also store a hash code. In some cases (e.g. strings) this + * may be a performance win. + */ struct _Hash_node_base { _Hash_node_base* _M_nxt; - _Hash_node_base() - : _M_nxt() { } - _Hash_node_base(_Hash_node_base* __next) - : _M_nxt(__next) { } + _Hash_node_base() : _M_nxt() { } + + _Hash_node_base(_Hash_node_base* __next) : _M_nxt(__next) { } }; - template<typename _Value, bool __cache_hash_code> + /** + * Primary template struct _Hash_node. + */ + template<typename _Value, bool _Cache_hash_code> struct _Hash_node; + /// Specialization. template<typename _Value> struct _Hash_node<_Value, true> : _Hash_node_base { @@ -96,10 +152,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hash_node(_Args&&... __args) : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { } - _Hash_node* _M_next() const - { return static_cast<_Hash_node*>(_M_nxt); } + _Hash_node* + _M_next() const { return static_cast<_Hash_node*>(_M_nxt); } }; + /// Specialization. template<typename _Value> struct _Hash_node<_Value, false> : _Hash_node_base { @@ -109,56 +166,64 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Hash_node(_Args&&... __args) : _M_v(std::forward<_Args>(__args)...) { } - _Hash_node* _M_next() const - { return static_cast<_Hash_node*>(_M_nxt); } + _Hash_node* + _M_next() const { return static_cast<_Hash_node*>(_M_nxt); } }; - // Node iterators, used to iterate through all the hashtable. - template<typename _Value, bool __cache> + /// Base class for node iterators. + template<typename _Value, bool _Cache_hash_code> struct _Node_iterator_base { - _Node_iterator_base(_Hash_node<_Value, __cache>* __p) + typedef _Hash_node<_Value, _Cache_hash_code> __node_type; + + __node_type* _M_cur; + + _Node_iterator_base(__node_type* __p) : _M_cur(__p) { } void _M_incr() { _M_cur = _M_cur->_M_next(); } - - _Hash_node<_Value, __cache>* _M_cur; }; - template<typename _Value, bool __cache> + template<typename _Value, bool _Cache_hash_code> inline bool - operator==(const _Node_iterator_base<_Value, __cache>& __x, - const _Node_iterator_base<_Value, __cache>& __y) + operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, + const _Node_iterator_base<_Value, _Cache_hash_code >& __y) { return __x._M_cur == __y._M_cur; } - template<typename _Value, bool __cache> + template<typename _Value, bool _Cache_hash_code> inline bool - operator!=(const _Node_iterator_base<_Value, __cache>& __x, - const _Node_iterator_base<_Value, __cache>& __y) + operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x, + const _Node_iterator_base<_Value, _Cache_hash_code>& __y) { return __x._M_cur != __y._M_cur; } + /// Node iterators, used to iterate through all the hashtable. template<typename _Value, bool __constant_iterators, bool __cache> struct _Node_iterator : public _Node_iterator_base<_Value, __cache> { + private: + using __base_type = _Node_iterator_base<_Value, __cache>; + using __node_type = typename __base_type::__node_type; + + public: typedef _Value value_type; - typedef typename std::conditional<__constant_iterators, - const _Value*, _Value*>::type - pointer; - typedef typename std::conditional<__constant_iterators, - const _Value&, _Value&>::type - reference; typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; + using pointer = typename std::conditional<__constant_iterators, + const _Value*, _Value*>::type; + + using reference = typename std::conditional<__constant_iterators, + const _Value&, _Value&>::type; + _Node_iterator() - : _Node_iterator_base<_Value, __cache>(0) { } + : __base_type(0) { } explicit - _Node_iterator(_Hash_node<_Value, __cache>* __p) - : _Node_iterator_base<_Value, __cache>(__p) { } + _Node_iterator(__node_type* __p) + : __base_type(__p) { } reference operator*() const @@ -184,26 +249,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } }; + /// Node const_iterators, used to iterate through all the hashtable. template<typename _Value, bool __constant_iterators, bool __cache> struct _Node_const_iterator : public _Node_iterator_base<_Value, __cache> { + private: + using __base_type = _Node_iterator_base<_Value, __cache>; + using __node_type = typename __base_type::__node_type; + + public: typedef _Value value_type; - typedef const _Value* pointer; - typedef const _Value& reference; typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; + typedef const _Value* pointer; + typedef const _Value& reference; + _Node_const_iterator() - : _Node_iterator_base<_Value, __cache>(0) { } + : __base_type(0) { } explicit - _Node_const_iterator(_Hash_node<_Value, __cache>* __p) - : _Node_iterator_base<_Value, __cache>(__p) { } + _Node_const_iterator(__node_type* __p) + : __base_type(__p) { } _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, __cache>& __x) - : _Node_iterator_base<_Value, __cache>(__x._M_cur) { } + : __base_type(__x._M_cur) { } reference operator*() const @@ -232,8 +304,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Many of class template _Hashtable's template parameters are policy // classes. These are defaults for the policies. - // Default range hashing function: use division to fold a large number - // into the range [0, N). + /// Default range hashing function: use division to fold a large number + /// into the range [0, N). struct _Mod_range_hashing { typedef std::size_t first_argument_type; @@ -245,15 +317,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { return __num % __den; } }; - // Default ranged hash function H. In principle it should be a - // function object composed from objects of type H1 and H2 such that - // h(k, N) = h2(h1(k), N), but that would mean making extra copies of - // h1 and h2. So instead we'll just use a tag to tell class template - // hashtable to do that composition. + /// Default ranged hash function H. In principle it should be a + /// function object composed from objects of type H1 and H2 such that + /// h(k, N) = h2(h1(k), N), but that would mean making extra copies of + /// h1 and h2. So instead we'll just use a tag to tell class template + /// hashtable to do that composition. struct _Default_ranged_hash { }; - // Default value for rehash policy. Bucket size is (usually) the - // smallest prime that keeps the load factor small enough. + /// Default value for rehash policy. Bucket size is (usually) the + /// smallest prime that keeps the load factor small enough. struct _Prime_rehash_policy { _Prime_rehash_policy(float __z = 1.0) @@ -385,77 +457,116 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } // Base classes for std::_Hashtable. We define these base classes - // because in some cases we want to do different things depending - // on the value of a policy class. In some cases the policy class + // because in some cases we want to do different things depending on + // the value of a policy class. In some cases the policy class // affects which member functions and nested typedefs are defined; // we handle that by specializing base class templates. Several of // the base class templates need to access other members of class - // template _Hashtable, so we use the "curiously recurring template - // pattern" for them. - - // class template _Map_base. If the hashtable has a value type of - // the form pair<T1, T2> and a key extraction policy that returns the - // first part of the pair, the hashtable gets a mapped_type typedef. - // If it satisfies those criteria and also has unique keys, then it - // also gets an operator[]. - template<typename _Key, typename _Value, typename _Ex, bool __unique, - typename _Hashtable> + // template _Hashtable, so we use a variant of the "Curiously + // Recurring Template Pattern" (CRTP) technique. + + /** + * Primary class template _Map_base. + * + * If the hashtable has a value type of the form pair<T1, T2> and a + * key extraction policy (_ExtractKey) that returns the first part + * of the pair, the hashtable gets a mapped_type typedef. If it + * satisfies those criteria and also has unique keys, then it also + * gets an operator[]. + */ + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits, + bool _Unique_keys = _Traits::__unique_keys::value> struct _Map_base { }; - template<typename _Key, typename _Pair, typename _Hashtable> - struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable> + /// Partial specialization, __unique_keys set to false. + template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> + struct _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, false> { - typedef typename _Pair::second_type mapped_type; + using mapped_type = typename _Pair::second_type; }; - template<typename _Key, typename _Pair, typename _Hashtable> - struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable> + /// Partial specialization, __unique_keys set to true. + template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> + struct _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true> { - typedef typename _Pair::second_type mapped_type; + private: + using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair, + std::_Select1st<_Pair>, + _Equal, _H1, _H2, _Hash, + _Traits>; + + using __hashtable = _Hashtable<_Key, _Pair, _Alloc, + std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>; + + using __hash_code = typename __hashtable_base::__hash_code; + using __node_type = typename __hashtable_base::__node_type; + + public: + using key_type = typename __hashtable_base::key_type; + using iterator = typename __hashtable_base::iterator; + using mapped_type = typename _Pair::second_type; mapped_type& - operator[](const _Key& __k); + operator[](const key_type& __k); mapped_type& - operator[](_Key&& __k); + operator[](key_type&& __k); // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 761. unordered_map needs an at() member function. mapped_type& - at(const _Key& __k); + at(const key_type& __k); const mapped_type& - at(const _Key& __k) const; + at(const key_type& __k) const; }; - template<typename _Key, typename _Pair, typename _Hashtable> - typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, - true, _Hashtable>::mapped_type& - _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: - operator[](const _Key& __k) + template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> + typename _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true> + ::mapped_type& + _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: + operator[](const key_type& __k) { - _Hashtable* __h = static_cast<_Hashtable*>(this); - typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); + __hashtable* __h = static_cast<__hashtable*>(this); + __hash_code __code = __h->_M_hash_code(__k); std::size_t __n = __h->_M_bucket_index(__k, __code); + __node_type* __p = __h->_M_find_node(__n, __k, __code); - typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); if (!__p) return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), __n, __code)->second; return (__p->_M_v).second; } - template<typename _Key, typename _Pair, typename _Hashtable> - typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, - true, _Hashtable>::mapped_type& - _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: - operator[](_Key&& __k) + template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> + typename _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true> + ::mapped_type& + _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: + operator[](key_type&& __k) { - _Hashtable* __h = static_cast<_Hashtable*>(this); - typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); + __hashtable* __h = static_cast<__hashtable*>(this); + __hash_code __code = __h->_M_hash_code(__k); std::size_t __n = __h->_M_bucket_index(__k, __code); + __node_type* __p = __h->_M_find_node(__n, __k, __code); - typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); if (!__p) return __h->_M_insert_bucket(std::make_pair(std::move(__k), mapped_type()), @@ -463,79 +574,320 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return (__p->_M_v).second; } - template<typename _Key, typename _Pair, typename _Hashtable> - typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, - true, _Hashtable>::mapped_type& - _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: - at(const _Key& __k) + template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> + typename _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true> + ::mapped_type& + _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: + at(const key_type& __k) { - _Hashtable* __h = static_cast<_Hashtable*>(this); - typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); + __hashtable* __h = static_cast<__hashtable*>(this); + __hash_code __code = __h->_M_hash_code(__k); std::size_t __n = __h->_M_bucket_index(__k, __code); + __node_type* __p = __h->_M_find_node(__n, __k, __code); - typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); if (!__p) __throw_out_of_range(__N("_Map_base::at")); return (__p->_M_v).second; } - template<typename _Key, typename _Pair, typename _Hashtable> - const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, - true, _Hashtable>::mapped_type& - _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: - at(const _Key& __k) const + template<typename _Key, typename _Pair, typename _Alloc, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> + const typename _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, + _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true> + ::mapped_type& + _Map_base<_Key, _Pair, _Alloc, std::_Select1st<_Pair>, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: + at(const key_type& __k) const { - const _Hashtable* __h = static_cast<const _Hashtable*>(this); - typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); + const __hashtable* __h = static_cast<const __hashtable*>(this); + __hash_code __code = __h->_M_hash_code(__k); std::size_t __n = __h->_M_bucket_index(__k, __code); + __node_type* __p = __h->_M_find_node(__n, __k, __code); - typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code); if (!__p) __throw_out_of_range(__N("_Map_base::at")); return (__p->_M_v).second; } - // class template _Rehash_base. Give hashtable the max_load_factor - // functions and reserve iff the rehash policy is _Prime_rehash_policy. - template<typename _RehashPolicy, typename _Hashtable> - struct _Rehash_base { }; + /** + * Primary class template _Insert_base. + * + * insert member functions appropriate to all _Hashtables. + */ + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> + struct _Insert_base + { + using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits>; + + using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _Traits>; + + using value_type = typename __hashtable_base::value_type; + using iterator = typename __hashtable_base::iterator; + using const_iterator = typename __hashtable_base::const_iterator; + using size_type = typename __hashtable_base::size_type; + + using __unique_keys = typename __hashtable_base::__unique_keys; + using __ireturn_type = typename __hashtable_base::__ireturn_type; + using __iconv_type = typename __hashtable_base::__iconv_type; + + __hashtable& + _M_conjure_hashtable() + { return *(static_cast<__hashtable*>(this)); } + + __ireturn_type + insert(const value_type& __v) + { + __hashtable& __h = _M_conjure_hashtable(); + return __h._M_insert(__v, __unique_keys()); + } + + iterator + insert(const_iterator, const value_type& __v) + { return __iconv_type()(insert(__v)); } + + void + insert(initializer_list<value_type> __l) + { this->insert(__l.begin(), __l.end()); } + + template<typename _InputIterator> + void + insert(_InputIterator __first, _InputIterator __last); + }; + + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> + template<typename _InputIterator> + void + _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits>:: + insert(_InputIterator __first, _InputIterator __last) + { + using __rehash_type = typename __hashtable::__rehash_type; + using __rehash_state = typename __hashtable::__rehash_state; + using pair_type = std::pair<bool, std::size_t>; + + size_type __n_elt = __detail::__distance_fw(__first, __last); + + __hashtable& __h = _M_conjure_hashtable(); + __rehash_type& __rehash = __h._M_rehash_policy; + const __rehash_state& __saved_state = __rehash._M_state(); + pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count, + __h._M_element_count, + __n_elt); + + if (__do_rehash.first) + __h._M_rehash(__do_rehash.second, __saved_state); + + for (; __first != __last; ++__first) + this->insert(*__first); + } + + /** + * Primary class template _Insert. + * + * Select insert member functions appropriate to _Hashtable policy choices. + */ + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits, + bool _Constant_iterators = _Traits::__constant_iterators::value, + bool _Unique_keys = _Traits::__unique_keys::value> + struct _Insert; + + /// Specialization. + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> + struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits, true, true> + : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits> + { + using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits>; + using value_type = typename __base_type::value_type; + using iterator = typename __base_type::iterator; + using const_iterator = typename __base_type::const_iterator; + + using __unique_keys = typename __base_type::__unique_keys; + using __hashtable = typename __base_type::__hashtable; + + using __base_type::insert; - template<typename _Hashtable> - struct _Rehash_base<_Prime_rehash_policy, _Hashtable> + std::pair<iterator, bool> + insert(value_type&& __v) + { + __hashtable& __h = this->_M_conjure_hashtable(); + return __h._M_insert(std::move(__v), __unique_keys()); + } + + iterator + insert(const_iterator, value_type&& __v) + { return insert(std::move(__v)).first; } + }; + + /// Specialization. + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> + struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits, true, false> + : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits> { + using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits>; + using value_type = typename __base_type::value_type; + using iterator = typename __base_type::iterator; + using const_iterator = typename __base_type::const_iterator; + + using __unique_keys = typename __base_type::__unique_keys; + using __hashtable = typename __base_type::__hashtable; + + using __base_type::insert; + + iterator + insert(value_type&& __v) + { + __hashtable& __h = this->_M_conjure_hashtable(); + return __h._M_insert(std::move(__v), __unique_keys()); + } + + iterator + insert(const_iterator, value_type&& __v) + { return insert(std::move(__v)); } + }; + + /// Specialization. + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits, bool _Unique_keys> + struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits, false, _Unique_keys> + : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits> + { + using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, _Traits>; + using value_type = typename __base_type::value_type; + using iterator = typename __base_type::iterator; + using const_iterator = typename __base_type::const_iterator; + + using __unique_keys = typename __base_type::__unique_keys; + using __hashtable = typename __base_type::__hashtable; + using __ireturn_type = typename __base_type::__ireturn_type; + using __iconv_type = typename __base_type::__iconv_type; + + using __base_type::insert; + + template<typename _Pair> + using __is_convertible = std::is_convertible<_Pair, value_type>; + + template<typename _Pair> + using _IFconv = std::enable_if<__is_convertible<_Pair>::value>; + + template<typename _Pair> + using _IFconvp = typename _IFconv<_Pair>::type; + + template<typename _Pair, typename = _IFconvp<_Pair>> + __ireturn_type + insert(_Pair&& __v) + { + __hashtable& __h = this->_M_conjure_hashtable(); + return __h._M_insert(std::forward<_Pair>(__v), __unique_keys()); + } + + template<typename _Pair, typename = _IFconvp<_Pair>> + iterator + insert(const_iterator, _Pair&& __v) + { return __iconv_type()(insert(std::forward<_Pair>(__v))); } + }; + + /** + * Primary class template _Rehash_base. + * + * Give hashtable the max_load_factor functions and reserve iff the + * rehash policy is _Prime_rehash_policy. + */ + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> + struct _Rehash_base; + + /// Specialization. + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _Traits> + struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _Prime_rehash_policy, _Traits> + { + using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, + _Equal, _H1, _H2, _Hash, + _Prime_rehash_policy, _Traits>; + float max_load_factor() const noexcept { - const _Hashtable* __this = static_cast<const _Hashtable*>(this); + const __hashtable* __this = static_cast<const __hashtable*>(this); return __this->__rehash_policy().max_load_factor(); } void max_load_factor(float __z) { - _Hashtable* __this = static_cast<_Hashtable*>(this); + __hashtable* __this = static_cast<__hashtable*>(this); __this->__rehash_policy(_Prime_rehash_policy(__z)); } void reserve(std::size_t __n) { - _Hashtable* __this = static_cast<_Hashtable*>(this); + __hashtable* __this = static_cast<__hashtable*>(this); __this->rehash(__builtin_ceil(__n / max_load_factor())); } }; - // Helper class using EBO when it is not forbidden, type is not final, - // and when it worth it, type is empty. + /** + * Primary class template _Hashtable_ebo_helper. + * + * Helper class using EBO when it is not forbidden, type is not + * final, and when it worth it, type is empty. + */ template<int _Nm, typename _Tp, bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)> struct _Hashtable_ebo_helper; - // Specialization using EBO. + /// Specialization using EBO. template<int _Nm, typename _Tp> - struct _Hashtable_ebo_helper<_Nm, _Tp, true> : private _Tp + struct _Hashtable_ebo_helper<_Nm, _Tp, true> + // See PR53067. + : public _Tp { _Hashtable_ebo_helper() = default; + _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp) { } @@ -548,11 +900,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { return static_cast<_Tp&>(__eboh); } }; - // Specialization not using EBO. + /// Specialization not using EBO. template<int _Nm, typename _Tp> struct _Hashtable_ebo_helper<_Nm, _Tp, false> { _Hashtable_ebo_helper() = default; + _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp) { } @@ -568,70 +921,73 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Tp _M_tp; }; - // Class template _Hash_code_base. Encapsulates two policy issues that - // aren't quite orthogonal. - // (1) the difference between using a ranged hash function and using - // the combination of a hash function and a range-hashing function. - // In the former case we don't have such things as hash codes, so - // we have a dummy type as placeholder. - // (2) Whether or not we cache hash codes. Caching hash codes is - // meaningless if we have a ranged hash function. - // We also put the key extraction objects here, for convenience. - // - // Each specialization derives from one or more of the template parameters to - // benefit from Ebo. This is important as this type is inherited in some cases - // by the _Local_iterator_base type used to implement local_iterator and - // const_local_iterator. As with any iterator type we prefer to make it as - // small as possible. - - // Primary template: unused except as a hook for specializations. + /** + * Primary class template _Hash_code_base. + * + * Encapsulates two policy issues that aren't quite orthogonal. + * (1) the difference between using a ranged hash function and using + * the combination of a hash function and a range-hashing function. + * In the former case we don't have such things as hash codes, so + * we have a dummy type as placeholder. + * (2) Whether or not we cache hash codes. Caching hash codes is + * meaningless if we have a ranged hash function. + * + * We also put the key extraction objects here, for convenience. + * Each specialization derives from one or more of the template + * parameters to benefit from Ebo. This is important as this type + * is inherited in some cases by the _Local_iterator_base type used + * to implement local_iterator and const_local_iterator. As with + * any iterator type we prefer to make it as small as possible. + * + * Primary template is unused except as a hook for specializations. + */ template<typename _Key, typename _Value, typename _ExtractKey, typename _H1, typename _H2, typename _Hash, bool __cache_hash_code> struct _Hash_code_base; - // Specialization: ranged hash function, no caching hash codes. H1 - // and H2 are provided but ignored. We define a dummy hash code type. - template<typename _Key, typename _Value, typename _ExtractKey, + /// Specialization: ranged hash function, no caching hash codes. H1 + /// and H2 are provided but ignored. We define a dummy hash code type. + template<typename _Key, typename _Value, typename _ExtractKey, typename _H1, typename _H2, typename _Hash> struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false> - : private _Hashtable_ebo_helper<0, _ExtractKey>, - private _Hashtable_ebo_helper<1, _Hash> + // See PR53067. + : public _Hashtable_ebo_helper<0, _ExtractKey>, + public _Hashtable_ebo_helper<1, _Hash> { private: - typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; - typedef _Hashtable_ebo_helper<1, _Hash> _EboHash; + typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; + typedef _Hashtable_ebo_helper<1, _Hash> _EboHash; protected: + typedef void* __hash_code; + typedef _Hash_node<_Value, false> __node_type; + // We need the default constructor for the local iterators. _Hash_code_base() = default; - _Hash_code_base(const _ExtractKey& __ex, - const _H1&, const _H2&, const _Hash& __h) - : _EboExtractKey(__ex), _EboHash(__h) { } - typedef void* _Hash_code_type; + _Hash_code_base(const _ExtractKey& __ex, const _H1&, const _H2&, + const _Hash& __h) + : _EboExtractKey(__ex), _EboHash(__h) { } - _Hash_code_type + __hash_code _M_hash_code(const _Key& __key) const { return 0; } std::size_t - _M_bucket_index(const _Key& __k, _Hash_code_type, - std::size_t __n) const + _M_bucket_index(const _Key& __k, __hash_code, std::size_t __n) const { return _M_ranged_hash()(__k, __n); } std::size_t - _M_bucket_index(const _Hash_node<_Value, false>* __p, - std::size_t __n) const + _M_bucket_index(const __node_type* __p, std::size_t __n) const { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); } void - _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const + _M_store_code(__node_type*, __hash_code) const { } void - _M_copy_code(_Hash_node<_Value, false>*, - const _Hash_node<_Value, false>*) const + _M_copy_code(__node_type*, const __node_type*) const { } void @@ -644,10 +1000,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION protected: const _ExtractKey& _M_extract() const { return _EboExtractKey::_S_cget(*this); } + _ExtractKey& _M_extract() { return _EboExtractKey::_S_get(*this); } + const _Hash& _M_ranged_hash() const { return _EboHash::_S_cget(*this); } + _Hash& _M_ranged_hash() { return _EboHash::_S_get(*this); } }; @@ -655,67 +1014,68 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // No specialization for ranged hash function while caching hash codes. // That combination is meaningless, and trying to do it is an error. - // Specialization: ranged hash function, cache hash codes. This - // combination is meaningless, so we provide only a declaration - // and no definition. + /// Specialization: ranged hash function, cache hash codes. This + /// combination is meaningless, so we provide only a declaration + /// and no definition. template<typename _Key, typename _Value, typename _ExtractKey, typename _H1, typename _H2, typename _Hash> struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>; - // Specialization: hash function and range-hashing function, no - // caching of hash codes. - // Provides typedef and accessor required by TR1. + /// Specialization: hash function and range-hashing function, no + /// caching of hash codes. + /// Provides typedef and accessor required by TR1. template<typename _Key, typename _Value, typename _ExtractKey, typename _H1, typename _H2> struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Default_ranged_hash, false> - : private _Hashtable_ebo_helper<0, _ExtractKey>, - private _Hashtable_ebo_helper<1, _H1>, - private _Hashtable_ebo_helper<2, _H2> + // See PR53067. + : public _Hashtable_ebo_helper<0, _ExtractKey>, + public _Hashtable_ebo_helper<1, _H1>, + public _Hashtable_ebo_helper<2, _H2> { private: - typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; - typedef _Hashtable_ebo_helper<1, _H1> _EboH1; - typedef _Hashtable_ebo_helper<2, _H2> _EboH2; + typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; + typedef _Hashtable_ebo_helper<1, _H1> _EboH1; + typedef _Hashtable_ebo_helper<2, _H2> _EboH2; public: - typedef _H1 hasher; + typedef _H1 hasher; hasher hash_function() const { return _M_h1(); } + typedef std::size_t __hash_code; + typedef _Hash_node<_Value, false> __node_type; + protected: // We need the default constructor for the local iterators. _Hash_code_base() = default; + _Hash_code_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2, const _Default_ranged_hash&) : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { } - typedef std::size_t _Hash_code_type; - - _Hash_code_type + __hash_code _M_hash_code(const _Key& __k) const { return _M_h1()(__k); } std::size_t - _M_bucket_index(const _Key&, _Hash_code_type __c, - std::size_t __n) const + _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const { return _M_h2()(__c, __n); } std::size_t - _M_bucket_index(const _Hash_node<_Value, false>* __p, + _M_bucket_index(const __node_type* __p, std::size_t __n) const { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); } void - _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const + _M_store_code(__node_type*, __hash_code) const { } void - _M_copy_code(_Hash_node<_Value, false>*, - const _Hash_node<_Value, false>*) const + _M_copy_code(__node_type*, const __node_type*) const { } void @@ -726,73 +1086,77 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::swap(_M_h2(), __x._M_h2()); } - protected: const _ExtractKey& _M_extract() const { return _EboExtractKey::_S_cget(*this); } + _ExtractKey& _M_extract() { return _EboExtractKey::_S_get(*this); } + const _H1& _M_h1() const { return _EboH1::_S_cget(*this); } + _H1& _M_h1() { return _EboH1::_S_get(*this); } + const _H2& _M_h2() const { return _EboH2::_S_cget(*this); } + _H2& _M_h2() { return _EboH2::_S_get(*this); } }; - // Specialization: hash function and range-hashing function, - // caching hash codes. H is provided but ignored. Provides - // typedef and accessor required by TR1. + /// Specialization: hash function and range-hashing function, + /// caching hash codes. H is provided but ignored. Provides + /// typedef and accessor required by TR1. template<typename _Key, typename _Value, typename _ExtractKey, typename _H1, typename _H2> struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Default_ranged_hash, true> - : private _Hashtable_ebo_helper<0, _ExtractKey>, - private _Hashtable_ebo_helper<1, _H1>, - private _Hashtable_ebo_helper<2, _H2> + // See PR53067. + : public _Hashtable_ebo_helper<0, _ExtractKey>, + public _Hashtable_ebo_helper<1, _H1>, + public _Hashtable_ebo_helper<2, _H2> { private: - typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; - typedef _Hashtable_ebo_helper<1, _H1> _EboH1; - typedef _Hashtable_ebo_helper<2, _H2> _EboH2; + typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey; + typedef _Hashtable_ebo_helper<1, _H1> _EboH1; + typedef _Hashtable_ebo_helper<2, _H2> _EboH2; public: - typedef _H1 hasher; + typedef _H1 hasher; hasher hash_function() const { return _M_h1(); } + typedef std::size_t __hash_code; + typedef _Hash_node<_Value, true> __node_type; + protected: _Hash_code_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2, const _Default_ranged_hash&) : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { } - typedef std::size_t _Hash_code_type; - - _Hash_code_type + __hash_code _M_hash_code(const _Key& __k) const { return _M_h1()(__k); } std::size_t - _M_bucket_index(const _Key&, _Hash_code_type __c, + _M_bucket_index(const _Key&, __hash_code __c, std::size_t __n) const { return _M_h2()(__c, __n); } std::size_t - _M_bucket_index(const _Hash_node<_Value, true>* __p, - std::size_t __n) const + _M_bucket_index(const __node_type* __p, std::size_t __n) const { return _M_h2()(__p->_M_hash_code, __n); } void - _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const + _M_store_code(__node_type* __n, __hash_code __c) const { __n->_M_hash_code = __c; } void - _M_copy_code(_Hash_node<_Value, true>* __to, - const _Hash_node<_Value, true>* __from) const + _M_copy_code(__node_type* __to, const __node_type* __from) const { __to->_M_hash_code = __from->_M_hash_code; } void @@ -803,110 +1167,75 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::swap(_M_h2(), __x._M_h2()); } - protected: const _ExtractKey& _M_extract() const { return _EboExtractKey::_S_cget(*this); } + _ExtractKey& _M_extract() { return _EboExtractKey::_S_get(*this); } + const _H1& _M_h1() const { return _EboH1::_S_cget(*this); } + _H1& _M_h1() { return _EboH1::_S_get(*this); } + const _H2& _M_h2() const { return _EboH2::_S_cget(*this); } + _H2& _M_h2() { return _EboH2::_S_get(*this); } }; + /** + * Primary class template _Equal_helper. + * + */ template <typename _Key, typename _Value, typename _ExtractKey, typename _Equal, typename _HashCodeType, bool __cache_hash_code> struct _Equal_helper; + /// Specialization. template<typename _Key, typename _Value, typename _ExtractKey, typename _Equal, typename _HashCodeType> struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true> { static bool _S_equals(const _Equal& __eq, const _ExtractKey& __extract, - const _Key& __k, _HashCodeType __c, - _Hash_node<_Value, true>* __n) - { return __c == __n->_M_hash_code - && __eq(__k, __extract(__n->_M_v)); } + const _Key& __k, _HashCodeType __c, _Hash_node<_Value, true>* __n) + { return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v)); } }; + /// Specialization. template<typename _Key, typename _Value, typename _ExtractKey, typename _Equal, typename _HashCodeType> struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false> { static bool _S_equals(const _Equal& __eq, const _ExtractKey& __extract, - const _Key& __k, _HashCodeType, - _Hash_node<_Value, false>* __n) + const _Key& __k, _HashCodeType, _Hash_node<_Value, false>* __n) { return __eq(__k, __extract(__n->_M_v)); } }; - // Helper class adding management of _Equal functor to _Hash_code_base - // type. - template<typename _Key, typename _Value, - typename _ExtractKey, typename _Equal, - typename _H1, typename _H2, typename _Hash, - bool __cache_hash_code> - struct _Hashtable_base - : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, - __cache_hash_code>, - private _Hashtable_ebo_helper<0, _Equal> - { - private: - typedef _Hashtable_ebo_helper<0, _Equal> _EboEqual; - - protected: - typedef _Hash_code_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, __cache_hash_code> _HCBase; - typedef typename _HCBase::_Hash_code_type _Hash_code_type; - - _Hashtable_base(const _ExtractKey& __ex, - const _H1& __h1, const _H2& __h2, - const _Hash& __hash, const _Equal& __eq) - : _HCBase(__ex, __h1, __h2, __hash), _EboEqual(__eq) { } - - bool - _M_equals(const _Key& __k, _Hash_code_type __c, - _Hash_node<_Value, __cache_hash_code>* __n) const - { - typedef _Equal_helper<_Key, _Value, _ExtractKey, - _Equal, _Hash_code_type, - __cache_hash_code> _EqualHelper; - return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), - __k, __c, __n); - } - void - _M_swap(_Hashtable_base& __x) - { - _HCBase::_M_swap(__x); - std::swap(_M_eq(), __x._M_eq()); - } - - protected: - const _Equal& - _M_eq() const { return _EboEqual::_S_cget(*this); } - _Equal& - _M_eq() { return _EboEqual::_S_get(*this); } - }; - - // Local iterators, used to iterate within a bucket but not between - // buckets. + /** + * Primary class template _Local_iterator_base. + * + * Base class for local iterators, used to iterate within a bucket + * but not between buckets. + */ template<typename _Key, typename _Value, typename _ExtractKey, typename _H1, typename _H2, typename _Hash, bool __cache_hash_code> struct _Local_iterator_base; + /// Specialization. template<typename _Key, typename _Value, typename _ExtractKey, typename _H1, typename _H2, typename _Hash> struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true> - : private _H2 + // See PR53067. + : public _H2 { _Local_iterator_base() = default; _Local_iterator_base(_Hash_node<_Value, true>* __p, @@ -933,12 +1262,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::size_t _M_bucket_count; }; + /// Specialization. template<typename _Key, typename _Value, typename _ExtractKey, typename _H1, typename _H2, typename _Hash> struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false> - : private _Hash_code_base<_Key, _Value, _ExtractKey, - _H1, _H2, _Hash, false> + // See PR53067. + : public _Hash_code_base<_Key, _Value, _ExtractKey, + _H1, _H2, _Hash, false> { _Local_iterator_base() = default; _Local_iterator_base(_Hash_node<_Value, false>* __p, @@ -980,6 +1311,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _H1, _H2, _Hash, __cache>& __y) { return __x._M_cur != __y._M_cur; } + /// local iterators template<typename _Key, typename _Value, typename _ExtractKey, typename _H1, typename _H2, typename _Hash, bool __constant_iterators, bool __cache> @@ -1030,6 +1362,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } }; + /// local const_iterators template<typename _Key, typename _Value, typename _ExtractKey, typename _H1, typename _H2, typename _Hash, bool __constant_iterators, bool __cache> @@ -1085,27 +1418,201 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } }; + /** + * Primary class template _Hashtable_base. + * + * Base class for _Hashtable. Helper class adding management of + * _Equal functor to _Hash_code_base type. + */ + template<typename _Key, typename _Value, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, typename _Traits> + struct _Hashtable_base + // See PR53067. + : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, + _Traits::__hash_cached::value>, + public _Hashtable_ebo_helper<0, _Equal> + { + public: + typedef _Key key_type; + typedef _Value value_type; + typedef _Equal key_equal; + typedef std::size_t size_type; + typedef std::ptrdiff_t difference_type; + + using __traits_type = _Traits; + using __hash_cached = typename __traits_type::__hash_cached; + using __constant_iterators = typename __traits_type::__constant_iterators; + using __unique_keys = typename __traits_type::__unique_keys; + + using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey, + _H1, _H2, _Hash, + __hash_cached::value>; + + using __hash_code = typename __hash_code_base::__hash_code; + using __node_type = typename __hash_code_base::__node_type; + + using iterator = __detail::_Node_iterator<value_type, + __constant_iterators::value, + __hash_cached::value>; + + using const_iterator = __detail::_Node_const_iterator<value_type, + __constant_iterators::value, + __hash_cached::value>; + + using local_iterator = __detail::_Local_iterator<key_type, value_type, + _ExtractKey, _H1, _H2, _Hash, + __constant_iterators::value, + __hash_cached::value>; + + using const_local_iterator = __detail::_Local_const_iterator<key_type, + value_type, + _ExtractKey, _H1, _H2, _Hash, + __constant_iterators::value, + __hash_cached::value>; + + using __ireturn_type = typename std::conditional<__unique_keys::value, + std::pair<iterator, bool>, + iterator>::type; + + using __iconv_type = typename std::conditional<__unique_keys::value, + std::_Select1st<__ireturn_type>, + std::_Identity<__ireturn_type> + >::type; + private: + using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>; + using _EqualHelper = _Equal_helper<_Key, _Value, _ExtractKey, _Equal, + __hash_code, __hash_cached::value>; + + protected: + using __node_base = __detail::_Hash_node_base; + using __bucket_type = __node_base*; + + _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2, + const _Hash& __hash, const _Equal& __eq) + : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq) + { } + + bool + _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const + { + return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), + __k, __c, __n); + } + + void + _M_swap(_Hashtable_base& __x) + { + __hash_code_base::_M_swap(__x); + std::swap(_M_eq(), __x._M_eq()); + } + + const _Equal& + _M_eq() const { return _EqualEBO::_S_cget(*this); } + + _Equal& + _M_eq() { return _EqualEBO::_S_get(*this); } + }; - // Class template _Equality_base. This is for implementing equality - // comparison for unordered containers, per N3068, by John Lakos and - // Pablo Halpern. Algorithmically, we follow closely the reference - // implementations therein. - template<typename _ExtractKey, bool __unique_keys, - typename _Hashtable> - struct _Equality_base; + /** + * struct _Equality_base. + * + * Common types and functions for class _Equality. + */ + struct _Equality_base + { + protected: + template<typename _Uiterator> + static bool + _S_is_permutation(_Uiterator, _Uiterator, _Uiterator); + }; - template<typename _ExtractKey, typename _Hashtable> - struct _Equality_base<_ExtractKey, true, _Hashtable> + // See std::is_permutation in N3068. + template<typename _Uiterator> + bool + _Equality_base:: + _S_is_permutation(_Uiterator __first1, _Uiterator __last1, + _Uiterator __first2) { - bool _M_equal(const _Hashtable&) const; + for (; __first1 != __last1; ++__first1, ++__first2) + if (!(*__first1 == *__first2)) + break; + + if (__first1 == __last1) + return true; + + _Uiterator __last2 = __first2; + std::advance(__last2, std::distance(__first1, __last1)); + + for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1) + { + _Uiterator __tmp = __first1; + while (__tmp != __it1 && !bool(*__tmp == *__it1)) + ++__tmp; + + // We've seen this one before. + if (__tmp != __it1) + continue; + + std::ptrdiff_t __n2 = 0; + for (__tmp = __first2; __tmp != __last2; ++__tmp) + if (*__tmp == *__it1) + ++__n2; + + if (!__n2) + return false; + + std::ptrdiff_t __n1 = 0; + for (__tmp = __it1; __tmp != __last1; ++__tmp) + if (*__tmp == *__it1) + ++__n1; + + if (__n1 != __n2) + return false; + } + return true; + } + + /** + * Primary class template _Equality. + * + * This is for implementing equality comparison for unordered + * containers, per N3068, by John Lakos and Pablo Halpern. + * Algorithmically, we follow closely the reference implementations + * therein. + */ + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits, + bool _Unique_keys = _Traits::__unique_keys::value> + struct _Equality; + + /// Specialization. + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> + struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true> + { + using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>; + + bool + _M_equal(const __hashtable&) const; }; - template<typename _ExtractKey, typename _Hashtable> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> bool - _Equality_base<_ExtractKey, true, _Hashtable>:: - _M_equal(const _Hashtable& __other) const + _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, true>:: + _M_equal(const __hashtable& __other) const { - const _Hashtable* __this = static_cast<const _Hashtable*>(this); + const __hashtable* __this = static_cast<const __hashtable*>(this); if (__this->size() != __other.size()) return false; @@ -1119,70 +1626,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return true; } - template<typename _ExtractKey, typename _Hashtable> - struct _Equality_base<_ExtractKey, false, _Hashtable> + /// Specialization. + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> + struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, false> + : public _Equality_base { - bool _M_equal(const _Hashtable&) const; - - private: - template<typename _Uiterator> - static bool - _S_is_permutation(_Uiterator, _Uiterator, _Uiterator); - }; + using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits>; - // See std::is_permutation in N3068. - template<typename _ExtractKey, typename _Hashtable> - template<typename _Uiterator> bool - _Equality_base<_ExtractKey, false, _Hashtable>:: - _S_is_permutation(_Uiterator __first1, _Uiterator __last1, - _Uiterator __first2) - { - for (; __first1 != __last1; ++__first1, ++__first2) - if (!(*__first1 == *__first2)) - break; - - if (__first1 == __last1) - return true; - - _Uiterator __last2 = __first2; - std::advance(__last2, std::distance(__first1, __last1)); - - for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1) - { - _Uiterator __tmp = __first1; - while (__tmp != __it1 && !bool(*__tmp == *__it1)) - ++__tmp; - - // We've seen this one before. - if (__tmp != __it1) - continue; - - std::ptrdiff_t __n2 = 0; - for (__tmp = __first2; __tmp != __last2; ++__tmp) - if (*__tmp == *__it1) - ++__n2; - - if (!__n2) - return false; - - std::ptrdiff_t __n1 = 0; - for (__tmp = __it1; __tmp != __last1; ++__tmp) - if (*__tmp == *__it1) - ++__n1; - - if (__n1 != __n2) - return false; - } - return true; - } + _M_equal(const __hashtable&) const; + }; - template<typename _ExtractKey, typename _Hashtable> + template<typename _Key, typename _Value, typename _Alloc, + typename _ExtractKey, typename _Equal, + typename _H1, typename _H2, typename _Hash, + typename _RehashPolicy, typename _Traits> bool - _Equality_base<_ExtractKey, false, _Hashtable>:: - _M_equal(const _Hashtable& __other) const + _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, _Traits, false>:: + _M_equal(const __hashtable& __other) const { - const _Hashtable* __this = static_cast<const _Hashtable*>(this); + const __hashtable* __this = static_cast<const __hashtable*>(this); if (__this->size() != __other.size()) return false; @@ -1196,8 +1665,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION != std::distance(__yrange.first, __yrange.second)) return false; - if (!_S_is_permutation(__xrange.first, - __xrange.second, + if (!_S_is_permutation(__xrange.first, __xrange.second, __yrange.first)) return false; @@ -1206,6 +1674,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return true; } + //@} hashtable-detail _GLIBCXX_END_NAMESPACE_VERSION } // namespace __detail } // namespace std diff --git a/libstdc++-v3/include/bits/ptr_traits.h b/libstdc++-v3/include/bits/ptr_traits.h index 7f120b1f8ac..bba9b49bfc6 100644 --- a/libstdc++-v3/include/bits/ptr_traits.h +++ b/libstdc++-v3/include/bits/ptr_traits.h @@ -140,14 +140,8 @@ _GLIBCXX_HAS_NESTED_TYPE(difference_type) /// Type used to represent the difference between two pointers typedef typename __ptrtr_diff_type<_Ptr>::__type difference_type; - private: template<typename _Up> using rebind = typename __ptrtr_rebind<_Ptr, _Up>::__type; - - // allocator_traits needs to use __rebind - template<typename> friend struct allocator_traits; - template<typename> friend struct pointer_traits; - template<typename, typename> friend class __ptrtr_rebind_helper2; }; /** diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc index d55b51838b8..5da353f8bd4 100644 --- a/libstdc++-v3/include/bits/random.tcc +++ b/libstdc++-v3/include/bits/random.tcc @@ -730,40 +730,65 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION independent_bits_engine<_RandomNumberEngine, __w, _UIntType>:: operator()() { - const long double __r = static_cast<long double>(_M_b.max()) - - static_cast<long double>(_M_b.min()) + 1.0L; - const result_type __m = std::log(__r) / std::log(2.0L); - result_type __n, __n0, __y0, __y1, __s0, __s1; + typedef typename _RandomNumberEngine::result_type _Eresult_type; + const _Eresult_type __r + = (_M_b.max() - _M_b.min() < std::numeric_limits<_Eresult_type>::max() + ? _M_b.max() - _M_b.min() + 1 : 0); + const unsigned __edig = std::numeric_limits<_Eresult_type>::digits; + const unsigned __m = __r ? std::__lg(__r) : __edig; + + typedef typename std::common_type<_Eresult_type, result_type>::type + __ctype; + const unsigned __cdig = std::numeric_limits<__ctype>::digits; + + unsigned __n, __n0; + __ctype __s0, __s1, __y0, __y1; + for (size_t __i = 0; __i < 2; ++__i) { __n = (__w + __m - 1) / __m + __i; __n0 = __n - __w % __n; - const result_type __w0 = __w / __n; - const result_type __w1 = __w0 + 1; - __s0 = result_type(1) << __w0; - __s1 = result_type(1) << __w1; - __y0 = __s0 * (__r / __s0); - __y1 = __s1 * (__r / __s1); - if (__r - __y0 <= __y0 / __n) + const unsigned __w0 = __w / __n; // __w0 <= __m + + __s0 = 0; + __s1 = 0; + if (__w0 < __cdig) + { + __s0 = __ctype(1) << __w0; + __s1 = __s0 << 1; + } + + __y0 = 0; + __y1 = 0; + if (__r) + { + __y0 = __s0 * (__r / __s0); + if (__s1) + __y1 = __s1 * (__r / __s1); + + if (__r - __y0 <= __y0 / __n) + break; + } + else break; } result_type __sum = 0; for (size_t __k = 0; __k < __n0; ++__k) { - result_type __u; + __ctype __u; do __u = _M_b() - _M_b.min(); - while (__u >= __y0); - __sum = __s0 * __sum + __u % __s0; + while (__y0 && __u >= __y0); + __sum = __s0 * __sum + (__s0 ? __u % __s0 : __u); } for (size_t __k = __n0; __k < __n; ++__k) { - result_type __u; + __ctype __u; do __u = _M_b() - _M_b.min(); - while (__u >= __y1); - __sum = __s1 * __sum + __u % __s1; + while (__y1 && __u >= __y1); + __sum = __s1 * __sum + (__s1 ? __u % __s1 : __u); } return __sum; } @@ -840,12 +865,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION operator()(_UniformRandomNumberGenerator& __urng, const param_type& __param) { - typedef typename std::make_unsigned<typename - _UniformRandomNumberGenerator::result_type>::type __urngtype; + typedef typename _UniformRandomNumberGenerator::result_type + _Gresult_type; typedef typename std::make_unsigned<result_type>::type __utype; - typedef typename std::conditional<(sizeof(__urngtype) - > sizeof(__utype)), - __urngtype, __utype>::type __uctype; + typedef typename std::common_type<_Gresult_type, __utype>::type + __uctype; const __uctype __urngmin = __urng.min(); const __uctype __urngmax = __urng.max(); diff --git a/libstdc++-v3/include/bits/shared_ptr_base.h b/libstdc++-v3/include/bits/shared_ptr_base.h index c48c18eaee9..39449f1b4bb 100644 --- a/libstdc++-v3/include/bits/shared_ptr_base.h +++ b/libstdc++-v3/include/bits/shared_ptr_base.h @@ -343,6 +343,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Sp_counted_deleter(_Ptr __p, _Deleter __d, const _Alloc& __a) : _M_ptr(__p), _M_del(__d, __a) { } + ~_Sp_counted_deleter() noexcept { } + virtual void _M_dispose() noexcept { _M_del._M_del(_M_ptr); } @@ -401,6 +403,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::forward<_Args>(__args)...); // might throw } + ~_Sp_counted_ptr_inplace() noexcept { } + virtual void _M_dispose() noexcept { allocator_traits<_Alloc>::destroy(_M_impl, _M_impl._M_ptr); } diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index c517a1963d1..f337e0c07a6 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -244,7 +244,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } } -#ifdef __GXX_EXPERIMENTAL_CXX0X__ /// This is an overload used by find_if_not() for the Input Iterator case. template<typename _InputIterator, typename _Predicate> inline _InputIterator @@ -303,7 +302,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __last; } } -#endif + + /// Provided for stable_partition to use. + template<typename _InputIterator, typename _Predicate> + inline _InputIterator + __find_if_not(_InputIterator __first, _InputIterator __last, + _Predicate __pred) + { + return std::__find_if_not(__first, __last, __pred, + std::__iterator_category(__first)); + } + + /// Like find_if_not(), but uses and updates a count of the + /// remaining range length instead of comparing against an end + /// iterator. + template<typename _InputIterator, typename _Predicate, typename _Distance> + _InputIterator + __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred) + { + for (; __len; --__len, ++__first) + if (!bool(__pred(*__first))) + break; + return __first; + } // set_difference // set_intersection @@ -789,8 +810,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, typename iterator_traits<_InputIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); - return std::__find_if_not(__first, __last, __pred, - std::__iterator_category(__first)); + return std::__find_if_not(__first, __last, __pred); } /** @@ -1784,30 +1804,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // partition /// This is a helper function... + /// Requires __len != 0 and !__pred(*__first), + /// same as __stable_partition_adaptive. template<typename _ForwardIterator, typename _Predicate, typename _Distance> _ForwardIterator __inplace_stable_partition(_ForwardIterator __first, - _ForwardIterator __last, _Predicate __pred, _Distance __len) { if (__len == 1) - return __pred(*__first) ? __last : __first; + return __first; _ForwardIterator __middle = __first; std::advance(__middle, __len / 2); - _ForwardIterator __begin = std::__inplace_stable_partition(__first, - __middle, - __pred, - __len / 2); - _ForwardIterator __end = std::__inplace_stable_partition(__middle, __last, - __pred, - __len - - __len / 2); - std::rotate(__begin, __middle, __end); - std::advance(__begin, std::distance(__middle, __end)); - return __begin; + _ForwardIterator __left_split = + std::__inplace_stable_partition(__first, __pred, __len / 2); + // Advance past true-predicate values to satisfy this + // function's preconditions. + _Distance __right_len = __len - __len / 2; + _ForwardIterator __right_split = + std::__find_if_not_n(__middle, __right_len, __pred); + if (__right_len) + __right_split = std::__inplace_stable_partition(__middle, + __pred, + __right_len); + std::rotate(__left_split, __middle, __right_split); + std::advance(__left_split, std::distance(__middle, __right_split)); + return __left_split; } /// This is a helper function... + /// Requires __first != __last and !__pred(*__first) + /// and __len == distance(__first, __last). + /// + /// !__pred(*__first) allows us to guarantee that we don't + /// move-assign an element onto itself. template<typename _ForwardIterator, typename _Pointer, typename _Predicate, typename _Distance> _ForwardIterator @@ -1821,6 +1850,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { _ForwardIterator __result1 = __first; _Pointer __result2 = __buffer; + // The precondition guarantees that !__pred(*__first), so + // move that element to the buffer before starting the loop. + // This ensures that we only call __pred once per element. + *__result2 = _GLIBCXX_MOVE(*__first); + ++__result2; + ++__first; for (; __first != __last; ++__first) if (__pred(*__first)) { @@ -1839,17 +1874,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { _ForwardIterator __middle = __first; std::advance(__middle, __len / 2); - _ForwardIterator __begin = + _ForwardIterator __left_split = std::__stable_partition_adaptive(__first, __middle, __pred, __len / 2, __buffer, __buffer_size); - _ForwardIterator __end = - std::__stable_partition_adaptive(__middle, __last, __pred, - __len - __len / 2, - __buffer, __buffer_size); - std::rotate(__begin, __middle, __end); - std::advance(__begin, std::distance(__middle, __end)); - return __begin; + // Advance past true-predicate values to satisfy this + // function's preconditions. + _Distance __right_len = __len - __len / 2; + _ForwardIterator __right_split = + std::__find_if_not_n(__middle, __right_len, __pred); + if (__right_len) + __right_split = + std::__stable_partition_adaptive(__right_split, __last, __pred, + __right_len, + __buffer, __buffer_size); + std::rotate(__left_split, __middle, __right_split); + std::advance(__left_split, std::distance(__middle, __right_split)); + return __left_split; } } @@ -1882,6 +1923,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename iterator_traits<_ForwardIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); + __first = std::__find_if_not(__first, __last, __pred); + if (__first == __last) return __first; else @@ -1901,7 +1944,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _DistanceType(__buf.size())); else return - std::__inplace_stable_partition(__first, __last, __pred, + std::__inplace_stable_partition(__first, __pred, _DistanceType(__buf.requested_size())); } } diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index 4e6e0f49c5b..1ccf8604f5f 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -989,14 +989,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __lg(int __n) { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } + inline unsigned + __lg(unsigned __n) + { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } + inline long __lg(long __n) { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } + inline unsigned long + __lg(unsigned long __n) + { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } + inline long long __lg(long long __n) { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } + inline unsigned long long + __lg(unsigned long long __n) + { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } + _GLIBCXX_END_NAMESPACE_VERSION _GLIBCXX_BEGIN_NAMESPACE_ALGO diff --git a/libstdc++-v3/include/bits/stl_function.h b/libstdc++-v3/include/bits/stl_function.h index 88655fc55c3..33d5e709628 100644 --- a/libstdc++-v3/include/bits/stl_function.h +++ b/libstdc++-v3/include/bits/stl_function.h @@ -1,6 +1,7 @@ // Functor implementations -*- C++ -*- -// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2011 +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009, 2010, +// 2011, 2012 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -471,7 +472,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /** @} */ template<typename _Tp> - struct _Identity : public unary_function<_Tp,_Tp> + struct _Identity +#ifndef __GXX_EXPERIMENTAL_CXX0X__ + // unary_function itself is deprecated in C++11 and deriving from + // it can even be a nuisance (see PR 52942). + : public unary_function<_Tp,_Tp> +#endif { _Tp& operator()(_Tp& __x) const @@ -483,8 +489,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION }; template<typename _Pair> - struct _Select1st : public unary_function<_Pair, - typename _Pair::first_type> + struct _Select1st +#ifndef __GXX_EXPERIMENTAL_CXX0X__ + : public unary_function<_Pair, typename _Pair::first_type> +#endif { typename _Pair::first_type& operator()(_Pair& __x) const @@ -508,8 +516,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION }; template<typename _Pair> - struct _Select2nd : public unary_function<_Pair, - typename _Pair::second_type> + struct _Select2nd +#ifndef __GXX_EXPERIMENTAL_CXX0X__ + : public unary_function<_Pair, typename _Pair::second_type> +#endif { typename _Pair::second_type& operator()(_Pair& __x) const diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index 95f5657762a..dd08b2645c1 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -1,6 +1,6 @@ // unordered_map implementation -*- C++ -*- -// Copyright (C) 2010, 2011 Free Software Foundation, Inc. +// Copyright (C) 2010, 2011, 2012 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 @@ -34,208 +34,41 @@ namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_CONTAINER - // NB: When we get typedef templates these class definitions - // will be unnecessary. - template<class _Key, class _Tp, - class _Hash = hash<_Key>, - class _Pred = std::equal_to<_Key>, - class _Alloc = std::allocator<std::pair<const _Key, _Tp> >, - bool __cache_hash_code = - __not_<__and_<is_integral<_Key>, is_empty<_Hash>, - integral_constant<bool, !__is_final(_Hash)>, - __detail::__is_noexcept_hash<_Key, _Hash>>>::value> - class __unordered_map - : public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc, - std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, false, true> - { - typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc, - std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, false, true> - _Base; - - public: - typedef typename _Base::value_type value_type; - typedef typename _Base::size_type size_type; - typedef typename _Base::hasher hasher; - typedef typename _Base::key_equal key_equal; - typedef typename _Base::allocator_type allocator_type; - - explicit - __unordered_map(size_type __n = 10, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), - __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) - { } - - template<typename _InputIterator> - __unordered_map(_InputIterator __f, _InputIterator __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), - __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) - { } - - __unordered_map(initializer_list<value_type> __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__l.begin(), __l.end(), __n, __hf, - __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), - __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) - { } - - __unordered_map& - operator=(initializer_list<value_type> __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } - }; - - template<class _Key, class _Tp, - class _Hash = hash<_Key>, - class _Pred = std::equal_to<_Key>, - class _Alloc = std::allocator<std::pair<const _Key, _Tp> >, - bool __cache_hash_code = - __not_<__and_<is_integral<_Key>, is_empty<_Hash>, - integral_constant<bool, !__is_final(_Hash)>, - __detail::__is_noexcept_hash<_Key, _Hash>>>::value> - class __unordered_multimap - : public _Hashtable<_Key, std::pair<const _Key, _Tp>, - _Alloc, - std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, false, false> - { - typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, - _Alloc, - std::_Select1st<std::pair<const _Key, _Tp> >, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, false, false> - _Base; - - public: - typedef typename _Base::value_type value_type; - typedef typename _Base::size_type size_type; - typedef typename _Base::hasher hasher; - typedef typename _Base::key_equal key_equal; - typedef typename _Base::allocator_type allocator_type; - - explicit - __unordered_multimap(size_type __n = 10, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), - __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) - { } - - - template<typename _InputIterator> - __unordered_multimap(_InputIterator __f, _InputIterator __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), - __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) - { } - - __unordered_multimap(initializer_list<value_type> __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__l.begin(), __l.end(), __n, __hf, - __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), - __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a) - { } - - __unordered_multimap& - operator=(initializer_list<value_type> __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } - }; - - template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, - bool __cache_hash_code> - inline void - swap(__unordered_map<_Key, _Tp, _Hash, _Pred, - _Alloc, __cache_hash_code>& __x, - __unordered_map<_Key, _Tp, _Hash, _Pred, - _Alloc, __cache_hash_code>& __y) - { __x.swap(__y); } - - template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, - bool __cache_hash_code> - inline void - swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred, - _Alloc, __cache_hash_code>& __x, - __unordered_multimap<_Key, _Tp, _Hash, _Pred, - _Alloc, __cache_hash_code>& __y) - { __x.swap(__y); } - - template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, - bool __cache_hash_code> - inline bool - operator==(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return __x._M_equal(__y); } - - template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, - bool __cache_hash_code> - inline bool - operator!=(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return !(__x == __y); } - - template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, - bool __cache_hash_code> - inline bool - operator==(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return __x._M_equal(__y); } - - template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, - bool __cache_hash_code> - inline bool - operator!=(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return !(__x == __y); } + /// Base types for unordered_map. + template<bool _Cache> + using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>; + + template<typename _Key, + typename _Tp, + typename _Hash = hash<_Key>, + typename _Pred = std::equal_to<_Key>, + typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >, + typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>> + using __umap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>, + _Alloc, + std::_Select1st<std::pair<const _Key, _Tp>>, + _Pred, _Hash, + __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, _Tr>; + + /// Base types for unordered_multimap. + template<bool _Cache> + using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>; + + template<typename _Key, + typename _Tp, + typename _Hash = hash<_Key>, + typename _Pred = std::equal_to<_Key>, + typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >, + typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>> + using __ummap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>, + _Alloc, + std::_Select1st<std::pair<const _Key, _Tp>>, + _Pred, _Hash, + __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, _Tr>; /** * @brief A standard container composed of unique keys (containing @@ -247,22 +80,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * Meets the requirements of a <a href="tables.html#65">container</a>, and * <a href="tables.html#xx">unordered associative container</a> * - * @param Key Type of key objects. - * @param Tp Type of mapped objects. - * @param Hash Hashing function object type, defaults to hash<Value>. - * @param Pred Predicate function object type, defaults to equal_to<Value>. - * @param Alloc Allocator type, defaults to allocator<Key>. + * @tparam _Key Type of key objects. + * @tparam _Tp Type of mapped objects. + * @tparam _Hash Hashing function object type, defaults to hash<_Value>. + * @tparam _Pred Predicate function object type, defaults + * to equal_to<_Value>. + * @tparam _Alloc Allocator type, defaults to allocator<_Key>. * - * The resulting value type of the container is std::pair<const Key, Tp>. + * The resulting value type of the container is std::pair<const _Key, _Tp>. + * + * Base is _Hashtable, dispatched at compile time via template + * alias __umap_hashtable. */ template<class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = std::equal_to<_Key>, class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > class unordered_map - : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> + : public __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> { - typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; + typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; public: typedef typename _Base::value_type value_type; @@ -280,13 +117,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { } template<typename _InputIterator> - unordered_map(_InputIterator __f, _InputIterator __l, + unordered_map(_InputIterator __f, _InputIterator __l, size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), const allocator_type& __a = allocator_type()) : _Base(__f, __l, __n, __hf, __eql, __a) - { } + { } unordered_map(initializer_list<value_type> __l, size_type __n = 0, @@ -295,16 +132,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER const allocator_type& __a = allocator_type()) : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) { } - - unordered_map& - operator=(initializer_list<value_type> __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } }; - + /** * @brief A standard container composed of equivalent keys * (possibly containing multiple of each key value) that associates @@ -315,22 +144,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * Meets the requirements of a <a href="tables.html#65">container</a>, and * <a href="tables.html#xx">unordered associative container</a> * - * @param Key Type of key objects. - * @param Tp Type of mapped objects. - * @param Hash Hashing function object type, defaults to hash<Value>. - * @param Pred Predicate function object type, defaults to equal_to<Value>. - * @param Alloc Allocator type, defaults to allocator<Key>. + * @tparam _Key Type of key objects. + * @tparam _Tp Type of mapped objects. + * @tparam _Hash Hashing function object type, defaults to hash<_Value>. + * @tparam _Pred Predicate function object type, defaults + * to equal_to<_Value>. + * @tparam _Alloc Allocator type, defaults to allocator<_Key>. + * + * The resulting value type of the container is std::pair<const _Key, _Tp>. * - * The resulting value type of the container is std::pair<const Key, Tp>. + * Base is _Hashtable, dispatched at compile time via template + * alias __ummap_hashtable. */ template<class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = std::equal_to<_Key>, class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > class unordered_multimap - : public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> + : public __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> { - typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; + typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Base; public: typedef typename _Base::value_type value_type; @@ -338,7 +171,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef typename _Base::hasher hasher; typedef typename _Base::key_equal key_equal; typedef typename _Base::allocator_type allocator_type; - + explicit unordered_multimap(size_type __n = 10, const hasher& __hf = hasher(), @@ -348,13 +181,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { } template<typename _InputIterator> - unordered_multimap(_InputIterator __f, _InputIterator __l, + unordered_multimap(_InputIterator __f, _InputIterator __l, size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), const allocator_type& __a = allocator_type()) : _Base(__f, __l, __n, __hf, __eql, __a) - { } + { } unordered_multimap(initializer_list<value_type> __l, size_type __n = 0, @@ -363,14 +196,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER const allocator_type& __a = allocator_type()) : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) { } - - unordered_multimap& - operator=(initializer_list<value_type> __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } }; template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index 3d5361d4266..bd0deb0717c 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -1,6 +1,6 @@ // unordered_set implementation -*- C++ -*- -// Copyright (C) 2010, 2011 Free Software Foundation, Inc. +// Copyright (C) 2010, 2011, 2012 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 @@ -34,228 +34,36 @@ namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_CONTAINER - // NB: When we get typedef templates these class definitions - // will be unnecessary. - template<class _Value, - class _Hash = hash<_Value>, - class _Pred = std::equal_to<_Value>, - class _Alloc = std::allocator<_Value>, - bool __cache_hash_code = - __not_<__and_<is_integral<_Value>, is_empty<_Hash>, - integral_constant<bool, !__is_final(_Hash)>, - __detail::__is_noexcept_hash<_Value, _Hash>>>::value> - class __unordered_set - : public _Hashtable<_Value, _Value, _Alloc, - std::_Identity<_Value>, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, true, true> - { - typedef _Hashtable<_Value, _Value, _Alloc, - std::_Identity<_Value>, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, true, true> - _Base; - - public: - typedef typename _Base::value_type value_type; - typedef typename _Base::size_type size_type; - typedef typename _Base::hasher hasher; - typedef typename _Base::key_equal key_equal; - typedef typename _Base::allocator_type allocator_type; - typedef typename _Base::iterator iterator; - typedef typename _Base::const_iterator const_iterator; - - explicit - __unordered_set(size_type __n = 10, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), __eql, - std::_Identity<value_type>(), __a) - { } - - template<typename _InputIterator> - __unordered_set(_InputIterator __f, _InputIterator __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), __eql, - std::_Identity<value_type>(), __a) - { } - - __unordered_set(initializer_list<value_type> __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__l.begin(), __l.end(), __n, __hf, - __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), __eql, - std::_Identity<value_type>(), __a) - { } - - __unordered_set& - operator=(initializer_list<value_type> __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } - - using _Base::insert; - - std::pair<iterator, bool> - insert(value_type&& __v) - { return this->_M_insert(std::move(__v), std::true_type()); } - - iterator - insert(const_iterator, value_type&& __v) - { return insert(std::move(__v)).first; } - }; - - template<class _Value, - class _Hash = hash<_Value>, - class _Pred = std::equal_to<_Value>, - class _Alloc = std::allocator<_Value>, - bool __cache_hash_code = - __not_<__and_<is_integral<_Value>, is_empty<_Hash>, - integral_constant<bool, !__is_final(_Hash)>, - __detail::__is_noexcept_hash<_Value, _Hash>>>::value> - class __unordered_multiset - : public _Hashtable<_Value, _Value, _Alloc, - std::_Identity<_Value>, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, true, false> - { - typedef _Hashtable<_Value, _Value, _Alloc, - std::_Identity<_Value>, _Pred, - _Hash, __detail::_Mod_range_hashing, - __detail::_Default_ranged_hash, - __detail::_Prime_rehash_policy, - __cache_hash_code, true, false> - _Base; - - public: - typedef typename _Base::value_type value_type; - typedef typename _Base::size_type size_type; - typedef typename _Base::hasher hasher; - typedef typename _Base::key_equal key_equal; - typedef typename _Base::allocator_type allocator_type; - typedef typename _Base::iterator iterator; - typedef typename _Base::const_iterator const_iterator; - - explicit - __unordered_multiset(size_type __n = 10, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), __eql, - std::_Identity<value_type>(), __a) - { } - - - template<typename _InputIterator> - __unordered_multiset(_InputIterator __f, _InputIterator __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), __eql, - std::_Identity<value_type>(), __a) - { } - - __unordered_multiset(initializer_list<value_type> __l, - size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), - const allocator_type& __a = allocator_type()) - : _Base(__l.begin(), __l.end(), __n, __hf, - __detail::_Mod_range_hashing(), - __detail::_Default_ranged_hash(), __eql, - std::_Identity<value_type>(), __a) - { } - - __unordered_multiset& - operator=(initializer_list<value_type> __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } - - using _Base::insert; - - iterator - insert(value_type&& __v) - { return this->_M_insert(std::move(__v), std::false_type()); } - - iterator - insert(const_iterator, value_type&& __v) - { return insert(std::move(__v)); } - }; - - template<class _Value, class _Hash, class _Pred, class _Alloc, - bool __cache_hash_code> - inline void - swap(__unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __x, - __unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __y) - { __x.swap(__y); } - - template<class _Value, class _Hash, class _Pred, class _Alloc, - bool __cache_hash_code> - inline void - swap(__unordered_multiset<_Value, _Hash, _Pred, - _Alloc, __cache_hash_code>& __x, - __unordered_multiset<_Value, _Hash, _Pred, - _Alloc, __cache_hash_code>& __y) - { __x.swap(__y); } - - template<class _Value, class _Hash, class _Pred, class _Alloc, - bool __cache_hash_code> - inline bool - operator==(const __unordered_set<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_set<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return __x._M_equal(__y); } - - template<class _Value, class _Hash, class _Pred, class _Alloc, - bool __cache_hash_code> - inline bool - operator!=(const __unordered_set<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_set<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return !(__x == __y); } - - template<class _Value, class _Hash, class _Pred, class _Alloc, - bool __cache_hash_code> - inline bool - operator==(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return __x._M_equal(__y); } - - template<class _Value, class _Hash, class _Pred, class _Alloc, - bool __cache_hash_code> - inline bool - operator!=(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __x, - const __unordered_multiset<_Value, _Hash, _Pred, _Alloc, - __cache_hash_code>& __y) - { return !(__x == __y); } + /// Base types for unordered_set. + template<bool _Cache> + using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>; + + template<typename _Value, + typename _Hash = hash<_Value>, + typename _Pred = std::equal_to<_Value>, + typename _Alloc = std::allocator<_Value>, + typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>> + using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc, + std::_Identity<_Value>, _Pred, _Hash, + __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, _Tr>; + + /// Base types for unordered_multiset. + template<bool _Cache> + using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>; + + template<typename _Value, + typename _Hash = hash<_Value>, + typename _Pred = std::equal_to<_Value>, + typename _Alloc = std::allocator<_Value>, + typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>> + using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc, + std::_Identity<_Value>, + _Pred, _Hash, + __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, _Tr>; /** * @brief A standard container composed of unique keys (containing @@ -267,19 +75,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * Meets the requirements of a <a href="tables.html#65">container</a>, and * <a href="tables.html#xx">unordered associative container</a> * - * @param Value Type of key objects. - * @param Hash Hashing function object type, defaults to hash<Value>. - * @param Pred Predicate function object type, defaults to equal_to<Value>. - * @param Alloc Allocator type, defaults to allocator<Key>. + * @tparam _Value Type of key objects. + * @tparam _Hash Hashing function object type, defaults to hash<_Value>. + + * @tparam _Pred Predicate function object type, defaults to + * equal_to<_Value>. + * + * @tparam _Alloc Allocator type, defaults to allocator<_Key>. + * + * Base is _Hashtable, dispatched at compile time via template + * alias __uset_hashtable. */ template<class _Value, class _Hash = hash<_Value>, class _Pred = std::equal_to<_Value>, class _Alloc = std::allocator<_Value> > class unordered_set - : public __unordered_set<_Value, _Hash, _Pred, _Alloc> + : public __uset_hashtable<_Value, _Hash, _Pred, _Alloc> { - typedef __unordered_set<_Value, _Hash, _Pred, _Alloc> _Base; + typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Base; public: typedef typename _Base::value_type value_type; @@ -287,7 +101,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef typename _Base::hasher hasher; typedef typename _Base::key_equal key_equal; typedef typename _Base::allocator_type allocator_type; - + explicit unordered_set(size_type __n = 10, const hasher& __hf = hasher(), @@ -297,13 +111,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { } template<typename _InputIterator> - unordered_set(_InputIterator __f, _InputIterator __l, + unordered_set(_InputIterator __f, _InputIterator __l, size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), const allocator_type& __a = allocator_type()) : _Base(__f, __l, __n, __hf, __eql, __a) - { } + { } unordered_set(initializer_list<value_type> __l, size_type __n = 0, @@ -312,14 +126,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER const allocator_type& __a = allocator_type()) : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) { } - - unordered_set& - operator=(initializer_list<value_type> __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } }; /** @@ -332,19 +138,23 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * Meets the requirements of a <a href="tables.html#65">container</a>, and * <a href="tables.html#xx">unordered associative container</a> * - * @param Value Type of key objects. - * @param Hash Hashing function object type, defaults to hash<Value>. - * @param Pred Predicate function object type, defaults to equal_to<Value>. - * @param Alloc Allocator type, defaults to allocator<Key>. + * @tparam _Value Type of key objects. + * @tparam _Hash Hashing function object type, defaults to hash<_Value>. + * @tparam _Pred Predicate function object type, defaults + * to equal_to<_Value>. + * @tparam _Alloc Allocator type, defaults to allocator<_Key>. + * + * Base is _Hashtable, dispatched at compile time via template + * alias __umset_hashtable. */ template<class _Value, class _Hash = hash<_Value>, class _Pred = std::equal_to<_Value>, class _Alloc = std::allocator<_Value> > class unordered_multiset - : public __unordered_multiset<_Value, _Hash, _Pred, _Alloc> + : public __umset_hashtable<_Value, _Hash, _Pred, _Alloc> { - typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc> _Base; + typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Base; public: typedef typename _Base::value_type value_type; @@ -352,7 +162,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER typedef typename _Base::hasher hasher; typedef typename _Base::key_equal key_equal; typedef typename _Base::allocator_type allocator_type; - + explicit unordered_multiset(size_type __n = 10, const hasher& __hf = hasher(), @@ -363,13 +173,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER template<typename _InputIterator> - unordered_multiset(_InputIterator __f, _InputIterator __l, + unordered_multiset(_InputIterator __f, _InputIterator __l, size_type __n = 0, - const hasher& __hf = hasher(), - const key_equal& __eql = key_equal(), + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), const allocator_type& __a = allocator_type()) : _Base(__f, __l, __n, __hf, __eql, __a) - { } + { } unordered_multiset(initializer_list<value_type> __l, size_type __n = 0, @@ -378,14 +188,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER const allocator_type& __a = allocator_type()) : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a) { } - - unordered_multiset& - operator=(initializer_list<value_type> __l) - { - this->clear(); - this->insert(__l.begin(), __l.end()); - return *this; - } }; template<class _Value, class _Hash, class _Pred, class _Alloc> @@ -428,4 +230,3 @@ _GLIBCXX_END_NAMESPACE_CONTAINER } // namespace std #endif /* _UNORDERED_SET_H */ - diff --git a/libstdc++-v3/include/debug/forward_list b/libstdc++-v3/include/debug/forward_list index 1f887da432c..8ad4336663e 100644 --- a/libstdc++-v3/include/debug/forward_list +++ b/libstdc++-v3/include/debug/forward_list @@ -409,6 +409,10 @@ namespace __debug _GLIBCXX_DEBUG_VERIFY(&__list != this, _M_message(__gnu_debug::__msg_self_splice) ._M_sequence(*this, "this")); + _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(), + _M_message(__gnu_debug::__msg_splice_alloc) + ._M_sequence(*this) + ._M_sequence(__list, "__list")); this->_M_transfer_from_if(__list, [&__list](_Base_const_iterator __it) { return __it != __list._M_base().cbefore_begin() @@ -418,6 +422,10 @@ namespace __debug } void + splice_after(const_iterator __pos, forward_list& __list) + { splice_after(__pos, std::move(__list)); } + + void splice_after(const_iterator __pos, forward_list&& __list, const_iterator __i) { @@ -429,6 +437,10 @@ namespace __debug _M_message(__gnu_debug::__msg_splice_other) ._M_iterator(__i, "__i") ._M_sequence(__list, "__list")); + _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(), + _M_message(__gnu_debug::__msg_splice_alloc) + ._M_sequence(*this) + ._M_sequence(__list, "__list")); // _GLIBCXX_RESOLVE_LIB_DEFECTS // 250. splicing invalidates iterators @@ -440,6 +452,11 @@ namespace __debug } void + splice_after(const_iterator __pos, forward_list& __list, + const_iterator __i) + { splice_after(__pos, std::move(__list), __i); } + + void splice_after(const_iterator __pos, forward_list&& __list, const_iterator __before, const_iterator __last) { @@ -460,6 +477,10 @@ namespace __debug ._M_sequence(__list, "list") ._M_iterator(__before, "before") ._M_iterator(__last, "last")); + _GLIBCXX_DEBUG_VERIFY(__list.get_allocator() == this->get_allocator(), + _M_message(__gnu_debug::__msg_splice_alloc) + ._M_sequence(*this) + ._M_sequence(__list, "__list")); for (_Base_const_iterator __tmp = std::next(__before.base()); __tmp != __last.base(); ++__tmp) @@ -485,6 +506,11 @@ namespace __debug } void + splice_after(const_iterator __pos, forward_list& __list, + const_iterator __before, const_iterator __last) + { splice_after(__pos, std::move(__list), __before, __last); } + + void remove(const _Tp& __val) { _Base_iterator __x = _Base::before_begin(); @@ -565,6 +591,10 @@ namespace __debug } } + void + merge(forward_list& __list) + { merge(std::move(__list)); } + template<typename _Comp> void merge(forward_list&& __list, _Comp __comp) @@ -584,6 +614,11 @@ namespace __debug } } + template<typename _Comp> + void + merge(forward_list& __list, _Comp __comp) + { merge(std::move(__list), __comp); } + using _Base::sort; using _Base::reverse; @@ -737,8 +772,12 @@ namespace __gnu_debug typedef typename _It::iterator_type _BaseIt; static bool - _M_Is(_BaseIt __it, const _Sequence* __seq) + _S_Is(_BaseIt __it, const _Sequence* __seq) { return __it == __seq->_M_base().cbefore_begin(); } + + static bool + _S_Is_Beginnest(_BaseIt __it, const _Sequence* __seq) + { return _S_Is(__it, __seq); } }; } diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h index b02fa7ab8ff..3cab2d7d8a2 100644 --- a/libstdc++-v3/include/debug/safe_iterator.h +++ b/libstdc++-v3/include/debug/safe_iterator.h @@ -50,8 +50,12 @@ namespace __gnu_debug typedef typename _It::iterator_type _BaseIt; static bool - _M_Is(_BaseIt __it, const _Sequence* __seq) + _S_Is(_BaseIt, const _Sequence*) { return false; } + + static bool + _S_Is_Beginnest(_BaseIt __it, const _Sequence* __seq) + { return __it == __seq->_M_base().begin(); } }; /** Iterators that derive from _Safe_iterator_base but that aren't @@ -465,7 +469,15 @@ namespace __gnu_debug /// any? bool _M_is_before_begin() const { - return _BeforeBeginHelper<_Sequence>::_M_Is(base(), _M_get_sequence()); + return _BeforeBeginHelper<_Sequence>::_S_Is(base(), _M_get_sequence()); + } + + /// Is this iterator equal to the sequence's before_begin() iterator if + /// any or begin() otherwise? + bool _M_is_beginnest() const + { + return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(base(), + _M_get_sequence()); } }; diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc index 777a707e7f3..f01252bf6c2 100644 --- a/libstdc++-v3/include/debug/safe_iterator.tcc +++ b/libstdc++-v3/include/debug/safe_iterator.tcc @@ -1,6 +1,6 @@ // Debugging iterator implementation (out of line) -*- C++ -*- -// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2011 +// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2011, 2012 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -91,10 +91,11 @@ namespace __gnu_debug /* We can only test for equality, but check if one of the iterators is at an extreme. */ /* Optim for classic [begin, it) or [it, end) ranges, limit checks - * when code is valid. */ - if (_M_is_begin() || __rhs._M_is_end()) + * when code is valid. Note, for the special case of forward_list, + * before_begin replaces the role of begin. */ + if (_M_is_beginnest() || __rhs._M_is_end()) return true; - if (_M_is_end() || __rhs._M_is_begin()) + if (_M_is_end() || __rhs._M_is_beginnest()) return false; // Assume that this is a valid range; we can't check anything else diff --git a/libstdc++-v3/include/ext/alloc_traits.h b/libstdc++-v3/include/ext/alloc_traits.h index 4862636645e..b3e3af663a6 100644 --- a/libstdc++-v3/include/ext/alloc_traits.h +++ b/libstdc++-v3/include/ext/alloc_traits.h @@ -99,6 +99,7 @@ template<typename _Alloc> typedef typename _Base_type::pointer pointer; typedef typename _Base_type::const_pointer const_pointer; typedef typename _Base_type::size_type size_type; + typedef typename _Base_type::difference_type difference_type; // C++0x allocators do not define reference or const_reference typedef value_type& reference; typedef const value_type& const_reference; @@ -170,6 +171,7 @@ template<typename _Alloc> typedef typename _Alloc::reference reference; typedef typename _Alloc::const_reference const_reference; typedef typename _Alloc::size_type size_type; + typedef typename _Alloc::difference_type difference_type; static pointer allocate(_Alloc& __a, size_type __n) diff --git a/libstdc++-v3/include/ext/functional b/libstdc++-v3/include/ext/functional index 85b944bf61d..f8402c16dc6 100644 --- a/libstdc++-v3/include/ext/functional +++ b/libstdc++-v3/include/ext/functional @@ -1,6 +1,6 @@ // Functional extensions -*- C++ -*- -// Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2009, 2010 +// Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2012 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -183,7 +183,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * @addtogroup SGIextensions */ template <class _Tp> - struct identity : public std::_Identity<_Tp> {}; + struct identity +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + : public std::unary_function<_Tp,_Tp>, + public std::_Identity<_Tp> {}; +#else + : public std::_Identity<_Tp> {}; +#endif /** @c select1st and @c select2nd are extensions provided by SGI. Their * @c operator()s @@ -197,11 +203,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION */ /// An \link SGIextensions SGI extension \endlink. template <class _Pair> - struct select1st : public std::_Select1st<_Pair> {}; + struct select1st +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + : public std::unary_function<_Pair, typename _Pair::first_type>, + public std::_Select1st<_Pair> {}; +#else + : public std::_Select1st<_Pair> {}; +#endif /// An \link SGIextensions SGI extension \endlink. template <class _Pair> - struct select2nd : public std::_Select2nd<_Pair> {}; + struct select2nd +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + : public std::unary_function<_Pair, typename _Pair::second_type>, + public std::_Select2nd<_Pair> {}; +#else + : public std::_Select2nd<_Pair> {}; +#endif /** @} */ // extension documented next diff --git a/libstdc++-v3/include/std/type_traits b/libstdc++-v3/include/std/type_traits index 41022630837..c03b7bd64bb 100644 --- a/libstdc++-v3/include/std/type_traits +++ b/libstdc++-v3/include/std/type_traits @@ -1147,30 +1147,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __is_nt_move_assignable_impl<_Tp> { }; - /// has_trivial_default_constructor + /// is_trivially_constructible (still unimplemented) + + /// is_trivially_default_constructible (still unimplemented) + + /// is_trivially_copy_constructible (still unimplemented) + + /// is_trivially_move_constructible (still unimplemented) + + /// is_trivially_assignable (still unimplemented) + + /// is_trivially_copy_assignable (still unimplemented) + + /// is_trivially_move_assignable (still unimplemented) + + /// is_trivially_destructible + template<typename _Tp> + struct is_trivially_destructible + : public __and_<is_destructible<_Tp>, integral_constant<bool, + __has_trivial_destructor(_Tp)>>::type + { }; + + /// has_trivial_default_constructor (temporary legacy) template<typename _Tp> struct has_trivial_default_constructor : public integral_constant<bool, __has_trivial_constructor(_Tp)> { }; - /// has_trivial_copy_constructor + /// has_trivial_copy_constructor (temporary legacy) template<typename _Tp> struct has_trivial_copy_constructor : public integral_constant<bool, __has_trivial_copy(_Tp)> { }; - /// has_trivial_copy_assign + /// has_trivial_copy_assign (temporary legacy) template<typename _Tp> struct has_trivial_copy_assign : public integral_constant<bool, __has_trivial_assign(_Tp)> { }; - /// has_trivial_destructor - template<typename _Tp> - struct has_trivial_destructor - : public integral_constant<bool, __has_trivial_destructor(_Tp)> - { }; - /// has_virtual_destructor template<typename _Tp> struct has_virtual_destructor @@ -1266,12 +1281,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __is_convertible_helper<_From, _To>::value> { }; - /// is_explicitly_convertible - template<typename _From, typename _To> - struct is_explicitly_convertible - : public is_constructible<_To, _From> - { }; - // const-volatile modifications. diff --git a/libstdc++-v3/python/libstdcxx/v6/printers.py b/libstdc++-v3/python/libstdcxx/v6/printers.py index 76c54b1598e..4520f32ac13 100644 --- a/libstdc++-v3/python/libstdcxx/v6/printers.py +++ b/libstdc++-v3/python/libstdcxx/v6/printers.py @@ -611,7 +611,7 @@ class StdStringPrinter: class Tr1HashtableIterator: def __init__ (self, hash): self.node = hash['_M_before_begin']['_M_nxt'] - self.node_type = find_type(hash.type, '_Node').pointer() + self.node_type = find_type(hash.type, '__node_type').pointer() def __iter__ (self): return self diff --git a/libstdc++-v3/src/c++11/debug.cc b/libstdc++-v3/src/c++11/debug.cc index 0c746c1fc37..f0ab4bc4ec6 100644 --- a/libstdc++-v3/src/c++11/debug.cc +++ b/libstdc++-v3/src/c++11/debug.cc @@ -131,7 +131,7 @@ namespace __gnu_debug "attempt to flip a singular bitset reference", // std::list checks "attempt to splice a list into itself", - "attempt to splice lists with inequal allocators", + "attempt to splice lists with unequal allocators", "attempt to splice elements referenced by a %1.state; iterator", "attempt to splice an iterator from a different container", "splice destination %1.name;" diff --git a/libstdc++-v3/src/c++98/mt_allocator.cc b/libstdc++-v3/src/c++98/mt_allocator.cc index 16c2fb8063e..92f252be79b 100644 --- a/libstdc++-v3/src/c++98/mt_allocator.cc +++ b/libstdc++-v3/src/c++98/mt_allocator.cc @@ -1,6 +1,7 @@ // Allocator details. -// Copyright (C) 2004, 2005, 2006, 2009, 2010 Free Software Foundation, Inc. +// Copyright (C) 2004, 2005, 2006, 2009, 2010, 2012 +// 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 @@ -48,6 +49,7 @@ namespace { __gthread_key_delete(_M_key); ::operator delete(static_cast<void*>(_M_thread_freelist_array)); + _M_thread_freelist = 0; } } }; diff --git a/libstdc++-v3/testsuite/20_util/declval/requirements/1_neg.cc b/libstdc++-v3/testsuite/20_util/declval/requirements/1_neg.cc index eafbe5f6666..0839e246df3 100644 --- a/libstdc++-v3/testsuite/20_util/declval/requirements/1_neg.cc +++ b/libstdc++-v3/testsuite/20_util/declval/requirements/1_neg.cc @@ -2,7 +2,7 @@ // { dg-do compile } // 2009-11-12 Paolo Carlini <paolo.carlini@oracle.com> // -// Copyright (C) 2009, 2010, 2011 Free Software Foundation, Inc. +// Copyright (C) 2009, 2010, 2011, 2012 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 @@ -19,7 +19,7 @@ // with this library; see the file COPYING3. If not see // <http://www.gnu.org/licenses/>. -// { dg-error "static assertion failed" "" { target *-*-* } 1777 } +// { dg-error "static assertion failed" "" { target *-*-* } 1786 } #include <utility> diff --git a/libstdc++-v3/testsuite/20_util/hash/52931.cc b/libstdc++-v3/testsuite/20_util/hash/52931.cc new file mode 100644 index 00000000000..f30a3e7d17a --- /dev/null +++ b/libstdc++-v3/testsuite/20_util/hash/52931.cc @@ -0,0 +1,32 @@ +// { dg-options "-std=gnu++11" } +// { dg-do compile } + +// Copyright (C) 2012 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/>. + +#include <type_traits> +#include <functional> + +class S{}; // No hash specialization + +template<class T> +auto f(int) -> decltype(std::hash<T>(), std::true_type()); + +template<class T> +auto f(...) -> decltype(std::false_type()); + +static_assert(!decltype(f<S>(0))::value, ""); diff --git a/libstdc++-v3/testsuite/20_util/is_explicitly_convertible/requirements/explicit_instantiation.cc b/libstdc++-v3/testsuite/20_util/is_trivially_destructible/requirements/explicit_instantiation.cc index 87dd950b27d..c6ab0b2c54e 100644 --- a/libstdc++-v3/testsuite/20_util/is_explicitly_convertible/requirements/explicit_instantiation.cc +++ b/libstdc++-v3/testsuite/20_util/is_trivially_destructible/requirements/explicit_instantiation.cc @@ -1,9 +1,9 @@ -// { dg-options "-std=gnu++0x" } +// { dg-options "-std=gnu++11" } // { dg-do compile } - -// 2009-12-30 Paolo Carlini <paolo.carlini@oracle.com> - -// Copyright (C) 2009 Free Software Foundation, Inc. +// +// 2012-04-15 Paolo Carlini <paolo.carlini@oracle.com> +// +// Copyright (C) 2012 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 @@ -27,5 +27,5 @@ namespace std { typedef short test_type; - template struct is_explicitly_convertible<test_type, test_type>; + template struct is_trivially_destructible<test_type>; } diff --git a/libstdc++-v3/testsuite/20_util/is_explicitly_convertible/requirements/typedefs.cc b/libstdc++-v3/testsuite/20_util/is_trivially_destructible/requirements/typedefs.cc index 52ba964b1fd..66b3f7bd920 100644 --- a/libstdc++-v3/testsuite/20_util/is_explicitly_convertible/requirements/typedefs.cc +++ b/libstdc++-v3/testsuite/20_util/is_trivially_destructible/requirements/typedefs.cc @@ -1,9 +1,8 @@ -// { dg-options "-std=gnu++0x" } -// { dg-do compile } - -// 2009-12-30 Paolo Carlini <paolo.carlini@oracle.com> +// { dg-options "-std=gnu++11" } +// +// 2012-04-15 Paolo Carlini <paolo.carlini@oracle.com> // -// Copyright (C) 2009 Free Software Foundation, Inc. +// Copyright (C) 2012 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 @@ -25,12 +24,14 @@ #include <type_traits> +// { dg-do compile } + void test01() { // Check for required typedefs - typedef std::is_explicitly_convertible<int, int> test_type; - typedef test_type::value_type value_type; - typedef test_type::type type; - typedef test_type::type::value_type type_value_type; - typedef test_type::type::type type_type; + typedef std::is_trivially_destructible<int> test_type; + typedef test_type::value_type value_type; + typedef test_type::type type; + typedef test_type::type::value_type type_value_type; + typedef test_type::type::type type_type; } diff --git a/libstdc++-v3/testsuite/20_util/is_explicitly_convertible/value.cc b/libstdc++-v3/testsuite/20_util/is_trivially_destructible/value.cc index 7e704873275..cfba8aeba9e 100644 --- a/libstdc++-v3/testsuite/20_util/is_explicitly_convertible/value.cc +++ b/libstdc++-v3/testsuite/20_util/is_trivially_destructible/value.cc @@ -1,6 +1,8 @@ -// { dg-options "-std=gnu++0x" } - -// Copyright (C) 2009 Free Software Foundation, Inc. +// { dg-options "-std=gnu++11" } +// +// 2012-04-15 Paolo Carlini <paolo.carlini@oracle.com> +// +// Copyright (C) 2012 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 @@ -24,18 +26,15 @@ void test01() { bool test __attribute__((unused)) = true; - using std::is_explicitly_convertible; + using std::is_trivially_destructible; using namespace __gnu_test; - // Positive tests. - VERIFY( (test_relationship<is_explicitly_convertible, double&, - ExplicitClass>(true)) ); - VERIFY( (test_relationship<is_explicitly_convertible, int&, - ExplicitClass>(true)) ); + VERIFY( (test_category<is_trivially_destructible, int>(true)) ); + VERIFY( (test_category<is_trivially_destructible, TType>(true)) ); + VERIFY( (test_category<is_trivially_destructible, PODType>(true)) ); - // Negative tests. - VERIFY( (test_relationship<is_explicitly_convertible, void*, - ExplicitClass>(false)) ); + VERIFY( (test_category<is_trivially_destructible, NType>(false)) ); + VERIFY( (test_category<is_trivially_destructible, SLType>(false)) ); } int main() diff --git a/libstdc++-v3/testsuite/20_util/make_signed/requirements/typedefs_neg.cc b/libstdc++-v3/testsuite/20_util/make_signed/requirements/typedefs_neg.cc index 6358d72c4a5..09ab111b796 100644 --- a/libstdc++-v3/testsuite/20_util/make_signed/requirements/typedefs_neg.cc +++ b/libstdc++-v3/testsuite/20_util/make_signed/requirements/typedefs_neg.cc @@ -3,7 +3,8 @@ // 2007-05-03 Benjamin Kosnik <bkoz@redhat.com> // -// Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. +// Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012 +// 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 @@ -42,11 +43,11 @@ void test01() typedef make_signed<float>::type test5_type; } -// { dg-error "does not name a type" "" { target *-*-* } 33 } -// { dg-error "required from here" "" { target *-*-* } 35 } -// { dg-error "required from here" "" { target *-*-* } 37 } -// { dg-error "required from here" "" { target *-*-* } 40 } -// { dg-error "required from here" "" { target *-*-* } 42 } +// { dg-error "does not name a type" "" { target *-*-* } 34 } +// { dg-error "required from here" "" { target *-*-* } 36 } +// { dg-error "required from here" "" { target *-*-* } 38 } +// { dg-error "required from here" "" { target *-*-* } 41 } +// { dg-error "required from here" "" { target *-*-* } 43 } -// { dg-error "invalid use of incomplete type" "" { target *-*-* } 1566 } -// { dg-error "declaration of" "" { target *-*-* } 1530 } +// { dg-error "invalid use of incomplete type" "" { target *-*-* } 1575 } +// { dg-error "declaration of" "" { target *-*-* } 1539 } diff --git a/libstdc++-v3/testsuite/20_util/make_unsigned/requirements/typedefs_neg.cc b/libstdc++-v3/testsuite/20_util/make_unsigned/requirements/typedefs_neg.cc index d9a0f178f6c..574a9bb05ca 100644 --- a/libstdc++-v3/testsuite/20_util/make_unsigned/requirements/typedefs_neg.cc +++ b/libstdc++-v3/testsuite/20_util/make_unsigned/requirements/typedefs_neg.cc @@ -3,7 +3,8 @@ // 2007-05-03 Benjamin Kosnik <bkoz@redhat.com> // -// Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. +// Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012 +// 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 @@ -42,11 +43,11 @@ void test01() typedef make_unsigned<float>::type test5_type; } -// { dg-error "does not name a type" "" { target *-*-* } 33 } -// { dg-error "required from here" "" { target *-*-* } 35 } -// { dg-error "required from here" "" { target *-*-* } 37 } -// { dg-error "required from here" "" { target *-*-* } 40 } -// { dg-error "required from here" "" { target *-*-* } 42 } +// { dg-error "does not name a type" "" { target *-*-* } 34 } +// { dg-error "required from here" "" { target *-*-* } 36 } +// { dg-error "required from here" "" { target *-*-* } 38 } +// { dg-error "required from here" "" { target *-*-* } 41 } +// { dg-error "required from here" "" { target *-*-* } 43 } -// { dg-error "invalid use of incomplete type" "" { target *-*-* } 1484 } -// { dg-error "declaration of" "" { target *-*-* } 1448 } +// { dg-error "invalid use of incomplete type" "" { target *-*-* } 1493 } +// { dg-error "declaration of" "" { target *-*-* } 1457 } diff --git a/libstdc++-v3/testsuite/20_util/pair/requirements/dr801.cc b/libstdc++-v3/testsuite/20_util/pair/requirements/dr801.cc index 36d380dcf87..e7d6626becd 100644 --- a/libstdc++-v3/testsuite/20_util/pair/requirements/dr801.cc +++ b/libstdc++-v3/testsuite/20_util/pair/requirements/dr801.cc @@ -1,7 +1,7 @@ // { dg-do compile } // { dg-options "-std=gnu++0x" } -// Copyright (C) 2010 Free Software Foundation, Inc. +// Copyright (C) 2010, 2012 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 @@ -29,7 +29,7 @@ void test_trivial() // static_assert(std::is_literal_type<pair_type>::value, "! literal"); static_assert(std::has_trivial_copy_constructor<pair_type>::value, "! triv copy"); - static_assert(std::has_trivial_destructor<pair_type>::value, + static_assert(std::is_trivially_destructible<pair_type>::value, "! triv destructor"); // static_assert(std::is_standard_layout<pair_type>::value, // "! standard layout"); diff --git a/libstdc++-v3/testsuite/20_util/pointer_traits/requirements/typedefs.cc b/libstdc++-v3/testsuite/20_util/pointer_traits/requirements/typedefs.cc index c682557a0e3..47b5212ff01 100644 --- a/libstdc++-v3/testsuite/20_util/pointer_traits/requirements/typedefs.cc +++ b/libstdc++-v3/testsuite/20_util/pointer_traits/requirements/typedefs.cc @@ -32,6 +32,7 @@ void test01() typedef typename test_type::pointer pointer; typedef typename test_type::element_type element_type; typedef typename test_type::difference_type difference_type; + typedef typename test_type::template rebind<char> rebind_type; } int main() diff --git a/libstdc++-v3/testsuite/20_util/shared_ptr/cons/43820_neg.cc b/libstdc++-v3/testsuite/20_util/shared_ptr/cons/43820_neg.cc index 39f9ce3b42e..d2110ca8b39 100644 --- a/libstdc++-v3/testsuite/20_util/shared_ptr/cons/43820_neg.cc +++ b/libstdc++-v3/testsuite/20_util/shared_ptr/cons/43820_neg.cc @@ -32,9 +32,9 @@ void test01() { X* px = 0; std::shared_ptr<X> p1(px); // { dg-error "here" } - // { dg-error "incomplete" "" { target *-*-* } 771 } + // { dg-error "incomplete" "" { target *-*-* } 775 } std::shared_ptr<X> p9(ap()); // { dg-error "here" } - // { dg-error "incomplete" "" { target *-*-* } 865 } + // { dg-error "incomplete" "" { target *-*-* } 869 } } diff --git a/libstdc++-v3/testsuite/20_util/shared_ptr/cons/52924.cc b/libstdc++-v3/testsuite/20_util/shared_ptr/cons/52924.cc new file mode 100644 index 00000000000..0cd6bad6401 --- /dev/null +++ b/libstdc++-v3/testsuite/20_util/shared_ptr/cons/52924.cc @@ -0,0 +1,44 @@ +// { dg-options "-std=gnu++0x" } +// { dg-do compile } + +// Copyright (C) 2012 Free Software Foundation +// +// 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/>. + +#include <memory> + +// libstdc++/52924 + +struct A { } a; + +struct D { + ~D() noexcept(false) { } + void operator()(A*) { } +} d; + +auto sp = std::shared_ptr<A>(&a, d); + +template<typename T> +struct Alloc : std::allocator<T> +{ + Alloc() = default; + ~Alloc() noexcept(false) { } + template<typename U> Alloc(const Alloc<U>&) { } +}; + +Alloc<A> al; + +auto as = std::allocate_shared<A>(al); diff --git a/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_copy/808590.cc b/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_copy/808590.cc new file mode 100644 index 00000000000..7ccd8da6b3f --- /dev/null +++ b/libstdc++-v3/testsuite/20_util/specialized_algorithms/uninitialized_copy/808590.cc @@ -0,0 +1,48 @@ +// Copyright (C) 2012 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 Pred 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/>. + +#include <vector> +#include <stdexcept> + +// 4.4.x only +struct c +{ + void *m; + + c(void* o = 0) : m(o) {} + c(const c &r) : m(r.m) {} + + template<class T> + explicit c(T &o) : m((void*)0xdeadfbeef) { } +}; + +int main() +{ + std::vector<c> cbs; + const c cb((void*)0xcafebabe); + + for (int fd = 62; fd < 67; ++fd) + { + cbs.resize(fd + 1); + cbs[fd] = cb; + } + + for (int fd = 62; fd< 67; ++fd) + if (cb.m != cbs[fd].m) + throw std::runtime_error("wrong"); + return 0; +} diff --git a/libstdc++-v3/testsuite/20_util/tuple/requirements/dr801.cc b/libstdc++-v3/testsuite/20_util/tuple/requirements/dr801.cc index fd21b9ee5c5..879bfd126bb 100644 --- a/libstdc++-v3/testsuite/20_util/tuple/requirements/dr801.cc +++ b/libstdc++-v3/testsuite/20_util/tuple/requirements/dr801.cc @@ -29,7 +29,7 @@ void test_trivial() // static_assert(std::is_literal_type<tuple_type>::value, "! literal"); static_assert(std::has_trivial_copy_constructor<tuple_type>::value, "! triv copy"); - static_assert(std::has_trivial_destructor<tuple_type>::value, + static_assert(std::is_trivially_destructible<tuple_type>::value, "! triv destructor"); // static_assert(std::is_standard_layout<tuple_type>::value, // "! standard layout"); diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after.cc b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after.cc index 60297551dcd..4cc1cfcf78d 100644 --- a/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after.cc +++ b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after.cc @@ -1,6 +1,6 @@ // { dg-options "-std=gnu++0x" } -// Copyright (C) 2010 Free Software Foundation, Inc. +// Copyright (C) 2010, 2012 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 @@ -34,6 +34,10 @@ test01() VERIFY( before == fl1.before_begin() ); VERIFY( end == fl1.end() ); + + // no-op just to check that debug mode does not see any problem with it. + fl1.splice_after(fl1.before_begin(), std::move(fl2), + fl2.before_begin(), fl2.begin()); } int diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after5_neg.cc b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after5_neg.cc new file mode 100644 index 00000000000..6b7d0da8815 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after5_neg.cc @@ -0,0 +1,41 @@ +// { dg-options "-std=gnu++0x" } +// { dg-require-debug-mode "" } +// { dg-do run { xfail *-*-* } } + +// Copyright (C) 2012 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 Pred 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/>. + +#include <forward_list> +#include <testsuite_allocator.h> + +void +test01() +{ + typedef __gnu_test::uneq_allocator<int> alloc_type; + + std::forward_list<int, alloc_type> fl1({1, 2, 3}, alloc_type(1)); + std::forward_list<int, alloc_type> fl2({1, 2, 3}, alloc_type(2)); + + fl1.splice_after(fl1.before_begin(), fl2); +} + +int +main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after6_neg.cc b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after6_neg.cc new file mode 100644 index 00000000000..620bb5c92cd --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after6_neg.cc @@ -0,0 +1,41 @@ +// { dg-options "-std=gnu++0x" } +// { dg-require-debug-mode "" } +// { dg-do run { xfail *-*-* } } + +// Copyright (C) 2012 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 Pred 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/>. + +#include <forward_list> +#include <testsuite_allocator.h> + +void +test01() +{ + typedef __gnu_test::uneq_allocator<int> alloc_type; + + std::forward_list<int, alloc_type> fl1({1, 2, 3}, alloc_type(1)); + std::forward_list<int, alloc_type> fl2({1, 2, 3}, alloc_type(2)); + + fl1.splice_after(fl1.before_begin(), fl2, fl2.begin()); +} + +int +main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after7_neg.cc b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after7_neg.cc new file mode 100644 index 00000000000..a2b5cfad949 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/forward_list/debug/splice_after7_neg.cc @@ -0,0 +1,41 @@ +// { dg-options "-std=gnu++0x" } +// { dg-require-debug-mode "" } +// { dg-do run { xfail *-*-* } } + +// Copyright (C) 2012 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 Pred 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/>. + +#include <forward_list> +#include <testsuite_allocator.h> + +void +test01() +{ + typedef __gnu_test::uneq_allocator<int> alloc_type; + + std::forward_list<int, alloc_type> fl1({1, 2, 3}, alloc_type(1)); + std::forward_list<int, alloc_type> fl2({1, 2, 3}, alloc_type(2)); + + fl1.splice_after(fl1.before_begin(), fl2, fl2.begin(), fl2.end()); +} + +int +main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/modifiers/6.cc b/libstdc++-v3/testsuite/23_containers/forward_list/modifiers/6.cc new file mode 100644 index 00000000000..e160381a776 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/forward_list/modifiers/6.cc @@ -0,0 +1,94 @@ +// { dg-options "-std=gnu++11" } + +// Copyright (C) 2012 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 Pred 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/>. + +#include <forward_list> + +#include <testsuite_hooks.h> + +void test01() +{ + bool test __attribute__((unused)) = true; + + std::forward_list<int> fl1(1, 5), fl2(1, 4), fl3(1, 3), + fl4(1, 2), fl5(1, 1), fl6(1, 0); + + fl1.splice_after(fl1.before_begin(), fl2); + + auto it = fl1.begin(); + + VERIFY( *it == 4 ); + + ++it; + + VERIFY( *it == 5 ); + + fl3.splice_after(fl3.before_begin(), fl4, fl4.before_begin()); + + it = fl3.begin(); + + VERIFY( *it == 2 ); + + ++it; + + VERIFY( *it == 3 ); + + fl5.splice_after(fl5.before_begin(), fl6, fl6.before_begin(), fl6.end()); + + it = fl5.begin(); + + VERIFY( *it == 0 ); + + ++it; + + VERIFY( *it == 1 ); + + fl1.merge(fl2); + + it = fl1.begin(); + + VERIFY( *it == 4 ); + + ++it; + + VERIFY( *it == 5 ); + + fl1.merge(fl3, std::less<int>()); + + it = fl1.begin(); + + VERIFY( *it == 2 ); + + ++it; + + VERIFY( *it == 3 ); + + ++it; + + VERIFY( *it == 4 ); + + ++it; + + VERIFY( *it == 5 ); +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/operations/1.cc b/libstdc++-v3/testsuite/23_containers/forward_list/operations/1.cc index 5a996f3411e..4a9e3644527 100644 --- a/libstdc++-v3/testsuite/23_containers/forward_list/operations/1.cc +++ b/libstdc++-v3/testsuite/23_containers/forward_list/operations/1.cc @@ -1,6 +1,6 @@ // { dg-options "-std=gnu++0x" } -// Copyright (C) 2008, 2009 Free Software Foundation, Inc. +// Copyright (C) 2008, 2009, 2012 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 @@ -68,7 +68,7 @@ test02() VERIFY(*befy == 10.0); ++befy; - VERIFY(*befy == 15.0); + VERIFY(*befy == 14.0); } // This test verifies the following: diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/52942.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/52942.cc new file mode 100644 index 00000000000..bf05fab0d28 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/52942.cc @@ -0,0 +1,37 @@ +// { dg-do compile } +// { dg-options "-std=gnu++11" } + +// Copyright (C) 2012 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 Pred 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/>. + +#include <unordered_map> +#include <functional> + +struct TFoo {}; + +struct TFoo_hash +{ + std::size_t operator()(const TFoo &) const { return 0; } +}; + +void f1(std::unordered_map<TFoo, int, TFoo_hash> &) {} + +void f2() +{ + std::unordered_map<TFoo, int, TFoo_hash> map1; + std::bind(f1, std::ref(map1)); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/53067.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/53067.cc new file mode 100644 index 00000000000..704f5998c0d --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_map/requirements/53067.cc @@ -0,0 +1,28 @@ +// { dg-do compile } +// { dg-options "-std=gnu++11" } + +// Copyright (C) 2012 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 Pred 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/>. + +#include <unordered_map> +#include <functional> + +void f() +{ + std::unordered_map<int, int> Foo; + ref(Foo); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc index eb16e81a4d3..ac304776cad 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc @@ -2,7 +2,7 @@ // { dg-options "-std=gnu++0x" } // { dg-require-normal-mode "" } -// Copyright (C) 2011 Free Software Foundation, Inc. +// Copyright (C) 2011, 2012 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 @@ -19,7 +19,7 @@ // with this library; see the file COPYING3. If not see // <http://www.gnu.org/licenses/>. -// { dg-error "static assertion failed" "" { target *-*-* } 185 } +// { dg-error "with noexcept" "" { target *-*-* } 248 } #include <unordered_set> @@ -35,7 +35,10 @@ namespace void test01() { - std::__unordered_set<int, hash_without_noexcept, - std::equal_to<int>, std::allocator<int>, - false> us; + using traits = std::__detail::_Hashtable_traits<false, true, true>; + using hashtable = std::__uset_hashtable<int, hash_without_noexcept, + std::equal_to<int>, + std::allocator<int>, traits>; + + hashtable ht; } diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/52942.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/52942.cc new file mode 100644 index 00000000000..067e57a5e26 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/52942.cc @@ -0,0 +1,37 @@ +// { dg-do compile } +// { dg-options "-std=gnu++11" } + +// Copyright (C) 2012 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 Pred 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/>. + +#include <unordered_set> +#include <functional> + +struct TFoo {}; + +struct TFoo_hash +{ + std::size_t operator()(const TFoo &) const { return 0; } +}; + +void f1(std::unordered_set<TFoo, TFoo_hash> &) {} + +void f2() +{ + std::unordered_set<TFoo, TFoo_hash> set1; + std::bind(f1, std::ref(set1)); +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/53067.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/53067.cc new file mode 100644 index 00000000000..760f10c7e85 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/requirements/53067.cc @@ -0,0 +1,28 @@ +// { dg-do compile } +// { dg-options "-std=gnu++11" } + +// Copyright (C) 2012 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 Pred 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/>. + +#include <unordered_set> +#include <functional> + +void f() +{ + std::unordered_set<int> Foo; + ref(Foo); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/stable_partition/moveable.cc b/libstdc++-v3/testsuite/25_algorithms/stable_partition/moveable.cc index b649b10e3cd..95d50061879 100644 --- a/libstdc++-v3/testsuite/25_algorithms/stable_partition/moveable.cc +++ b/libstdc++-v3/testsuite/25_algorithms/stable_partition/moveable.cc @@ -35,6 +35,11 @@ const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17}; const int B[] = {2, 4, 6, 8, 10, 12, 14, 16, 1, 3, 5, 7, 9, 11, 13, 15, 17}; const int N = sizeof(A) / sizeof(int); +// Check that starting with a true predicate works too. (PR52822) +const int A2[] = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17}; +const int B2[] = {2, 4, 6, 8, 10, 12, 14, 16, 3, 5, 7, 9, 11, 13, 15, 17}; +const int N2 = sizeof(A2) / sizeof(int); + struct Pred { bool @@ -42,7 +47,7 @@ struct Pred { return (x.val % 2) == 0; } }; -// 25.2.12 stable_partition() +// 25.2.12 stable_partition(), starting with a false predicate. void test01() { @@ -56,9 +61,24 @@ test01() VERIFY( std::equal(s1, s1 + N, B) ); } +// 25.2.12 stable_partition(), starting with a true predicate. +void +test02() +{ + bool test __attribute__((unused)) = true; + + rvalstruct s1[N2]; + std::copy(A2, A2 + N2, s1); + Container con(s1, s1 + N2); + + std::stable_partition(con.begin(), con.end(), Pred()); + VERIFY( std::equal(s1, s1 + N2, B2) ); +} + int main() { test01(); + test02(); return 0; } diff --git a/libstdc++-v3/testsuite/25_algorithms/stable_partition/pr52822.cc b/libstdc++-v3/testsuite/25_algorithms/stable_partition/pr52822.cc new file mode 100644 index 00000000000..c5f95f36779 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/stable_partition/pr52822.cc @@ -0,0 +1,43 @@ +// { dg-options "-std=gnu++0x" } + +// Copyright (C) 2012 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 Pred 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/>. + +// 25.2.12 [lib.alg.partitions] Partitions. + +#include <algorithm> +#include <vector> +#include <testsuite_hooks.h> + +bool true_vector_pred(const std::vector<int>&) { return true; } + +void +test01() +{ + std::vector<std::vector<int> > v(1); + v[0].push_back(7); + VERIFY( v[0].size() == 1 ); + std::stable_partition(v.begin(), v.end(), &true_vector_pred); + VERIFY( v[0].size() == 1 ); +} + +int +main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/26_numerics/cmath/51083.cc b/libstdc++-v3/testsuite/26_numerics/headers/cmath/51083.cc index 8ba9b10e5d8..8ba9b10e5d8 100644 --- a/libstdc++-v3/testsuite/26_numerics/cmath/51083.cc +++ b/libstdc++-v3/testsuite/26_numerics/headers/cmath/51083.cc diff --git a/libstdc++-v3/testsuite/Makefile.am b/libstdc++-v3/testsuite/Makefile.am index 7094ad52991..0cf8de501c8 100644 --- a/libstdc++-v3/testsuite/Makefile.am +++ b/libstdc++-v3/testsuite/Makefile.am @@ -134,7 +134,7 @@ check-DEJAGNU $(check_DEJAGNU_normal_targets): check-DEJAGNU%: site.exp normal0) \ if $(SHELL) -c "$$runtest --version" > /dev/null 2>&1; then \ $$runtest $(AM_RUNTESTFLAGS) $(RUNTESTDEFAULTFLAGS) \ - $(RUNTESTFLAGS) abi.exp; \ + $(RUNTESTFLAGS) abi.exp prettyprinters.exp; \ else echo "WARNING: could not find \`runtest'" 1>&2; :;\ fi; \ dirs="`cd $$srcdir; echo [013-9][0-9]_*/*`";; \ diff --git a/libstdc++-v3/testsuite/Makefile.in b/libstdc++-v3/testsuite/Makefile.in index 0bef85abb8c..5cf725490b5 100644 --- a/libstdc++-v3/testsuite/Makefile.in +++ b/libstdc++-v3/testsuite/Makefile.in @@ -578,7 +578,7 @@ check-DEJAGNU $(check_DEJAGNU_normal_targets): check-DEJAGNU%: site.exp normal0) \ if $(SHELL) -c "$$runtest --version" > /dev/null 2>&1; then \ $$runtest $(AM_RUNTESTFLAGS) $(RUNTESTDEFAULTFLAGS) \ - $(RUNTESTFLAGS) abi.exp; \ + $(RUNTESTFLAGS) abi.exp prettyprinters.exp; \ else echo "WARNING: could not find \`runtest'" 1>&2; :;\ fi; \ dirs="`cd $$srcdir; echo [013-9][0-9]_*/*`";; \ diff --git a/libstdc++-v3/testsuite/lib/prune.exp b/libstdc++-v3/testsuite/lib/prune.exp index a5644061d23..a2371c60d5f 100644 --- a/libstdc++-v3/testsuite/lib/prune.exp +++ b/libstdc++-v3/testsuite/lib/prune.exp @@ -32,6 +32,12 @@ proc dg-prune-output { args } { proc libstdc++-dg-prune { system text } { global additional_prunes +# send_user "Before:$text\n" + + # Ignore caret diagnostics. Unfortunately dejaGNU trims leading + # spaces, so one cannot rely on them being present. + regsub -all "(^|\n)\[^\n\]+\n *\\^\n" $text "\n" text + # Cygwin warns about -ffunction-sections regsub -all "(^|\n)\[^\n\]*: -ffunction-sections may affect debugging on some targets\[^\n\]*" $text "" text @@ -68,5 +74,6 @@ proc libstdc++-dg-prune { system text } { } } +# send_user "After:$text\n" return $text } diff --git a/libstdc++-v3/testsuite/performance/30_threads/future/polling.cc b/libstdc++-v3/testsuite/performance/30_threads/future/polling.cc index 83fde27100f..26cf632e429 100644 --- a/libstdc++-v3/testsuite/performance/30_threads/future/polling.cc +++ b/libstdc++-v3/testsuite/performance/30_threads/future/polling.cc @@ -1,4 +1,4 @@ -// Copyright (C) 2009, 2010 Free Software Foundation, Inc. +// Copyright (C) 2009, 2010, 2012 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 @@ -22,7 +22,7 @@ inline bool is_ready(std::shared_future<void>& f) { - return f.wait_for(std::chrono::microseconds(1)); + return f.wait_for(std::chrono::microseconds(1)) == std::future_status::ready; } void poll(std::shared_future<void> f) diff --git a/libstdc++-v3/testsuite/util/testsuite_abi.cc b/libstdc++-v3/testsuite/util/testsuite_abi.cc index a0294c694cd..4721ccd6042 100644 --- a/libstdc++-v3/testsuite/util/testsuite_abi.cc +++ b/libstdc++-v3/testsuite/util/testsuite_abi.cc @@ -530,7 +530,7 @@ compare_symbols(const char* baseline_file, const char* test_file, } } - cout << "\n\t\t=== libstdc++-v3 check-abi Summary ===" << endl; + cout << "\n\t\t==== libstdc++-v3 check-abi Summary ====" << endl; cout << endl; cout << "# of added symbols:\t\t " << added_names.size() << endl; cout << "# of missing symbols:\t\t " << missing_names.size() << endl; diff --git a/libstdc++-v3/testsuite/util/testsuite_common_types.h b/libstdc++-v3/testsuite/util/testsuite_common_types.h index 03be0acac25..c9be94d8f21 100644 --- a/libstdc++-v3/testsuite/util/testsuite_common_types.h +++ b/libstdc++-v3/testsuite/util/testsuite_common_types.h @@ -549,7 +549,7 @@ namespace __gnu_test typedef std::has_trivial_default_constructor<_Tp> ctor_p; static_assert(ctor_p::value, "default constructor not trivial"); - typedef std::has_trivial_destructor<_Tp> dtor_p; + typedef std::is_trivially_destructible<_Tp> dtor_p; static_assert(dtor_p::value, "destructor not trivial"); } }; |