2012-01-03 Basile Starynkevitch <basile@starynkevitch.net>

	MELT branch merged with trunk rev 182833 using svnmerge



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/melt-branch@182834 138bc75d-0d04-0410-961f-82ee72b054a4

11 files changed, 591 insertions, 215 deletions

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 3874cbc5a64..aeb330cef2f 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -155,7 +155,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 					       __cache_hash_code,
 					       __constant_iterators,
 					       __unique_keys> >,
-      public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
+      public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
 				       _H1, _H2, _Hash, __cache_hash_code>,
       public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
 				 _Hashtable<_Key, _Value, _Allocator,
@@ -174,9 +174,37 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 						 __constant_iterators,
 						 __unique_keys> >
     {
-      static_assert(__or_<integral_constant<bool, __cache_hash_code>,
-			  __detail::__is_noexcept_hash<_Key, _H1>>::value,
+      template<typename _Cond>
+	using __if_hash_code_cached
+	  = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>;
+
+      template<typename _Cond>
+	using __if_hash_code_not_cached
+	  = __or_<integral_constant<bool, __cache_hash_code>, _Cond>;
+
+      static_assert(__if_hash_code_not_cached<__detail::__is_noexcept_hash<_Key,
+								_H1>>::value,
       	    "Cache the hash code or qualify your hash functor with noexcept");
+
+      // Following two static assertions are necessary to guarantee that
+      // swapping two hashtable instances won't invalidate associated local
+      // iterators.
+
+      // When hash codes are cached local iterator only uses H2 which must then
+      // be empty.
+      static_assert(__if_hash_code_cached<is_empty<_H2>>::value,
+	    "Functor used to map hash code to bucket index must be empty");
+
+      typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey,
+					_H1, _H2, _Hash,
+				       	__cache_hash_code> _HCBase;
+
+      // When hash codes are not cached local iterator is going to use _HCBase
+      // above to compute node bucket index so it has to be empty.
+      static_assert(__if_hash_code_not_cached<is_empty<_HCBase>>::value,
+	    "Cache the hash code or make functors involved in hash code"
+	    " and bucket index computation empty");
+
     public:
       typedef _Allocator                                  allocator_type;
       typedef _Value                                      value_type;
@@ -191,16 +219,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       typedef std::size_t                                 size_type;
       typedef std::ptrdiff_t                              difference_type;
+      typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey,
+					_H1, _H2, _Hash,
+					__constant_iterators,
+					__cache_hash_code>
+							  local_iterator;
+      typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey,
+					      _H1, _H2, _Hash,
+					      __constant_iterators,
+					      __cache_hash_code>
+							  const_local_iterator;
       typedef __detail::_Node_iterator<value_type, __constant_iterators,
 				       __cache_hash_code>
-							  local_iterator;
+							  iterator;
       typedef __detail::_Node_const_iterator<value_type,
 					     __constant_iterators,
 					     __cache_hash_code>
-							  const_local_iterator;
-
-      typedef local_iterator iterator;
-      typedef const_local_iterator const_iterator;
+							  const_iterator;
 
       template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
 	       typename _Hashtable2>
@@ -212,7 +247,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       typedef typename _Allocator::template rebind<_Node>::other
 							_Node_allocator_type;
       typedef _Node* _Bucket;
-      //typedef __detail::_Bucket<_Value, __cache_hash_code> _Bucket;
       typedef typename _Allocator::template rebind<_Bucket>::other
 							_Bucket_allocator_type;
 
@@ -253,14 +287,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _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
       _Hashtable(size_type __bucket_hint,
@@ -364,35 +390,35 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       size_type
       bucket(const key_type& __k) const
-      {
-	return this->_M_bucket_index(__k, this->_M_hash_code(__k),
-				     bucket_count());
-      }
+      { return _M_bucket_index(__k, this->_M_hash_code(__k)); }
 
       local_iterator
       begin(size_type __n)
-      { return local_iterator(_M_bucket_begin(__n)); }
+      { return local_iterator(_M_bucket_begin(__n), __n,
+			      _M_bucket_count); }
 
       local_iterator
       end(size_type __n)
-      { return local_iterator(_M_bucket_past_the_end(__n)); }
+      { return local_iterator(nullptr, __n, _M_bucket_count); }
 
       const_local_iterator
       begin(size_type __n) const
-      { return const_local_iterator(_M_bucket_begin(__n)); }
+      { return const_local_iterator(_M_bucket_begin(__n), __n,
+				    _M_bucket_count); }
 
       const_local_iterator
       end(size_type __n) const
-      { return const_local_iterator(_M_bucket_past_the_end(__n)); }
+      { return const_local_iterator(nullptr, __n, _M_bucket_count); }
 
       // DR 691.
       const_local_iterator
       cbegin(size_type __n) const
-      { return const_local_iterator(_M_bucket_begin(__n)); }
+      { return const_local_iterator(_M_bucket_begin(__n), __n,
+				    _M_bucket_count); }
 
       const_local_iterator
       cend(size_type __n) const
-      { return const_local_iterator(_M_bucket_past_the_end(__n)); }
+      { return const_local_iterator(nullptr, __n, _M_bucket_count); }
 
       float
       load_factor() const noexcept
@@ -428,6 +454,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       equal_range(const key_type& __k) const;
 
     private:
+      size_type
+      _M_bucket_index(_Node* __n) const
+      { return _HCBase::_M_bucket_index(__n, _M_bucket_count); }
+
+      size_type
+      _M_bucket_index(const key_type& __k,
+		      typename _Hashtable::_Hash_code_type __c) const
+      { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); }
+
       // Find and insert helper functions and types
       _Node*
       _M_find_node(size_type, const key_type&,
@@ -679,9 +714,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _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)
+	  if (!__n->_M_next || _M_bucket_index(__n->_M_next) != __bkt)
 	    break;
       return __n;
     }
@@ -697,9 +730,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       const _Equal& __eq, const _ExtractKey& __exk,
 	       const allocator_type& __a)
     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
-      __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
-				_H1, _H2, _Hash, __chc>(__exk, __eq,
-							__h1, __h2, __h),
+      __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
+				_H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
+							__eq),
       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
       _M_node_allocator(__a),
       _M_bucket_count(0),
@@ -727,9 +760,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		 const _Equal& __eq, const _ExtractKey& __exk,
 		 const allocator_type& __a)
       : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
-	__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
-				  _H1, _H2, _Hash, __chc>(__exk, __eq,
-							  __h1, __h2, __h),
+	__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
+				  _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
+							  __eq),
 	__detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
 	_M_node_allocator(__a),
 	_M_bucket_count(0),
@@ -768,7 +801,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
     _Hashtable(const _Hashtable& __ht)
     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
-      __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
+      __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
 				_H1, _H2, _Hash, __chc>(__ht),
       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
       _M_node_allocator(__ht._M_node_allocator),
@@ -833,7 +866,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
     _Hashtable(_Hashtable&& __ht)
     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
-      __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
+      __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
 				_H1, _H2, _Hash, __chc>(__ht),
       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
       _M_node_allocator(std::move(__ht._M_node_allocator)),
@@ -874,8 +907,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // The only base class with member variables is hash_code_base.  We
       // define _Hash_code_base::_M_swap because different specializations
       // have different members.
-      __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
-	_H1, _H2, _Hash, __chc>::_M_swap(__x);
+      this->_M_swap(__x);
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
       // 431. Swapping containers with unequal allocators.
@@ -916,7 +948,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     find(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);
+      std::size_t __n = _M_bucket_index(__k, __code);
       _Node* __p = _M_find_node(__n, __k, __code);
       return __p ? iterator(__p) : this->end();
     }
@@ -933,7 +965,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     find(const key_type& __k) const
     {
       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
-      std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+      std::size_t __n = _M_bucket_index(__k, __code);
       _Node* __p = _M_find_node(__n, __k, __code);
       return __p ? const_iterator(__p) : this->end();
     }
@@ -950,7 +982,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     count(const key_type& __k) const
     {
       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
-      std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+      std::size_t __n = _M_bucket_index(__k, __code);
       _Node* __p = _M_bucket_begin(__n);
       if (!__p)
 	return 0;
@@ -958,16 +990,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       std::size_t __result = 0;
       for (;; __p = __p->_M_next)
 	{
-	  if (this->_M_compare(__k, __code, __p))
+	  if (this->_M_equals(__k, __code, __p))
 	    ++__result;
 	  else if (__result)
 	    // All equivalent values are next to each other, if we found a not
 	    // equivalent value after an equivalent one it means that we won't
 	    // find anymore an equivalent value.
 	    break;
-	  if (!__p->_M_next
-	      || this->_M_bucket_index(__p->_M_next, _M_bucket_count)
-		 != __n)
+	  if (!__p->_M_next || _M_bucket_index(__p->_M_next) != __n)
 	    break;
 	}
       return __result;
@@ -990,15 +1020,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     equal_range(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);
+      std::size_t __n = _M_bucket_index(__k, __code);
       _Node* __p = _M_find_node(__n, __k, __code);
 
       if (__p)
 	{
 	  _Node* __p1 = __p->_M_next;
-	  while (__p1
-		 && this->_M_bucket_index(__p1, _M_bucket_count) == __n
-		 && this->_M_compare(__k, __code, __p1))
+	  while (__p1 && _M_bucket_index(__p1) == __n
+		 && this->_M_equals(__k, __code, __p1))
 	    __p1 = __p1->_M_next;
 
 	  return std::make_pair(iterator(__p), iterator(__p1));
@@ -1024,15 +1053,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     equal_range(const key_type& __k) const
     {
       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
-      std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+      std::size_t __n = _M_bucket_index(__k, __code);
       _Node* __p = _M_find_node(__n, __k, __code);
 
       if (__p)
 	{
 	  _Node* __p1 = __p->_M_next;
-	  while (__p1
-		 && this->_M_bucket_index(__p1, _M_bucket_count) == __n
-		 && this->_M_compare(__k, __code, __p1))
+	  while (__p1 && _M_bucket_index(__p1) == __n
+		 && this->_M_equals(__k, __code, __p1))
 	    __p1 = __p1->_M_next;
 
 	  return std::make_pair(const_iterator(__p), const_iterator(__p1));
@@ -1060,10 +1088,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return nullptr;
       for (;; __p = __p->_M_next)
 	{
-	  if (this->_M_compare(__k, __code, __p))
+	  if (this->_M_equals(__k, __code, __p))
 	    return __p;
-	  if (!(__p->_M_next)
-	      || this->_M_bucket_index(__p->_M_next, _M_bucket_count) != __n)
+	  if (!(__p->_M_next) || _M_bucket_index(__p->_M_next) != __n)
 	    break;
 	}
       return nullptr;
@@ -1119,8 +1146,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       if (__prev_n->_M_next)
 	{
-	  size_type __next_bkt =
-	    this->_M_bucket_index(__prev_n->_M_next, _M_bucket_count);
+	  size_type __next_bkt = _M_bucket_index(__prev_n->_M_next);
 	  if (__next_bkt != __bkt)
 	    _M_buckets[__next_bkt] = __new_n;
 	}
@@ -1196,11 +1222,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
 	__try
 	  {
-	    const key_type& __k = this->_M_extract(__new_node->_M_v);
+	    const key_type& __k = this->_M_extract()(__new_node->_M_v);
 	    typename _Hashtable::_Hash_code_type __code
 	      = this->_M_hash_code(__k);
-	    size_type __bkt
-	      = this->_M_bucket_index(__k, __code, _M_bucket_count);
+	    size_type __bkt = _M_bucket_index(__k, __code);
 
 	    if (_Node* __p = _M_find_node(__bkt, __k, __code))
 	      {
@@ -1220,7 +1245,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    if (__do_rehash.first)
 	      {
 		_M_rehash(__do_rehash.second, __saved_state);
-		__bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+		__bkt = _M_bucket_index(__k, __code);
 	      }
 
 	    if (_M_buckets[__bkt])
@@ -1258,12 +1283,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
 	__try
 	  {
-	    const key_type& __k = this->_M_extract(__new_node->_M_v);
+	    const key_type& __k = this->_M_extract()(__new_node->_M_v);
 	    typename _Hashtable::_Hash_code_type __code
 	      = this->_M_hash_code(__k);
 	    this->_M_store_code(__new_node, __code);
-	    size_type __bkt
-	      = this->_M_bucket_index(__k, __code, _M_bucket_count);
+	    size_type __bkt = _M_bucket_index(__k, __code);
 
 	    // Second find the node, avoid rehash if compare throws.
 	    _Node* __prev = _M_find_node(__bkt, __k, __code);
@@ -1271,7 +1295,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    if (__do_rehash.first)
 	      {
 		_M_rehash(__do_rehash.second, __saved_state);
-		__bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+		__bkt = _M_bucket_index(__k, __code);
 		// __prev is still valid because rehash do not invalidate nodes
 	      }
 
@@ -1322,8 +1346,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	if (__do_rehash.first)
 	  {
-	    const key_type& __k = this->_M_extract(__v);
-	    __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
+	    const key_type& __k = this->_M_extract()(__v);
+	    __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second);
 	  }
 
 	_Node* __new_node = nullptr;
@@ -1367,9 +1391,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
       _M_insert(_Arg&& __v, std::true_type)
       {
-	const key_type& __k = this->_M_extract(__v);
+	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);
+	size_type __n = _M_bucket_index(__k, __code);
 
 	if (_Node* __p = _M_find_node(__n, __k, __code))
 	  return std::make_pair(iterator(__p), false);
@@ -1395,9 +1419,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  = _M_rehash_policy._M_need_rehash(_M_bucket_count,
 					    _M_element_count, 1);
 
-	const key_type& __k = this->_M_extract(__v);
+	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);
+	size_type __n = _M_bucket_index(__k, __code);
 
 	// First find the node, avoid leaking new_node if compare throws.
 	_Node* __prev = _M_find_node(__n, __k, __code);
@@ -1410,7 +1434,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    if (__do_rehash.first)
 	      {
 		_M_rehash(__do_rehash.second, __saved_state);
-		__n = this->_M_bucket_index(__k, __code, _M_bucket_count);
+		__n = _M_bucket_index(__k, __code);
 		// __prev is still valid because rehash do not invalidate nodes
 	      }
 
@@ -1477,7 +1501,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     erase(const_iterator __it)
     {
       _Node* __n = __it._M_cur;
-      std::size_t __bkt = this->_M_bucket_index(__n, _M_bucket_count);
+      std::size_t __bkt = _M_bucket_index(__n);
 
       // Look for previous node to unlink it from the erased one, this is why
       // we need buckets to contain the before begin node of the bucket to make
@@ -1485,12 +1509,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _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);
+	   __n->_M_next ? _M_bucket_index(__n->_M_next) : 0);
       else if (__n->_M_next)
 	{
-	  size_type __next_bkt =
-	    this->_M_bucket_index(__n->_M_next, _M_bucket_count);
+	  size_type __next_bkt = _M_bucket_index(__n->_M_next);
 	  if (__next_bkt != __bkt)
 	    _M_buckets[__next_bkt] = __prev_n;
 	}
@@ -1516,7 +1538,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     erase(const key_type& __k)
     {
       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
-      std::size_t __bkt = this->_M_bucket_index(__k, __code, _M_bucket_count);
+      std::size_t __bkt = _M_bucket_index(__k, __code);
       // Look for the first matching node with its previous node at the same
       // time
       _Node* __n = _M_buckets[__bkt];
@@ -1531,10 +1553,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       bool __is_bucket_begin = true;
       for (;; __prev_n = __n, __n = __n->_M_next)
 	{
-	  if (this->_M_compare(__k, __code, __n))
+	  if (this->_M_equals(__k, __code, __n))
 	    break;
-	  if (!(__n->_M_next)
-	      || this->_M_bucket_index(__n->_M_next, _M_bucket_count) != __bkt)
+	  if (!(__n->_M_next) || _M_bucket_index(__n->_M_next) != __bkt)
 	    return 0;
 	  __is_bucket_begin = false;
 	}
@@ -1551,7 +1572,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
 	  // 526. Is it undefined if a function in the standard changes
 	  // in parameters?
-	  if (std::__addressof(this->_M_extract(__p->_M_v))
+	  if (std::__addressof(this->_M_extract()(__p->_M_v))
 	      != std::__addressof(__k))
 	    _M_deallocate_node(__p);
 	  else
@@ -1560,9 +1581,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  ++__result;
 	  if (!__next_n)
 	    break;
-	  __next_bkt = this->_M_bucket_index(__next_n, _M_bucket_count);
+	  __next_bkt = _M_bucket_index(__next_n);
 	}
-      while (__next_bkt == __bkt && this->_M_compare(__k, __code, __next_n));
+      while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n));
 
       if (__saved_n)
 	_M_deallocate_node(__saved_n);
@@ -1591,7 +1612,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (__n == __last_n)
 	return iterator(__n);
 
-      std::size_t __bkt = this->_M_bucket_index(__n, _M_bucket_count);
+      std::size_t __bkt = _M_bucket_index(__n);
 
       _Node* __prev_n = _M_get_previous_node(__bkt, __n);
       bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
@@ -1606,7 +1627,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      --_M_element_count;
 	      if (!__n)
 		break;
-	      __n_bkt = this->_M_bucket_index(__n, _M_bucket_count);
+	      __n_bkt = _M_bucket_index(__n);
 	    }
 	  while (__n != __last_n && __n_bkt == __bkt);
 	  if (__is_bucket_begin)
@@ -1672,7 +1693,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  while (__p)
 	    {
 	      _Node* __next = __p->_M_next;
-	      std::size_t __new_index = this->_M_bucket_index(__p, __n);
+	      std::size_t __new_index = _HCBase::_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
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index e97685c6ae7..261e56bfcb0 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -101,8 +101,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  _M_next() { }
     };
 
-  // Local iterators, used to iterate within a bucket but not between
-  // buckets.
+  // Node iterators, used to iterate through all the hashtable.
   template<typename _Value, bool __cache>
     struct _Node_iterator_base
     {
@@ -425,8 +424,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       _Hashtable* __h = static_cast<_Hashtable*>(this);
       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
-      std::size_t __n = __h->_M_bucket_index(__k, __code,
-					     __h->_M_bucket_count);
+      std::size_t __n = __h->_M_bucket_index(__k, __code);
 
       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
       if (!__p)
@@ -443,8 +441,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       _Hashtable* __h = static_cast<_Hashtable*>(this);
       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
-      std::size_t __n = __h->_M_bucket_index(__k, __code,
-					     __h->_M_bucket_count);
+      std::size_t __n = __h->_M_bucket_index(__k, __code);
 
       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
       if (!__p)
@@ -462,8 +459,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       _Hashtable* __h = static_cast<_Hashtable*>(this);
       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
-      std::size_t __n = __h->_M_bucket_index(__k, __code,
-					     __h->_M_bucket_count);
+      std::size_t __n = __h->_M_bucket_index(__k, __code);
 
       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
       if (!__p)
@@ -479,8 +475,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       const _Hashtable* __h = static_cast<const _Hashtable*>(this);
       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
-      std::size_t __n = __h->_M_bucket_index(__k, __code,
-					     __h->_M_bucket_count);
+      std::size_t __n = __h->_M_bucket_index(__k, __code);
 
       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
       if (!__p)
@@ -518,6 +513,49 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       }
     };
 
+  // Helper class using EBO when it is not forbidden, type is not final,
+  // and when it worth it, type is empty.
+  template<int _Nm, typename _Tp,
+	   bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
+    struct _Ebo_helper;
+
+  // Specialization using EBO.
+  template<int _Nm, typename _Tp>
+    struct _Ebo_helper<_Nm, _Tp, true> : _Tp
+    {
+      _Ebo_helper() = default;
+      _Ebo_helper(const _Tp& __tp) : _Tp(__tp)
+      { }
+
+      static const _Tp&
+      _S_cget(const _Ebo_helper& __eboh)
+      { return static_cast<const _Tp&>(__eboh); }
+
+      static _Tp&
+      _S_get(_Ebo_helper& __eboh)
+      { return static_cast<_Tp&>(__eboh); }
+    };
+
+  // Specialization not using EBO.
+  template<int _Nm, typename _Tp>
+    struct _Ebo_helper<_Nm, _Tp, false>
+    {
+      _Ebo_helper() = default;
+      _Ebo_helper(const _Tp& __tp) : __m_tp(__tp)
+      { }
+
+      static const _Tp&
+      _S_cget(const _Ebo_helper& __eboh)
+      { return __eboh.__m_tp; }
+
+      static _Tp&
+      _S_get(_Ebo_helper& __eboh)
+      { return __eboh.__m_tp; }
+
+    private:
+      _Tp __m_tp;
+    };
+
   // Class template _Hash_code_base.  Encapsulates two policy issues that
   // aren't quite orthogonal.
   //   (1) the difference between using a ranged hash function and using
@@ -526,28 +564,36 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   //       we have a dummy type as placeholder.
   //   (2) Whether or not we cache hash codes.  Caching hash codes is
   //       meaningless if we have a ranged hash function.
-  // We also put the key extraction and equality comparison function
-  // objects here, for convenience.
+  // We also put the key extraction objects here, for convenience.
+  //
+  // Each specialization derives from one or more of the template parameters to
+  // benefit from Ebo. This is important as this type is inherited in some cases
+  // by the _Local_iterator_base type used to implement local_iterator and
+  // const_local_iterator. As with any iterator type we prefer to make it as
+  // small as possible.
 
   // Primary template: unused except as a hook for specializations.
-  template<typename _Key, typename _Value,
-	   typename _ExtractKey, typename _Equal,
+  template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash,
 	   bool __cache_hash_code>
     struct _Hash_code_base;
 
   // Specialization: ranged hash function, no caching hash codes.  H1
   // and H2 are provided but ignored.  We define a dummy hash code type.
-  template<typename _Key, typename _Value,
-	   typename _ExtractKey, typename _Equal,
+  template<typename _Key, typename _Value, typename _ExtractKey, 
 	   typename _H1, typename _H2, typename _Hash>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
-			   _Hash, false>
+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
+    : _Ebo_helper<0, _ExtractKey>, _Ebo_helper<1, _Hash>
     {
+    private:
+      typedef _Ebo_helper<0, _ExtractKey> _EboExtractKey;
+      typedef _Ebo_helper<1, _Hash> _EboHash;
     protected:
-      _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
+      // We need the default constructor for the local iterators.
+      _Hash_code_base() = default;
+      _Hash_code_base(const _ExtractKey& __ex,
 		      const _H1&, const _H2&, const _Hash& __h)
-      : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { }
+	: _EboExtractKey(__ex), _EboHash(__h) { }
 
       typedef void* _Hash_code_type;
 
@@ -558,17 +604,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       std::size_t
       _M_bucket_index(const _Key& __k, _Hash_code_type,
 		      std::size_t __n) const
-      { return _M_ranged_hash(__k, __n); }
+      { return _M_ranged_hash()(__k, __n); }
 
       std::size_t
       _M_bucket_index(const _Hash_node<_Value, false>* __p,
 		      std::size_t __n) const
-      { return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
-
-      bool
-      _M_compare(const _Key& __k, _Hash_code_type,
-		 _Hash_node<_Value, false>* __n) const
-      { return _M_eq(__k, _M_extract(__n->_M_v)); }
+      { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); }
 
       void
       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
@@ -582,72 +623,75 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       void
       _M_swap(_Hash_code_base& __x)
       {
-	std::swap(_M_extract, __x._M_extract);
-	std::swap(_M_eq, __x._M_eq);
-	std::swap(_M_ranged_hash, __x._M_ranged_hash);
+	std::swap(_M_extract(), __x._M_extract());
+	std::swap(_M_ranged_hash(), __x._M_ranged_hash());
       }
 
     protected:
-      _ExtractKey  _M_extract;
-      _Equal       _M_eq;
-      _Hash        _M_ranged_hash;
+      const _ExtractKey&
+      _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+      _ExtractKey&
+      _M_extract() { return _EboExtractKey::_S_get(*this); }
+      const _Hash&
+      _M_ranged_hash() const { return _EboHash::_S_cget(*this); }
+      _Hash&
+      _M_ranged_hash() { return _EboHash::_S_get(*this); }
     };
 
-
   // No specialization for ranged hash function while caching hash codes.
   // That combination is meaningless, and trying to do it is an error.
 
-
   // Specialization: ranged hash function, cache hash codes.  This
   // combination is meaningless, so we provide only a declaration
   // and no definition.
-  template<typename _Key, typename _Value,
-	   typename _ExtractKey, typename _Equal,
+  template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
-			   _Hash, true>;
+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
 
   // Specialization: hash function and range-hashing function, no
-  // caching of hash codes.  H is provided but ignored.  Provides
-  // typedef and accessor required by TR1.
-  template<typename _Key, typename _Value,
-	   typename _ExtractKey, typename _Equal,
+  // caching of hash codes.
+  // Provides typedef and accessor required by TR1.
+  template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
 			   _Default_ranged_hash, false>
+    : _Ebo_helper<0, _ExtractKey>, _Ebo_helper<1, _H1>, _Ebo_helper<2, _H2>
     {
+    private:
+      typedef _Ebo_helper<0, _ExtractKey> _EboExtractKey;
+      typedef _Ebo_helper<1, _H1> _EboH1;
+      typedef _Ebo_helper<2, _H2> _EboH2;
+
+    public:
       typedef _H1 hasher;
 
       hasher
       hash_function() const
-      { return _M_h1; }
+      { return _M_h1(); }
 
     protected:
-      _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
+      // We need the default constructor for the local iterators.
+      _Hash_code_base() = default;
+      _Hash_code_base(const _ExtractKey& __ex,
 		      const _H1& __h1, const _H2& __h2,
 		      const _Default_ranged_hash&)
-      : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
+      : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
 
       typedef std::size_t _Hash_code_type;
 
       _Hash_code_type
       _M_hash_code(const _Key& __k) const
-      { return _M_h1(__k); }
+      { return _M_h1()(__k); }
 
       std::size_t
       _M_bucket_index(const _Key&, _Hash_code_type __c,
 		      std::size_t __n) const
-      { return _M_h2(__c, __n); }
+      { return _M_h2()(__c, __n); }
 
       std::size_t
       _M_bucket_index(const _Hash_node<_Value, false>* __p,
 		      std::size_t __n) const
-      { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
-
-      bool
-      _M_compare(const _Key& __k, _Hash_code_type,
-		 _Hash_node<_Value, false>* __n) const
-      { return _M_eq(__k, _M_extract(__n->_M_v)); }
+      { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); }
 
       void
       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
@@ -661,60 +705,68 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       void
       _M_swap(_Hash_code_base& __x)
       {
-	std::swap(_M_extract, __x._M_extract);
-	std::swap(_M_eq, __x._M_eq);
-	std::swap(_M_h1, __x._M_h1);
-	std::swap(_M_h2, __x._M_h2);
+	std::swap(_M_extract(), __x._M_extract());
+	std::swap(_M_h1(), __x._M_h1());
+	std::swap(_M_h2(), __x._M_h2());
       }
 
     protected:
-      _ExtractKey  _M_extract;
-      _Equal       _M_eq;
-      _H1          _M_h1;
-      _H2          _M_h2;
+      const _ExtractKey&
+      _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+      _ExtractKey&
+      _M_extract() { return _EboExtractKey::_S_get(*this); }
+      const _H1&
+      _M_h1() const { return _EboH1::_S_cget(*this); }
+      _H1&
+      _M_h1() { return _EboH1::_S_get(*this); }
+      const _H2&
+      _M_h2() const { return _EboH2::_S_cget(*this); }
+      _H2&
+      _M_h2() { return _EboH2::_S_get(*this); }
     };
 
   // Specialization: hash function and range-hashing function,
   // caching hash codes.  H is provided but ignored.  Provides
   // typedef and accessor required by TR1.
-  template<typename _Key, typename _Value,
-	   typename _ExtractKey, typename _Equal,
+  template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
 			   _Default_ranged_hash, true>
+    : _Ebo_helper<0, _ExtractKey>, _Ebo_helper<1, _H1>, _Ebo_helper<2, _H2>
     {
+    private:
+      typedef _Ebo_helper<0, _ExtractKey> _EboExtractKey;
+      typedef _Ebo_helper<1, _H1> _EboH1;
+      typedef _Ebo_helper<2, _H2> _EboH2;
+
+    public:
       typedef _H1 hasher;
 
       hasher
       hash_function() const
-      { return _M_h1; }
+      { return _M_h1(); }
 
     protected:
-      _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
+      _Hash_code_base(const _ExtractKey& __ex,
 		      const _H1& __h1, const _H2& __h2,
 		      const _Default_ranged_hash&)
-      : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
+      : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
 
       typedef std::size_t _Hash_code_type;
 
       _Hash_code_type
       _M_hash_code(const _Key& __k) const
-      { return _M_h1(__k); }
+      { return _M_h1()(__k); }
 
       std::size_t
       _M_bucket_index(const _Key&, _Hash_code_type __c,
 		      std::size_t __n) const
-      { return _M_h2(__c, __n); }
+      { return _M_h2()(__c, __n); }
 
       std::size_t
       _M_bucket_index(const _Hash_node<_Value, true>* __p,
 		      std::size_t __n) const
-      { return _M_h2(__p->_M_hash_code, __n); }
-
-      bool
-      _M_compare(const _Key& __k, _Hash_code_type __c,
-		 _Hash_node<_Value, true>* __n) const
-      { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); }
+      { return _M_h2()(__p->_M_hash_code, __n); }
 
       void
       _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
@@ -728,17 +780,290 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       void
       _M_swap(_Hash_code_base& __x)
       {
-	std::swap(_M_extract, __x._M_extract);
-	std::swap(_M_eq, __x._M_eq);
-	std::swap(_M_h1, __x._M_h1);
-	std::swap(_M_h2, __x._M_h2);
+	std::swap(_M_extract(), __x._M_extract());
+	std::swap(_M_h1(), __x._M_h1());
+	std::swap(_M_h2(), __x._M_h2());
       }
 
     protected:
-      _ExtractKey  _M_extract;
-      _Equal       _M_eq;
-      _H1          _M_h1;
-      _H2          _M_h2;
+      const _ExtractKey&
+      _M_extract() const { return _EboExtractKey::_S_cget(*this); }
+      _ExtractKey&
+      _M_extract() { return _EboExtractKey::_S_get(*this); }
+      const _H1&
+      _M_h1() const { return _EboH1::_S_cget(*this); }
+      _H1&
+      _M_h1() { return _EboH1::_S_get(*this); }
+      const _H2&
+      _M_h2() const { return _EboH2::_S_cget(*this); }
+      _H2&
+      _M_h2() { return _EboH2::_S_get(*this); }
+    };
+
+  template <typename _Key, typename _Value, typename _ExtractKey,
+	    typename _Equal, typename _HashCodeType,
+	    bool __cache_hash_code>
+  struct _Equal_helper;
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+	   typename _Equal, typename _HashCodeType>
+  struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true>
+  {
+    static bool
+    _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
+	      const _Key& __k, _HashCodeType __c,
+	      _Hash_node<_Value, true>* __n)
+    { return __c == __n->_M_hash_code
+	     && __eq(__k, __extract(__n->_M_v)); }
+  };
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+	   typename _Equal, typename _HashCodeType>
+  struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false>
+  {
+    static bool
+    _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
+	      const _Key& __k, _HashCodeType,
+	      _Hash_node<_Value, false>* __n)
+    { return __eq(__k, __extract(__n->_M_v)); }
+  };
+
+  // Helper class adding management of _Equal functor to _Hash_code_base
+  // type.
+  template<typename _Key, typename _Value,
+	   typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash,
+	   bool __cache_hash_code>
+  struct _Hashtable_base
+  : _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+		    __cache_hash_code>,
+    _Ebo_helper<0, _Equal>
+  {
+  private:
+    typedef _Ebo_helper<0, _Equal> _EboEqual;
+
+  protected:
+    typedef _Hash_code_base<_Key, _Value, _ExtractKey,
+			    _H1, _H2, _Hash, __cache_hash_code> _HCBase;
+    typedef typename _HCBase::_Hash_code_type _Hash_code_type;
+
+    _Hashtable_base(const _ExtractKey& __ex,
+		    const _H1& __h1, const _H2& __h2,
+		    const _Hash& __hash, const _Equal& __eq)
+      : _HCBase(__ex, __h1, __h2, __hash), _EboEqual(__eq) { }
+
+    bool
+    _M_equals(const _Key& __k, _Hash_code_type __c,
+	      _Hash_node<_Value, __cache_hash_code>* __n) const
+    {
+      typedef _Equal_helper<_Key, _Value, _ExtractKey,
+			   _Equal, _Hash_code_type,
+			   __cache_hash_code> _EqualHelper;
+      return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(), __k, __c, __n);
+    }
+
+    void
+    _M_swap(_Hashtable_base& __x)
+    {
+      _HCBase::_M_swap(__x);
+      std::swap(_M_eq(), __x._M_eq());
+    }
+
+  private:
+    const _Equal&
+    _M_eq() const { return _EboEqual::_S_cget(*this); }
+    _Equal&
+    _M_eq() { return _EboEqual::_S_get(*this); }
+  };
+
+  // Local iterators, used to iterate within a bucket but not between
+  // buckets.
+  template<typename _Key, typename _Value, typename _ExtractKey,
+	   typename _H1, typename _H2, typename _Hash,
+	   bool __cache_hash_code>
+    struct _Local_iterator_base;
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+	   typename _H1, typename _H2, typename _Hash>
+    struct _Local_iterator_base<_Key, _Value, _ExtractKey,
+				_H1, _H2, _Hash, true>
+      : _H2
+    {
+      _Local_iterator_base() = default;
+      _Local_iterator_base(_Hash_node<_Value, true>* __p,
+			   std::size_t __bkt, std::size_t __bkt_count)
+      : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+
+      void
+      _M_incr()
+      {
+	_M_cur = _M_cur->_M_next;
+	if (_M_cur)
+	  {
+	    std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count);
+	    if (__bkt != _M_bucket)
+	      _M_cur = nullptr;
+	  }
+      }
+
+      const _H2& _M_h2() const
+      { return *this; }
+
+      _Hash_node<_Value, true>*  _M_cur;
+      std::size_t _M_bucket;
+      std::size_t _M_bucket_count;
+    };
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+	   typename _H1, typename _H2, typename _Hash>
+    struct _Local_iterator_base<_Key, _Value, _ExtractKey,
+				_H1, _H2, _Hash, false>
+      : _Hash_code_base<_Key, _Value, _ExtractKey,
+			_H1, _H2, _Hash, false>
+    {
+      _Local_iterator_base() = default;
+      _Local_iterator_base(_Hash_node<_Value, false>* __p,
+			   std::size_t __bkt, std::size_t __bkt_count)
+      : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+
+      void
+      _M_incr()
+      {
+	_M_cur = _M_cur->_M_next;
+	if (_M_cur)
+	  {
+	    std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
+	    if (__bkt != _M_bucket)
+	      _M_cur = nullptr;
+	  }
+      }
+
+      _Hash_node<_Value, false>*  _M_cur;
+      std::size_t _M_bucket;
+      std::size_t _M_bucket_count;
+    };
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+	   typename _H1, typename _H2, typename _Hash, bool __cache>
+    inline bool
+    operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
+					  _H1, _H2, _Hash, __cache>& __x,
+	       const _Local_iterator_base<_Key, _Value, _ExtractKey,
+					  _H1, _H2, _Hash, __cache>& __y)
+    { return __x._M_cur == __y._M_cur; }
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+	   typename _H1, typename _H2, typename _Hash, bool __cache>
+    inline bool
+    operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
+					  _H1, _H2, _Hash, __cache>& __x,
+	       const _Local_iterator_base<_Key, _Value, _ExtractKey,
+					  _H1, _H2, _Hash, __cache>& __y)
+    { return __x._M_cur != __y._M_cur; }
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+	   typename _H1, typename _H2, typename _Hash,
+	   bool __constant_iterators, bool __cache>
+    struct _Local_iterator
+    : public _Local_iterator_base<_Key, _Value, _ExtractKey,
+				  _H1, _H2, _Hash, __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;
+
+      _Local_iterator() = default;
+
+      explicit
+      _Local_iterator(_Hash_node<_Value, __cache>* __p,
+		      std::size_t __bkt, std::size_t __bkt_count)
+      : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+			     __cache>(__p, __bkt, __bkt_count)
+      { }
+
+      reference
+      operator*() const
+      { return this->_M_cur->_M_v; }
+
+      pointer
+      operator->() const
+      { return std::__addressof(this->_M_cur->_M_v); }
+
+      _Local_iterator&
+      operator++()
+      {
+	this->_M_incr();
+	return *this;
+      }
+
+      _Local_iterator
+      operator++(int)
+      {
+	_Local_iterator __tmp(*this);
+	this->_M_incr();
+	return __tmp;
+      }
+    };
+
+  template<typename _Key, typename _Value, typename _ExtractKey,
+	   typename _H1, typename _H2, typename _Hash,
+	   bool __constant_iterators, bool __cache>
+    struct _Local_const_iterator
+    : public _Local_iterator_base<_Key, _Value, _ExtractKey,
+				  _H1, _H2, _Hash, __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;
+
+      _Local_const_iterator() = default;
+
+      explicit
+      _Local_const_iterator(_Hash_node<_Value, __cache>* __p,
+			    std::size_t __bkt, std::size_t __bkt_count)
+      : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+			     __cache>(__p, __bkt, __bkt_count)
+      { }
+
+      _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
+						  _H1, _H2, _Hash,
+						  __constant_iterators,
+						  __cache>& __x)
+      : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+			     __cache>(__x._M_cur, __x._M_bucket,
+				      __x._M_bucket_count)
+      { }
+
+      reference
+      operator*() const
+      { return this->_M_cur->_M_v; }
+
+      pointer
+      operator->() const
+      { return std::__addressof(this->_M_cur->_M_v); }
+
+      _Local_const_iterator&
+      operator++()
+      {
+	this->_M_incr();
+	return *this;
+      }
+
+      _Local_const_iterator
+      operator++(int)
+      {
+	_Local_const_iterator __tmp(*this);
+	this->_M_incr();
+	return __tmp;
+      }
     };
 
 
diff --git a/libstdc++-v3/include/bits/regex.h b/libstdc++-v3/include/bits/regex.h
index cc1abccaba0..4c496653cb8 100644
--- a/libstdc++-v3/include/bits/regex.h
+++ b/libstdc++-v3/include/bits/regex.h
@@ -1490,8 +1490,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       typedef const_iterator                                  iterator;
       typedef typename std::iterator_traits<_Bi_iter>::difference_type
                                                               difference_type;
-      /* TODO: needs allocator_traits */
-      typedef typename _Allocator::size_type                  size_type;
+      typedef typename allocator_traits<_Allocator>::size_type
+                                                              size_type;
       typedef _Allocator                                      allocator_type;
       typedef typename std::iterator_traits<_Bi_iter>::value_type
                                                               char_type;
@@ -2223,7 +2223,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		  regex_constants::match_flag_type __flags
 		  = regex_constants::match_default)
     {
-      std::string __result;
+      basic_string<_Ch_type> __result;
       regex_replace(std::back_inserter(__result),
 		    __s.begin(), __s.end(), __e, __fmt, __flags);
       return __result;
diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h
index 7c810d3801f..95f5657762a 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -41,7 +41,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	   class _Pred = std::equal_to<_Key>,
 	   class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
 	   bool __cache_hash_code =
-	     __not_<__and_<is_integral<_Key>,
+	     __not_<__and_<is_integral<_Key>, is_empty<_Hash>,
+			   integral_constant<bool, !__is_final(_Hash)>,
 			   __detail::__is_noexcept_hash<_Key, _Hash>>>::value>
     class __unordered_map
     : public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
@@ -112,7 +113,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	   class _Pred = std::equal_to<_Key>,
 	   class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
 	   bool __cache_hash_code =
-	     __not_<__and_<is_integral<_Key>,
+	     __not_<__and_<is_integral<_Key>, is_empty<_Hash>,
+			   integral_constant<bool, !__is_final(_Hash)>,
 			   __detail::__is_noexcept_hash<_Key, _Hash>>>::value>
     class __unordered_multimap
     : public _Hashtable<_Key, std::pair<const _Key, _Tp>,
diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h
index 9aef0829749..3d5361d4266 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -41,7 +41,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	   class _Pred = std::equal_to<_Value>,
 	   class _Alloc = std::allocator<_Value>,
 	   bool __cache_hash_code =
-	     __not_<__and_<is_integral<_Value>,
+	     __not_<__and_<is_integral<_Value>, is_empty<_Hash>,
+			   integral_constant<bool, !__is_final(_Hash)>,
 			   __detail::__is_noexcept_hash<_Value, _Hash>>>::value>
     class __unordered_set
     : public _Hashtable<_Value, _Value, _Alloc,
@@ -124,7 +125,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	   class _Pred = std::equal_to<_Value>,
 	   class _Alloc = std::allocator<_Value>,
 	   bool __cache_hash_code =
-	     __not_<__and_<is_integral<_Value>,
+	     __not_<__and_<is_integral<_Value>, is_empty<_Hash>,
+			   integral_constant<bool, !__is_final(_Hash)>,
 			   __detail::__is_noexcept_hash<_Value, _Hash>>>::value>
     class __unordered_multiset
     : public _Hashtable<_Value, _Value, _Alloc,
diff --git a/libstdc++-v3/include/c_global/cinttypes b/libstdc++-v3/include/c_global/cinttypes
index df733407bd3..030962bdf32 100644
--- a/libstdc++-v3/include/c_global/cinttypes
+++ b/libstdc++-v3/include/c_global/cinttypes
@@ -1,6 +1,6 @@
 // <cinttypes> -*- C++ -*-
 
-// Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
 // software; you can redistribute it and/or modify it under the
@@ -37,7 +37,7 @@
 
 #include <cstdint>
 
-// For 8.11.1/1 (see C99, Note 184)
+// For 27.9.2/3 (see C99, Note 184)
 #if _GLIBCXX_HAVE_INTTYPES_H
 # ifndef __STDC_FORMAT_MACROS
 #  define _UNDEF__STDC_FORMAT_MACROS
@@ -59,16 +59,10 @@ namespace std
 
   // functions
   using ::imaxabs;
-
-  // May collide with _Longlong abs(_Longlong), and is not described
-  // anywhere outside the synopsis.  Likely, a defect.
-  //
-  // intmax_t abs(intmax_t)
-
   using ::imaxdiv;
 
-  // Likewise, with lldiv_t div(_Longlong, _Longlong).
-  //
+  // GCC does not support extended integer types
+  // intmax_t abs(intmax_t)
   // imaxdiv_t div(intmax_t, intmax_t)
 
   using ::strtoimax;
diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index cf84948f049..37ca3cee7cc 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -418,11 +418,19 @@ namespace __debug
 
       static _Base_local_iterator
       _S_to_local(_Base_iterator __it)
-      { return _Base_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+	// need to compute __it's node bucket
+	return _Base_local_iterator(__it._M_cur, 0, 0);
+      }
 
       static _Base_const_local_iterator
       _S_to_local(_Base_const_iterator __it)
-      { return _Base_const_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+	// need to compute __it's node bucket
+	return _Base_const_local_iterator(__it._M_cur, 0, 0);
+      }
     };
 
   template<typename _Key, typename _Tp, typename _Hash,
@@ -820,11 +828,19 @@ namespace __debug
 
       static _Base_local_iterator
       _S_to_local(_Base_iterator __it)
-      { return _Base_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+	// need to compute __it's node bucket
+	return _Base_local_iterator(__it._M_cur, 0, 0);
+      }
 
       static _Base_const_local_iterator
       _S_to_local(_Base_const_iterator __it)
-      { return _Base_const_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+	// need to compute __it's node bucket
+	return _Base_const_local_iterator(__it._M_cur, 0, 0);
+      }
     };
 
   template<typename _Key, typename _Tp, typename _Hash,
diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set
index ba4404028e3..7323184d438 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -417,11 +417,19 @@ namespace __debug
 
       static _Base_local_iterator
       _S_to_local(_Base_iterator __it)
-      { return _Base_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+	// need to compute __it's node bucket
+	return _Base_local_iterator(__it._M_cur, 0, 0);
+      }
 
       static _Base_const_local_iterator
       _S_to_local(_Base_const_iterator __it)
-      { return _Base_const_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+	// need to compute __it's node bucket
+	return _Base_const_local_iterator(__it._M_cur, 0, 0);
+      }
     };
 
   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
@@ -805,11 +813,19 @@ namespace __debug
 
       static _Base_local_iterator
       _S_to_local(_Base_iterator __it)
-      { return _Base_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+	// need to compute __it's node bucket
+	return _Base_local_iterator(__it._M_cur, 0, 0);
+      }
 
       static _Base_const_local_iterator
       _S_to_local(_Base_const_iterator __it)
-      { return _Base_const_local_iterator(__it._M_cur); }
+      {
+        // The returned local iterator will not be incremented so we don't
+	// need to compute __it's node bucket
+	return _Base_const_local_iterator(__it._M_cur, 0, 0);
+      }
     };
 
   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
diff --git a/libstdc++-v3/include/profile/unordered_map b/libstdc++-v3/include/profile/unordered_map
index 3688d549f65..1d0f0d53064 100644
--- a/libstdc++-v3/include/profile/unordered_map
+++ b/libstdc++-v3/include/profile/unordered_map
@@ -308,9 +308,9 @@ namespace __profile
 	while (__it != this->end())
 	  {
 	    size_type __bkt = this->bucket(__it->first);
-	    for (++__it; __it != this->end()
-			 && this->bucket(__it->first) == __bkt;
-		 ++__it)
+	    auto __lit = this->begin(__bkt);
+	    auto __lend = this->end(__bkt);
+	    for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
 	      ++__chain;
 	    if (__chain)
 	      {
@@ -577,9 +577,9 @@ namespace __profile
 	while (__it != this->end())
 	  {
 	    size_type __bkt = this->bucket(__it->first);
-	    for (++__it; __it != this->end()
-			 && this->bucket(__it->first) == __bkt;
-		 ++__it)
+	    auto __lit = this->begin(__bkt);
+	    auto __lend = this->end(__bkt);
+	    for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
 	      ++__chain;
 	    if (__chain)
 	      {
diff --git a/libstdc++-v3/include/profile/unordered_set b/libstdc++-v3/include/profile/unordered_set
index 55177b33559..7bb10dc45c0 100644
--- a/libstdc++-v3/include/profile/unordered_set
+++ b/libstdc++-v3/include/profile/unordered_set
@@ -277,10 +277,10 @@ namespace __profile
 	while (__it != this->end())
 	  {
 	    size_type __bkt = this->bucket(*__it);
-	    for (++__it; __it != this->end() && this->bucket(*__it) == __bkt;
-		 ++__it)
+	    auto __lit = this->begin(__bkt);
+	    auto __lend = this->end(__bkt);
+	    for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
 	      ++__chain;
-
 	    if (__chain)
 	      {
 		++__chain;
@@ -539,10 +539,10 @@ namespace __profile
 	while (__it != this->end())
 	  {
 	    size_type __bkt = this->bucket(*__it);
-	    for (++__it; __it != this->end() && this->bucket(*__it) == __bkt;
-		 ++__it)
+	    auto __lit = this->begin(__bkt);
+	    auto __lend = this->end(__bkt);
+	    for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
 	      ++__chain;
-
 	    if (__chain)
 	      {
 		++__chain;
diff --git a/libstdc++-v3/include/std/future b/libstdc++-v3/include/std/future
index 040f573ea72..d3180e9a6cf 100644
--- a/libstdc++-v3/include/std/future
+++ b/libstdc++-v3/include/std/future
@@ -60,10 +60,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   /// Error code for futures
   enum class future_errc
   {
-    broken_promise,
-    future_already_retrieved,
+    future_already_retrieved = 1,
     promise_already_satisfied,
-    no_state
+    no_state,
+    broken_promise
   };
 
   /// Specialization.