Hi
Here is a patch to enhance the _Hashtable extract node API and fix
a FIXME request.
The enhancement to the extract node Api is that extract(const
key_type&) do not call extract(const_iterator) anymore. Doing so we had
to loop again through bucket nodes to find the previous node to the one
to extract. Even if a bucket shall not contain many nodes (in unique key
mode) it's easy to avoid it.
To fix the FIXME I introduced a node smart pointer type managing
the node lifetime. The node is extracted from this smart pointer only
when there can't be any exception raised. In the context of the node
extract api the node handle is considered as a smart pointer. So the
node handle will remain owner of the node in case of exception when
reinserting it, I hope it is the expected behavior.
* include/bits/hashtable_policy.h
(struct _NodeSmartPointer<_NodeAlloc>): New.
(_Map_base<>::operator[](const key_type&)): Use latter, adapt.
(_Map_base<>::operator[](key_type&&)): Likewise.
* include/bits/hashtable.h
(_Hashtable<>::__node_sp_t): New.
(_Hashtable<>::_M_insert_unique_node(size_type, __hash_code,
__node_type*, size_type)): Replace by...
(_Hashtable<>::_M_insert_unique_node<_NodeAccessor>(const key_type&,
size_type, __hash_code, const _NodeAccessor&, size_type)): ...that.
(_Hashtable<>::_M_insert_multi_node(__node_type*, __hash_code,
__node_type*)): Replace by...
(_Hashtable<>::_M_insert_multi_node<_NodeAccessor>(__node_type*,
__hash_code, const _NodeAccessor&)): ...that.
(_Hashtable<>::_M_reinsert_node): Adapt.
(_Hashtable<>::_M_reinsert_node_multi): Adapt.
(_Hashtable<>::_M_extract_node(size_t, __node_base*)): New.
(_Hashtable<>::extract(const_iterator)): Use latter.
(_Hashtable<>::extract(const _Key&)): Likewise.
(_Hashtable<>::_M_merge_unique): Adapt.
(_Hashtable<>::_M_emplace<_Args>(true_type, _Args&&...)): Adapt.
(_Hashtable<>::_M_emplace<_Args>(const_iterator, false_type,
_Args&&...)): Adapt.
Tested under Linux x86_64.
Ok to commit ?
François
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index e2e3f016a35..307865b96bf 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -197,6 +197,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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 __node_sp_t = __detail::_NodeSmartPointer<__node_alloc_type>;
using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>;
@@ -669,18 +670,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__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
- // no element with its key already present). Take ownership of the node,
- // deallocate it on exception.
+ // Insert node with key __k and hash code __code, in bucket __bkt if no
+ // rehash (assumes no element with its key already present).
+ template<typename _NodeAccessor>
iterator
- _M_insert_unique_node(size_type __bkt, __hash_code __code,
- __node_type* __n, size_type __n_elt = 1);
+ _M_insert_unique_node(const key_type& __k, size_type __bkt,
+ __hash_code __code, const _NodeAccessor&,
+ size_type __n_elt = 1);
- // Insert node with hash code __code. Take ownership of the node,
- // deallocate it on exception.
+ // Insert node with hash code __code.
+ template<typename _NodeAccessor>
iterator
- _M_insert_multi_node(__node_type* __hint,
- __hash_code __code, __node_type* __n);
+ _M_insert_multi_node(__node_type* __hint, __hash_code __code,
+ const _NodeAccessor& __node_accessor);
template<typename... _Args>
std::pair<iterator, bool>
@@ -805,9 +807,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
else
{
- __ret.position
- = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
- __nh._M_ptr = nullptr;
+ __ret.position = _M_insert_unique_node(__k, __bkt, __code,
+ [&__nh]()
+ { return std::exchange(__nh._M_ptr, nullptr); });
__ret.inserted = true;
}
}
@@ -818,33 +820,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
iterator
_M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
{
- iterator __ret;
if (__nh.empty())
- __ret = end();
- else
- {
+ return end();
+
__glibcxx_assert(get_allocator() == __nh.get_allocator());
auto __code = this->_M_hash_code(__nh._M_key());
- auto __node = std::exchange(__nh._M_ptr, nullptr);
- // FIXME: this deallocates the node on exception.
- __ret = _M_insert_multi_node(__hint._M_cur, __code, __node);
- }
- return __ret;
+ return _M_insert_multi_node(__hint._M_cur, __code,
+ [&__nh]()
+ { return std::exchange(__nh._M_ptr, nullptr); });
}
+ private:
/// Extract a node.
node_type
- extract(const_iterator __pos)
+ _M_extract_node(size_t __bkt, __node_base* __prev_n)
{
- __node_type* __n = __pos._M_cur;
- 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);
-
+ __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
if (__prev_n == _M_buckets[__bkt])
_M_remove_bucket_begin(__bkt, __n->_M_next(),
__n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
@@ -861,14 +853,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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);
- if (__pos != end())
- __nh = extract(const_iterator(__pos));
+ __hash_code __code = this->_M_hash_code(__k);
+ std::size_t __bkt = _M_bucket_index(__k, __code);
+ if (__node_base* __prev_node = _M_find_before_node(__bkt, __k, __code))
+ __nh = _M_extract_node(__bkt, __prev_node);
return __nh;
}
@@ -885,14 +887,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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);
- __nh._M_ptr = nullptr;
+ _M_insert_unique_node(__k, __bkt, __code,
+ [&__nh]()
+ { return std::exchange(__nh._M_ptr, nullptr); },
+ __n_elt);
__n_elt = 1;
}
else if (__n_elt != 1)
@@ -1634,31 +1638,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
-> 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)...);
- const key_type& __k = this->_M_extract()(__node->_M_v());
- __hash_code __code;
- __try
- {
- __code = this->_M_hash_code(__k);
- }
- __catch(...)
- {
- this->_M_deallocate_node(__node);
- __throw_exception_again;
- }
+ __node_sp_t __node_sp(*this,
+ this->_M_allocate_node(std::forward<_Args>(__args)...));
+ const key_type& __k
+ = this->_M_extract()(__node_sp._M_get()->_M_v());
+ __hash_code __code = this->_M_hash_code(__k);
size_type __bkt = _M_bucket_index(__k, __code);
- if (__node_type* __p = _M_find_node(__bkt, __k, __code))
- {
+ if (__node_type* __node = _M_find_node(__bkt, __k, __code))
// There is already an equivalent node, no insertion
- this->_M_deallocate_node(__node);
- return std::make_pair(iterator(__p), false);
- }
+ return { iterator(__node), false };
// Insert the node
- return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
- true);
+ return
+ {
+ _M_insert_unique_node(__k, __bkt, __code,
+ [&__node_sp]()
+ { return __node_sp._M_release(); }),
+ true
+ };
}
template<typename _Key, typename _Value,
@@ -1673,32 +1671,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
-> iterator
{
// First build the node to get its hash code.
- __node_type* __node =
- this->_M_allocate_node(std::forward<_Args>(__args)...);
+ __node_sp_t __node_sp(*this,
+ this->_M_allocate_node(std::forward<_Args>(__args)...));
- __hash_code __code;
- __try
- {
- __code = this->_M_hash_code(this->_M_extract()(__node->_M_v()));
- }
- __catch(...)
- {
- this->_M_deallocate_node(__node);
- __throw_exception_again;
- }
-
- return _M_insert_multi_node(__hint._M_cur, __code, __node);
+ const key_type& __k
+ = this->_M_extract()(__node_sp._M_get()->_M_v());
+ return _M_insert_multi_node(__hint._M_cur, this->_M_hash_code(__k),
+ [&__node_sp]()
+ { return __node_sp._M_release(); });
}
template<typename _Key, typename _Value,
typename _Alloc, typename _ExtractKey, typename _Equal,
typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
typename _Traits>
+ template<typename _NodeAccessor>
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
- _M_insert_unique_node(size_type __bkt, __hash_code __code,
- __node_type* __node, size_type __n_elt)
+ _M_insert_unique_node(const key_type& __k, size_type __bkt,
+ __hash_code __code,
+ const _NodeAccessor& __node_accessor,
+ size_type __n_elt)
-> iterator
{
const __rehash_state& __saved_state = _M_rehash_policy._M_state();
@@ -1706,15 +1700,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
= _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
__n_elt);
- __try
- {
if (__do_rehash.first)
{
_M_rehash(__do_rehash.second, __saved_state);
- __bkt
- = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
+ __bkt = _M_bucket_index(__k, __code);
}
+ __node_type* __node = __node_accessor();
this->_M_store_code(__node, __code);
// Always insert at the beginning of the bucket.
@@ -1722,12 +1714,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
++_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.
@@ -1735,22 +1721,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Alloc, typename _ExtractKey, typename _Equal,
typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
typename _Traits>
+ template<typename _NodeAccessor>
auto
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_insert_multi_node(__node_type* __hint, __hash_code __code,
- __node_type* __node)
+ const _NodeAccessor& __node_accessor)
-> 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);
+ 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);
+ __node_type* __node = __node_accessor();
this->_M_store_code(__node, __code);
const key_type& __k = this->_M_extract()(__node->_M_v());
size_type __bkt = _M_bucket_index(__k, __code);
@@ -1779,20 +1765,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
}
else
- // The inserted node has no equivalent in the
- // hashtable. We must insert the new node at the
- // beginning of the bucket to preserve equivalent
- // elements' relative positions.
+ // The inserted node has no equivalent in the hashtable. We must
+ // insert the new node at the beginning of the bucket to preserve
+ // equivalent elements' relative positions.
_M_insert_bucket_begin(__bkt, __node);
++_M_element_count;
return iterator(__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,
@@ -1811,12 +1790,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__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 (__n)
- return std::make_pair(iterator(__n), false);
+ if (__node_type* __node = _M_find_node(__bkt, __k, __code))
+ return { iterator(__node), false };
- __n = __node_gen(std::forward<_Arg>(__v));
- return { _M_insert_unique_node(__bkt, __code, __n, __n_elt), true };
+ __node_sp_t __node_sp(*this, __node_gen(std::forward<_Arg>(__v)));
+ return
+ {
+ _M_insert_unique_node(__k, __bkt, __code,
+ [&__node_sp]()
+ { return __node_sp._M_release(); },
+ __n_elt),
+ true
+ };
}
// Insert v unconditionally.
@@ -1837,9 +1822,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__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));
+ __node_sp_t __node_sp(*this, __node_gen(std::forward<_Arg>(__v)));
- return _M_insert_multi_node(__hint._M_cur, __code, __node);
+ return _M_insert_multi_node(__hint._M_cur, __code,
+ [&__node_sp]()
+ { return __node_sp._M_release(); });
}
template<typename _Key, typename _Value,
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 878154ae210..ddcff0ec9d0 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -170,6 +170,40 @@ namespace __detail
__hashtable_alloc& _M_h;
};
+ // Node smart pointer to benefit from RAII.
+ template<typename _NodeAlloc>
+ struct _NodeSmartPointer
+ {
+ private:
+ using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>;
+ using __node_type = typename __hashtable_alloc::__node_type;
+
+ public:
+ _NodeSmartPointer(__hashtable_alloc& __h, __node_type* __node) noexcept
+ : _M_h(__h), _M_node(__node) { }
+
+ ~_NodeSmartPointer()
+ {
+ if (_M_node)
+ _M_h._M_deallocate_node(_M_node);
+ }
+
+ __node_type*
+ _M_get() const { return _M_node; }
+
+ __node_type*
+ _M_release() noexcept
+ {
+ __node_type* __tmp = _M_node;
+ _M_node = nullptr;
+ return __tmp;
+ }
+
+ private:
+ __hashtable_alloc& _M_h;
+ __node_type* _M_node;
+ };
+
// Auxiliary types used for all instantiations of _Hashtable nodes
// and iterators.
@@ -706,17 +740,18 @@ namespace __detail
__hashtable* __h = static_cast<__hashtable*>(this);
__hash_code __code = __h->_M_hash_code(__k);
std::size_t __bkt = __h->_M_bucket_index(__k, __code);
- __node_type* __p = __h->_M_find_node(__bkt, __k, __code);
- if (!__p)
- {
- __p = __h->_M_allocate_node(std::piecewise_construct,
- std::tuple<const key_type&>(__k),
- std::tuple<>());
- return __h->_M_insert_unique_node(__bkt, __code, __p)->second;
- }
+ if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code))
+ return __node->_M_v().second;
- return __p->_M_v().second;
+ using __node_sp_t = typename __hashtable::__node_sp_t;
+ __node_sp_t __node_sp(*__h,
+ __h->_M_allocate_node(std::piecewise_construct,
+ std::tuple<const key_type&>(__k),
+ std::tuple<>()));
+ return __h->_M_insert_unique_node(__k, __bkt, __code,
+ [&__node_sp]()
+ { return __node_sp._M_release(); })->second;
}
template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
@@ -731,17 +766,20 @@ namespace __detail
__hashtable* __h = static_cast<__hashtable*>(this);
__hash_code __code = __h->_M_hash_code(__k);
std::size_t __bkt = __h->_M_bucket_index(__k, __code);
- __node_type* __p = __h->_M_find_node(__bkt, __k, __code);
- if (!__p)
- {
- __p = __h->_M_allocate_node(std::piecewise_construct,
- std::forward_as_tuple(std::move(__k)),
- std::tuple<>());
- return __h->_M_insert_unique_node(__bkt, __code, __p)->second;
- }
+ if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code))
+ return __node->_M_v().second;
- return __p->_M_v().second;
+ using __node_sp_t = typename __hashtable::__node_sp_t;
+ __node_sp_t __node_sp(*__h,
+ __h->_M_allocate_node(std::piecewise_construct,
+ std::forward_as_tuple(std::move(__k)),
+ std::tuple<>()));
+ return __h->_M_insert_unique_node(
+ __h->_M_extract()(__node_sp._M_get()->_M_v()),
+ __bkt, __code,
+ [&__node_sp]()
+ { return __node_sp._M_release(); })->second;
}
template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
