// template parameter of class template _Hashtable controls whether
// nodes also store a hash code. In some cases (e.g. strings) this
// may be a performance win.
+ struct _Hash_node_base
+ {
+ _Hash_node_base* _M_nxt;
+
+ _Hash_node_base()
+ : _M_nxt() { }
+ _Hash_node_base(_Hash_node_base* __next)
+ : _M_nxt(__next) { }
+ };
+
template<typename _Value, bool __cache_hash_code>
struct _Hash_node;
template<typename _Value>
- struct _Hash_node<_Value, true>
+ struct _Hash_node<_Value, true> : _Hash_node_base
{
_Value _M_v;
std::size_t _M_hash_code;
- _Hash_node* _M_next;
template<typename... _Args>
_Hash_node(_Args&&... __args)
- : _M_v(std::forward<_Args>(__args)...),
- _M_hash_code(), _M_next() { }
+ : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { }
+
+ _Hash_node* _M_next() const
+ { return static_cast<_Hash_node*>(_M_nxt); }
};
template<typename _Value>
- struct _Hash_node<_Value, false>
+ struct _Hash_node<_Value, false> : _Hash_node_base
{
_Value _M_v;
- _Hash_node* _M_next;
template<typename... _Args>
_Hash_node(_Args&&... __args)
- : _M_v(std::forward<_Args>(__args)...),
- _M_next() { }
+ : _M_v(std::forward<_Args>(__args)...) { }
+
+ _Hash_node* _M_next() const
+ { return static_cast<_Hash_node*>(_M_nxt); }
};
// Node iterators, used to iterate through all the hashtable.
void
_M_incr()
- { _M_cur = _M_cur->_M_next; }
+ { _M_cur = _M_cur->_M_next(); }
_Hash_node<_Value, __cache>* _M_cur;
};
enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
+ static const std::size_t _S_growth_factor = 2;
+
float _M_max_load_factor;
mutable std::size_t _M_prev_resize;
mutable std::size_t _M_next_resize;
static const unsigned char __fast_bkt[12]
= { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
- if (__n <= 11)
+ const std::size_t __grown_n = __n * _S_growth_factor;
+ if (__grown_n <= 11)
{
_M_prev_resize = 0;
_M_next_resize
- = __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor);
- return __fast_bkt[__n];
+ = __builtin_ceil(__fast_bkt[__grown_n]
+ * (long double)_M_max_load_factor);
+ return __fast_bkt[__grown_n];
}
- const unsigned long* __p
- = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, __n);
+ const unsigned long* __next_bkt
+ = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes,
+ __grown_n);
+ const unsigned long* __prev_bkt
+ = std::lower_bound(__prime_list + 1, __next_bkt, __n / _S_growth_factor);
- // Shrink will take place only if the number of elements is small enough
- // so that the prime number 2 steps before __p is large enough to still
- // conform to the max load factor:
_M_prev_resize
- = __builtin_floor(*(__p - 2) * (long double)_M_max_load_factor);
-
- // Let's guaranty that a minimal grow step of 11 is used
- if (*__p - __n < 11)
- __p = std::lower_bound(__p, __prime_list + _S_n_primes, __n + 11);
- _M_next_resize = __builtin_ceil(*__p * (long double)_M_max_load_factor);
- return *__p;
+ = __builtin_floor(*(__prev_bkt - 1) * (long double)_M_max_load_factor);
+ _M_next_resize
+ = __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
+ return *__next_bkt;
}
// Return the smallest prime p such that alpha p >= n, where alpha
// Specialization using EBO.
template<int _Nm, typename _Tp>
- struct _Hashtable_ebo_helper<_Nm, _Tp, true> : private _Tp
+ struct _Hashtable_ebo_helper<_Nm, _Tp, true>
+ // See PR53067.
+ : public _Tp
{
_Hashtable_ebo_helper() = default;
_Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp)
template<typename _Key, typename _Value, typename _ExtractKey,
typename _H1, typename _H2, typename _Hash>
struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
- : private _Hashtable_ebo_helper<0, _ExtractKey>,
- private _Hashtable_ebo_helper<1, _Hash>
+ // See PR53067.
+ : public _Hashtable_ebo_helper<0, _ExtractKey>,
+ public _Hashtable_ebo_helper<1, _Hash>
{
private:
typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
typename _H1, typename _H2>
struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
_Default_ranged_hash, false>
- : private _Hashtable_ebo_helper<0, _ExtractKey>,
- private _Hashtable_ebo_helper<1, _H1>,
- private _Hashtable_ebo_helper<2, _H2>
+ // See PR53067.
+ : public _Hashtable_ebo_helper<0, _ExtractKey>,
+ public _Hashtable_ebo_helper<1, _H1>,
+ public _Hashtable_ebo_helper<2, _H2>
{
private:
typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
typename _H1, typename _H2>
struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
_Default_ranged_hash, true>
- : private _Hashtable_ebo_helper<0, _ExtractKey>,
- private _Hashtable_ebo_helper<1, _H1>,
- private _Hashtable_ebo_helper<2, _H2>
+ // See PR53067.
+ : public _Hashtable_ebo_helper<0, _ExtractKey>,
+ public _Hashtable_ebo_helper<1, _H1>,
+ public _Hashtable_ebo_helper<2, _H2>
{
private:
typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
typename _H1, typename _H2, typename _Hash,
bool __cache_hash_code>
struct _Hashtable_base
+ // See PR53067.
: public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
__cache_hash_code>,
- private _Hashtable_ebo_helper<0, _Equal>
+ public _Hashtable_ebo_helper<0, _Equal>
{
private:
typedef _Hashtable_ebo_helper<0, _Equal> _EboEqual;
typename _H1, typename _H2, typename _Hash>
struct _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, true>
- : private _H2
+ // See PR53067.
+ : public _H2
{
_Local_iterator_base() = default;
_Local_iterator_base(_Hash_node<_Value, true>* __p,
void
_M_incr()
{
- _M_cur = _M_cur->_M_next;
+ _M_cur = _M_cur->_M_next();
if (_M_cur)
{
std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count);
typename _H1, typename _H2, typename _Hash>
struct _Local_iterator_base<_Key, _Value, _ExtractKey,
_H1, _H2, _Hash, false>
- : private _Hash_code_base<_Key, _Value, _ExtractKey,
- _H1, _H2, _Hash, false>
+ // See PR53067.
+ : public _Hash_code_base<_Key, _Value, _ExtractKey,
+ _H1, _H2, _Hash, false>
{
_Local_iterator_base() = default;
_Local_iterator_base(_Hash_node<_Value, false>* __p,
void
_M_incr()
{
- _M_cur = _M_cur->_M_next;
+ _M_cur = _M_cur->_M_next();
if (_M_cur)
{
std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
{
const auto __ity = __other.find(_ExtractKey()(*__itx));
- if (__ity == __other.end() || *__ity != *__itx)
+ if (__ity == __other.end() || !bool(*__ity == *__itx))
return false;
}
return true;
for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
{
_Uiterator __tmp = __first1;
- while (__tmp != __it1 && !(*__tmp == *__it1))
+ while (__tmp != __it1 && !bool(*__tmp == *__it1))
++__tmp;
// We've seen this one before.
OSDN Git Service
