Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  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
  98.