diff options
Diffstat (limited to 'libstdc++-v3/include')
38 files changed, 1106 insertions, 558 deletions
diff --git a/libstdc++-v3/include/backward/binders.h b/libstdc++-v3/include/backward/binders.h index f98b56aaede..076f8d2e219 100644 --- a/libstdc++-v3/include/backward/binders.h +++ b/libstdc++-v3/include/backward/binders.h @@ -80,7 +80,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * * The type @c binder2nd and its creator function @c bind2nd do the same * thing, but the stored argument is passed as the second parameter instead - * of the first, e.g., @c bind2nd(std::minus<float>,1.3) will create a + * of the first, e.g., @c bind2nd(std::minus<float>(),1.3) will create a * functor whose @c operator() accepts a floating-point number, subtracts * 1.3 from it, and returns the result. (If @c bind1st had been used, * the functor would perform <em>1.3 - x</em> instead. @@ -89,10 +89,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * calling algorithms. Their return values will be temporary objects. * (The goal is to not require you to type names like * @c std::binder1st<std::plus<int>> for declaring a variable to hold the - * return value from @c bind1st(std::plus<int>,5). + * return value from @c bind1st(std::plus<int>(),5). * * These become more useful when combined with the composition functions. * + * These functions are deprecated in C++11 and can be replaced by + * @c std::bind (or @c std::tr1::bind) which is more powerful and flexible, + * supporting functions with any number of arguments. Uses of @c bind1st + * can be replaced by @c std::bind(f, x, std::placeholders::_1) and + * @c bind2nd by @c std::bind(f, std::placeholders::_1, x). * @{ */ /// One of the @link binders binder functors@endlink. diff --git a/libstdc++-v3/include/bits/atomic_base.h b/libstdc++-v3/include/bits/atomic_base.h index f0336611d3f..cf292a85385 100644 --- a/libstdc++-v3/include/bits/atomic_base.h +++ b/libstdc++-v3/include/bits/atomic_base.h @@ -93,6 +93,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #define LOCKFREE_PROP(T) (__atomic_always_lock_free (sizeof (T), 0) ? 2 : 1) +#define ATOMIC_BOOL_LOCK_FREE LOCKFREE_PROP (bool) #define ATOMIC_CHAR_LOCK_FREE LOCKFREE_PROP (char) #define ATOMIC_CHAR16_T_LOCK_FREE LOCKFREE_PROP (char16_t) #define ATOMIC_CHAR32_T_LOCK_FREE LOCKFREE_PROP (char32_t) @@ -101,7 +102,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #define ATOMIC_INT_LOCK_FREE LOCKFREE_PROP (int) #define ATOMIC_LONG_LOCK_FREE LOCKFREE_PROP (long) #define ATOMIC_LLONG_LOCK_FREE LOCKFREE_PROP (long long) - +#define ATOMIC_POINTER_LOCK_FREE LOCKFREE_PROP (void *) // Base types for atomics. template<typename _IntTp> diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h index 00f9bccd419..169daf58613 100644 --- a/libstdc++-v3/include/bits/basic_string.h +++ b/libstdc++-v3/include/bits/basic_string.h @@ -3044,7 +3044,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, string> { size_t - operator()(const string& __s) const + operator()(const string& __s) const noexcept { return std::_Hash_impl::hash(__s.data(), __s.length()); } }; @@ -3055,7 +3055,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, wstring> { size_t - operator()(const wstring& __s) const + operator()(const wstring& __s) const noexcept { return std::_Hash_impl::hash(__s.data(), __s.length() * sizeof(wchar_t)); } }; @@ -3069,7 +3069,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, u16string> { size_t - operator()(const u16string& __s) const + operator()(const u16string& __s) const noexcept { return std::_Hash_impl::hash(__s.data(), __s.length() * sizeof(char16_t)); } }; @@ -3080,7 +3080,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, u32string> { size_t - operator()(const u32string& __s) const + operator()(const u32string& __s) const noexcept { return std::_Hash_impl::hash(__s.data(), __s.length() * sizeof(char32_t)); } }; diff --git a/libstdc++-v3/include/bits/functional_hash.h b/libstdc++-v3/include/bits/functional_hash.h index e77cb4e17bf..2b82b21f716 100644 --- a/libstdc++-v3/include/bits/functional_hash.h +++ b/libstdc++-v3/include/bits/functional_hash.h @@ -66,61 +66,64 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION struct hash<_Tp*> : public __hash_base<size_t, _Tp*> { size_t - operator()(_Tp* __p) const + operator()(_Tp* __p) const noexcept { return reinterpret_cast<size_t>(__p); } }; // Explicit specializations for integer types. #define _Cxx_hashtable_define_trivial_hash(_Tp) \ template<> \ - inline size_t \ - hash<_Tp>::operator()(_Tp __val) const \ - { return static_cast<size_t>(__val); } + struct hash<_Tp> : public __hash_base<size_t, _Tp> \ + { \ + size_t \ + operator()(_Tp __val) const noexcept \ + { return static_cast<size_t>(__val); } \ + }; /// Explicit specialization for bool. - _Cxx_hashtable_define_trivial_hash(bool); + _Cxx_hashtable_define_trivial_hash(bool) /// Explicit specialization for char. - _Cxx_hashtable_define_trivial_hash(char); + _Cxx_hashtable_define_trivial_hash(char) /// Explicit specialization for signed char. - _Cxx_hashtable_define_trivial_hash(signed char); + _Cxx_hashtable_define_trivial_hash(signed char) /// Explicit specialization for unsigned char. - _Cxx_hashtable_define_trivial_hash(unsigned char); + _Cxx_hashtable_define_trivial_hash(unsigned char) /// Explicit specialization for wchar_t. - _Cxx_hashtable_define_trivial_hash(wchar_t); + _Cxx_hashtable_define_trivial_hash(wchar_t) /// Explicit specialization for char16_t. - _Cxx_hashtable_define_trivial_hash(char16_t); + _Cxx_hashtable_define_trivial_hash(char16_t) /// Explicit specialization for char32_t. - _Cxx_hashtable_define_trivial_hash(char32_t); + _Cxx_hashtable_define_trivial_hash(char32_t) /// Explicit specialization for short. - _Cxx_hashtable_define_trivial_hash(short); + _Cxx_hashtable_define_trivial_hash(short) /// Explicit specialization for int. - _Cxx_hashtable_define_trivial_hash(int); + _Cxx_hashtable_define_trivial_hash(int) /// Explicit specialization for long. - _Cxx_hashtable_define_trivial_hash(long); + _Cxx_hashtable_define_trivial_hash(long) /// Explicit specialization for long long. - _Cxx_hashtable_define_trivial_hash(long long); + _Cxx_hashtable_define_trivial_hash(long long) /// Explicit specialization for unsigned short. - _Cxx_hashtable_define_trivial_hash(unsigned short); + _Cxx_hashtable_define_trivial_hash(unsigned short) /// Explicit specialization for unsigned int. - _Cxx_hashtable_define_trivial_hash(unsigned int); + _Cxx_hashtable_define_trivial_hash(unsigned int) /// Explicit specialization for unsigned long. - _Cxx_hashtable_define_trivial_hash(unsigned long); + _Cxx_hashtable_define_trivial_hash(unsigned long) /// Explicit specialization for unsigned long long. - _Cxx_hashtable_define_trivial_hash(unsigned long long); + _Cxx_hashtable_define_trivial_hash(unsigned long long) #undef _Cxx_hashtable_define_trivial_hash @@ -162,26 +165,36 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /// Specialization for float. template<> - inline size_t - hash<float>::operator()(float __val) const + struct hash<float> : public __hash_base<size_t, float> { - // 0 and -0 both hash to zero. - return __val != 0.0f ? std::_Hash_impl::hash(__val) : 0; - } + size_t + operator()(float __val) const noexcept + { + // 0 and -0 both hash to zero. + return __val != 0.0f ? std::_Hash_impl::hash(__val) : 0; + } + }; /// Specialization for double. template<> - inline size_t - hash<double>::operator()(double __val) const + struct hash<double> : public __hash_base<size_t, double> { - // 0 and -0 both hash to zero. - return __val != 0.0 ? std::_Hash_impl::hash(__val) : 0; - } + size_t + operator()(double __val) const noexcept + { + // 0 and -0 both hash to zero. + return __val != 0.0 ? std::_Hash_impl::hash(__val) : 0; + } + }; /// Specialization for long double. template<> - _GLIBCXX_PURE size_t - hash<long double>::operator()(long double __val) const; + struct hash<long double> + : public __hash_base<size_t, long double> + { + _GLIBCXX_PURE size_t + operator()(long double __val) const noexcept; + }; // @} group hashes diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 95d06b21262..dfa91f7cc8c 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -48,7 +48,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // value type is Value. As a conforming extension, we allow for // value type != Value. - // _ExtractKey: function object that takes a object of 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 @@ -78,9 +78,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // count. If so, returns make_pair(true, n), where n is the new // bucket count. If not, returns make_pair(false, <anything>). - // ??? Right now it is hard-wired that the number of buckets never - // shrinks. Should we allow _RehashPolicy to change that? - // __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 @@ -94,6 +91,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // 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 + * - size_type _M_bucket_count + * - size_type _M_begin_bucket_index + * - size_type _M_element_count + * + * with _Bucket being _Node* and _Node: + * - _Node* _M_next + * - Tp _M_value + * - size_t _M_code if cache_hash_code is true + * + * 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 + * + * The first non-empty bucket with index _M_begin_bucket_index contains the + * first container node which is also the first bucket node whereas other + * non-empty buckets contain the node before the first bucket node. This is so + * to implement something like a std::forward_list::erase_after on container + * erase calls. + * + * Access to the bucket last element 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 no matter 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 is the first one in the bucket we must find the + * previous non-empty bucket where the previous node rely. To keep this loop + * minimal it is important that the number of bucket is not too high compared + * to the number of elements. So the hash policy must be carefully design so + * that it computes a bucket count large enough to respect the user defined + * load factor but also not too large to limit impact on the insert operation. + * + * 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. + * + * _M_begin_bucket_index is used to offer contant time access to the container + * begin iterator. + */ template<typename _Key, typename _Value, typename _Allocator, typename _ExtractKey, typename _Equal, @@ -130,6 +174,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __constant_iterators, __unique_keys> > { + static_assert(__or_<integral_constant<bool, __cache_hash_code>, + __detail::__is_noexcept_hash<_Key, _H1>>::value, + "Cache the hash code or qualify your hash functor with noexcept"); public: typedef _Allocator allocator_type; typedef _Value value_type; @@ -152,30 +199,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __cache_hash_code> const_local_iterator; - typedef __detail::_Hashtable_iterator<value_type, __constant_iterators, - __cache_hash_code> - iterator; - typedef __detail::_Hashtable_const_iterator<value_type, - __constant_iterators, - __cache_hash_code> - const_iterator; + typedef local_iterator iterator; + typedef const_local_iterator const_iterator; template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2, typename _Hashtable2> friend struct __detail::_Map_base; private: + typedef typename _RehashPolicy::_State _RehashPolicyState; typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node; typedef typename _Allocator::template rebind<_Node>::other _Node_allocator_type; - typedef typename _Allocator::template rebind<_Node*>::other + typedef _Node* _Bucket; + //typedef __detail::_Bucket<_Value, __cache_hash_code> _Bucket; + typedef typename _Allocator::template rebind<_Bucket>::other _Bucket_allocator_type; typedef typename _Allocator::template rebind<_Value>::other _Value_allocator_type; _Node_allocator_type _M_node_allocator; - _Node** _M_buckets; + _Bucket* _M_buckets; size_type _M_bucket_count; size_type _M_begin_bucket_index; // First non-empty bucket. size_type _M_element_count; @@ -188,14 +233,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _M_deallocate_node(_Node* __n); + // Deallocate all nodes contained in the bucket array, buckets' nodes + // are not linked to each other + void + _M_deallocate_nodes(_Bucket*, size_type); + + // Deallocate the linked list of nodes pointed to by __n void - _M_deallocate_nodes(_Node**, size_type); + _M_deallocate_nodes(_Node* __n); - _Node** + _Bucket* _M_allocate_buckets(size_type __n); void - _M_deallocate_buckets(_Node**, size_type __n); + _M_deallocate_buckets(_Bucket*, size_type __n); + + // Gets bucket begin dealing with the difference between first non-empty + // bucket containing the first container node and the other non-empty + // buckets containing the node before the one belonging to the bucket. + _Node* + _M_bucket_begin(size_type __bkt) const; + + // Gets the bucket last node if any + _Node* + _M_bucket_end(size_type __bkt) const; + + // Gets the bucket node after the last if any + _Node* + _M_bucket_past_the_end(size_type __bkt) const + { + _Node* __end = _M_bucket_end(__bkt); + return __end ? __end->_M_next : nullptr; + } public: // Constructor, destructor, assignment, swap @@ -240,27 +309,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Basic container operations iterator begin() noexcept - { return iterator(_M_buckets + _M_begin_bucket_index); } + { return iterator(_M_buckets[_M_begin_bucket_index]); } const_iterator begin() const noexcept - { return const_iterator(_M_buckets + _M_begin_bucket_index); } + { return const_iterator(_M_buckets[_M_begin_bucket_index]); } iterator end() noexcept - { return iterator(_M_buckets + _M_bucket_count); } + { return iterator(nullptr); } const_iterator end() const noexcept - { return const_iterator(_M_buckets + _M_bucket_count); } + { return const_iterator(nullptr); } const_iterator cbegin() const noexcept - { return const_iterator(_M_buckets + _M_begin_bucket_index); } + { return const_iterator(_M_buckets[_M_begin_bucket_index]); } const_iterator cend() const noexcept - { return const_iterator(_M_buckets + _M_bucket_count); } + { return const_iterator(nullptr); } size_type size() const noexcept @@ -307,28 +376,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION local_iterator begin(size_type __n) - { return local_iterator(_M_buckets[__n]); } + { return local_iterator(_M_bucket_begin(__n)); } local_iterator - end(size_type) - { return local_iterator(0); } + end(size_type __n) + { return local_iterator(_M_bucket_past_the_end(__n)); } const_local_iterator begin(size_type __n) const - { return const_local_iterator(_M_buckets[__n]); } + { return const_local_iterator(_M_bucket_begin(__n)); } const_local_iterator - end(size_type) const - { return const_local_iterator(0); } + end(size_type __n) const + { return const_local_iterator(_M_bucket_past_the_end(__n)); } // DR 691. const_local_iterator cbegin(size_type __n) const - { return const_local_iterator(_M_buckets[__n]); } + { return const_local_iterator(_M_bucket_begin(__n)); } const_local_iterator - cend(size_type) const - { return const_local_iterator(0); } + cend(size_type __n) const + { return const_local_iterator(_M_bucket_past_the_end(__n)); } float load_factor() const noexcept @@ -366,9 +435,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION private: // Find and insert helper functions and types _Node* - _M_find_node(_Node*, const key_type&, + _M_find_node(size_type, const key_type&, typename _Hashtable::_Hash_code_type) const; + // Insert a node in an empty bucket + void + _M_insert_bucket_begin(size_type, _Node*); + + // Insert a node after an other one in a non-empty bucket + void + _M_insert_after(size_type, _Node*, _Node*); + + // Remove the bucket first node + void + _M_remove_bucket_begin(size_type __bkt, _Node* __next_n, + size_type __next_bkt); + + // Get the node before __n in the bucket __bkt + _Node* + _M_get_previous_node(size_type __bkt, _Node* __n); + template<typename _Arg> iterator _M_insert_bucket(_Arg&&, size_type, @@ -432,6 +518,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION iterator erase(const_iterator); + // LWG 2059. + iterator + erase(iterator __it) + { return erase(const_iterator(__it)); } + size_type erase(const key_type&); @@ -449,8 +540,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION private: // Unconditionally change size of bucket array to n, restore hash policy - // resize value to __next_resize on exception. - void _M_rehash(size_type __n, size_type __next_resize); + // state to __state on exception. + void _M_rehash(size_type __n, const _RehashPolicyState& __state); }; @@ -471,7 +562,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __try { _M_node_allocator.construct(__n, std::forward<_Args>(__args)...); - __n->_M_next = 0; return __n; } __catch(...) @@ -501,18 +591,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_deallocate_nodes(_Node** __array, size_type __n) + _M_deallocate_nodes(_Bucket* __buckets, size_type __n) + { + for (size_type __i = 0; __i != __n; ++__i) + _M_deallocate_nodes(__buckets[__i]); + } + + 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> + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_deallocate_nodes(_Node* __n) { - for (size_type __i = 0; __i < __n; ++__i) + while (__n) { - _Node* __p = __array[__i]; - while (__p) - { - _Node* __tmp = __p; - __p = __p->_M_next; - _M_deallocate_node(__tmp); - } - __array[__i] = 0; + _Node* __tmp = __n; + __n = __n->_M_next; + _M_deallocate_node(__tmp); } } @@ -522,18 +620,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION bool __chc, bool __cit, bool __uk> typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, - __chc, __cit, __uk>::_Node** + __chc, __cit, __uk>::_Bucket* _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: _M_allocate_buckets(size_type __n) { _Bucket_allocator_type __alloc(_M_node_allocator); - // We allocate one extra bucket to hold a sentinel, an arbitrary - // non-null pointer. Iterator increment relies on this. - _Node** __p = __alloc.allocate(__n + 1); - std::fill(__p, __p + __n, (_Node*) 0); - __p[__n] = reinterpret_cast<_Node*>(0x1000); + // We allocate one extra bucket to have _M_begin_bucket_index + // point to it as long as container is empty + _Bucket* __p = __alloc.allocate(__n + 1); + __builtin_memset(__p, 0, (__n + 1) * sizeof(_Bucket)); return __p; } @@ -544,7 +641,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_deallocate_buckets(_Node** __p, size_type __n) + _M_deallocate_buckets(_Bucket* __p, size_type __n) { _Bucket_allocator_type __alloc(_M_node_allocator); __alloc.deallocate(__p, __n + 1); @@ -554,6 +651,44 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Allocator, 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>::_Node* + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_bucket_begin(size_type __bkt) const + { + if (__bkt == _M_begin_bucket_index) + return _M_buckets[__bkt]; + _Node* __n = _M_buckets[__bkt]; + return __n ? __n->_M_next : nullptr; + } + + 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> + 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>:: + _M_bucket_end(size_type __bkt) const + { + _Node* __n = _M_bucket_begin(__bkt); + if (__n) + for (;; __n = __n->_M_next) + if (!__n->_M_next + || this->_M_bucket_index(__n->_M_next, _M_bucket_count) + != __bkt) + break; + return __n; + } + + 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> _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: _Hashtable(size_type __bucket_hint, @@ -571,6 +706,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _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. + _M_rehash_policy._M_prev_resize = 0; _M_buckets = _M_allocate_buckets(_M_bucket_count); _M_begin_bucket_index = _M_bucket_count; } @@ -602,6 +740,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. + _M_rehash_policy._M_prev_resize = 0; _M_buckets = _M_allocate_buckets(_M_bucket_count); _M_begin_bucket_index = _M_bucket_count; __try @@ -637,17 +779,41 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_buckets = _M_allocate_buckets(_M_bucket_count); __try { - for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i) + const _Node* __ht_n = __ht._M_buckets[__ht._M_begin_bucket_index]; + if (!__ht_n) + return; + + // Note that the copy constructor do not rely on hash code usage. + // First deal with the special first node that is directly store in + // the first non-empty bucket + _Node* __this_n = _M_allocate_node(__ht_n->_M_v); + this->_M_copy_code(__this_n, __ht_n); + _M_buckets[_M_begin_bucket_index] = __this_n; + __ht_n = __ht_n->_M_next; + // Second deal with following non-empty buckets containing previous + // nodes node. + for (size_type __i = __ht._M_begin_bucket_index + 1; + __i != __ht._M_bucket_count; ++__i) { - _Node* __n = __ht._M_buckets[__i]; - _Node** __tail = _M_buckets + __i; - while (__n) + if (!__ht._M_buckets[__i]) + continue; + + for (; __ht_n != __ht._M_buckets[__i]->_M_next; + __ht_n = __ht_n->_M_next) { - *__tail = _M_allocate_node(__n->_M_v); - this->_M_copy_code(*__tail, __n); - __tail = &((*__tail)->_M_next); - __n = __n->_M_next; + __this_n->_M_next = _M_allocate_node(__ht_n->_M_v); + this->_M_copy_code(__this_n->_M_next, __ht_n); + __this_n = __this_n->_M_next; } + + _M_buckets[__i] = __this_n; + } + // Last finalize copy of the nodes of the last non-empty bucket + for (; __ht_n; __ht_n = __ht_n->_M_next) + { + __this_n->_M_next = _M_allocate_node(__ht_n->_M_v); + this->_M_copy_code(__this_n->_M_next, __ht_n); + __this_n = __this_n->_M_next; } } __catch(...) @@ -732,8 +898,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __rehash_policy(const _RehashPolicy& __pol) { size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); - if (__n_bkt > _M_bucket_count) - _M_rehash(__n_bkt, _M_rehash_policy._M_next_resize); + if (__n_bkt != _M_bucket_count) + _M_rehash(__n_bkt, _M_rehash_policy._M_state()); _M_rehash_policy = __pol; } @@ -750,8 +916,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); - _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); - return __p ? iterator(__p, _M_buckets + __n) : this->end(); + _Node* __p = _M_find_node(__n, __k, __code); + return __p ? iterator(__p) : this->end(); } template<typename _Key, typename _Value, @@ -767,8 +933,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); - _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); - return __p ? const_iterator(__p, _M_buckets + __n) : this->end(); + _Node* __p = _M_find_node(__n, __k, __code); + return __p ? const_iterator(__p) : this->end(); } template<typename _Key, typename _Value, @@ -784,10 +950,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + _Node* __p = _M_bucket_begin(__n); + if (!__p) + return 0; + std::size_t __result = 0; - for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next) - if (this->_M_compare(__k, __code, __p)) - ++__result; + for (;; __p = __p->_M_next) + { + if (this->_M_compare(__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. + break; + if (!__p->_M_next + || this->_M_bucket_index(__p->_M_next, _M_bucket_count) + != __n) + break; + } return __result; } @@ -809,21 +990,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); - _Node** __head = _M_buckets + __n; - _Node* __p = _M_find_node(*__head, __k, __code); + _Node* __p = _M_find_node(__n, __k, __code); if (__p) { _Node* __p1 = __p->_M_next; - for (; __p1; __p1 = __p1->_M_next) - if (!this->_M_compare(__k, __code, __p1)) - break; + while (__p1 + && this->_M_bucket_index(__p1, _M_bucket_count) == __n + && this->_M_compare(__k, __code, __p1)) + __p1 = __p1->_M_next; - iterator __first(__p, __head); - iterator __last(__p1, __head); - if (!__p1) - __last._M_incr_bucket(); - return std::make_pair(__first, __last); + return std::make_pair(iterator(__p), iterator(__p1)); } else return std::make_pair(this->end(), this->end()); @@ -847,28 +1024,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); - _Node** __head = _M_buckets + __n; - _Node* __p = _M_find_node(*__head, __k, __code); + _Node* __p = _M_find_node(__n, __k, __code); if (__p) { _Node* __p1 = __p->_M_next; - for (; __p1; __p1 = __p1->_M_next) - if (!this->_M_compare(__k, __code, __p1)) - break; + while (__p1 + && this->_M_bucket_index(__p1, _M_bucket_count) == __n + && this->_M_compare(__k, __code, __p1)) + __p1 = __p1->_M_next; - const_iterator __first(__p, __head); - const_iterator __last(__p1, __head); - if (!__p1) - __last._M_incr_bucket(); - return std::make_pair(__first, __last); + return std::make_pair(const_iterator(__p), const_iterator(__p1)); } else return std::make_pair(this->end(), this->end()); } - // Find the node whose key compares equal to k, beginning the search - // at p (usually the head of a bucket). Return nil 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 _H1, typename _H2, typename _Hash, typename _RehashPolicy, @@ -878,13 +1051,131 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __chc, __cit, __uk>::_Node* _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_find_node(_Node* __p, const key_type& __k, + _M_find_node(size_type __n, const key_type& __k, typename _Hashtable::_Hash_code_type __code) const { - for (; __p; __p = __p->_M_next) - if (this->_M_compare(__k, __code, __p)) - return __p; - return false; + _Node* __p = _M_bucket_begin(__n); + if (!__p) + return nullptr; + for (;; __p = __p->_M_next) + { + if (this->_M_compare(__k, __code, __p)) + return __p; + if (!(__p->_M_next) + || this->_M_bucket_index(__p->_M_next, _M_bucket_count) != __n) + break; + } + return nullptr; + } + + 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> + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_insert_bucket_begin(size_type __bkt, _Node* __new_node) + { + _Node* __prev_n; + if (__bkt < _M_begin_bucket_index) + { + if (_M_begin_bucket_index != _M_bucket_count) + { + __new_node->_M_next = _M_buckets[_M_begin_bucket_index]; + _M_buckets[_M_begin_bucket_index] = __new_node; + } + __prev_n = __new_node; + _M_begin_bucket_index = __bkt; + } + else + { + // We need to find previous non-empty bucket to link the new node. + // There are several ways to find this previous bucket: + // 1. Move backward until we find it (the current method) + // 2. Start from the begin bucket index and move forward until we + // cross __n position. + // 3. Move forward until we find a non-empty bucket that will + // contain the previous node. + size_type __prev_bkt; + for (__prev_bkt = __bkt; __prev_bkt-- != 0;) + if (_M_buckets[__prev_bkt]) + break; + __prev_n = _M_bucket_end(__prev_bkt); + _M_insert_after(__prev_bkt, __prev_n, __new_node); + } + _M_buckets[__bkt] = __prev_n; + } + + 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> + void + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_insert_after(size_type __bkt, _Node* __prev_n, _Node* __new_n) + { + if (__prev_n->_M_next) + { + size_type __next_bkt = + this->_M_bucket_index(__prev_n->_M_next, _M_bucket_count); + if (__next_bkt != __bkt) + _M_buckets[__next_bkt] = __new_n; + } + __new_n->_M_next = __prev_n->_M_next; + __prev_n->_M_next = __new_n; + } + + 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> + 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) + { + if (!__next || __next_bkt != __bkt) + { + // Bucket is now empty + if (__next && __next_bkt != __bkt) + // Update next non-empty bucket before begin node + _M_buckets[__next_bkt] = _M_buckets[__bkt]; + _M_buckets[__bkt] = nullptr; + if (__bkt == _M_begin_bucket_index) + // We need to update begin bucket index + if (__next) + { + _M_begin_bucket_index = __next_bkt; + _M_buckets[_M_begin_bucket_index] = __next; + } + else + _M_begin_bucket_index = _M_bucket_count; + } + else if (__bkt == _M_begin_bucket_index) + _M_buckets[__bkt] = __next; + } + + 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> + 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>:: + _M_get_previous_node(size_type __bkt, _Node* __n) + { + _Node* __prev_n = nullptr; + if (__bkt != _M_begin_bucket_index || __n != _M_buckets[__bkt]) + { + __prev_n = _M_buckets[__bkt]; + while (__prev_n->_M_next != __n) + __prev_n = __prev_n->_M_next; + } + return __prev_n; } // Insert v in bucket n (assumes no element with its key already present). @@ -901,7 +1192,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_insert_bucket(_Arg&& __v, size_type __n, typename _Hashtable::_Hash_code_type __code) { - const size_type __saved_next_resize = _M_rehash_policy._M_next_resize; + 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, 1); @@ -912,27 +1203,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __n = this->_M_bucket_index(__k, __code, __do_rehash.second); } - _Node* __new_node = 0; + _Node* __new_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); if (__do_rehash.first) - _M_rehash(__do_rehash.second, __saved_next_resize); + _M_rehash(__do_rehash.second, __saved_state); - __new_node->_M_next = _M_buckets[__n]; - this->_M_store_code(__new_node, __code); - _M_buckets[__n] = __new_node; + if (_M_buckets[__n]) + _M_insert_after(__n, _M_buckets[__n], __new_node); + else + _M_insert_bucket_begin(__n, __new_node); ++_M_element_count; - if (__n < _M_begin_bucket_index) - _M_begin_bucket_index = __n; - return iterator(__new_node, _M_buckets + __n); + return iterator(__new_node); } __catch(...) { if (!__new_node) - _M_rehash_policy._M_next_resize = __saved_next_resize; + _M_rehash_policy._M_reset(__saved_state); else _M_deallocate_node(__new_node); __throw_exception_again; @@ -957,8 +1248,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); - if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code)) - return std::make_pair(iterator(__p, _M_buckets + __n), false); + if (_Node* __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); } @@ -976,37 +1267,58 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: _M_insert(_Arg&& __v, std::false_type) { - const size_type __saved_next_resize = _M_rehash_policy._M_next_resize; + 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, 1); - if (__do_rehash.first) - _M_rehash(__do_rehash.second, __saved_next_resize); const key_type& __k = this->_M_extract(__v); typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); // First find the node, avoid leaking new_node if compare throws. - _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code); - _Node* __new_node = _M_allocate_node(std::forward<_Arg>(__v)); - - if (__prev) + _Node* __prev = _M_find_node(__n, __k, __code); + _Node* __new_node = nullptr; + __try { - __new_node->_M_next = __prev->_M_next; - __prev->_M_next = __new_node; + // 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); + if (__do_rehash.first) + { + _M_rehash(__do_rehash.second, __saved_state); + __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + // __prev is still valid because rehash do not invalidate nodes + } + + if (__prev) + // Insert after the previous equivalent node + _M_insert_after(__n, __prev, __new_node); + else if (_M_buckets[__n]) + // Bucket is not empty and the inserted node has no equivalent in + // the hashtable. We must insert the new node at the beginning or + // end of the bucket to preserve equivalent elements relative + // positions. + if (__n != _M_begin_bucket_index) + // We insert the new node at the beginning + _M_insert_after(__n, _M_buckets[__n], __new_node); + else + // We insert the new node at the end + _M_insert_after(__n, _M_bucket_end(__n), __new_node); + else + _M_insert_bucket_begin(__n, __new_node); + ++_M_element_count; + return iterator(__new_node); } - else + __catch(...) { - __new_node->_M_next = _M_buckets[__n]; - _M_buckets[__n] = __new_node; - if (__n < _M_begin_bucket_index) - _M_begin_bucket_index = __n; + if (!__new_node) + _M_rehash_policy._M_reset(__saved_state); + else + _M_deallocate_node(__new_node); + __throw_exception_again; } - this->_M_store_code(__new_node, __code); - ++_M_element_count; - return iterator(__new_node, _M_buckets + __n); } template<typename _Key, typename _Value, @@ -1020,12 +1332,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION insert(_InputIterator __first, _InputIterator __last) { size_type __n_elt = __detail::__distance_fw(__first, __last); - const size_type __saved_next_resize = _M_rehash_policy._M_next_resize; + 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_next_resize); + _M_rehash(__do_rehash.second, __saved_state); for (; __first != __last; ++__first) this->insert(*__first); @@ -1042,31 +1354,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: erase(const_iterator __it) { - iterator __result(__it._M_cur_node, __it._M_cur_bucket); - ++__result; - - _Node* __cur = *__it._M_cur_bucket; - if (__cur == __it._M_cur_node) + _Node* __n = __it._M_cur; + std::size_t __bkt = this->_M_bucket_index(__n, _M_bucket_count); + + // Look for previous node to unlink it from the erased one, this is why + // we need buckets to contain the before begin node of the bucket to make + // this research fast. + _Node* __prev_n = _M_get_previous_node(__bkt, __n); + if (__n == _M_bucket_begin(__bkt)) + _M_remove_bucket_begin(__bkt, __n->_M_next, + __n->_M_next ? this->_M_bucket_index(__n->_M_next, _M_bucket_count) + : 0); + else if (__n->_M_next) { - *__it._M_cur_bucket = __cur->_M_next; - - // If _M_begin_bucket_index no longer indexes the first non-empty - // bucket - its single node is being erased - update it. - if (!_M_buckets[_M_begin_bucket_index]) - _M_begin_bucket_index = __result._M_cur_bucket - _M_buckets; - } - else - { - _Node* __next = __cur->_M_next; - while (__next != __it._M_cur_node) - { - __cur = __next; - __next = __cur->_M_next; - } - __cur->_M_next = __next->_M_next; + size_type __next_bkt = + this->_M_bucket_index(__n->_M_next, _M_bucket_count); + if (__next_bkt != __bkt) + _M_buckets[__next_bkt] = __prev_n; } - _M_deallocate_node(__it._M_cur_node); + if (__prev_n) + __prev_n->_M_next = __n->_M_next; + iterator __result(__n->_M_next); + _M_deallocate_node(__n); --_M_element_count; return __result; @@ -1084,64 +1394,65 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION erase(const key_type& __k) { typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); - std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); - size_type __result = 0; - - _Node** __slot = _M_buckets + __n; - while (*__slot && !this->_M_compare(__k, __code, *__slot)) - __slot = &((*__slot)->_M_next); + std::size_t __bkt = this->_M_bucket_index(__k, __code, _M_bucket_count); + // Look for the first matching node with its previous node at the same + // time + _Node* __n = _M_buckets[__bkt]; + if (!__n) + return 0; + _Node* __prev_n = nullptr; + if (__bkt != _M_begin_bucket_index) + { + __prev_n = __n; + __n = __n->_M_next; + } + bool __is_bucket_begin = true; + for (;; __prev_n = __n, __n = __n->_M_next) + { + if (this->_M_compare(__k, __code, __n)) + break; + if (!(__n->_M_next) + || this->_M_bucket_index(__n->_M_next, _M_bucket_count) != __bkt) + return 0; + __is_bucket_begin = false; + } - _Node** __saved_slot = 0; - while (*__slot && this->_M_compare(__k, __code, *__slot)) + // We found a matching node, start deallocation loop from it + std::size_t __next_bkt = __bkt; + _Node* __next_n = __n; + size_type __result = 0; + _Node* __saved_n = nullptr; + do { + _Node* __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? - if (std::__addressof(this->_M_extract((*__slot)->_M_v)) + if (std::__addressof(this->_M_extract(__p->_M_v)) != std::__addressof(__k)) - { - _Node* __p = *__slot; - *__slot = __p->_M_next; - _M_deallocate_node(__p); - --_M_element_count; - ++__result; - } + _M_deallocate_node(__p); else - { - __saved_slot = __slot; - __slot = &((*__slot)->_M_next); - } - } - - if (__saved_slot) - { - _Node* __p = *__saved_slot; - *__saved_slot = __p->_M_next; - _M_deallocate_node(__p); + __saved_n = __p; --_M_element_count; ++__result; + if (!__next_n) + break; + __next_bkt = this->_M_bucket_index(__next_n, _M_bucket_count); } - - // If the entire bucket indexed by _M_begin_bucket_index has been - // erased look forward for the first non-empty bucket. - if (!_M_buckets[_M_begin_bucket_index]) - { - if (!_M_element_count) - _M_begin_bucket_index = _M_bucket_count; - else - { - ++_M_begin_bucket_index; - while (!_M_buckets[_M_begin_bucket_index]) - ++_M_begin_bucket_index; - } - } - + while (__next_bkt == __bkt && this->_M_compare(__k, __code, __next_n)); + + if (__saved_n) + _M_deallocate_node(__saved_n); + if (__is_bucket_begin) + _M_remove_bucket_begin(__bkt, __next_n, __next_bkt); + else if (__next_n && __next_bkt != __bkt) + _M_buckets[__next_bkt] = __prev_n; + if (__prev_n) + __prev_n->_M_next = __next_n; return __result; } - // ??? This could be optimized by taking advantage of the bucket - // structure, but it's not clear that it's worth doing. It probably - // wouldn't even be an optimization unless the load factor is large. template<typename _Key, typename _Value, typename _Allocator, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, @@ -1153,9 +1464,42 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: erase(const_iterator __first, const_iterator __last) { - while (__first != __last) - __first = this->erase(__first); - return iterator(__last._M_cur_node, __last._M_cur_bucket); + _Node* __n = __first._M_cur; + _Node* __last_n = __last._M_cur; + if (__n == __last_n) + return iterator(__n); + + std::size_t __bkt = this->_M_bucket_index(__n, _M_bucket_count); + + _Node* __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; + __n = __n->_M_next; + _M_deallocate_node(__tmp); + --_M_element_count; + if (!__n) + break; + __n_bkt = this->_M_bucket_index(__n, _M_bucket_count); + } + while (__n != __last_n && __n_bkt == __bkt); + if (__is_bucket_begin) + _M_remove_bucket_begin(__bkt, __n, __n_bkt); + if (__n == __last_n) + break; + __is_bucket_begin = true; + __bkt = __n_bkt; + } + + if (__n && __n_bkt != __bkt) + _M_buckets[__n_bkt] = __prev_n; + if (__prev_n) + __prev_n->_M_next = __n; + return iterator(__n); } template<typename _Key, typename _Value, @@ -1167,7 +1511,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: clear() noexcept { - _M_deallocate_nodes(_M_buckets, _M_bucket_count); + _M_deallocate_nodes(_M_buckets[_M_begin_bucket_index]); + __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(_Bucket)); _M_element_count = 0; _M_begin_bucket_index = _M_bucket_count; } @@ -1181,11 +1526,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: rehash(size_type __n) { - const size_type __saved_next_resize = _M_rehash_policy._M_next_resize; + const _RehashPolicyState& __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)), - __saved_next_resize); + __saved_state); } template<typename _Key, typename _Value, @@ -1195,46 +1540,75 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: - _M_rehash(size_type __n, size_type __next_resize) + _M_rehash(size_type __n, const _RehashPolicyState& __state) { - _Node** __new_array = 0; + _Bucket* __new_buckets = nullptr; + _Node* __p = _M_buckets[_M_begin_bucket_index]; __try { - __new_array = _M_allocate_buckets(__n); + __new_buckets = _M_allocate_buckets(__n); + // First loop to store each node in its new bucket + while (__p) + { + _Node* __next = __p->_M_next; + std::size_t __new_index = this->_M_bucket_index(__p, __n); + if (!__new_buckets[__new_index]) + // Store temporarily bucket end node in _M_buckets if possible. + // This will boost second loop where we need to access bucket + // end node quickly. + if (__new_index < _M_bucket_count) + _M_buckets[__new_index] = __p; + __p->_M_next = __new_buckets[__new_index]; + __new_buckets[__new_index] = __p; + __p = __next; + } _M_begin_bucket_index = __n; - for (size_type __i = 0; __i < _M_bucket_count; ++__i) - while (_Node* __p = _M_buckets[__i]) + _Node* __prev_node = nullptr; + // Second loop to link all nodes together and to fix bucket values so + // that they contain the before begin node of the bucket. + for (size_type __i = 0; __i != __n; ++__i) + if (__new_buckets[__i]) { - std::size_t __new_index = this->_M_bucket_index(__p, __n); - _M_buckets[__i] = __p->_M_next; - __p->_M_next = __new_array[__new_index]; - __new_array[__new_index] = __p; - if (__new_index < _M_begin_bucket_index) - _M_begin_bucket_index = __new_index; + if (__prev_node) + { + __prev_node->_M_next = __new_buckets[__i]; + __new_buckets[__i] = __prev_node; + } + else + _M_begin_bucket_index = __i; + if (__i < _M_bucket_count) + __prev_node = _M_buckets[__i]; + else + { + __prev_node = __new_buckets[__i]; + while (__prev_node->_M_next) + __prev_node = __prev_node->_M_next; + } } _M_deallocate_buckets(_M_buckets, _M_bucket_count); _M_bucket_count = __n; - _M_buckets = __new_array; + _M_buckets = __new_buckets; } __catch(...) { - if (__new_array) + if (__new_buckets) { // A failure here means that a hash function threw an exception. // We can't restore the previous state without calling the hash // function again, so the only sensible recovery is to delete // everything. - _M_deallocate_nodes(__new_array, __n); - _M_deallocate_buckets(__new_array, __n); - _M_deallocate_nodes(_M_buckets, _M_bucket_count); + _M_deallocate_nodes(__new_buckets, __n); + _M_deallocate_buckets(__new_buckets, __n); + _M_deallocate_nodes(__p); + __builtin_memset(_M_buckets, 0, sizeof(_Bucket) * _M_bucket_count); _M_element_count = 0; _M_begin_bucket_index = _M_bucket_count; - _M_rehash_policy._M_next_resize = 0; + _M_rehash_policy._M_reset(_RehashPolicyState()); } else // A failure here means that buckets allocation failed. We only // have to restore hash policy previous state. - _M_rehash_policy._M_next_resize = __next_resize; + _M_rehash_policy._M_reset(__state); __throw_exception_again; } } diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index acb7e99a8df..44c749af515 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -59,6 +59,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return __distance_fw(__first, __last, _Tag()); } + // Helper type used to detect when the hash functor is noexcept qualified or + // not + 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 // and iterators. @@ -211,155 +218,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } }; - template<typename _Value, bool __cache> - struct _Hashtable_iterator_base - { - _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node, - _Hash_node<_Value, __cache>** __bucket) - : _M_cur_node(__node), _M_cur_bucket(__bucket) { } - - void - _M_incr() - { - _M_cur_node = _M_cur_node->_M_next; - if (!_M_cur_node) - _M_incr_bucket(); - } - - void - _M_incr_bucket(); - - _Hash_node<_Value, __cache>* _M_cur_node; - _Hash_node<_Value, __cache>** _M_cur_bucket; - }; - - // Global iterators, used for arbitrary iteration within a hash - // table. Larger and more expensive than local iterators. - template<typename _Value, bool __cache> - void - _Hashtable_iterator_base<_Value, __cache>:: - _M_incr_bucket() - { - ++_M_cur_bucket; - - // This loop requires the bucket array to have a non-null sentinel. - while (!*_M_cur_bucket) - ++_M_cur_bucket; - _M_cur_node = *_M_cur_bucket; - } - - template<typename _Value, bool __cache> - inline bool - operator==(const _Hashtable_iterator_base<_Value, __cache>& __x, - const _Hashtable_iterator_base<_Value, __cache>& __y) - { return __x._M_cur_node == __y._M_cur_node; } - - template<typename _Value, bool __cache> - inline bool - operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x, - const _Hashtable_iterator_base<_Value, __cache>& __y) - { return __x._M_cur_node != __y._M_cur_node; } - - template<typename _Value, bool __constant_iterators, bool __cache> - struct _Hashtable_iterator - : public _Hashtable_iterator_base<_Value, __cache> - { - 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; - - _Hashtable_iterator() - : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } - - _Hashtable_iterator(_Hash_node<_Value, __cache>* __p, - _Hash_node<_Value, __cache>** __b) - : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } - - explicit - _Hashtable_iterator(_Hash_node<_Value, __cache>** __b) - : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } - - reference - operator*() const - { return this->_M_cur_node->_M_v; } - - pointer - operator->() const - { return std::__addressof(this->_M_cur_node->_M_v); } - - _Hashtable_iterator& - operator++() - { - this->_M_incr(); - return *this; - } - - _Hashtable_iterator - operator++(int) - { - _Hashtable_iterator __tmp(*this); - this->_M_incr(); - return __tmp; - } - }; - - template<typename _Value, bool __constant_iterators, bool __cache> - struct _Hashtable_const_iterator - : public _Hashtable_iterator_base<_Value, __cache> - { - 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; - - _Hashtable_const_iterator() - : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } - - _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p, - _Hash_node<_Value, __cache>** __b) - : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } - - explicit - _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b) - : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } - - _Hashtable_const_iterator(const _Hashtable_iterator<_Value, - __constant_iterators, __cache>& __x) - : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node, - __x._M_cur_bucket) { } - - reference - operator*() const - { return this->_M_cur_node->_M_v; } - - pointer - operator->() const - { return std::__addressof(this->_M_cur_node->_M_v); } - - _Hashtable_const_iterator& - operator++() - { - this->_M_incr(); - return *this; - } - - _Hashtable_const_iterator - operator++(int) - { - _Hashtable_const_iterator __tmp(*this); - this->_M_incr(); - return __tmp; - } - }; - - // Many of class template _Hashtable's template parameters are policy // classes. These are defaults for the policies. @@ -388,7 +246,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION struct _Prime_rehash_policy { _Prime_rehash_policy(float __z = 1.0) - : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) { } + : _M_max_load_factor(__z), _M_prev_resize(0), _M_next_resize(0) { } float max_load_factor() const noexcept @@ -410,10 +268,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, std::size_t __n_ins) const; + typedef std::pair<std::size_t, std::size_t> _State; + + _State + _M_state() const + { return std::make_pair(_M_prev_resize, _M_next_resize); } + + void + _M_reset(const _State& __state) + { + _M_prev_resize = __state.first; + _M_next_resize = __state.second; + } + enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 }; float _M_max_load_factor; - float _M_growth_factor; + mutable std::size_t _M_prev_resize; mutable std::size_t _M_next_resize; }; @@ -429,15 +300,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { // Optimize lookups involving the first elements of __prime_list. // (useful to speed-up, eg, constructors) - static const unsigned char __fast_bkt[12] + static const unsigned long __fast_bkt[12] = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 }; - const unsigned long __p - = __n <= 11 ? __fast_bkt[__n] - : *std::lower_bound(__prime_list + 5, - __prime_list + _S_n_primes, __n); - _M_next_resize = __builtin_floor(__p * (long double)_M_max_load_factor); - return __p; + const unsigned long* __p + = __n <= 11 ? __fast_bkt + __n + : std::lower_bound(__prime_list + 5, + __prime_list + _S_n_primes, __n); + + _M_prev_resize = __builtin_floor(*__p * (long double)_M_max_load_factor); + if (__p != __fast_bkt) + _M_prev_resize = std::min(_M_prev_resize, + static_cast<std::size_t>(*(__p - 1))); + // Lets guaranty a minimal grow step of 11: + if (*__p - __n < 11) + __p = std::lower_bound(__prime_list + 5, + __prime_list + _S_n_primes, __n + 11); + _M_next_resize = __builtin_floor(*__p * (long double)_M_max_load_factor); + return *__p; } // Return the smallest prime p such that alpha p >= n, where alpha @@ -461,17 +341,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, std::size_t __n_ins) const { - if (__n_elt + __n_ins > _M_next_resize) + if (__n_elt + __n_ins >= _M_next_resize) { - long double __min_bkts = ((__n_elt + __n_ins) - / (long double)_M_max_load_factor); - if (__min_bkts > __n_bkt) - { - __min_bkts = std::max(__min_bkts, (long double)_M_growth_factor - * __n_bkt); - return std::make_pair(true, - _M_next_bkt(__builtin_ceil(__min_bkts))); - } + long double __min_bkts = (__n_elt + __n_ins) + / (long double)_M_max_load_factor; + if (__min_bkts >= __n_bkt) + return std::make_pair(true, + _M_next_bkt(__builtin_floor(__min_bkts) + 1)); else { _M_next_resize @@ -479,6 +355,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return std::make_pair(false, 0); } } + else if (__n_elt + __n_ins < _M_prev_resize) + { + long double __min_bkts = (__n_elt + __n_ins) + / (long double)_M_max_load_factor; + return std::make_pair(true, + _M_next_bkt(__builtin_floor(__min_bkts) + 1)); + } else return std::make_pair(false, 0); } @@ -538,8 +421,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::size_t __n = __h->_M_bucket_index(__k, __code, __h->_M_bucket_count); - typename _Hashtable::_Node* __p = - __h->_M_find_node(__h->_M_buckets[__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; @@ -557,8 +439,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::size_t __n = __h->_M_bucket_index(__k, __code, __h->_M_bucket_count); - typename _Hashtable::_Node* __p = - __h->_M_find_node(__h->_M_buckets[__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()), @@ -577,8 +458,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::size_t __n = __h->_M_bucket_index(__k, __code, __h->_M_bucket_count); - typename _Hashtable::_Node* __p = - __h->_M_find_node(__h->_M_buckets[__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; @@ -595,8 +475,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION std::size_t __n = __h->_M_bucket_index(__k, __code, __h->_M_bucket_count); - typename _Hashtable::_Node* __p = - __h->_M_find_node(__h->_M_buckets[__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; diff --git a/libstdc++-v3/include/bits/shared_ptr.h b/libstdc++-v3/include/bits/shared_ptr.h index 32addf95105..33128dd4ed6 100644 --- a/libstdc++-v3/include/bits/shared_ptr.h +++ b/libstdc++-v3/include/bits/shared_ptr.h @@ -619,7 +619,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, shared_ptr<_Tp>> { size_t - operator()(const shared_ptr<_Tp>& __s) const + operator()(const shared_ptr<_Tp>& __s) const noexcept { return std::hash<_Tp*>()(__s.get()); } }; diff --git a/libstdc++-v3/include/bits/shared_ptr_base.h b/libstdc++-v3/include/bits/shared_ptr_base.h index fbbadd1aaaa..c0677547553 100644 --- a/libstdc++-v3/include/bits/shared_ptr_base.h +++ b/libstdc++-v3/include/bits/shared_ptr_base.h @@ -1450,7 +1450,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, __shared_ptr<_Tp, _Lp>> { size_t - operator()(const __shared_ptr<_Tp, _Lp>& __s) const + operator()(const __shared_ptr<_Tp, _Lp>& __s) const noexcept { return std::hash<_Tp*>()(__s.get()); } }; diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index 8f286400aec..bec63ff03f9 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -1075,7 +1075,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>> { size_t - operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const; + operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept; }; _GLIBCXX_END_NAMESPACE_VERSION diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h index 45824f04079..f1c4cfefa57 100644 --- a/libstdc++-v3/include/bits/stl_map.h +++ b/libstdc++-v3/include/bits/stl_map.h @@ -617,6 +617,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER iterator erase(const_iterator __position) { return _M_t.erase(__position); } + + // LWG 2059. + iterator + erase(iterator __position) + { return _M_t.erase(__position); } #else /** * @brief Erases an element from a %map. diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h index fd5a5a8cffb..ae4389e2709 100644 --- a/libstdc++-v3/include/bits/stl_multimap.h +++ b/libstdc++-v3/include/bits/stl_multimap.h @@ -536,6 +536,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER iterator erase(const_iterator __position) { return _M_t.erase(__position); } + + // LWG 2059. + iterator + erase(iterator __position) + { return _M_t.erase(__position); } #else /** * @brief Erases an element from a %multimap. diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index 8c5f0c30a0f..ee56bbc7525 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -767,6 +767,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_erase_aux(__position); return __result._M_const_cast(); } + + // LWG 2059. + iterator + erase(iterator __position) + { + iterator __result = __position; + ++__result; + _M_erase_aux(__position); + return __result; + } #else void erase(iterator __position) diff --git a/libstdc++-v3/include/bits/unique_ptr.h b/libstdc++-v3/include/bits/unique_ptr.h index 869d931330c..0a127996e52 100644 --- a/libstdc++-v3/include/bits/unique_ptr.h +++ b/libstdc++-v3/include/bits/unique_ptr.h @@ -545,7 +545,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, unique_ptr<_Tp, _Dp>> { size_t - operator()(const unique_ptr<_Tp, _Dp>& __u) const + operator()(const unique_ptr<_Tp, _Dp>& __u) const noexcept { typedef unique_ptr<_Tp, _Dp> _UP; return std::hash<typename _UP::pointer>()(__u.get()); diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index c77bab12fba..7c810d3801f 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -40,7 +40,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER class _Hash = hash<_Key>, class _Pred = std::equal_to<_Key>, class _Alloc = std::allocator<std::pair<const _Key, _Tp> >, - bool __cache_hash_code = false> + bool __cache_hash_code = + __not_<__and_<is_integral<_Key>, + __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, @@ -109,7 +111,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER class _Hash = hash<_Key>, class _Pred = std::equal_to<_Key>, class _Alloc = std::allocator<std::pair<const _Key, _Tp> >, - bool __cache_hash_code = false> + bool __cache_hash_code = + __not_<__and_<is_integral<_Key>, + __detail::__is_noexcept_hash<_Key, _Hash>>>::value> class __unordered_multimap : public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc, diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index 12b7bda138f..9aef0829749 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -40,7 +40,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER class _Hash = hash<_Value>, class _Pred = std::equal_to<_Value>, class _Alloc = std::allocator<_Value>, - bool __cache_hash_code = false> + bool __cache_hash_code = + __not_<__and_<is_integral<_Value>, + __detail::__is_noexcept_hash<_Value, _Hash>>>::value> class __unordered_set : public _Hashtable<_Value, _Value, _Alloc, std::_Identity<_Value>, _Pred, @@ -121,7 +123,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER class _Hash = hash<_Value>, class _Pred = std::equal_to<_Value>, class _Alloc = std::allocator<_Value>, - bool __cache_hash_code = false> + bool __cache_hash_code = + __not_<__and_<is_integral<_Value>, + __detail::__is_noexcept_hash<_Value, _Hash>>>::value> class __unordered_multiset : public _Hashtable<_Value, _Value, _Alloc, std::_Identity<_Value>, _Pred, diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc index b74684228c1..d9c3b659e6b 100644 --- a/libstdc++-v3/include/bits/vector.tcc +++ b/libstdc++-v3/include/bits/vector.tcc @@ -818,7 +818,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Alloc> size_t hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>:: - operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const + operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept { size_t __hash = 0; using _GLIBCXX_STD_C::_S_word_bit; diff --git a/libstdc++-v3/include/debug/bitset b/libstdc++-v3/include/debug/bitset index 21d281787ad..3d865c1c1c2 100644 --- a/libstdc++-v3/include/debug/bitset +++ b/libstdc++-v3/include/debug/bitset @@ -51,7 +51,7 @@ namespace __debug public: // In C++0x we rely on normal reference type to preserve the property // of bitset to be use as a literal. - // TODO: Find an other solution. + // TODO: Find another solution. #ifdef __GXX_EXPERIMENTAL_CXX0X__ typedef typename _Base::reference reference; #else @@ -272,11 +272,14 @@ namespace __debug // _GLIBCXX_RESOLVE_LIB_DEFECTS // 11. Bitset minor problems - bool + _GLIBCXX_CONSTEXPR bool operator[](size_t __pos) const { +#ifndef __GXX_EXPERIMENTAL_CXX0X__ + // TODO: Check in debug-mode too. __glibcxx_check_subscript(__pos); - return _M_base()[__pos]; +#endif + return _Base::operator[](__pos); } using _Base::to_ulong; @@ -414,7 +417,7 @@ namespace __debug : public __hash_base<size_t, __debug::bitset<_Nb>> { size_t - operator()(const __debug::bitset<_Nb>& __b) const + operator()(const __debug::bitset<_Nb>& __b) const noexcept { return std::hash<_GLIBCXX_STD_C::bitset<_Nb>>()(__b._M_base()); } }; #endif diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h index e80c1e3b4b7..9abfee867d0 100644 --- a/libstdc++-v3/include/debug/map.h +++ b/libstdc++-v3/include/debug/map.h @@ -271,6 +271,10 @@ namespace __debug this->_M_invalidate_if(_Equal(__position.base())); return iterator(_Base::erase(__position.base()), this); } + + iterator + erase(iterator __position) + { return erase(const_iterator(__position)); } #else void erase(iterator __position) diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h index cf18d7cc114..e43094f8b4d 100644 --- a/libstdc++-v3/include/debug/multimap.h +++ b/libstdc++-v3/include/debug/multimap.h @@ -254,6 +254,10 @@ namespace __debug this->_M_invalidate_if(_Equal(__position.base())); return iterator(_Base::erase(__position.base()), this); } + + iterator + erase(iterator __position) + { return erase(const_iterator(__position)); } #else void erase(iterator __position) diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map index 6eeff6429e4..6ad46b627d3 100644 --- a/libstdc++-v3/include/debug/unordered_map +++ b/libstdc++-v3/include/debug/unordered_map @@ -334,6 +334,10 @@ namespace __debug } iterator + erase(iterator __it) + { return erase(const_iterator(__it)); } + + iterator erase(const_iterator __first, const_iterator __last) { __glibcxx_check_erase_range(__first, __last); @@ -391,11 +395,11 @@ namespace __debug static _Base_local_iterator _S_to_local(_Base_iterator __it) - { return _Base_local_iterator(__it._M_cur_node); } + { return _Base_local_iterator(__it._M_cur); } static _Base_const_local_iterator _S_to_local(_Base_const_iterator __it) - { return _Base_const_local_iterator(__it._M_cur_node); } + { return _Base_const_local_iterator(__it._M_cur); } }; template<typename _Key, typename _Tp, typename _Hash, @@ -709,6 +713,10 @@ namespace __debug } iterator + erase(iterator __it) + { return erase(const_iterator(__it)); } + + iterator erase(const_iterator __first, const_iterator __last) { __glibcxx_check_erase_range(__first, __last); @@ -766,11 +774,11 @@ namespace __debug static _Base_local_iterator _S_to_local(_Base_iterator __it) - { return _Base_local_iterator(__it._M_cur_node); } + { return _Base_local_iterator(__it._M_cur); } static _Base_const_local_iterator _S_to_local(_Base_const_iterator __it) - { return _Base_const_local_iterator(__it._M_cur_node); } + { return _Base_const_local_iterator(__it._M_cur); } }; template<typename _Key, typename _Tp, typename _Hash, diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set index 0cc3a12cf37..2f41bc3a25d 100644 --- a/libstdc++-v3/include/debug/unordered_set +++ b/libstdc++-v3/include/debug/unordered_set @@ -330,6 +330,10 @@ namespace __debug } iterator + erase(iterator __it) + { return erase(const_iterator(__it)); } + + iterator erase(const_iterator __first, const_iterator __last) { __glibcxx_check_erase_range(__first, __last); @@ -390,11 +394,11 @@ namespace __debug static _Base_local_iterator _S_to_local(_Base_iterator __it) - { return _Base_local_iterator(__it._M_cur_node); } + { return _Base_local_iterator(__it._M_cur); } static _Base_const_local_iterator _S_to_local(_Base_const_iterator __it) - { return _Base_const_local_iterator(__it._M_cur_node); } + { return _Base_const_local_iterator(__it._M_cur); } }; template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> @@ -696,6 +700,10 @@ namespace __debug } iterator + erase(iterator __it) + { return erase(const_iterator(__it)); } + + iterator erase(const_iterator __first, const_iterator __last) { __glibcxx_check_erase_range(__first, __last); @@ -751,11 +759,11 @@ namespace __debug static _Base_local_iterator _S_to_local(_Base_iterator __it) - { return _Base_local_iterator(__it._M_cur_node); } + { return _Base_local_iterator(__it._M_cur); } static _Base_const_local_iterator _S_to_local(_Base_const_iterator __it) - { return _Base_const_local_iterator(__it._M_cur_node); } + { return _Base_const_local_iterator(__it._M_cur); } }; template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector index 82662b44605..5ee0fabc32a 100644 --- a/libstdc++-v3/include/debug/vector +++ b/libstdc++-v3/include/debug/vector @@ -625,7 +625,7 @@ namespace __debug : public __hash_base<size_t, __debug::vector<bool, _Alloc>> { size_t - operator()(const __debug::vector<bool, _Alloc>& __b) const + operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>() (__b._M_base()); } }; diff --git a/libstdc++-v3/include/ext/vstring.h b/libstdc++-v3/include/ext/vstring.h index a613e364d3a..8c4120a3be2 100644 --- a/libstdc++-v3/include/ext/vstring.h +++ b/libstdc++-v3/include/ext/vstring.h @@ -2769,7 +2769,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, __gnu_cxx::__vstring> { size_t - operator()(const __gnu_cxx::__vstring& __s) const + operator()(const __gnu_cxx::__vstring& __s) const noexcept { return std::_Hash_impl::hash(__s.data(), __s.length()); } }; @@ -2780,7 +2780,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, __gnu_cxx::__wvstring> { size_t - operator()(const __gnu_cxx::__wvstring& __s) const + operator()(const __gnu_cxx::__wvstring& __s) const noexcept { return std::_Hash_impl::hash(__s.data(), __s.length() * sizeof(wchar_t)); } }; @@ -2793,7 +2793,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, __gnu_cxx::__u16vstring> { size_t - operator()(const __gnu_cxx::__u16vstring& __s) const + operator()(const __gnu_cxx::__u16vstring& __s) const noexcept { return std::_Hash_impl::hash(__s.data(), __s.length() * sizeof(char16_t)); } }; @@ -2804,7 +2804,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, __gnu_cxx::__u32vstring> { size_t - operator()(const __gnu_cxx::__u32vstring& __s) const + operator()(const __gnu_cxx::__u32vstring& __s) const noexcept { return std::_Hash_impl::hash(__s.data(), __s.length() * sizeof(char32_t)); } }; diff --git a/libstdc++-v3/include/profile/bitset b/libstdc++-v3/include/profile/bitset index bd4aa3e152f..17ee49b5a60 100644 --- a/libstdc++-v3/include/profile/bitset +++ b/libstdc++-v3/include/profile/bitset @@ -232,10 +232,10 @@ namespace __profile // _GLIBCXX_RESOLVE_LIB_DEFECTS // 11. Bitset minor problems - bool + _GLIBCXX_CONSTEXPR bool operator[](size_t __pos) const { - return _M_base()[__pos]; + return _Base::operator[](__pos); } using _Base::to_ulong; @@ -372,7 +372,7 @@ namespace __profile : public __hash_base<size_t, __profile::bitset<_Nb>> { size_t - operator()(const __profile::bitset<_Nb>& __b) const + operator()(const __profile::bitset<_Nb>& __b) const noexcept { return std::hash<_GLIBCXX_STD_C::bitset<_Nb>>()(__b._M_base()); } }; #endif diff --git a/libstdc++-v3/include/profile/map.h b/libstdc++-v3/include/profile/map.h index 622bc575ad2..eb5c5d90d9c 100644 --- a/libstdc++-v3/include/profile/map.h +++ b/libstdc++-v3/include/profile/map.h @@ -327,6 +327,10 @@ namespace __profile __profcxx_map_to_unordered_map_erase(this, size(), 1); return __i; } + + iterator + erase(iterator __position) + { return erase(const_iterator(__position)); } #else void erase(iterator __position) diff --git a/libstdc++-v3/include/profile/multimap.h b/libstdc++-v3/include/profile/multimap.h index 547a221b330..b71be4570bd 100644 --- a/libstdc++-v3/include/profile/multimap.h +++ b/libstdc++-v3/include/profile/multimap.h @@ -226,6 +226,10 @@ namespace __profile iterator erase(const_iterator __position) { return iterator(_Base::erase(__position)); } + + iterator + erase(iterator __position) + { return iterator(_Base::erase(__position)); } #else void erase(iterator __position) diff --git a/libstdc++-v3/include/profile/vector b/libstdc++-v3/include/profile/vector index 86aefd649e3..0526c5aabb7 100644 --- a/libstdc++-v3/include/profile/vector +++ b/libstdc++-v3/include/profile/vector @@ -529,7 +529,7 @@ namespace __profile : public __hash_base<size_t, __profile::vector<bool, _Alloc>> { size_t - operator()(const __profile::vector<bool, _Alloc>& __b) const + operator()(const __profile::vector<bool, _Alloc>& __b) const noexcept { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>() (__b._M_base()); } }; diff --git a/libstdc++-v3/include/std/bitset b/libstdc++-v3/include/std/bitset index 813ed4b2599..e07c5e08970 100644 --- a/libstdc++-v3/include/std/bitset +++ b/libstdc++-v3/include/std/bitset @@ -1555,7 +1555,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<_Nb>> { size_t - operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const + operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const noexcept { const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__; return std::_Hash_impl::hash(__b._M_getdata(), __clength); @@ -1567,7 +1567,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<0>> { size_t - operator()(const _GLIBCXX_STD_C::bitset<0>&) const + operator()(const _GLIBCXX_STD_C::bitset<0>&) const noexcept { return 0; } }; diff --git a/libstdc++-v3/include/std/functional b/libstdc++-v3/include/std/functional index 4a04eca8969..465fc569b23 100644 --- a/libstdc++-v3/include/std/functional +++ b/libstdc++-v3/include/std/functional @@ -843,22 +843,24 @@ _GLIBCXX_HAS_NESTED_TYPE(result_type) : public integral_constant<int, 0> { }; - /// The type of placeholder objects defined by libstdc++. + /** @brief The type of placeholder objects defined by libstdc++. + * @ingroup binders + */ template<int _Num> struct _Placeholder { }; _GLIBCXX_END_NAMESPACE_VERSION /** @namespace std::placeholders - * @brief ISO C++ 0x entities sub namespace for functional. + * @brief ISO C++11 entities sub-namespace for functional. * @ingroup binders - * - * Define a large number of placeholders. There is no way to - * simplify this with variadic templates, because we're introducing - * unique names for each. */ namespace placeholders { _GLIBCXX_BEGIN_NAMESPACE_VERSION + /* Define a large number of placeholders. There is no way to + * simplify this with variadic templates, because we're introducing + * unique names for each. + */ extern const _Placeholder<1> _1; extern const _Placeholder<2> _2; extern const _Placeholder<3> _3; @@ -903,6 +905,11 @@ _GLIBCXX_HAS_NESTED_TYPE(result_type) : public integral_constant<int, _Num> { }; + template<int _Num> + struct is_placeholder<const _Placeholder<_Num> > + : public integral_constant<int, _Num> + { }; + /** * Used by _Safe_tuple_element to indicate that there is no tuple * element at this position. @@ -1424,8 +1431,56 @@ _GLIBCXX_HAS_NESTED_TYPE(result_type) * @brief Class template _Bind is always a bind expression. * @ingroup binders */ + template<typename _Signature> + struct is_bind_expression<const _Bind<_Signature> > + : public true_type { }; + + /** + * @brief Class template _Bind is always a bind expression. + * @ingroup binders + */ + template<typename _Signature> + struct is_bind_expression<volatile _Bind<_Signature> > + : public true_type { }; + + /** + * @brief Class template _Bind is always a bind expression. + * @ingroup binders + */ + template<typename _Signature> + struct is_bind_expression<const volatile _Bind<_Signature>> + : public true_type { }; + + /** + * @brief Class template _Bind_result is always a bind expression. + * @ingroup binders + */ + template<typename _Result, typename _Signature> + struct is_bind_expression<_Bind_result<_Result, _Signature>> + : public true_type { }; + + /** + * @brief Class template _Bind_result is always a bind expression. + * @ingroup binders + */ + template<typename _Result, typename _Signature> + struct is_bind_expression<const _Bind_result<_Result, _Signature>> + : public true_type { }; + + /** + * @brief Class template _Bind_result is always a bind expression. + * @ingroup binders + */ + template<typename _Result, typename _Signature> + struct is_bind_expression<volatile _Bind_result<_Result, _Signature>> + : public true_type { }; + + /** + * @brief Class template _Bind_result is always a bind expression. + * @ingroup binders + */ template<typename _Result, typename _Signature> - struct is_bind_expression<_Bind_result<_Result, _Signature> > + struct is_bind_expression<const volatile _Bind_result<_Result, _Signature>> : public true_type { }; // Trait type used to remove std::bind() from overload set via SFINAE diff --git a/libstdc++-v3/include/std/iomanip b/libstdc++-v3/include/std/iomanip index ea2c44acf6f..e725b2514df 100644 --- a/libstdc++-v3/include/std/iomanip +++ b/libstdc++-v3/include/std/iomanip @@ -1,7 +1,7 @@ // Standard stream manipulators -*- C++ -*- // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 -// 2006, 2007, 2008, 2009, 2010 +// 2006, 2007, 2008, 2009, 2010, 2011 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -262,18 +262,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION basic_istream<_CharT, _Traits>& operator>>(basic_istream<_CharT, _Traits>& __is, _Get_money<_MoneyT> __f) { - typedef istreambuf_iterator<_CharT, _Traits> _Iter; - typedef money_get<_CharT, _Iter> _MoneyGet; - - ios_base::iostate __err = ios_base::goodbit; - const _MoneyGet& __mg = use_facet<_MoneyGet>(__is.getloc()); - - __mg.get(_Iter(__is.rdbuf()), _Iter(), __f._M_intl, - __is, __err, __f._M_mon); - - if (ios_base::goodbit != __err) - __is.setstate(__err); - + typename basic_istream<_CharT, _Traits>::sentry __cerb(__is, false); + if (__cerb) + { + ios_base::iostate __err = ios_base::goodbit; + __try + { + typedef istreambuf_iterator<_CharT, _Traits> _Iter; + typedef money_get<_CharT, _Iter> _MoneyGet; + + const _MoneyGet& __mg = use_facet<_MoneyGet>(__is.getloc()); + __mg.get(_Iter(__is.rdbuf()), _Iter(), __f._M_intl, + __is, __err, __f._M_mon); + } + __catch(__cxxabiv1::__forced_unwind&) + { + __is._M_setstate(ios_base::badbit); + __throw_exception_again; + } + __catch(...) + { __is._M_setstate(ios_base::badbit); } + if (ios_base::goodbit != __err) + __is.setstate(__err); + } return __is; } @@ -298,16 +309,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION basic_ostream<_CharT, _Traits>& operator<<(basic_ostream<_CharT, _Traits>& __os, _Put_money<_MoneyT> __f) { - typedef ostreambuf_iterator<_CharT, _Traits> _Iter; - typedef money_put<_CharT, _Iter> _MoneyPut; - - const _MoneyPut& __mp = use_facet<_MoneyPut>(__os.getloc()); - const _Iter __end = __mp.put(_Iter(__os.rdbuf()), __f._M_intl, - __os, __os.fill(), __f._M_mon); - - if (__end.failed()) - __os.setstate(ios_base::badbit); - + typename basic_ostream<_CharT, _Traits>::sentry __cerb(__os); + if (__cerb) + { + __try + { + typedef ostreambuf_iterator<_CharT, _Traits> _Iter; + typedef money_put<_CharT, _Iter> _MoneyPut; + const _MoneyPut& __mp = use_facet<_MoneyPut>(__os.getloc()); + const _Iter __end = __mp.put(_Iter(__os.rdbuf()), __f._M_intl, + __os, __os.fill(), __f._M_mon); + if (__end.failed()) + __os.setstate(ios_base::badbit); + } + __catch(__cxxabiv1::__forced_unwind&) + { + __os._M_setstate(ios_base::badbit); + __throw_exception_again; + } + __catch(...) + { __os._M_setstate(ios_base::badbit); } + } return __os; } diff --git a/libstdc++-v3/include/std/system_error b/libstdc++-v3/include/std/system_error index 565261e709b..19482bc2181 100644 --- a/libstdc++-v3/include/std/system_error +++ b/libstdc++-v3/include/std/system_error @@ -361,7 +361,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, error_code> { size_t - operator()(const error_code& __e) const + operator()(const error_code& __e) const noexcept { const size_t __tmp = std::_Hash_impl::hash(__e._M_value); return std::_Hash_impl::__hash_combine(__e._M_cat, __tmp); diff --git a/libstdc++-v3/include/std/thread b/libstdc++-v3/include/std/thread index 8cc06903ebf..1d1733731bf 100644 --- a/libstdc++-v3/include/std/thread +++ b/libstdc++-v3/include/std/thread @@ -221,7 +221,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : public __hash_base<size_t, thread::id> { size_t - operator()(const thread::id& __id) const + operator()(const thread::id& __id) const noexcept { return std::_Hash_impl::hash(__id._M_thread); } }; diff --git a/libstdc++-v3/include/std/tuple b/libstdc++-v3/include/std/tuple index 51be289d506..282d4509d3a 100644 --- a/libstdc++-v3/include/std/tuple +++ b/libstdc++-v3/include/std/tuple @@ -69,35 +69,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION struct __add_r_ref<_Tp&> { typedef _Tp& type; }; - // To work around c++/49225 aka c++/48322. - template<typename...> - struct __conv_types { }; - - template<typename _Tuple1, typename _Tuple2> - struct __one_by_one_convertible - : public false_type { }; - - template<typename _Tp, typename _Up> - struct __one_by_one_convertible<__conv_types<_Tp>, __conv_types<_Up>> - : public is_convertible<_Tp, _Up>::type { }; - - template<typename _T1, typename... _TR, typename _U1, typename... _UR> - struct __one_by_one_convertible<__conv_types<_T1, _TR...>, - __conv_types<_U1, _UR...>> - : public __and_<is_convertible<_T1, _U1>, - __one_by_one_convertible<__conv_types<_TR...>, - __conv_types<_UR...>>>::type - { }; - - template<typename _Tuple1, typename _Tuple2> - struct __all_convertible; - - template<typename... _TTypes, typename... _UTypes> - struct __all_convertible<__conv_types<_TTypes...>, - __conv_types<_UTypes...>> - : public __one_by_one_convertible<__conv_types<_TTypes...>, - __conv_types<_UTypes...>>::type { }; - template<std::size_t _Idx, typename _Head, bool _IsEmpty> struct _Head_base; @@ -408,11 +379,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION : _Inherited(__elements...) { } template<typename... _UElements, typename = typename - enable_if<__and_<integral_constant<bool, sizeof...(_UElements) - == sizeof...(_Elements)>, - __all_convertible<__conv_types<_UElements...>, - __conv_types<_Elements...>> - >::value>::type> + enable_if<__and_<is_convertible<_UElements, + _Elements>...>::value>::type> explicit constexpr tuple(_UElements&&... __elements) : _Inherited(std::forward<_UElements>(__elements)...) { } @@ -422,21 +390,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION constexpr tuple(tuple&&) = default; template<typename... _UElements, typename = typename - enable_if<__and_<integral_constant<bool, sizeof...(_UElements) - == sizeof...(_Elements)>, - __all_convertible<__conv_types<const _UElements&...>, - __conv_types<_Elements...>> - >::value>::type> + enable_if<__and_<is_convertible<const _UElements&, + _Elements>...>::value>::type> constexpr tuple(const tuple<_UElements...>& __in) : _Inherited(static_cast<const _Tuple_impl<0, _UElements...>&>(__in)) { } template<typename... _UElements, typename = typename - enable_if<__and_<integral_constant<bool, sizeof...(_UElements) - == sizeof...(_Elements)>, - __all_convertible<__conv_types<_UElements...>, - __conv_types<_Elements...>> - >::value>::type> + enable_if<__and_<is_convertible<_UElements, + _Elements>...>::value>::type> constexpr tuple(tuple<_UElements...>&& __in) : _Inherited(static_cast<_Tuple_impl<0, _UElements...>&&>(__in)) { } diff --git a/libstdc++-v3/include/std/type_traits b/libstdc++-v3/include/std/type_traits index a0208590bb5..46e3f800cab 100644 --- a/libstdc++-v3/include/std/type_traits +++ b/libstdc++-v3/include/std/type_traits @@ -745,6 +745,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Implementation for non-reference types. To meet the proper // variable definition semantics, we also need to test for // is_destructible in this case. + // This form should be simplified by a single expression: + // ::delete ::new _Tp(declval<_Arg>()), see c++/51222. struct __do_is_direct_constructible_impl { template<typename _Tp, typename _Arg, typename @@ -778,9 +780,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION struct remove_reference; template<typename _From, typename _To, bool - = is_reference<_From>::value> + = __not_<__or_<is_void<_From>, + is_function<_From>>>::value> struct __is_base_to_derived_ref; + // Detect whether we have a downcast situation during + // reference binding. template<typename _From, typename _To> struct __is_base_to_derived_ref<_From, _To, true> { @@ -803,6 +808,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION is_rvalue_reference<_To>>::value> struct __is_lvalue_to_rvalue_ref; + // Detect whether we have an lvalue of non-function type + // bound to a reference-compatible rvalue-reference. template<typename _From, typename _To> struct __is_lvalue_to_rvalue_ref<_From, _To, true> { @@ -810,8 +817,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _From>::type>::type __src_t; typedef typename remove_cv<typename remove_reference< _To>::type>::type __dst_t; - typedef __or_<is_same<__src_t, __dst_t>, - is_base_of<__dst_t, __src_t>> type; + typedef __and_<__not_<is_function<__src_t>>, + __or_<is_same<__src_t, __dst_t>, + is_base_of<__dst_t, __src_t>>> type; static constexpr bool value = type::value; }; @@ -823,9 +831,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Here we handle direct-initialization to a reference type as // equivalent to a static_cast modulo overshooting conversions. // These are restricted to the following conversions: - // a) A glvalue of a base class to a derived class reference + // a) A base class value to a derived class reference // b) An lvalue to an rvalue-reference of reference-compatible - // types + // types that are not functions template<typename _Tp, typename _Arg> struct __is_direct_constructible_ref_cast : public __and_<__is_static_castable<_Arg, _Tp>, @@ -850,7 +858,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Since default-construction and binary direct-initialization have // been handled separately, the implementation of the remaining - // n-ary construction cases is rather straightforward. + // n-ary construction cases is rather straightforward. We can use + // here a functional cast, because array types are excluded anyway + // and this form is never interpreted as a C cast. struct __do_is_nary_constructible_impl { template<typename _Tp, typename... _Args, typename diff --git a/libstdc++-v3/include/std/typeindex b/libstdc++-v3/include/std/typeindex index a92c2969b97..fa07ac620e6 100644 --- a/libstdc++-v3/include/std/typeindex +++ b/libstdc++-v3/include/std/typeindex @@ -76,7 +76,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { return !_M_target->before(*__rhs._M_target); } size_t - hash_code() const + hash_code() const noexcept { return _M_target->hash_code(); } const char* @@ -97,7 +97,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typedef type_index argument_type; size_t - operator()(const type_index& __ti) const + operator()(const type_index& __ti) const noexcept { return __ti.hash_code(); } }; diff --git a/libstdc++-v3/include/tr1/functional b/libstdc++-v3/include/tr1/functional index 7651326955a..ff2bd2a7134 100644 --- a/libstdc++-v3/include/tr1/functional +++ b/libstdc++-v3/include/tr1/functional @@ -43,9 +43,20 @@ #include <tr1/functional_hash.h> #include <ext/type_traits.h> #include <bits/move.h> // for std::__addressof +#ifdef __GXX_EXPERIMENTAL_CXX0X__ +# include <type_traits> // for integral_constant, true_type, false_type +#endif namespace std _GLIBCXX_VISIBILITY(default) { +#ifdef __GXX_EXPERIMENTAL_CXX0X__ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + template<int> struct _Placeholder; + template<typename> class _Bind; + template<typename, typename> class _Bind_result; +_GLIBCXX_END_NAMESPACE_VERSION +#endif + namespace tr1 { _GLIBCXX_BEGIN_NAMESPACE_VERSION @@ -847,16 +858,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _GLIBCXX_END_NAMESPACE_VERSION - /** @namespace std::placeholders - * @brief ISO C++ 0x entities sub namespace for functional. - * - * Define a large number of placeholders. There is no way to - * simplify this with variadic templates, because we're introducing - * unique names for each. + /** @namespace std::tr1::placeholders + * @brief Sub-namespace for tr1/functional. */ namespace placeholders { _GLIBCXX_BEGIN_NAMESPACE_VERSION + /* Define a large number of placeholders. There is no way to + * simplify this with variadic templates, because we're introducing + * unique names for each. + */ namespace { _Placeholder<1> _1; @@ -904,6 +915,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<int _Num> const int is_placeholder<_Placeholder<_Num> >::value; +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template<int _Num> + struct is_placeholder<std::_Placeholder<_Num>> + : std::integral_constant<int, _Num> + { }; + + template<int _Num> + struct is_placeholder<const std::_Placeholder<_Num>> + : std::integral_constant<int, _Num> + { }; +#endif + /** * Stores a tuple of indices. Used by bind() to extract the elements * in a tuple. @@ -1347,6 +1370,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Signature> const bool is_bind_expression<_Bind<_Signature> >::value; + /// Class template _Bind is always a bind expression. + template<typename _Signature> + struct is_bind_expression<const _Bind<_Signature> > + { static const bool value = true; }; + + template<typename _Signature> + const bool is_bind_expression<const _Bind<_Signature> >::value; + + /// Class template _Bind is always a bind expression. + template<typename _Signature> + struct is_bind_expression<volatile _Bind<_Signature> > + { static const bool value = true; }; + + template<typename _Signature> + const bool is_bind_expression<volatile _Bind<_Signature> >::value; + + /// Class template _Bind is always a bind expression. + template<typename _Signature> + struct is_bind_expression<const volatile _Bind<_Signature> > + { static const bool value = true; }; + + template<typename _Signature> + const bool is_bind_expression<const volatile _Bind<_Signature> >::value; + /// Class template _Bind_result is always a bind expression. template<typename _Result, typename _Signature> struct is_bind_expression<_Bind_result<_Result, _Signature> > @@ -1355,6 +1402,70 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Result, typename _Signature> const bool is_bind_expression<_Bind_result<_Result, _Signature> >::value; + /// Class template _Bind_result is always a bind expression. + template<typename _Result, typename _Signature> + struct is_bind_expression<const _Bind_result<_Result, _Signature> > + { static const bool value = true; }; + + template<typename _Result, typename _Signature> + const bool + is_bind_expression<const _Bind_result<_Result, _Signature> >::value; + + /// Class template _Bind_result is always a bind expression. + template<typename _Result, typename _Signature> + struct is_bind_expression<volatile _Bind_result<_Result, _Signature> > + { static const bool value = true; }; + + template<typename _Result, typename _Signature> + const bool + is_bind_expression<volatile _Bind_result<_Result, _Signature> >::value; + + /// Class template _Bind_result is always a bind expression. + template<typename _Result, typename _Signature> + struct + is_bind_expression<const volatile _Bind_result<_Result, _Signature> > + { static const bool value = true; }; + + template<typename _Result, typename _Signature> + const bool + is_bind_expression<const volatile _Bind_result<_Result, + _Signature> >::value; + +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template<typename _Signature> + struct is_bind_expression<std::_Bind<_Signature>> + : true_type { }; + + template<typename _Signature> + struct is_bind_expression<const std::_Bind<_Signature>> + : true_type { }; + + template<typename _Signature> + struct is_bind_expression<volatile std::_Bind<_Signature>> + : true_type { }; + + template<typename _Signature> + struct is_bind_expression<const volatile std::_Bind<_Signature>> + : true_type { }; + + template<typename _Result, typename _Signature> + struct is_bind_expression<std::_Bind_result<_Result, _Signature>> + : true_type { }; + + template<typename _Result, typename _Signature> + struct is_bind_expression<const std::_Bind_result<_Result, _Signature>> + : true_type { }; + + template<typename _Result, typename _Signature> + struct is_bind_expression<volatile std::_Bind_result<_Result, _Signature>> + : true_type { }; + + template<typename _Result, typename _Signature> + struct is_bind_expression<const volatile std::_Bind_result<_Result, + _Signature>> + : true_type { }; +#endif + /// bind template<typename _Functor, typename... _ArgTypes> inline @@ -2147,6 +2258,59 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _GLIBCXX_END_NAMESPACE_VERSION } + +#ifdef __GXX_EXPERIMENTAL_CXX0X__ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + template<typename> struct is_placeholder; + + template<int _Num> + struct is_placeholder<tr1::_Placeholder<_Num>> + : integral_constant<int, _Num> + { }; + + template<int _Num> + struct is_placeholder<const tr1::_Placeholder<_Num>> + : integral_constant<int, _Num> + { }; + + template<typename> struct is_bind_expression; + + template<typename _Signature> + struct is_bind_expression<tr1::_Bind<_Signature>> + : true_type { }; + + template<typename _Signature> + struct is_bind_expression<const tr1::_Bind<_Signature>> + : true_type { }; + + template<typename _Signature> + struct is_bind_expression<volatile tr1::_Bind<_Signature>> + : true_type { }; + + template<typename _Signature> + struct is_bind_expression<const volatile tr1::_Bind<_Signature>> + : true_type { }; + + template<typename _Result, typename _Signature> + struct is_bind_expression<tr1::_Bind_result<_Result, _Signature>> + : true_type { }; + + template<typename _Result, typename _Signature> + struct is_bind_expression<const tr1::_Bind_result<_Result, _Signature>> + : true_type { }; + + template<typename _Result, typename _Signature> + struct is_bind_expression<volatile tr1::_Bind_result<_Result, _Signature>> + : true_type { }; + + template<typename _Result, typename _Signature> + struct is_bind_expression<const volatile tr1::_Bind_result<_Result, + _Signature>> + : true_type { }; + +_GLIBCXX_END_NAMESPACE_VERSION +#endif } #endif // _GLIBCXX_TR1_FUNCTIONAL diff --git a/libstdc++-v3/include/tr1/hashtable.h b/libstdc++-v3/include/tr1/hashtable.h index 5d1e02c2592..5e17b238a1f 100644 --- a/libstdc++-v3/include/tr1/hashtable.h +++ b/libstdc++-v3/include/tr1/hashtable.h @@ -813,7 +813,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } // Find the node whose key compares equal to k, beginning the search - // at p (usually the head of a bucket). Return nil if no node is found. + // at p (usually the head of a bucket). Return zero if no node is found. template<typename _Key, typename _Value, typename _Allocator, typename _ExtractKey, typename _Equal, typename _H1, typename _H2, typename _Hash, typename _RehashPolicy, @@ -829,7 +829,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION for (; __p; __p = __p->_M_next) if (this->_M_compare(__k, __code, __p)) return __p; - return false; + return 0; } // Insert v in bucket n (assumes no element with its key already present). diff --git a/libstdc++-v3/include/tr1/poly_hermite.tcc b/libstdc++-v3/include/tr1/poly_hermite.tcc index e86b3777c74..95e8079d543 100644 --- a/libstdc++-v3/include/tr1/poly_hermite.tcc +++ b/libstdc++-v3/include/tr1/poly_hermite.tcc @@ -1,6 +1,6 @@ // Special functions -*- C++ -*- -// Copyright (C) 2006, 2007, 2008, 2009, 2010 +// Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -84,7 +84,7 @@ namespace tr1 unsigned int __i; for (__H_nm2 = __H_0, __H_nm1 = __H_1, __i = 2; __i <= __n; ++__i) { - __H_n = 2 * (__x * __H_nm1 + (__i - 1) * __H_nm2); + __H_n = 2 * (__x * __H_nm1 - (__i - 1) * __H_nm2); __H_nm2 = __H_nm1; __H_nm1 = __H_n; } |