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 44PB_DS_CLASS_T_DEC 45PB_DS_CLASS_C_DEC:: 46hash_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 51PB_DS_CLASS_T_DEC 52inline void 53PB_DS_CLASS_C_DEC:: 54notify_find_search_start() 55{ PB_DS_ASSERT_VALID((*this)) } 56 57PB_DS_CLASS_T_DEC 58inline void 59PB_DS_CLASS_C_DEC:: 60notify_find_search_collision() 61{ PB_DS_ASSERT_VALID((*this)) } 62 63PB_DS_CLASS_T_DEC 64inline void 65PB_DS_CLASS_C_DEC:: 66notify_find_search_end() 67{ PB_DS_ASSERT_VALID((*this)) } 68 69PB_DS_CLASS_T_DEC 70inline void 71PB_DS_CLASS_C_DEC:: 72notify_insert_search_start() 73{ PB_DS_ASSERT_VALID((*this)) } 74 75PB_DS_CLASS_T_DEC 76inline void 77PB_DS_CLASS_C_DEC:: 78notify_insert_search_collision() 79{ PB_DS_ASSERT_VALID((*this)) } 80 81PB_DS_CLASS_T_DEC 82inline void 83PB_DS_CLASS_C_DEC:: 84notify_insert_search_end() 85{ PB_DS_ASSERT_VALID((*this)) } 86 87PB_DS_CLASS_T_DEC 88inline void 89PB_DS_CLASS_C_DEC:: 90notify_erase_search_start() 91{ PB_DS_ASSERT_VALID((*this)) } 92 93PB_DS_CLASS_T_DEC 94inline void 95PB_DS_CLASS_C_DEC:: 96notify_erase_search_collision() 97{ PB_DS_ASSERT_VALID((*this)) } 98 99PB_DS_CLASS_T_DEC 100inline void 101PB_DS_CLASS_C_DEC:: 102notify_erase_search_end() 103{ PB_DS_ASSERT_VALID((*this)) } 104 105PB_DS_CLASS_T_DEC 106inline void 107PB_DS_CLASS_C_DEC:: 108notify_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 115PB_DS_CLASS_T_DEC 116inline void 117PB_DS_CLASS_C_DEC:: 118notify_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 125PB_DS_CLASS_T_DEC 126inline bool 127PB_DS_CLASS_C_DEC:: 128is_resize_needed() const 129{ 130 PB_DS_ASSERT_VALID((*this)) 131 return m_resize_needed; 132} 133 134PB_DS_CLASS_T_DEC 135inline bool 136PB_DS_CLASS_C_DEC:: 137is_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 143PB_DS_CLASS_T_DEC 144PB_DS_CLASS_C_DEC:: 145~hash_load_check_resize_trigger() { } 146 147PB_DS_CLASS_T_DEC 148void 149PB_DS_CLASS_C_DEC:: 150notify_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 168PB_DS_CLASS_T_DEC 169void 170PB_DS_CLASS_C_DEC:: 171notify_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 202PB_DS_CLASS_T_DEC 203void 204PB_DS_CLASS_C_DEC:: 205notify_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 213PB_DS_CLASS_T_DEC 214void 215PB_DS_CLASS_C_DEC:: 216swap(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 232PB_DS_CLASS_T_DEC 233inline std::pair<float, float> 234PB_DS_CLASS_C_DEC:: 235get_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 241PB_DS_CLASS_T_DEC 242void 243PB_DS_CLASS_C_DEC:: 244set_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 270PB_DS_CLASS_T_DEC 271void 272PB_DS_CLASS_C_DEC:: 273do_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 283PB_DS_CLASS_T_DEC 284void 285PB_DS_CLASS_C_DEC:: 286assert_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