Subversion Repositories Kolibri OS

Rev

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

  1. // -*- C++ -*-
  2.  
  3. // Copyright (C) 2005-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 terms
  7. // of the GNU General Public License as published by the Free Software
  8. // Foundation; either version 3, or (at your option) any later
  9. // version.
  10.  
  11. // This library is distributed in the hope that it will be useful, but
  12. // WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14. // 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. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26.  
  27. // Permission to use, copy, modify, sell, and distribute this software
  28. // is hereby granted without fee, provided that the above copyright
  29. // notice appears in all copies, and that both that copyright notice
  30. // and this permission notice appear in supporting documentation. None
  31. // of the above authors, nor IBM Haifa Research Laboratories, make any
  32. // representation about the suitability of this software for any
  33. // purpose. It is provided "as is" without express or implied
  34. // warranty.
  35.  
  36. /**
  37.  * @file hash_load_check_resize_trigger_imp.hpp
  38.  * Contains a resize trigger implementation.
  39.  */
  40.  
  41. #define PB_DS_ASSERT_VALID(X)                                           \
  42.   _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
  43.  
  44. PB_DS_CLASS_T_DEC
  45. PB_DS_CLASS_C_DEC::
  46. hash_load_check_resize_trigger(float load_min, float load_max)
  47. : m_load_min(load_min), m_load_max(load_max), m_next_shrink_size(0),
  48.   m_next_grow_size(0), m_resize_needed(false)
  49. { PB_DS_ASSERT_VALID((*this)) }
  50.  
  51. PB_DS_CLASS_T_DEC
  52. inline void
  53. PB_DS_CLASS_C_DEC::
  54. notify_find_search_start()
  55. { PB_DS_ASSERT_VALID((*this)) }
  56.  
  57. PB_DS_CLASS_T_DEC
  58. inline void
  59. PB_DS_CLASS_C_DEC::
  60. notify_find_search_collision()
  61. { PB_DS_ASSERT_VALID((*this)) }
  62.  
  63. PB_DS_CLASS_T_DEC
  64. inline void
  65. PB_DS_CLASS_C_DEC::
  66. notify_find_search_end()
  67. { PB_DS_ASSERT_VALID((*this)) }
  68.  
  69. PB_DS_CLASS_T_DEC
  70. inline void
  71. PB_DS_CLASS_C_DEC::
  72. notify_insert_search_start()
  73. { PB_DS_ASSERT_VALID((*this)) }
  74.  
  75. PB_DS_CLASS_T_DEC
  76. inline void
  77. PB_DS_CLASS_C_DEC::
  78. notify_insert_search_collision()
  79. { PB_DS_ASSERT_VALID((*this)) }
  80.  
  81. PB_DS_CLASS_T_DEC
  82. inline void
  83. PB_DS_CLASS_C_DEC::
  84. notify_insert_search_end()
  85. { PB_DS_ASSERT_VALID((*this)) }
  86.  
  87. PB_DS_CLASS_T_DEC
  88. inline void
  89. PB_DS_CLASS_C_DEC::
  90. notify_erase_search_start()
  91. { PB_DS_ASSERT_VALID((*this)) }
  92.  
  93. PB_DS_CLASS_T_DEC
  94. inline void
  95. PB_DS_CLASS_C_DEC::
  96. notify_erase_search_collision()
  97. { PB_DS_ASSERT_VALID((*this)) }
  98.  
  99. PB_DS_CLASS_T_DEC
  100. inline void
  101. PB_DS_CLASS_C_DEC::
  102. notify_erase_search_end()
  103. { PB_DS_ASSERT_VALID((*this)) }
  104.  
  105. PB_DS_CLASS_T_DEC
  106. inline void
  107. PB_DS_CLASS_C_DEC::
  108. notify_inserted(size_type num_entries)
  109. {
  110.   m_resize_needed = (num_entries >= m_next_grow_size);
  111.   size_base::set_size(num_entries);
  112.   PB_DS_ASSERT_VALID((*this))
  113. }
  114.  
  115. PB_DS_CLASS_T_DEC
  116. inline void
  117. PB_DS_CLASS_C_DEC::
  118. notify_erased(size_type num_entries)
  119. {
  120.   size_base::set_size(num_entries);
  121.   m_resize_needed = num_entries <= m_next_shrink_size;
  122.   PB_DS_ASSERT_VALID((*this))
  123. }
  124.  
  125. PB_DS_CLASS_T_DEC
  126. inline bool
  127. PB_DS_CLASS_C_DEC::
  128. is_resize_needed() const
  129. {
  130.   PB_DS_ASSERT_VALID((*this))
  131.   return m_resize_needed;
  132. }
  133.  
  134. PB_DS_CLASS_T_DEC
  135. inline bool
  136. PB_DS_CLASS_C_DEC::
  137. is_grow_needed(size_type /*size*/, size_type num_entries) const
  138. {
  139.   _GLIBCXX_DEBUG_ASSERT(m_resize_needed);
  140.   return num_entries >= m_next_grow_size;
  141. }
  142.  
  143. PB_DS_CLASS_T_DEC
  144. PB_DS_CLASS_C_DEC::
  145. ~hash_load_check_resize_trigger() { }
  146.  
  147. PB_DS_CLASS_T_DEC
  148. void
  149. PB_DS_CLASS_C_DEC::
  150. notify_resized(size_type new_size)
  151. {
  152.   m_resize_needed = false;
  153.   m_next_grow_size = size_type(m_load_max * new_size - 1);
  154.   m_next_shrink_size = size_type(m_load_min * new_size);
  155.  
  156. #ifdef PB_DS_HT_MAP_RESIZE_TRACE_
  157.   std::cerr << "hlcrt::notify_resized "  << std::endl
  158.             << "1 " << new_size << std::endl
  159.             << "2 " << m_load_min << std::endl
  160.             << "3 " << m_load_max << std::endl
  161.             << "4 " << m_next_shrink_size << std::endl
  162.             << "5 " << m_next_grow_size << std::endl;
  163. #endif
  164.  
  165.   PB_DS_ASSERT_VALID((*this))
  166. }
  167.  
  168. PB_DS_CLASS_T_DEC
  169. void
  170. PB_DS_CLASS_C_DEC::
  171. notify_externally_resized(size_type new_size)
  172. {
  173.   m_resize_needed = false;
  174.   size_type new_grow_size = size_type(m_load_max * new_size - 1);
  175.   size_type new_shrink_size = size_type(m_load_min * new_size);
  176.  
  177. #ifdef PB_DS_HT_MAP_RESIZE_TRACE_
  178.   std::cerr << "hlcrt::notify_externally_resized "  << std::endl
  179.             << "1 " << new_size << std::endl
  180.             << "2 " << m_load_min << std::endl
  181.             << "3 " << m_load_max << std::endl
  182.             << "4 " << m_next_shrink_size << std::endl
  183.             << "5 " << m_next_grow_size << std::endl
  184.             << "6 " << new_shrink_size << std::endl
  185.             << "7 " << new_grow_size << std::endl;
  186. #endif
  187.  
  188.   if (new_grow_size >= m_next_grow_size)
  189.     {
  190.       _GLIBCXX_DEBUG_ASSERT(new_shrink_size >= m_next_shrink_size);
  191.       m_next_grow_size = new_grow_size;
  192.     }
  193.   else
  194.     {
  195.       _GLIBCXX_DEBUG_ASSERT(new_shrink_size <= m_next_shrink_size);
  196.       m_next_shrink_size = new_shrink_size;
  197.     }
  198.  
  199.   PB_DS_ASSERT_VALID((*this))
  200. }
  201.  
  202. PB_DS_CLASS_T_DEC
  203. void
  204. PB_DS_CLASS_C_DEC::
  205. notify_cleared()
  206. {
  207.   PB_DS_ASSERT_VALID((*this))
  208.   size_base::set_size(0);
  209.   m_resize_needed = (0 < m_next_shrink_size);
  210.   PB_DS_ASSERT_VALID((*this))
  211. }
  212.  
  213. PB_DS_CLASS_T_DEC
  214. void
  215. PB_DS_CLASS_C_DEC::
  216. swap(PB_DS_CLASS_C_DEC& other)
  217. {
  218.   PB_DS_ASSERT_VALID((*this))
  219.   PB_DS_ASSERT_VALID(other)
  220.  
  221.   size_base::swap(other);
  222.   std::swap(m_load_min, other.m_load_min);
  223.   std::swap(m_load_max, other.m_load_max);
  224.   std::swap(m_resize_needed, other.m_resize_needed);
  225.   std::swap(m_next_grow_size, other.m_next_grow_size);
  226.   std::swap(m_next_shrink_size, other.m_next_shrink_size);
  227.  
  228.   PB_DS_ASSERT_VALID((*this))
  229.   PB_DS_ASSERT_VALID(other)
  230. }
  231.  
  232. PB_DS_CLASS_T_DEC
  233. inline std::pair<float, float>
  234. PB_DS_CLASS_C_DEC::
  235. get_loads() const
  236. {
  237.   PB_DS_STATIC_ASSERT(access, external_load_access);
  238.   return std::make_pair(m_load_min, m_load_max);
  239. }
  240.  
  241. PB_DS_CLASS_T_DEC
  242. void
  243. PB_DS_CLASS_C_DEC::
  244. set_loads(std::pair<float, float> load_pair)
  245. {
  246.   PB_DS_STATIC_ASSERT(access, external_load_access);
  247.   const float old_load_min = m_load_min;
  248.   const float old_load_max = m_load_max;
  249.   const size_type old_next_shrink_size = m_next_shrink_size;
  250.   const size_type old_next_grow_size = m_next_grow_size;
  251.   const bool old_resize_needed = m_resize_needed;
  252.  
  253.   __try
  254.     {
  255.       m_load_min = load_pair.first;
  256.       m_load_max = load_pair.second;
  257.       do_resize(static_cast<size_type>(size_base::get_size() / ((m_load_min + m_load_max) / 2)));
  258.     }
  259.   __catch(...)
  260.     {
  261.       m_load_min = old_load_min;
  262.       m_load_max = old_load_max;
  263.       m_next_shrink_size = old_next_shrink_size;
  264.       m_next_grow_size = old_next_grow_size;
  265.       m_resize_needed = old_resize_needed;
  266.       __throw_exception_again;
  267.     }
  268. }
  269.  
  270. PB_DS_CLASS_T_DEC
  271. void
  272. PB_DS_CLASS_C_DEC::
  273. do_resize(size_type)
  274. { std::abort(); }
  275.  
  276. #ifdef _GLIBCXX_DEBUG
  277. # define PB_DS_DEBUG_VERIFY(_Cond)                                      \
  278.   _GLIBCXX_DEBUG_VERIFY_AT(_Cond,                                       \
  279.                            _M_message(#_Cond" assertion from %1;:%2;")  \
  280.                            ._M_string(__FILE__)._M_integer(__LINE__)    \
  281.                            ,__file,__line)
  282.  
  283. PB_DS_CLASS_T_DEC
  284. void
  285. PB_DS_CLASS_C_DEC::
  286. assert_valid(const char* __file, int __line) const
  287. {
  288.   PB_DS_DEBUG_VERIFY(m_load_max > m_load_min);
  289.   PB_DS_DEBUG_VERIFY(m_next_grow_size >= m_next_shrink_size);
  290. }
  291. # undef PB_DS_DEBUG_VERIFY
  292. #endif
  293. #undef PB_DS_ASSERT_VALID
  294.