Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // std::__detail definitions -*- C++ -*-
  2.  
  3. // Copyright (C) 2007-2015 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/hashtable_policy.h>
  34.  
  35. namespace std _GLIBCXX_VISIBILITY(default)
  36. {
  37. #include "../shared/hashtable-aux.cc"
  38.  
  39. namespace __detail
  40. {
  41.   _GLIBCXX_BEGIN_NAMESPACE_VERSION
  42.  
  43.   // Return a prime no smaller than n.
  44.   std::size_t
  45.   _Prime_rehash_policy::_M_next_bkt(std::size_t __n) const
  46.   {
  47.     // Optimize lookups involving the first elements of __prime_list.
  48.     // (useful to speed-up, eg, constructors)
  49.     static const unsigned char __fast_bkt[12]
  50.       = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
  51.  
  52.     if (__n <= 11)
  53.       {
  54.         _M_next_resize =
  55.           __builtin_ceil(__fast_bkt[__n] * (long double)_M_max_load_factor);
  56.         return __fast_bkt[__n];
  57.       }
  58.  
  59.     const unsigned long* __next_bkt =
  60.       std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes, __n);
  61.     _M_next_resize =
  62.       __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
  63.     return *__next_bkt;
  64.   }
  65.  
  66.   // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
  67.   // If p > __n_bkt, return make_pair(true, p); otherwise return
  68.   // make_pair(false, 0).  In principle this isn't very different from
  69.   // _M_bkt_for_elements.
  70.  
  71.   // The only tricky part is that we're caching the element count at
  72.   // which we need to rehash, so we don't have to do a floating-point
  73.   // multiply for every insertion.
  74.  
  75.   std::pair<bool, std::size_t>
  76.   _Prime_rehash_policy::
  77.   _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
  78.                  std::size_t __n_ins) const
  79.   {
  80.     if (__n_elt + __n_ins >= _M_next_resize)
  81.       {
  82.         long double __min_bkts = (__n_elt + __n_ins)
  83.                                    / (long double)_M_max_load_factor;
  84.         if (__min_bkts >= __n_bkt)
  85.           return std::make_pair(true,
  86.             _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
  87.                                               __n_bkt * _S_growth_factor)));
  88.  
  89.         _M_next_resize
  90.           = __builtin_floor(__n_bkt * (long double)_M_max_load_factor);
  91.         return std::make_pair(false, 0);
  92.       }
  93.     else
  94.       return std::make_pair(false, 0);
  95.   }
  96.  
  97. _GLIBCXX_END_NAMESPACE_VERSION
  98. } // namespace __detail
  99. } // namespace std
  100.