Subversion Repositories openrisc

// Internal policy header for unordered_set and unordered_map -*- C++ -*-

// Copyright (C) 2010, 2011, 2012 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)

// any later version.

// This library is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// <http://www.gnu.org/licenses/>.

/** @file bits/hashtable_policy.h

 *  This is an internal header file, included by other library headers.

 *  Do not attempt to use it directly.

 *  @headername{unordered_map,unordered_set}

 */

#ifndef _HASHTABLE_POLICY_H

#define _HASHTABLE_POLICY_H 1

namespace std _GLIBCXX_VISIBILITY(default)

{

namespace __detail

{

_GLIBCXX_BEGIN_NAMESPACE_VERSION

  // Helper function: return distance(first, last) for forward

  // iterators, or 0 for input iterators.

  template<class _Iterator>

    inline typename std::iterator_traits<_Iterator>::difference_type

    __distance_fw(_Iterator __first, _Iterator __last,

                  std::input_iterator_tag)

    { return 0; }

  template<class _Iterator>

    inline typename std::iterator_traits<_Iterator>::difference_type

    __distance_fw(_Iterator __first, _Iterator __last,

                  std::forward_iterator_tag)

    { return std::distance(__first, __last); }

  template<class _Iterator>

    inline typename std::iterator_traits<_Iterator>::difference_type

    __distance_fw(_Iterator __first, _Iterator __last)

    {

      typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;

      return __distance_fw(__first, __last, _Tag());

    }

  // Helper type used to detect when the hash functor is noexcept qualified or

  // not

  template <typename _Key, typename _Hash>

    struct __is_noexcept_hash : std::integral_constant<bool,

        noexcept(declval<const _Hash&>()(declval<const _Key&>()))>

    {};

  // Auxiliary types used for all instantiations of _Hashtable: nodes

  // and iterators.

  // Nodes, used to wrap elements stored in the hash table.  A policy

  // 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> : _Hash_node_base

    {

      _Value       _M_v;

      std::size_t  _M_hash_code;

      template<typename... _Args>

        _Hash_node(_Args&&... __args)

        : _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> : _Hash_node_base

    {

      _Value       _M_v;

      template<typename... _Args>

        _Hash_node(_Args&&... __args)

        : _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.

  template<typename _Value, bool __cache>

    struct _Node_iterator_base

    {

      _Node_iterator_base(_Hash_node<_Value, __cache>* __p)

      : _M_cur(__p) { }

      void

      _M_incr()

      { _M_cur = _M_cur->_M_next(); }

      _Hash_node<_Value, __cache>*  _M_cur;

    };

  template<typename _Value, bool __cache>

    inline bool

    operator==(const _Node_iterator_base<_Value, __cache>& __x,

               const _Node_iterator_base<_Value, __cache>& __y)

    { return __x._M_cur == __y._M_cur; }

  template<typename _Value, bool __cache>

    inline bool

    operator!=(const _Node_iterator_base<_Value, __cache>& __x,

               const _Node_iterator_base<_Value, __cache>& __y)

    { return __x._M_cur != __y._M_cur; }

  template<typename _Value, bool __constant_iterators, bool __cache>

    struct _Node_iterator

    : public _Node_iterator_base<_Value, __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;

      _Node_iterator()

      : _Node_iterator_base<_Value, __cache>(0) { }

      explicit

      _Node_iterator(_Hash_node<_Value, __cache>* __p)

      : _Node_iterator_base<_Value, __cache>(__p) { }

      reference

      operator*() const

      { return this->_M_cur->_M_v; }

      pointer

      operator->() const

      { return std::__addressof(this->_M_cur->_M_v); }

      _Node_iterator&

      operator++()

      {

        this->_M_incr();

        return *this;

      }

      _Node_iterator

      operator++(int)

      {

        _Node_iterator __tmp(*this);

        this->_M_incr();

        return __tmp;

      }

    };

  template<typename _Value, bool __constant_iterators, bool __cache>

    struct _Node_const_iterator

    : public _Node_iterator_base<_Value, __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;

      _Node_const_iterator()

      : _Node_iterator_base<_Value, __cache>(0) { }

      explicit

      _Node_const_iterator(_Hash_node<_Value, __cache>* __p)

      : _Node_iterator_base<_Value, __cache>(__p) { }

      _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,

                           __cache>& __x)

      : _Node_iterator_base<_Value, __cache>(__x._M_cur) { }

      reference

      operator*() const

      { return this->_M_cur->_M_v; }

      pointer

      operator->() const

      { return std::__addressof(this->_M_cur->_M_v); }

      _Node_const_iterator&

      operator++()

      {

        this->_M_incr();

        return *this;

      }

      _Node_const_iterator

      operator++(int)

      {

        _Node_const_iterator __tmp(*this);

        this->_M_incr();

        return __tmp;

      }

    };

  // Many of class template _Hashtable's template parameters are policy

  // classes.  These are defaults for the policies.

  // Default range hashing function: use division to fold a large number

  // into the range [0, N).

  struct _Mod_range_hashing

  {

    typedef std::size_t first_argument_type;

    typedef std::size_t second_argument_type;

    typedef std::size_t result_type;

    result_type

    operator()(first_argument_type __num, second_argument_type __den) const

    { return __num % __den; }

  };

  // Default ranged hash function H.  In principle it should be a

  // function object composed from objects of type H1 and H2 such that

  // h(k, N) = h2(h1(k), N), but that would mean making extra copies of

  // h1 and h2.  So instead we'll just use a tag to tell class template

  // hashtable to do that composition.

  struct _Default_ranged_hash { };

  // Default value for rehash policy.  Bucket size is (usually) the

  // smallest prime that keeps the load factor small enough.

  struct _Prime_rehash_policy

  {

    _Prime_rehash_policy(float __z = 1.0)

    : _M_max_load_factor(__z), _M_prev_resize(0), _M_next_resize(0) { }

    float

    max_load_factor() const noexcept

    { return _M_max_load_factor; }

    // Return a bucket size no smaller than n.

    std::size_t

    _M_next_bkt(std::size_t __n) const;

    // Return a bucket count appropriate for n elements

    std::size_t

    _M_bkt_for_elements(std::size_t __n) const;

    // __n_bkt is current bucket count, __n_elt is current element count,

    // and __n_ins is number of elements to be inserted.  Do we need to

    // increase bucket count?  If so, return make_pair(true, n), where n

    // is the new bucket count.  If not, return make_pair(false, 0).

    std::pair<bool, std::size_t>

    _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,

                   std::size_t __n_ins) const;

    typedef std::pair<std::size_t, std::size_t> _State;

    _State

    _M_state() const

    { return std::make_pair(_M_prev_resize, _M_next_resize); }

    void

    _M_reset(const _State& __state)

    {

      _M_prev_resize = __state.first;

      _M_next_resize = __state.second;

    }

    enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };

    float                _M_max_load_factor;

    mutable std::size_t  _M_prev_resize;

    mutable std::size_t  _M_next_resize;

  };

  extern const unsigned long __prime_list[];

  // XXX This is a hack.  There's no good reason for any of

  // _Prime_rehash_policy's member functions to be inline.

  // Return a prime no smaller than n.

  inline std::size_t

  _Prime_rehash_policy::

  _M_next_bkt(std::size_t __n) const

  {

    // Optimize lookups involving the first elements of __prime_list.

    // (useful to speed-up, eg, constructors)

    static const unsigned char __fast_bkt[12]

      = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };

    if (__n <= 11)

      {

        _M_prev_resize = 0;

        _M_next_resize

          = __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor);

        return __fast_bkt[__n];

      }

    const unsigned long* __p

      = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, __n);

    // 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;

  }

  // Return the smallest prime p such that alpha p >= n, where alpha

  // is the load factor.

  inline std::size_t

  _Prime_rehash_policy::

  _M_bkt_for_elements(std::size_t __n) const

  { return _M_next_bkt(__builtin_ceil(__n / (long double)_M_max_load_factor)); }

  // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.

  // If p > __n_bkt, return make_pair(true, p); otherwise return

  // make_pair(false, 0).  In principle this isn't very different from

  // _M_bkt_for_elements.

  // The only tricky part is that we're caching the element count at

  // which we need to rehash, so we don't have to do a floating-point

  // multiply for every insertion.

  inline std::pair<bool, std::size_t>

  _Prime_rehash_policy::

  _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,

                 std::size_t __n_ins) const

  {

    if (__n_elt + __n_ins >= _M_next_resize)

      {

        long double __min_bkts = (__n_elt + __n_ins)

                                 / (long double)_M_max_load_factor;

        if (__min_bkts >= __n_bkt)

          return std::make_pair(true,

                                _M_next_bkt(__builtin_floor(__min_bkts) + 1));

        else

          {

            _M_next_resize

              = __builtin_floor(__n_bkt * (long double)_M_max_load_factor);

            return std::make_pair(false, 0);

          }

      }

    else if (__n_elt + __n_ins < _M_prev_resize)

      {

        long double __min_bkts = (__n_elt + __n_ins)

                                 / (long double)_M_max_load_factor;

        return std::make_pair(true,

                              _M_next_bkt(__builtin_floor(__min_bkts) + 1));

      }

    else

      return std::make_pair(false, 0);

  }

  // Base classes for std::_Hashtable.  We define these base classes

  // because in some cases we want to do different things depending

  // on the value of a policy class.  In some cases the policy class

  // affects which member functions and nested typedefs are defined;

  // we handle that by specializing base class templates.  Several of

  // the base class templates need to access other members of class

  // template _Hashtable, so we use the "curiously recurring template

  // pattern" for them.

  // class template _Map_base.  If the hashtable has a value type of

  // the form pair<T1, T2> and a key extraction policy that returns the

  // first part of the pair, the hashtable gets a mapped_type typedef.

  // If it satisfies those criteria and also has unique keys, then it

  // also gets an operator[].

  template<typename _Key, typename _Value, typename _Ex, bool __unique,

           typename _Hashtable>

    struct _Map_base { };

  template<typename _Key, typename _Pair, typename _Hashtable>

    struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable>

    {

      typedef typename _Pair::second_type mapped_type;

    };

  template<typename _Key, typename _Pair, typename _Hashtable>

    struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>

    {

      typedef typename _Pair::second_type mapped_type;

      mapped_type&

      operator[](const _Key& __k);

      mapped_type&

      operator[](_Key&& __k);

      // _GLIBCXX_RESOLVE_LIB_DEFECTS

      // DR 761. unordered_map needs an at() member function.

      mapped_type&

      at(const _Key& __k);

      const mapped_type&

      at(const _Key& __k) const;

    };

  template<typename _Key, typename _Pair, typename _Hashtable>

    typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,

                       true, _Hashtable>::mapped_type&

    _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::

    operator[](const _Key& __k)

    {

      _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);

      typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);

      if (!__p)

        return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),

                                     __n, __code)->second;

      return (__p->_M_v).second;

    }

  template<typename _Key, typename _Pair, typename _Hashtable>

    typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,

                       true, _Hashtable>::mapped_type&

    _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::

    operator[](_Key&& __k)

    {

      _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);

      typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);

      if (!__p)

        return __h->_M_insert_bucket(std::make_pair(std::move(__k),

                                                    mapped_type()),

                                     __n, __code)->second;

      return (__p->_M_v).second;

    }

  template<typename _Key, typename _Pair, typename _Hashtable>

    typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,

                       true, _Hashtable>::mapped_type&

    _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::

    at(const _Key& __k)

    {

      _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);

      typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);

      if (!__p)

        __throw_out_of_range(__N("_Map_base::at"));

      return (__p->_M_v).second;

    }

  template<typename _Key, typename _Pair, typename _Hashtable>

    const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,

                             true, _Hashtable>::mapped_type&

    _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::

    at(const _Key& __k) const

    {

      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);

      typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);

      if (!__p)

        __throw_out_of_range(__N("_Map_base::at"));

      return (__p->_M_v).second;

    }

  // class template _Rehash_base.  Give hashtable the max_load_factor

  // functions and reserve iff the rehash policy is _Prime_rehash_policy.

  template<typename _RehashPolicy, typename _Hashtable>

    struct _Rehash_base { };

  template<typename _Hashtable>

    struct _Rehash_base<_Prime_rehash_policy, _Hashtable>

    {

      float

      max_load_factor() const noexcept

      {

        const _Hashtable* __this = static_cast<const _Hashtable*>(this);

        return __this->__rehash_policy().max_load_factor();

      }

      void

      max_load_factor(float __z)

      {

        _Hashtable* __this = static_cast<_Hashtable*>(this);

        __this->__rehash_policy(_Prime_rehash_policy(__z));

      }

      void

      reserve(std::size_t __n)

      {

        _Hashtable* __this = static_cast<_Hashtable*>(this);

        __this->rehash(__builtin_ceil(__n / max_load_factor()));

      }

    };

  // 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 _Hashtable_ebo_helper;

  // Specialization using EBO.

  template<int _Nm, typename _Tp>

    struct _Hashtable_ebo_helper<_Nm, _Tp, true> : private _Tp

    {

      _Hashtable_ebo_helper() = default;

      _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp)

      { }

      static const _Tp&

      _S_cget(const _Hashtable_ebo_helper& __eboh)

      { return static_cast<const _Tp&>(__eboh); }

      static _Tp&

      _S_get(_Hashtable_ebo_helper& __eboh)

      { return static_cast<_Tp&>(__eboh); }

    };

  // Specialization not using EBO.

  template<int _Nm, typename _Tp>

    struct _Hashtable_ebo_helper<_Nm, _Tp, false>

    {

      _Hashtable_ebo_helper() = default;

      _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp)

      { }

      static const _Tp&

      _S_cget(const _Hashtable_ebo_helper& __eboh)

      { return __eboh._M_tp; }

      static _Tp&

      _S_get(_Hashtable_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

  //       the combination of a hash function and a range-hashing function.

  //       In the former case we don't have such things as hash codes, so

  //       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 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 _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 _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>

    {

    private:

      typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;

      typedef _Hashtable_ebo_helper<1, _Hash> _EboHash;

    protected:

      // 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)

        : _EboExtractKey(__ex), _EboHash(__h) { }

      typedef void* _Hash_code_type;

      _Hash_code_type

      _M_hash_code(const _Key& __key) const

      { return 0; }

      std::size_t

      _M_bucket_index(const _Key& __k, _Hash_code_type,

                      std::size_t __n) const

      { 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); }

      void

      _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const

      { }

      void

      _M_copy_code(_Hash_node<_Value, false>*,

                   const _Hash_node<_Value, false>*) const

      { }

      void

      _M_swap(_Hash_code_base& __x)

      {

        std::swap(_M_extract(), __x._M_extract());

        std::swap(_M_ranged_hash(), __x._M_ranged_hash());

      }

    protected:

      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 _H1, typename _H2, typename _Hash>

    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;