// hashtable.h header -*- C++ -*-
-// Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
+// Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012, 2013
+// 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
* - size_type _M_bucket_count
* - size_type _M_element_count
*
- * with _Bucket being _Hash_node* and _Hash_node constaining:
+ * with _Bucket being _Hash_node* and _Hash_node containing:
* - _Hash_node* _M_next
* - Tp _M_value
- * - size_t _M_code if cache_hash_code is true
+ * - size_t _M_hash_code if cache_hash_code is true
*
- * In terms of Standard containers the hastable is like the aggregation of:
+ * In terms of Standard containers the hashtable is like the aggregation of:
* - std::forward_list<_Node> containing the elements
* - std::vector<std::forward_list<_Node>::iterator> representing the buckets
*
- * The non-empty buckets contain the node before the first bucket node. This
- * design allow to implement something like a std::forward_list::insert_after
- * on container insertion and std::forward_list::erase_after on container
- * erase calls. _M_before_begin is equivalent to
- * std::foward_list::before_begin. Empty buckets are containing nullptr.
- * Note that one of the non-empty bucket contains &_M_before_begin which is
- * not a derefenrenceable node so the node pointers in buckets shall never be
- * derefenrenced, only its next node can be.
+ * The non-empty buckets contain the node before the first node in the
+ * bucket. This design makes it possible to implement something like a
+ * std::forward_list::insert_after on container insertion and
+ * std::forward_list::erase_after on container erase calls.
+ * _M_before_begin is equivalent to std::foward_list::before_begin.
+ * Empty buckets contain nullptr.
+ * Note that one of the non-empty buckets contains &_M_before_begin which is
+ * not a dereferenceable node so the node pointer in a bucket shall never be
+ * dereferenced, only its next node can be.
*
- * Walk through a bucket nodes require a check on the hash code to see if the
- * node is still in the bucket. Such a design impose a quite efficient hash
- * functor and is one of the reasons it is highly advise to set
- * __cache_hash_code to true.
+ * Walking through a bucket's nodes requires a check on the hash code to see
+ * if each node is still in the bucket. Such a design assumes a quite
+ * efficient hash functor and is one of the reasons it is
+ * highly advisable to set __cache_hash_code to true.
*
* The container iterators are simply built from nodes. This way incrementing
* the iterator is perfectly efficient independent of how many empty buckets
* there are in the container.
*
- * On insert we compute element hash code and thanks to it find the bucket
- * index. If the element must be inserted on an empty bucket we add it at the
- * beginning of the singly linked list and make the bucket point to
+ * On insert we compute the element's hash code and use it to it find the
+ * bucket index. If the element must be inserted in an empty bucket we add
+ * it at the beginning of the singly linked list and make the bucket point to
* _M_before_begin. The bucket that used to point to _M_before_begin, if any,
* is updated to point to its new before begin node.
*
- * On erase, the simple iterator design impose to use the hash functor to get
- * the index of the bucket to update. For this reason, when __cache_hash_code
- * is set to false, there is a static assertion that the hash functor cannot
- * throw.
+ * On erase, the simple iterator design requires using the hash functor to
+ * get the index of the bucket to update. For this reason, when
+ * __cache_hash_code is set to false, the hash functor must not throw
+ * and this is enforced by a statied assertion.
*/
template<typename _Key, typename _Value, typename _Allocator,
template<typename _Pair, typename = typename
std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
- std::is_convertible<_Pair,
- value_type>>::value>::type>
+ std::is_constructible<value_type,
+ _Pair&&>>::value>::type>
_Insert_Return_Type
insert(_Pair&& __v)
{ return _M_insert(std::forward<_Pair>(__v),
template<typename _Pair, typename = typename
std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
- std::is_convertible<_Pair,
- value_type>>::value>::type>
+ std::is_constructible<value_type,
+ _Pair&&>>::value>::type>
iterator
insert(const_iterator, _Pair&& __v)
{ return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); }
_M_element_count(0),
_M_rehash_policy()
{
- _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
- _M_rehash_policy.
- _M_bkt_for_elements(__detail::
- __distance_fw(__f,
- __l)));
+ _M_bucket_count =
+ _M_rehash_policy._M_bkt_for_elements(__detail::__distance_fw(__f,
+ __l));
+ if (_M_bucket_count <= __bucket_hint)
+ _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
+
// We don't want the rehash policy to ask for the hashtable to shrink
// on the first insertion so we need to reset its previous resize
// level.
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.
+ // find any more equivalent values.
break;
if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
break;
else
{
// The bucket is empty, the new node is inserted at the beginning of
- // the singly linked list and the bucket will contain _M_before_begin
+ // the singly-linked list and the bucket will contain _M_before_begin
// pointer.
__new_node->_M_nxt = _M_before_begin._M_nxt;
_M_before_begin._M_nxt = __new_node;
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.
+ // equivalent elements' relative positions.
_M_insert_bucket_begin(__bkt, __new_node);
++_M_element_count;
return iterator(__new_node);
std::size_t __bkt = _M_bucket_index(__n);
// Look for previous node to unlink it from the erased one, this is why
- // we need buckets to contain the before begin to make this research fast.
+ // we need buckets to contain the before begin to make this search fast.
_BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);
if (__n == _M_bucket_begin(__bkt))
_M_remove_bucket_begin(__bkt, __n->_M_next(),
rehash(size_type __n)
{
const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
- _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
- _M_rehash_policy._M_bkt_for_elements(_M_element_count
- + 1)),
- __saved_state);
+ std::size_t __buckets
+ = _M_rehash_policy._M_bkt_for_elements(_M_element_count + 1);
+ if (__buckets <= __n)
+ __buckets = _M_rehash_policy._M_next_bkt(__n);
+
+ if (__buckets != _M_bucket_count)
+ {
+ _M_rehash(__buckets, __saved_state);
+
+ // We don't want the rehash policy to ask for the hashtable to shrink
+ // on the next insertion so we need to reset its previous resize
+ // level.
+ _M_rehash_policy._M_prev_resize = 0;
+ }
+ else
+ // No rehash, restore previous state to keep a consistent state.
+ _M_rehash_policy._M_reset(__saved_state);
}
template<typename _Key, typename _Value,
_Bucket* __new_buckets = _M_allocate_buckets(__n);
_Node* __p = _M_begin();
_M_before_begin._M_nxt = nullptr;
- std::size_t __bbegin_bkt;
+ std::size_t __bbegin_bkt = 0;
while (__p)
{
_Node* __next = __p->_M_next();
_Node* __p = _M_begin();
_M_before_begin._M_nxt = nullptr;
- std::size_t __bbegin_bkt;
- std::size_t __prev_bkt;
+ std::size_t __bbegin_bkt = 0;
+ std::size_t __prev_bkt = 0;
_Node* __prev_p = nullptr;
bool __check_bucket = false;
while (__p)
{
- bool __check_now = true;
_Node* __next = __p->_M_next();
std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
- if (!__new_buckets[__bkt])
+ if (__prev_p && __prev_bkt == __bkt)
{
- __p->_M_nxt = _M_before_begin._M_nxt;
- _M_before_begin._M_nxt = __p;
- __new_buckets[__bkt] = &_M_before_begin;
- if (__p->_M_nxt)
- __new_buckets[__bbegin_bkt] = __p;
- __bbegin_bkt = __bkt;
+ // Previous insert was already in this bucket, we insert after
+ // the previously inserted one to preserve equivalent elements
+ // relative order.
+ __p->_M_nxt = __prev_p->_M_nxt;
+ __prev_p->_M_nxt = __p;
+
+ // Inserting after a node in a bucket require to check that we
+ // haven't change the bucket last node, in this case next
+ // bucket containing its before begin node must be updated. We
+ // schedule a check as soon as we move out of the sequence of
+ // equivalent nodes to limit the number of checks.
+ __check_bucket = true;
}
else
{
- if (__prev_p && __prev_bkt == __bkt)
+ if (__check_bucket)
{
- // Previous insert was already in this bucket, we insert after
- // the previously inserted one to preserve equivalent elements
- // relative order.
- __p->_M_nxt = __prev_p->_M_nxt;
- __prev_p->_M_nxt = __p;
-
- // Inserting after a node in a bucket require to check that we
- // haven't change the bucket last node, in this case next
- // bucket containing its before begin node must be updated. We
- // schedule a check as soon as we move out of the sequence of
- // equivalent nodes to limit the number of checks.
- __check_bucket = true;
- __check_now = false;
+ // Check if we shall update the next bucket because of
+ // insertions into __prev_bkt bucket.
+ if (__prev_p->_M_nxt)
+ {
+ std::size_t __next_bkt
+ = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
+ if (__next_bkt != __prev_bkt)
+ __new_buckets[__next_bkt] = __prev_p;
+ }
+ __check_bucket = false;
+ }
+ if (!__new_buckets[__bkt])
+ {
+ __p->_M_nxt = _M_before_begin._M_nxt;
+ _M_before_begin._M_nxt = __p;
+ __new_buckets[__bkt] = &_M_before_begin;
+ if (__p->_M_nxt)
+ __new_buckets[__bbegin_bkt] = __p;
+ __bbegin_bkt = __bkt;
}
else
{
__new_buckets[__bkt]->_M_nxt = __p;
}
}
-
- if (__check_now && __check_bucket)
- {
- // Check if we shall update the next bucket because of insertions
- // into __prev_bkt bucket.
- if (__prev_p->_M_nxt)
- {
- std::size_t __next_bkt
- = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
- if (__next_bkt != __prev_bkt)
- __new_buckets[__next_bkt] = __prev_p;
- }
- __check_bucket = false;
- }
+
__prev_p = __p;
__prev_bkt = __bkt;
__p = __next;
projects / l4.git / blobdiff