l4/pkg/l4re-core/libstdc++-v3/contrib/libstdc++-v3-4.8/src/c++11/hashtable_c++0x.cc

   1 // std::__detail definitions -*- C++ -*-
   2
   3 // Copyright (C) 2007-2013 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 #if __cplusplus < 201103L
  26 # error "hashtable_c++0x.cc must be compiled with -std=gnu++0x"
  27 #endif
  28
  29 #include <initializer_list>
  30 #include <tuple>
  31 #include <bits/hashtable_policy.h>
  32
  33 namespace std _GLIBCXX_VISIBILITY(default)
  34 {
  35 #include "../shared/hashtable-aux.cc"
  36
  37 namespace __detail
  38 {
  39   _GLIBCXX_BEGIN_NAMESPACE_VERSION
  40
  41   // Return a prime no smaller than n.
  42   std::size_t
  43   _Prime_rehash_policy::_M_next_bkt(std::size_t __n) const
  44   {
  45     // Optimize lookups involving the first elements of __prime_list.
  46     // (useful to speed-up, eg, constructors)
  47     static const unsigned char __fast_bkt[12]
  48       = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
  49
  50     if (__n <= 11)
  51       {
  52         _M_next_resize =
  53           __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor);
  54         return __fast_bkt[__n];
  55       }
  56
  57     const unsigned long* __next_bkt =
  58       std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, __n);
  59     _M_next_resize =
  60       __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
  61     return *__next_bkt;
  62   }
  63
  64   // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
  65   // If p > __n_bkt, return make_pair(true, p); otherwise return
  66   // make_pair(false, 0).  In principle this isn't very different from
  67   // _M_bkt_for_elements.
  68
  69   // The only tricky part is that we're caching the element count at
  70   // which we need to rehash, so we don't have to do a floating-point
  71   // multiply for every insertion.
  72
  73   std::pair<bool, std::size_t>
  74   _Prime_rehash_policy::
  75   _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
  76                  std::size_t __n_ins) const
  77   {
  78     if (__n_elt + __n_ins >= _M_next_resize)
  79       {
  80         long double __min_bkts = (__n_elt + __n_ins)
  81                                    / (long double)_M_max_load_factor;
  82         if (__min_bkts >= __n_bkt)
  83           return std::make_pair(true,
  84             _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
  85                                               __n_bkt * _S_growth_factor)));
  86
  87         _M_next_resize
  88           = __builtin_floor(__n_bkt * (long double)_M_max_load_factor);
  89         return std::make_pair(false, 0);
  90       }
  91     else
  92       return std::make_pair(false, 0);
  93   }
  94
  95 _GLIBCXX_END_NAMESPACE_VERSION
  96 } // namespace __detail
  97 } // namespace std