CbC/CbC_gcc: libstdc++-v3/include/bits/hashtable.h comparison

comparison libstdc++-v3/include/bits/hashtable.h @ 145:1830386684a0

gcc-9.2.0

author	anatofuz
date	Thu, 13 Feb 2020 11:34:05 +0900
parents	84e7813d76e9
children	dafe684d005c

comparison

equal deleted inserted replaced

-:84e7813d76e9
+:1830386684a0
 // hashtable.h header -*- C++ -*-
-// Copyright (C) 2007-2018 Free Software Foundation, Inc.
+// Copyright (C) 2007-2020 Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
 // software; you can redistribute it and/or modify it under the
 // terms of the GNU General Public License as published by the
 // Free Software Foundation; either version 3, or (at your option)
 		       __detail::_Hash_node<_Value,
 					    _Traits::__hash_cached::value>>>
 {
 static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
 	  "unordered container must have a non-const, non-volatile value_type");
-#ifdef __STRICT_ANSI__
+#if __cplusplus > 201703L || defined __STRICT_ANSI__
 static_assert(is_same<typename _Alloc::value_type, _Value>{},
 	  "unordered container must have the same value_type as its allocator");
 #endif
-static_assert(__is_invocable<const _H1&, const _Key&>{},
-	  "hash function must be invocable with an argument of key type");
-static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
-	  "key equality predicate must be invocable with two arguments of "
-	  "key type");
 using __traits_type = _Traits;
 using __hash_cached = typename __traits_type::__hash_cached;
 using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>;
 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
 using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey,
 					    _Equal, _H1, _H2, _Hash,
 					    _RehashPolicy, _Traits>;
-using __reuse_or_alloc_node_type =
+using __reuse_or_alloc_node_gen_t =
 	__detail::_ReuseOrAllocNode<__node_alloc_type>;
+using __alloc_node_gen_t =
+	__detail::_AllocNode<__node_alloc_type>;
+// Simple RAII type for managing a node containing an element
+struct _Scoped_node
+{
+	// Take ownership of a node with a constructed element.
+	_Scoped_node(__node_type* __n, __hashtable_alloc* __h)
+	: _M_h(__h), _M_node(__n) { }
+	// Allocate a node and construct an element within it.
+	template<typename... _Args>
+	  _Scoped_node(__hashtable_alloc* __h, _Args&&... __args)
+	  : _M_h(__h),
+	    _M_node(__h->_M_allocate_node(std::forward<_Args>(__args)...))
+	  { }
+	// Destroy element and deallocate node.
+	~_Scoped_node() { if (_M_node) _M_h->_M_deallocate_node(_M_node); };
+	_Scoped_node(const _Scoped_node&) = delete;
+	_Scoped_node& operator=(const _Scoped_node&) = delete;
+	__hashtable_alloc* _M_h;
+	__node_type* _M_node;
+};
+template<typename _Ht>
+	static constexpr
+	typename conditional<std::is_lvalue_reference<_Ht>::value,
+			     const value_type&, value_type&&>::type
+	__fwd_value_for(value_type& __val) noexcept
+	{ return std::move(__val); }
 // Metaprogramming for picking apart hash caching.
 template<typename _Cond>
 	using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>;
 			     ._M_bucket_index((const __node_type*)nullptr,
 					      (std::size_t)0)),
 		    "Cache the hash code or qualify your functors involved"
 		    " in hash code and bucket index computation with noexcept");
-// Following two static assertions are necessary to guarantee
-// that local_iterator will be default constructible.
 // When hash codes are cached local iterator inherits from H2 functor
 // which must then be default constructible.
 static_assert(__if_hash_cached<is_default_constructible<_H2>>::value,
 		    "Functor used to map hash code to bucket index"
 		    " must be default constructible");
 	       typename _H1a, typename _H2a, typename _Hasha,
 	       typename _RehashPolicya, typename _Traitsa,
 	       bool _Constant_iteratorsa>
 	friend struct __detail::_Insert;
+template<typename _Keya, typename _Valuea, typename _Alloca,
+	       typename _ExtractKeya, typename _Equala,
+	       typename _H1a, typename _H2a, typename _Hasha,
+	       typename _RehashPolicya, typename _Traitsa,
+	       bool _Unique_keysa>
+	friend struct __detail::_Equality;
 public:
 using size_type = typename __hashtable_base::size_type;
 using difference_type = typename __hashtable_base::difference_type;
 using iterator = typename __hashtable_base::iterator;
 __node_base		_M_before_begin;
 size_type			_M_element_count	= 0;
 _RehashPolicy		_M_rehash_policy;
 // A single bucket used when only need for 1 bucket. Especially
-// interesting in move semantic to leave hashtable with only 1 buckets
+// interesting in move semantic to leave hashtable with only 1 bucket
 // which is not allocated so that we can have those operations noexcept
 // qualified.
 // Note that we can't leave hashtable with 0 bucket without adding
 // numerous checks in the code to avoid 0 modulus.
 __bucket_type		_M_single_bucket	= nullptr;
 __hashtable_alloc&
 _M_base_alloc() { return *this; }
 __bucket_type*
-_M_allocate_buckets(size_type __n)
+_M_allocate_buckets(size_type __bkt_count)
 {
-	if (__builtin_expect(__n == 1, false))
+	if (__builtin_expect(__bkt_count == 1, false))
 	  {
 	    _M_single_bucket = nullptr;
 	    return &_M_single_bucket;
 	  }
-	return __hashtable_alloc::_M_allocate_buckets(__n);
+	return __hashtable_alloc::_M_allocate_buckets(__bkt_count);
 }
 void
-_M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
+_M_deallocate_buckets(__bucket_type* __bkts, size_type __bkt_count)
 {
 	if (_M_uses_single_bucket(__bkts))
 	  return;
-	__hashtable_alloc::_M_deallocate_buckets(__bkts, __n);
+	__hashtable_alloc::_M_deallocate_buckets(__bkts, __bkt_count);
 }
 void
 _M_deallocate_buckets()
 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
 __node_type*
 _M_begin() const
 { return static_cast<__node_type*>(_M_before_begin._M_nxt); }
-template<typename _NodeGenerator>
+// Assign *this using another _Hashtable instance. Whether elements
+// are copied or moved depends on the _Ht reference.
+template<typename _Ht>
 	void
-	_M_assign(const _Hashtable&, const _NodeGenerator&);
+	_M_assign_elements(_Ht&&);
+template<typename _Ht, typename _NodeGenerator>
+	void
+	_M_assign(_Ht&&, const _NodeGenerator&);
 void
-_M_move_assign(_Hashtable&&, std::true_type);
+_M_move_assign(_Hashtable&&, true_type);
 void
-_M_move_assign(_Hashtable&&, std::false_type);
+_M_move_assign(_Hashtable&&, false_type);
 void
 _M_reset() noexcept;
 _Hashtable(const _H1& __h1, const _H2& __h2, const _Hash& __h,
 		 const _Equal& __eq, const _ExtractKey& __exk,
 		 const allocator_type& __a)
-	: __hashtable_base(__exk, __h1, __h2, __h, __eq),
+: __hashtable_base(__exk, __h1, __h2, __h, __eq),
-	  __hashtable_alloc(__node_alloc_type(__a))
+	__hashtable_alloc(__node_alloc_type(__a))
 { }
 public:
 // Constructor, destructor, assignment, swap
 _Hashtable() = default;
-_Hashtable(size_type __bucket_hint,
+_Hashtable(size_type __bkt_count_hint,
 		 const _H1&, const _H2&, const _Hash&,
 		 const _Equal&, const _ExtractKey&,
 		 const allocator_type&);
 template<typename _InputIterator>
 	_Hashtable(_InputIterator __first, _InputIterator __last,
-		   size_type __bucket_hint,
+		   size_type __bkt_count_hint,
 		   const _H1&, const _H2&, const _Hash&,
 		   const _Equal&, const _ExtractKey&,
 		   const allocator_type&);
 _Hashtable(const _Hashtable&);
 _Hashtable(_Hashtable&&, const allocator_type&);
 // Use delegating constructors.
 explicit
 _Hashtable(const allocator_type& __a)
-	: __hashtable_alloc(__node_alloc_type(__a))
+: __hashtable_alloc(__node_alloc_type(__a))
 { }
 explicit
-_Hashtable(size_type __n,
+_Hashtable(size_type __bkt_count_hint,
 		 const _H1& __hf = _H1(),
 		 const key_equal& __eql = key_equal(),
 		 const allocator_type& __a = allocator_type())
-: _Hashtable(__n, __hf, _H2(), _Hash(), __eql,
+: _Hashtable(__bkt_count_hint, __hf, _H2(), _Hash(), __eql,
 		   __key_extract(), __a)
 { }
 template<typename _InputIterator>
 	_Hashtable(_InputIterator __f, _InputIterator __l,
-		   size_type __n = 0,
+		   size_type __bkt_count_hint = 0,
 		   const _H1& __hf = _H1(),
 		   const key_equal& __eql = key_equal(),
 		   const allocator_type& __a = allocator_type())
-	: _Hashtable(__f, __l, __n, __hf, _H2(), _Hash(), __eql,
+	: _Hashtable(__f, __l, __bkt_count_hint, __hf, _H2(), _Hash(), __eql,
 		     __key_extract(), __a)
 	{ }
 _Hashtable(initializer_list<value_type> __l,
-		 size_type __n = 0,
+		 size_type __bkt_count_hint = 0,
 		 const _H1& __hf = _H1(),
 		 const key_equal& __eql = key_equal(),
 		 const allocator_type& __a = allocator_type())
-: _Hashtable(__l.begin(), __l.end(), __n, __hf, _H2(), _Hash(), __eql,
+: _Hashtable(__l.begin(), __l.end(), __bkt_count_hint,
+		   __hf, _H2(), _Hash(), __eql,
 		   __key_extract(), __a)
 { }
 _Hashtable&
 operator=(const _Hashtable& __ht);
 }
 _Hashtable&
 operator=(initializer_list<value_type> __l)
 {
-	__reuse_or_alloc_node_type __roan(_M_begin(), *this);
+	__reuse_or_alloc_node_gen_t __roan(_M_begin(), *this);
 	_M_before_begin._M_nxt = nullptr;
 	clear();
 	this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys());
 	return *this;
 }
 size_type
 size() const noexcept
 { return _M_element_count; }
-bool
+_GLIBCXX_NODISCARD bool
 empty() const noexcept
 { return size() == 0; }
 allocator_type
 get_allocator() const noexcept
 size_type
 max_bucket_count() const noexcept
 { return max_size(); }
 size_type
-bucket_size(size_type __n) const
+bucket_size(size_type __bkt) const
-{ return std::distance(begin(__n), end(__n)); }
+{ return std::distance(begin(__bkt), end(__bkt)); }
 size_type
 bucket(const key_type& __k) const
 { return _M_bucket_index(__k, this->_M_hash_code(__k)); }
 local_iterator
-begin(size_type __n)
+begin(size_type __bkt)
 {
-	return local_iterator(*this, _M_bucket_begin(__n),
+	return local_iterator(*this, _M_bucket_begin(__bkt),
-			      __n, _M_bucket_count);
+			      __bkt, _M_bucket_count);
 }
 local_iterator
-end(size_type __n)
+end(size_type __bkt)
-{ return local_iterator(*this, nullptr, __n, _M_bucket_count); }
+{ return local_iterator(*this, nullptr, __bkt, _M_bucket_count); }
 const_local_iterator
-begin(size_type __n) const
+begin(size_type __bkt) const
 {
-	return const_local_iterator(*this, _M_bucket_begin(__n),
+	return const_local_iterator(*this, _M_bucket_begin(__bkt),
-				    __n, _M_bucket_count);
+				    __bkt, _M_bucket_count);
 }
 const_local_iterator
-end(size_type __n) const
+end(size_type __bkt) const
-{ return const_local_iterator(*this, nullptr, __n, _M_bucket_count); }
+{ return const_local_iterator(*this, nullptr, __bkt, _M_bucket_count); }
 // DR 691.
 const_local_iterator
-cbegin(size_type __n) const
+cbegin(size_type __bkt) const
 {
-	return const_local_iterator(*this, _M_bucket_begin(__n),
+	return const_local_iterator(*this, _M_bucket_begin(__bkt),
-				    __n, _M_bucket_count);
+				    __bkt, _M_bucket_count);
 }
 const_local_iterator
-cend(size_type __n) const
+cend(size_type __bkt) const
-{ return const_local_iterator(*this, nullptr, __n, _M_bucket_count); }
+{ return const_local_iterator(*this, nullptr, __bkt, _M_bucket_count); }
 float
 load_factor() const noexcept
 {
 	return static_cast<float>(size()) / static_cast<float>(bucket_count());
 // Get the node before __n in the bucket __bkt
 __node_base*
 _M_get_previous_node(size_type __bkt, __node_base* __n);
-// Insert node with hash code __code, in bucket bkt if no rehash (assumes
+// Insert node __n with key __k and hash code __code, in bucket __bkt
-// no element with its key already present). Take ownership of the node,
+// if no rehash (assumes no element with same key already present).
-// deallocate it on exception.
+// Takes ownership of __n if insertion succeeds, throws otherwise.
 iterator
-_M_insert_unique_node(size_type __bkt, __hash_code __code,
+_M_insert_unique_node(const key_type& __k, size_type __bkt,
-			    __node_type* __n, size_type __n_elt = 1);
+			    __hash_code __code, __node_type* __n,
+			    size_type __n_elt = 1);
-// Insert node with hash code __code. Take ownership of the node,
-// deallocate it on exception.
+// Insert node __n with key __k and hash code __code.
+// Takes ownership of __n if insertion succeeds, throws otherwise.
 iterator
-_M_insert_multi_node(__node_type* __hint,
+_M_insert_multi_node(__node_type* __hint, const key_type& __k,
 			   __hash_code __code, __node_type* __n);
 template<typename... _Args>
 	std::pair<iterator, bool>
-	_M_emplace(std::true_type, _Args&&... __args);
+	_M_emplace(true_type, _Args&&... __args);
 template<typename... _Args>
 	iterator
-	_M_emplace(std::false_type __uk, _Args&&... __args)
+	_M_emplace(false_type __uk, _Args&&... __args)
 	{ return _M_emplace(cend(), __uk, std::forward<_Args>(__args)...); }
 // Emplace with hint, useless when keys are unique.
 template<typename... _Args>
 	iterator
-	_M_emplace(const_iterator, std::true_type __uk, _Args&&... __args)
+	_M_emplace(const_iterator, true_type __uk, _Args&&... __args)
 	{ return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
 template<typename... _Args>
 	iterator
-	_M_emplace(const_iterator, std::false_type, _Args&&... __args);
+	_M_emplace(const_iterator, false_type, _Args&&... __args);
 template<typename _Arg, typename _NodeGenerator>
 	std::pair<iterator, bool>
 	_M_insert(_Arg&&, const _NodeGenerator&, true_type, size_type = 1);
 	iterator
 	_M_insert(const_iterator, _Arg&&,
 		  const _NodeGenerator&, false_type);
 size_type
-_M_erase(std::true_type, const key_type&);
+_M_erase(true_type, const key_type&);
 size_type
-_M_erase(std::false_type, const key_type&);
+_M_erase(false_type, const key_type&);
 iterator
 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n);
 public:
 erase(const_iterator, const_iterator);
 void
 clear() noexcept;
-// Set number of buckets to be appropriate for container of n element.
+// Set number of buckets keeping it appropriate for container's number
-void rehash(size_type __n);
+// of elements.
+void rehash(size_type __bkt_count);
 // DR 1189.
 // reserve, if present, comes from _Rehash_base.
 #if __cplusplus > 201402L
 		__ret.inserted = false;
 	      }
 	    else
 	      {
 		__ret.position
-		  = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
+		  = _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr);
 		__nh._M_ptr = nullptr;
 		__ret.inserted = true;
 	      }
 	  }
 	return __ret;
 /// Re-insert an extracted node into a container with equivalent keys.
 iterator
 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
 {
-	iterator __ret;
 	if (__nh.empty())
-	  __ret = end();
+	  return end();
-	else
-	  {
+	__glibcxx_assert(get_allocator() == __nh.get_allocator());
-	    __glibcxx_assert(get_allocator() == __nh.get_allocator());
+	const key_type& __k = __nh._M_key();
-	    auto __code = this->_M_hash_code(__nh._M_key());
+	auto __code = this->_M_hash_code(__k);
-	    auto __node = std::exchange(__nh._M_ptr, nullptr);
+	auto __ret
-	    // FIXME: this deallocates the node on exception.
+	  = _M_insert_multi_node(__hint._M_cur, __k, __code, __nh._M_ptr);
-	    __ret = _M_insert_multi_node(__hint._M_cur, __code, __node);
+	__nh._M_ptr = nullptr;
-	  }
 	return __ret;
 }
-/// Extract a node.
+private:
 node_type
-extract(const_iterator __pos)
+_M_extract_node(size_t __bkt, __node_base* __prev_n)
 {
-	__node_type* __n = __pos._M_cur;
+	__node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
-	size_t __bkt = _M_bucket_index(__n);
-	// Look for previous node to unlink it from the erased one, this
-	// is why we need buckets to contain the before begin to make
-	// this search fast.
-	__node_base* __prev_n = _M_get_previous_node(__bkt, __n);
 	if (__prev_n == _M_buckets[__bkt])
 	  _M_remove_bucket_begin(__bkt, __n->_M_next(),
 	     __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
 	else if (__n->_M_nxt)
 	  {
 	__n->_M_nxt = nullptr;
 	--_M_element_count;
 	return { __n, this->_M_node_allocator() };
 }
+public:
+// Extract a node.
+node_type
+extract(const_iterator __pos)
+{
+	size_t __bkt = _M_bucket_index(__pos._M_cur);
+	return _M_extract_node(__bkt,
+			       _M_get_previous_node(__bkt, __pos._M_cur));
+}
 /// Extract a node.
 node_type
 extract(const _Key& __k)
 {
 	node_type __nh;
-	auto __pos = find(__k);
+	__hash_code __code = this->_M_hash_code(__k);
-	if (__pos != end())
+	std::size_t __bkt = _M_bucket_index(__k, __code);
-	  __nh = extract(const_iterator(__pos));
+	if (__node_base* __prev_node = _M_find_before_node(__bkt, __k, __code))
+	  __nh = _M_extract_node(__bkt, __prev_node);
 	return __nh;
 }
 /// Merge from a compatible container into one with unique keys.
 template<typename _Compatible_Hashtable>
 	  auto __n_elt = __src.size();
 	  for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
 	    {
 	      auto __pos = __i++;
-	      const key_type& __k = this->_M_extract()(__pos._M_cur->_M_v());
+	      const key_type& __k = this->_M_extract()(*__pos);
 	      __hash_code __code = this->_M_hash_code(__k);
 	      size_type __bkt = _M_bucket_index(__k, __code);
 	      if (_M_find_node(__bkt, __k, __code) == nullptr)
 		{
 		  auto __nh = __src.extract(__pos);
-		  _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
+		  _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr,
+					__n_elt);
 		  __nh._M_ptr = nullptr;
 		  __n_elt = 1;
 		}
 	      else if (__n_elt != 1)
 		--__n_elt;
 	}
 #endif // C++17
 private:
 // Helper rehash method used when keys are unique.
-void _M_rehash_aux(size_type __n, std::true_type);
+void _M_rehash_aux(size_type __bkt_count, true_type);
 // Helper rehash method used when keys can be non-unique.
-void _M_rehash_aux(size_type __n, std::false_type);
+void _M_rehash_aux(size_type __bkt_count, false_type);
 // Unconditionally change size of bucket array to n, restore
 // hash policy state to __state on exception.
-void _M_rehash(size_type __n, const __rehash_state& __state);
+void _M_rehash(size_type __bkt_count, const __rehash_state& __state);
 };
 // Definitions of class template _Hashtable's out-of-line member functions.
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-_Hashtable(size_type __bucket_hint,
+_Hashtable(size_type __bkt_count_hint,
 	       const _H1& __h1, const _H2& __h2, const _Hash& __h,
 	       const _Equal& __eq, const _ExtractKey& __exk,
 	       const allocator_type& __a)
 : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
 {
-auto __bkt = _M_rehash_policy._M_next_bkt(__bucket_hint);
+auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
-if (__bkt > _M_bucket_count)
+if (__bkt_count > _M_bucket_count)
 	{
-	  _M_buckets = _M_allocate_buckets(__bkt);
+	  _M_buckets = _M_allocate_buckets(__bkt_count);
-	  _M_bucket_count = __bkt;
+	  _M_bucket_count = __bkt_count;
 	}
 }
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _Traits>
 template<typename _InputIterator>
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
 _Hashtable(_InputIterator __f, _InputIterator __l,
-		 size_type __bucket_hint,
+		 size_type __bkt_count_hint,
 		 const _H1& __h1, const _H2& __h2, const _Hash& __h,
 		 const _Equal& __eq, const _ExtractKey& __exk,
 		 const allocator_type& __a)
-	: _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
+: _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
 {
 	auto __nb_elems = __detail::__distance_fw(__f, __l);
 	auto __bkt_count =
 	  _M_rehash_policy._M_next_bkt(
 	    std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
-		     __bucket_hint));
+		     __bkt_count_hint));
 	if (__bkt_count > _M_bucket_count)
 	  {
 	    _M_buckets = _M_allocate_buckets(__bkt_count);
 	    _M_bucket_count = __bkt_count;
 	      std::__alloc_on_copy(__this_alloc, __that_alloc);
 	      __hashtable_base::operator=(__ht);
 	      _M_bucket_count = __ht._M_bucket_count;
 	      _M_element_count = __ht._M_element_count;
 	      _M_rehash_policy = __ht._M_rehash_policy;
+	      __alloc_node_gen_t __alloc_node_gen(*this);
 	      __try
 		{
-		  _M_assign(__ht,
+		  _M_assign(__ht, __alloc_node_gen);
-			    [this](const __node_type* __n)
-			    { return this->_M_allocate_node(__n->_M_v()); });
 		}
 	      __catch(...)
 		{
 		  // _M_assign took care of deallocating all memory. Now we
 		  // must make sure this instance remains in a usable state.
 	    }
 	  std::__alloc_on_copy(__this_alloc, __that_alloc);
 	}
 // Reuse allocated buckets and nodes.
-__bucket_type* __former_buckets = nullptr;
+_M_assign_elements(__ht);
-std::size_t __former_bucket_count = _M_bucket_count;
-const __rehash_state& __former_state = _M_rehash_policy._M_state();
-if (_M_bucket_count != __ht._M_bucket_count)
-	{
-	  __former_buckets = _M_buckets;
-	  _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
-	  _M_bucket_count = __ht._M_bucket_count;
-	}
-else
-	__builtin_memset(_M_buckets, 0,
-			 _M_bucket_count * sizeof(__bucket_type));
-__try
-	{
-	  __hashtable_base::operator=(__ht);
-	  _M_element_count = __ht._M_element_count;
-	  _M_rehash_policy = __ht._M_rehash_policy;
-	  __reuse_or_alloc_node_type __roan(_M_begin(), *this);
-	  _M_before_begin._M_nxt = nullptr;
-	  _M_assign(__ht,
-		    [&__roan](const __node_type* __n)
-		    { return __roan(__n->_M_v()); });
-	  if (__former_buckets)
-	    _M_deallocate_buckets(__former_buckets, __former_bucket_count);
-	}
-__catch(...)
-	{
-	  if (__former_buckets)
-	    {
-	      // Restore previous buckets.
-	      _M_deallocate_buckets();
-	      _M_rehash_policy._M_reset(__former_state);
-	      _M_buckets = __former_buckets;
-	      _M_bucket_count = __former_bucket_count;
-	    }
-	  __builtin_memset(_M_buckets, 0,
-			   _M_bucket_count * sizeof(__bucket_type));
-	  __throw_exception_again;
-	}
 return *this;
 }
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
-template<typename _NodeGenerator>
+template<typename _Ht>
 void
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-_M_assign(const _Hashtable& __ht, const _NodeGenerator& __node_gen)
+_M_assign_elements(_Ht&& __ht)
+{
+	__bucket_type* __former_buckets = nullptr;
+	std::size_t __former_bucket_count = _M_bucket_count;
+	const __rehash_state& __former_state = _M_rehash_policy._M_state();
+	if (_M_bucket_count != __ht._M_bucket_count)
+	  {
+	    __former_buckets = _M_buckets;
+	    _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
+	    _M_bucket_count = __ht._M_bucket_count;
+	  }
+	else
+	  __builtin_memset(_M_buckets, 0,
+			   _M_bucket_count * sizeof(__bucket_type));
+	__try
+	  {
+	    __hashtable_base::operator=(std::forward<_Ht>(__ht));
+	    _M_element_count = __ht._M_element_count;
+	    _M_rehash_policy = __ht._M_rehash_policy;
+	    __reuse_or_alloc_node_gen_t __roan(_M_begin(), *this);
+	    _M_before_begin._M_nxt = nullptr;
+	    _M_assign(std::forward<_Ht>(__ht), __roan);
+	    if (__former_buckets)
+	      _M_deallocate_buckets(__former_buckets, __former_bucket_count);
+	  }
+	__catch(...)
+	  {
+	    if (__former_buckets)
+	      {
+		// Restore previous buckets.
+		_M_deallocate_buckets();
+		_M_rehash_policy._M_reset(__former_state);
+		_M_buckets = __former_buckets;
+		_M_bucket_count = __former_bucket_count;
+	      }
+	    __builtin_memset(_M_buckets, 0,
+			     _M_bucket_count * sizeof(__bucket_type));
+	    __throw_exception_again;
+	  }
+}
+template<typename _Key, typename _Value,
+	   typename _Alloc, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   typename _Traits>
+template<typename _Ht, typename _NodeGenerator>
+void
+_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+_M_assign(_Ht&& __ht, const _NodeGenerator& __node_gen)
 {
 	__bucket_type* __buckets = nullptr;
 	if (!_M_buckets)
 	  _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
 	      return;
 	    // First deal with the special first node pointed to by
 	    // _M_before_begin.
 	    __node_type* __ht_n = __ht._M_begin();
-	    __node_type* __this_n = __node_gen(__ht_n);
+	    __node_type* __this_n
+	      = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
 	    this->_M_copy_code(__this_n, __ht_n);
 	    _M_before_begin._M_nxt = __this_n;
 	    _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
 	    // Then deal with other nodes.
 	    __node_base* __prev_n = __this_n;
 	    for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
 	      {
-		__this_n = __node_gen(__ht_n);
+		__this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
 		__prev_n->_M_nxt = __this_n;
 		this->_M_copy_code(__this_n, __ht_n);
 		size_type __bkt = _M_bucket_index(__this_n);
 		if (!_M_buckets[__bkt])
 		  _M_buckets[__bkt] = __prev_n;
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
 void
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-_M_move_assign(_Hashtable&& __ht, std::true_type)
+_M_move_assign(_Hashtable&& __ht, true_type)
 {
 this->_M_deallocate_nodes(_M_begin());
 _M_deallocate_buckets();
 __hashtable_base::operator=(std::move(__ht));
 _M_rehash_policy = __ht._M_rehash_policy;
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
 void
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-_M_move_assign(_Hashtable&& __ht, std::false_type)
+_M_move_assign(_Hashtable&& __ht, false_type)
 {
 if (__ht._M_node_allocator() == this->_M_node_allocator())
-	_M_move_assign(std::move(__ht), std::true_type());
+	_M_move_assign(std::move(__ht), true_type());
 else
 	{
 	  // Can't move memory, move elements then.
-	  __bucket_type* __former_buckets = nullptr;
+	  _M_assign_elements(std::move(__ht));
-	  size_type __former_bucket_count = _M_bucket_count;
+	  __ht.clear();
-	  const __rehash_state& __former_state = _M_rehash_policy._M_state();
-	  if (_M_bucket_count != __ht._M_bucket_count)
-	    {
-	      __former_buckets = _M_buckets;
-	      _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
-	      _M_bucket_count = __ht._M_bucket_count;
-	    }
-	  else
-	    __builtin_memset(_M_buckets, 0,
-			     _M_bucket_count * sizeof(__bucket_type));
-	  __try
-	    {
-	      __hashtable_base::operator=(std::move(__ht));
-	      _M_element_count = __ht._M_element_count;
-	      _M_rehash_policy = __ht._M_rehash_policy;
-	      __reuse_or_alloc_node_type __roan(_M_begin(), *this);
-	      _M_before_begin._M_nxt = nullptr;
-	      _M_assign(__ht,
-			[&__roan](__node_type* __n)
-			{ return __roan(std::move_if_noexcept(__n->_M_v())); });
-	      __ht.clear();
-	    }
-	  __catch(...)
-	    {
-	      if (__former_buckets)
-		{
-		  _M_deallocate_buckets();
-		  _M_rehash_policy._M_reset(__former_state);
-		  _M_buckets = __former_buckets;
-		  _M_bucket_count = __former_bucket_count;
-		}
-	      __builtin_memset(_M_buckets, 0,
-			       _M_bucket_count * sizeof(__bucket_type));
-	      __throw_exception_again;
-	    }
 	}
 }
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 _M_buckets(nullptr),
 _M_bucket_count(__ht._M_bucket_count),
 _M_element_count(__ht._M_element_count),
 _M_rehash_policy(__ht._M_rehash_policy)
 {
-_M_assign(__ht,
+__alloc_node_gen_t __alloc_node_gen(*this);
-		[this](const __node_type* __n)
+_M_assign(__ht, __alloc_node_gen);
-		{ return this->_M_allocate_node(__n->_M_v()); });
 }
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 _M_buckets(),
 _M_bucket_count(__ht._M_bucket_count),
 _M_element_count(__ht._M_element_count),
 _M_rehash_policy(__ht._M_rehash_policy)
 {
-_M_assign(__ht,
+__alloc_node_gen_t __alloc_node_gen(*this);
-		[this](const __node_type* __n)
+_M_assign(__ht, __alloc_node_gen);
-		{ return this->_M_allocate_node(__n->_M_v()); });
 }
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	    _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
 	  __ht._M_reset();
 	}
 else
 	{
-	  _M_assign(__ht,
+	  __alloc_node_gen_t __alloc_gen(*this);
-		    [this](__node_type* __n)
-		    {
+	  using _Fwd_Ht = typename
-		      return this->_M_allocate_node(
+	    conditional<__move_if_noexcept_cond<value_type>::value,
-					std::move_if_noexcept(__n->_M_v()));
+			const _Hashtable&, _Hashtable&&>::type;
-		    });
+	  _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen);
 	  __ht.clear();
 	}
 }
 template<typename _Key, typename _Value,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
 find(const key_type& __k)
 -> iterator
 {
 __hash_code __code = this->_M_hash_code(__k);
-std::size_t __n = _M_bucket_index(__k, __code);
+std::size_t __bkt = _M_bucket_index(__k, __code);
-__node_type* __p = _M_find_node(__n, __k, __code);
+__node_type* __p = _M_find_node(__bkt, __k, __code);
 return __p ? iterator(__p) : end();
 }
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
 find(const key_type& __k) const
 -> const_iterator
 {
 __hash_code __code = this->_M_hash_code(__k);
-std::size_t __n = _M_bucket_index(__k, __code);
+std::size_t __bkt = _M_bucket_index(__k, __code);
-__node_type* __p = _M_find_node(__n, __k, __code);
+__node_type* __p = _M_find_node(__bkt, __k, __code);
 return __p ? const_iterator(__p) : end();
 }
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
 count(const key_type& __k) const
 -> size_type
 {
 __hash_code __code = this->_M_hash_code(__k);
-std::size_t __n = _M_bucket_index(__k, __code);
+std::size_t __bkt = _M_bucket_index(__k, __code);
-__node_type* __p = _M_bucket_begin(__n);
+__node_type* __p = _M_bucket_begin(__bkt);
 if (!__p)
 	return 0;
 std::size_t __result = 0;
 for (;; __p = __p->_M_next())
 	  else if (__result)
 	    // All equivalent values are next to each other, if we
 	    // found a non-equivalent value after an equivalent one it
 	    // means that we won't find any new equivalent value.
 	    break;
-	  if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
+	  if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __bkt)
 	    break;
 	}
 return __result;
 }
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
 equal_range(const key_type& __k)
 -> pair<iterator, iterator>
 {
 __hash_code __code = this->_M_hash_code(__k);
-std::size_t __n = _M_bucket_index(__k, __code);
+std::size_t __bkt = _M_bucket_index(__k, __code);
-__node_type* __p = _M_find_node(__n, __k, __code);
+__node_type* __p = _M_find_node(__bkt, __k, __code);
 if (__p)
 	{
 	  __node_type* __p1 = __p->_M_next();
-	  while (__p1 && _M_bucket_index(__p1) == __n
+	  while (__p1 && _M_bucket_index(__p1) == __bkt
 		 && this->_M_equals(__k, __code, __p1))
 	    __p1 = __p1->_M_next();
 	  return std::make_pair(iterator(__p), iterator(__p1));
 	}
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
 equal_range(const key_type& __k) const
 -> pair<const_iterator, const_iterator>
 {
 __hash_code __code = this->_M_hash_code(__k);
-std::size_t __n = _M_bucket_index(__k, __code);
+std::size_t __bkt = _M_bucket_index(__k, __code);
-__node_type* __p = _M_find_node(__n, __k, __code);
+__node_type* __p = _M_find_node(__bkt, __k, __code);
 if (__p)
 	{
 	  __node_type* __p1 = __p->_M_next();
-	  while (__p1 && _M_bucket_index(__p1) == __n
+	  while (__p1 && _M_bucket_index(__p1) == __bkt
 		 && this->_M_equals(__k, __code, __p1))
 	    __p1 = __p1->_M_next();
 	  return std::make_pair(const_iterator(__p), const_iterator(__p1));
 	}
 else
 	return std::make_pair(end(), end());
 }
-// Find the node whose key compares equal to k in the bucket n.
+// Find the node whose key compares equal to k in the bucket bkt.
 // Return nullptr if no node is found.
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
 auto
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-_M_find_before_node(size_type __n, const key_type& __k,
+_M_find_before_node(size_type __bkt, const key_type& __k,
 			__hash_code __code) const
 -> __node_base*
 {
-__node_base* __prev_p = _M_buckets[__n];
+__node_base* __prev_p = _M_buckets[__bkt];
 if (!__prev_p)
 	return nullptr;
 for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);;
 	   __p = __p->_M_next())
 	{
 	  if (this->_M_equals(__k, __code, __p))
 	    return __prev_p;
-	  if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
+	  if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __bkt)
 	    break;
 	  __prev_p = __p;
 	}
 return nullptr;
 }
 	   typename _Traits>
 template<typename... _Args>
 auto
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-_M_emplace(std::true_type, _Args&&... __args)
+_M_emplace(true_type, _Args&&... __args)
 -> pair<iterator, bool>
 {
 	// First build the node to get access to the hash code
-	__node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...);
+	_Scoped_node __node { this, std::forward<_Args>(__args)...  };
-	const key_type& __k = this->_M_extract()(__node->_M_v());
+	const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
-	__hash_code __code;
+	__hash_code __code = this->_M_hash_code(__k);
-	__try
-	  {
-	    __code = this->_M_hash_code(__k);
-	  }
-	__catch(...)
-	  {
-	    this->_M_deallocate_node(__node);
-	    __throw_exception_again;
-	  }
 	size_type __bkt = _M_bucket_index(__k, __code);
 	if (__node_type* __p = _M_find_node(__bkt, __k, __code))
-	  {
+	  // There is already an equivalent node, no insertion
-	    // There is already an equivalent node, no insertion
+	  return std::make_pair(iterator(__p), false);
-	    this->_M_deallocate_node(__node);
-	    return std::make_pair(iterator(__p), false);
-	  }
 	// Insert the node
-	return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
+	auto __pos = _M_insert_unique_node(__k, __bkt, __code, __node._M_node);
-			      true);
+	__node._M_node = nullptr;
+	return { __pos, true };
 }
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
 template<typename... _Args>
 auto
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-_M_emplace(const_iterator __hint, std::false_type, _Args&&... __args)
+_M_emplace(const_iterator __hint, false_type, _Args&&... __args)
 -> iterator
 {
 	// First build the node to get its hash code.
-	__node_type* __node =
+	_Scoped_node __node { this, std::forward<_Args>(__args)...  };
-	  this->_M_allocate_node(std::forward<_Args>(__args)...);
+	const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
-	__hash_code __code;
+	__hash_code __code = this->_M_hash_code(__k);
-	__try
+	auto __pos
-	  {
+	  = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node);
-	    __code = this->_M_hash_code(this->_M_extract()(__node->_M_v()));
+	__node._M_node = nullptr;
-	  }
+	return __pos;
-	__catch(...)
-	  {
-	    this->_M_deallocate_node(__node);
-	    __throw_exception_again;
-	  }
-	return _M_insert_multi_node(__hint._M_cur, __code, __node);
 }
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
 auto
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-_M_insert_unique_node(size_type __bkt, __hash_code __code,
+_M_insert_unique_node(const key_type& __k, size_type __bkt,
-			  __node_type* __node, size_type __n_elt)
+			  __hash_code __code, __node_type* __node,
+			  size_type __n_elt)
 -> iterator
 {
 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
 std::pair<bool, std::size_t> __do_rehash
 	= _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
 					  __n_elt);
-__try
+if (__do_rehash.first)
 	{
-	  if (__do_rehash.first)
+	  _M_rehash(__do_rehash.second, __saved_state);
-	    {
+	  __bkt = _M_bucket_index(__k, __code);
-	      _M_rehash(__do_rehash.second, __saved_state);
+	}
-	      __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
-	    }
+this->_M_store_code(__node, __code);
-	  this->_M_store_code(__node, __code);
+// Always insert at the beginning of the bucket.
+_M_insert_bucket_begin(__bkt, __node);
-	  // Always insert at the beginning of the bucket.
+++_M_element_count;
-	  _M_insert_bucket_begin(__bkt, __node);
+return iterator(__node);
-	  ++_M_element_count;
+}
-	  return iterator(__node);
-	}
-__catch(...)
-	{
-	  this->_M_deallocate_node(__node);
-	  __throw_exception_again;
-	}
-}
-// Insert node, in bucket bkt if no rehash (assumes no element with its key
-// already present). Take ownership of the node, deallocate it on exception.
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
 auto
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-_M_insert_multi_node(__node_type* __hint, __hash_code __code,
+_M_insert_multi_node(__node_type* __hint, const key_type& __k,
-			 __node_type* __node)
+			 __hash_code __code, __node_type* __node)
 -> iterator
 {
 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
 std::pair<bool, std::size_t> __do_rehash
 	= _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
-__try
+if (__do_rehash.first)
-	{
+	_M_rehash(__do_rehash.second, __saved_state);
-	  if (__do_rehash.first)
-	    _M_rehash(__do_rehash.second, __saved_state);
+this->_M_store_code(__node, __code);
+size_type __bkt = _M_bucket_index(__k, __code);
-	  this->_M_store_code(__node, __code);
-	  const key_type& __k = this->_M_extract()(__node->_M_v());
+// Find the node before an equivalent one or use hint if it exists and
-	  size_type __bkt = _M_bucket_index(__k, __code);
+// if it is equivalent.
+__node_base* __prev
-	  // Find the node before an equivalent one or use hint if it exists and
+	= __builtin_expect(__hint != nullptr, false)
-	  // if it is equivalent.
+	  && this->_M_equals(__k, __code, __hint)
-	  __node_base* __prev
+	    ? __hint
-	    = __builtin_expect(__hint != nullptr, false)
+	    : _M_find_before_node(__bkt, __k, __code);
-	      && this->_M_equals(__k, __code, __hint)
+if (__prev)
-		? __hint
+	{
-		: _M_find_before_node(__bkt, __k, __code);
+	  // Insert after the node before the equivalent one.
-	  if (__prev)
+	  __node->_M_nxt = __prev->_M_nxt;
-	    {
+	  __prev->_M_nxt = __node;
-	      // Insert after the node before the equivalent one.
+	  if (__builtin_expect(__prev == __hint, false))
-	      __node->_M_nxt = __prev->_M_nxt;
+	    // hint might be the last bucket node, in this case we need to
-	      __prev->_M_nxt = __node;
+	    // update next bucket.
-	      if (__builtin_expect(__prev == __hint, false))
+	    if (__node->_M_nxt
-	      	// hint might be the last bucket node, in this case we need to
+		&& !this->_M_equals(__k, __code, __node->_M_next()))
-	      	// update next bucket.
+	      {
-	      	if (__node->_M_nxt
+		size_type __next_bkt = _M_bucket_index(__node->_M_next());
-	      	    && !this->_M_equals(__k, __code, __node->_M_next()))
+		if (__next_bkt != __bkt)
-	      	  {
+		  _M_buckets[__next_bkt] = __node;
-	      	    size_type __next_bkt = _M_bucket_index(__node->_M_next());
+	      }
-	      	    if (__next_bkt != __bkt)
+	}
-	      	      _M_buckets[__next_bkt] = __node;
+else
-	      	  }
+	// The inserted node has no equivalent in the hashtable. We must
-	    }
+	// insert the new node at the beginning of the bucket to preserve
-	  else
+	// equivalent elements' relative positions.
-	    // The inserted node has no equivalent in the
+	_M_insert_bucket_begin(__bkt, __node);
-	    // hashtable. We must insert the new node at the
+++_M_element_count;
-	    // beginning of the bucket to preserve equivalent
+return iterator(__node);
-	    // elements' relative positions.
-	    _M_insert_bucket_begin(__bkt, __node);
-	  ++_M_element_count;
-	  return iterator(__node);
-	}
-__catch(...)
-	{
-	  this->_M_deallocate_node(__node);
-	  __throw_exception_again;
-	}
 }
 // Insert v if no element with its key is already present.
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 {
 	const key_type& __k = this->_M_extract()(__v);
 	__hash_code __code = this->_M_hash_code(__k);
 	size_type __bkt = _M_bucket_index(__k, __code);
-	__node_type* __n = _M_find_node(__bkt, __k, __code);
+	if (__node_type* __node = _M_find_node(__bkt, __k, __code))
-	if (__n)
+	  return { iterator(__node), false };
-	  return std::make_pair(iterator(__n), false);
+	_Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
-	__n = __node_gen(std::forward<_Arg>(__v));
+	auto __pos
-	return { _M_insert_unique_node(__bkt, __code, __n, __n_elt), true };
+	  = _M_insert_unique_node(__k, __bkt, __code, __node._M_node, __n_elt);
+	__node._M_node = nullptr;
+	return { __pos, true };
 }
 // Insert v unconditionally.
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	// First compute the hash code so that we don't do anything if it
 	// throws.
 	__hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
 	// Second allocate new node so that we don't rehash if it throws.
-	__node_type* __node = __node_gen(std::forward<_Arg>(__v));
+	_Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
+	const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
-	return _M_insert_multi_node(__hint._M_cur, __code, __node);
+	auto __pos
+	  = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node);
+	__node._M_node = nullptr;
+	return __pos;
 }
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
 auto
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-_M_erase(std::true_type, const key_type& __k)
+_M_erase(true_type, const key_type& __k)
 -> size_type
 {
 __hash_code __code = this->_M_hash_code(__k);
 std::size_t __bkt = _M_bucket_index(__k, __code);
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
 auto
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-_M_erase(std::false_type, const key_type& __k)
+_M_erase(false_type, const key_type& __k)
 -> size_type
 {
 __hash_code __code = this->_M_hash_code(__k);
 std::size_t __bkt = _M_bucket_index(__k, __code);
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
 void
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-rehash(size_type __n)
+rehash(size_type __bkt_count)
 {
 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
-std::size_t __buckets
+__bkt_count
 	= std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
-		   __n);
+		   __bkt_count);
-__buckets = _M_rehash_policy._M_next_bkt(__buckets);
+__bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count);
-if (__buckets != _M_bucket_count)
+if (__bkt_count != _M_bucket_count)
-	_M_rehash(__buckets, __saved_state);
+	_M_rehash(__bkt_count, __saved_state);
 else
-	// No rehash, restore previous state to keep a consistent state.
+	// No rehash, restore previous state to keep it consistent with
+	// container state.
 	_M_rehash_policy._M_reset(__saved_state);
 }
 template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
 void
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-_M_rehash(size_type __n, const __rehash_state& __state)
+_M_rehash(size_type __bkt_count, const __rehash_state& __state)
 {
 __try
 	{
-	  _M_rehash_aux(__n, __unique_keys());
+	  _M_rehash_aux(__bkt_count, __unique_keys());
 	}
 __catch(...)
 	{
 	  // A failure here means that buckets allocation failed.  We only
 	  // have to restore hash policy previous state.
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
 void
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-_M_rehash_aux(size_type __n, std::true_type)
+_M_rehash_aux(size_type __bkt_count, true_type)
 {
-__bucket_type* __new_buckets = _M_allocate_buckets(__n);
+__bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
 __node_type* __p = _M_begin();
 _M_before_begin._M_nxt = nullptr;
 std::size_t __bbegin_bkt = 0;
 while (__p)
 	{
 	  __node_type* __next = __p->_M_next();
-	  std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
+	  std::size_t __bkt
+	    = __hash_code_base::_M_bucket_index(__p, __bkt_count);
 	  if (!__new_buckets[__bkt])
 	    {
 	      __p->_M_nxt = _M_before_begin._M_nxt;
 	      _M_before_begin._M_nxt = __p;
 	      __new_buckets[__bkt] = &_M_before_begin;
 	    }
 	  __p = __next;
 	}
 _M_deallocate_buckets();
-_M_bucket_count = __n;
+_M_bucket_count = __bkt_count;
 _M_buckets = __new_buckets;
 }
 // Rehash when there can be equivalent elements, preserve their relative
 // order.
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
 void
 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-_M_rehash_aux(size_type __n, std::false_type)
+_M_rehash_aux(size_type __bkt_count, false_type)
 {
-__bucket_type* __new_buckets = _M_allocate_buckets(__n);
+__bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
 __node_type* __p = _M_begin();
 _M_before_begin._M_nxt = nullptr;
 std::size_t __bbegin_bkt = 0;
 std::size_t __prev_bkt = 0;
 bool __check_bucket = false;
 while (__p)
 	{
 	  __node_type* __next = __p->_M_next();
-	  std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
+	  std::size_t __bkt
+	    = __hash_code_base::_M_bucket_index(__p, __bkt_count);
 	  if (__prev_p && __prev_bkt == __bkt)
 	    {
 	      // Previous insert was already in this bucket, we insert after
 	      // the previously inserted one to preserve equivalent elements
 		  // insertions into __prev_bkt bucket.
 		  if (__prev_p->_M_nxt)
 		    {
 		      std::size_t __next_bkt
 			= __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
-							    __n);
+							    __bkt_count);
 		      if (__next_bkt != __prev_bkt)
 			__new_buckets[__next_bkt] = __prev_p;
 		    }
 		  __check_bucket = false;
 		}
 	}
 if (__check_bucket && __prev_p->_M_nxt)
 	{
 	  std::size_t __next_bkt
-	    = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n);
+	    = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
+						__bkt_count);
 	  if (__next_bkt != __prev_bkt)
 	    __new_buckets[__next_bkt] = __prev_p;
 	}
 _M_deallocate_buckets();
-_M_bucket_count = __n;
+_M_bucket_count = __bkt_count;
 _M_buckets = __new_buckets;
 }
 #if __cplusplus > 201402L
 template<typename, typename, typename> class _Hash_merge_helper { };
 #endif // C++17
+#if __cpp_deduction_guides >= 201606
+// Used to constrain deduction guides
+template<typename _Hash>
+using _RequireNotAllocatorOrIntegral
+= __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
+#endif
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace std
 #endif // _HASHTABLE_H

Mercurial > hg > CbC > CbC_gcc

comparison libstdc++-v3/include/bits/hashtable.h @ 145:1830386684a0