libstdc++-v3/src/c++11/hashtable_c++0x.cc

   1 // std::__detail definitions -*- C++ -*-
   2
   3 // Copyright (C) 2007-2024 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 <ext/aligned_buffer.h>
  32 #include <ext/alloc_traits.h>
  33 #include <bits/functional_hash.h>
  34 #include <bits/hashtable_policy.h>
  35
  36 namespace std _GLIBCXX_VISIBILITY(default)
  37 {
  38 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  39
  40 #include "../shared/hashtable-aux.cc"
  41
  42 namespace __detail
  43 {
  44   // Return a prime no smaller than n.
  45   std::size_t
  46   _Prime_rehash_policy::_M_next_bkt(std::size_t __n) const
  47   {
  48     // Optimize lookups involving the first elements of __prime_list.
  49     // (useful to speed-up, eg, constructors)
  50     static const unsigned char __fast_bkt[]
  51       = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13 };
  52
  53     if (__n < sizeof(__fast_bkt))
  54       {
  55         if (__n == 0)
  56           // Special case on container 1st initialization with 0 bucket count
  57           // hint. We keep _M_next_resize to 0 to make sure that next time we
  58           // want to add an element allocation will take place.
  59           return 1;
  60
  61         _M_next_resize =
  62           __builtin_floor(__fast_bkt[__n] * (double)_M_max_load_factor);
  63         return __fast_bkt[__n];
  64       }
  65
  66     // Number of primes (without sentinel).
  67     constexpr auto __n_primes
  68       = sizeof(__prime_list) / sizeof(unsigned long) - 1;
  69
  70     // Don't include the last prime in the search, so that anything
  71     // higher than the second-to-last prime returns a past-the-end
  72     // iterator that can be dereferenced to get the last prime.
  73     constexpr auto __last_prime = __prime_list + __n_primes - 1;
  74
  75     const unsigned long* __next_bkt =
  76       std::lower_bound(__prime_list + 6, __last_prime, __n);
  77
  78     if (__next_bkt == __last_prime)
  79       // Set next resize to the max value so that we never try to rehash again
  80       // as we already reach the biggest possible bucket number.
  81       // Note that it might result in max_load_factor not being respected.
  82       _M_next_resize = size_t(-1);
  83     else
  84       _M_next_resize =
  85         __builtin_floor(*__next_bkt * (double)_M_max_load_factor);
  86
  87     return *__next_bkt;
  88   }
  89
  90   // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
  91   // If p > __n_bkt, return make_pair(true, p); otherwise return
  92   // make_pair(false, 0).  In principle this isn't very different from
  93   // _M_bkt_for_elements.
  94
  95   // The only tricky part is that we're caching the element count at
  96   // which we need to rehash, so we don't have to do a floating-point
  97   // multiply for every insertion.
  98
  99   std::pair<bool, std::size_t>
 100   _Prime_rehash_policy::
 101   _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
 102                  std::size_t __n_ins) const
 103   {
 104     if (__n_elt + __n_ins > _M_next_resize)
 105       {
 106         // If _M_next_resize is 0 it means that we have nothing allocated so
 107         // far and that we start inserting elements. In this case we start
 108         // with an initial bucket size of 11.
 109         double __min_bkts
 110           = std::max<std::size_t>(__n_elt + __n_ins, _M_next_resize ? 0 : 11)
 111           / (double)_M_max_load_factor;
 112         if (__min_bkts >= __n_bkt)
 113           return { true,
 114             _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
 115                                               __n_bkt * _S_growth_factor)) };
 116
 117         _M_next_resize
 118           = __builtin_floor(__n_bkt * (double)_M_max_load_factor);
 119         return { false, 0 };
 120       }
 121     else
 122       return { false, 0 };
 123   }
 124 } // namespace __detail
 125
 126 _GLIBCXX_END_NAMESPACE_VERSION
 127 } // namespace std