1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING. If not, write to 18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19// MA 02111-1307, USA. 20 21// As a special exception, you may use this file as part of a free 22// software library without restriction. Specifically, if other files 23// instantiate templates or use macros or inline functions from this 24// file, or you compile this file and link it with other files to 25// produce an executable, this file does not by itself cause the 26// resulting executable to be covered by the GNU General Public 27// License. This exception does not however invalidate any other 28// reasons why the executable file might be covered by the GNU General 29// Public License. 30 31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33// Permission to use, copy, modify, sell, and distribute this software 34// is hereby granted without fee, provided that the above copyright 35// notice appears in all copies, and that both that copyright notice 36// and this permission notice appear in supporting documentation. None 37// of the above authors, nor IBM Haifa Research Laboratories, make any 38// representation about the suitability of this software for any 39// purpose. It is provided "as is" without express or implied 40// warranty. 41 42/** 43 * @file hash_load_check_resize_trigger_imp.hpp 44 * Contains a resize trigger implementation. 45 */ 46 47#define PB_DS_STATIC_ASSERT(UNIQUE, E) \ 48 typedef detail::static_assert_dumclass<sizeof(detail::static_assert<bool(E)>)> UNIQUE##static_assert_type 49 50PB_DS_CLASS_T_DEC 51PB_DS_CLASS_C_DEC:: 52hash_load_check_resize_trigger(float load_min, float load_max) 53: m_load_min(load_min), m_load_max(load_max), m_next_shrink_size(0), 54 m_next_grow_size(0), m_resize_needed(false) 55{ _GLIBCXX_DEBUG_ONLY(assert_valid();) } 56 57PB_DS_CLASS_T_DEC 58inline void 59PB_DS_CLASS_C_DEC:: 60notify_find_search_start() 61{ _GLIBCXX_DEBUG_ONLY(assert_valid();) } 62 63PB_DS_CLASS_T_DEC 64inline void 65PB_DS_CLASS_C_DEC:: 66notify_find_search_collision() 67{ _GLIBCXX_DEBUG_ONLY(assert_valid();) } 68 69PB_DS_CLASS_T_DEC 70inline void 71PB_DS_CLASS_C_DEC:: 72notify_find_search_end() 73{ _GLIBCXX_DEBUG_ONLY(assert_valid();) } 74 75PB_DS_CLASS_T_DEC 76inline void 77PB_DS_CLASS_C_DEC:: 78notify_insert_search_start() 79{ _GLIBCXX_DEBUG_ONLY(assert_valid();) } 80 81PB_DS_CLASS_T_DEC 82inline void 83PB_DS_CLASS_C_DEC:: 84notify_insert_search_collision() 85{ _GLIBCXX_DEBUG_ONLY(assert_valid();) } 86 87PB_DS_CLASS_T_DEC 88inline void 89PB_DS_CLASS_C_DEC:: 90notify_insert_search_end() 91{ _GLIBCXX_DEBUG_ONLY(assert_valid();) } 92 93PB_DS_CLASS_T_DEC 94inline void 95PB_DS_CLASS_C_DEC:: 96notify_erase_search_start() 97{ _GLIBCXX_DEBUG_ONLY(assert_valid();) } 98 99PB_DS_CLASS_T_DEC 100inline void 101PB_DS_CLASS_C_DEC:: 102notify_erase_search_collision() 103{ _GLIBCXX_DEBUG_ONLY(assert_valid();) } 104 105PB_DS_CLASS_T_DEC 106inline void 107PB_DS_CLASS_C_DEC:: 108notify_erase_search_end() 109{ _GLIBCXX_DEBUG_ONLY(assert_valid();) } 110 111PB_DS_CLASS_T_DEC 112inline void 113PB_DS_CLASS_C_DEC:: 114notify_inserted(size_type num_entries) 115{ 116 m_resize_needed = (num_entries >= m_next_grow_size); 117 size_base::set_size(num_entries); 118 _GLIBCXX_DEBUG_ONLY(assert_valid();) 119} 120 121PB_DS_CLASS_T_DEC 122inline void 123PB_DS_CLASS_C_DEC:: 124notify_erased(size_type num_entries) 125{ 126 size_base::set_size(num_entries); 127 m_resize_needed = num_entries <= m_next_shrink_size; 128 _GLIBCXX_DEBUG_ONLY(assert_valid();) 129} 130 131PB_DS_CLASS_T_DEC 132inline bool 133PB_DS_CLASS_C_DEC:: 134is_resize_needed() const 135{ 136 _GLIBCXX_DEBUG_ONLY(assert_valid();) 137 return m_resize_needed; 138} 139 140PB_DS_CLASS_T_DEC 141inline bool 142PB_DS_CLASS_C_DEC:: 143is_grow_needed(size_type /*size*/, size_type num_entries) const 144{ 145 _GLIBCXX_DEBUG_ASSERT(m_resize_needed); 146 return num_entries >= m_next_grow_size; 147} 148 149PB_DS_CLASS_T_DEC 150PB_DS_CLASS_C_DEC:: 151~hash_load_check_resize_trigger() { } 152 153PB_DS_CLASS_T_DEC 154void 155PB_DS_CLASS_C_DEC:: 156notify_resized(size_type new_size) 157{ 158 m_resize_needed = false; 159 m_next_grow_size = size_type(m_load_max * new_size - 1); 160 m_next_shrink_size = size_type(m_load_min * new_size); 161 162#ifdef PB_DS_HT_MAP_RESIZE_TRACE_ 163 std::cerr << "hlcrt::notify_resized " << 164 static_cast<unsigned long>(new_size) << " " << 165 static_cast<unsigned long>(m_load_min) << " " << 166 static_cast<unsigned long>(m_load_max) << " " << 167 static_cast<unsigned long>(m_next_shrink_size) << " " << 168 static_cast<unsigned long>(m_next_grow_size) << " " << std::endl; 169#endif 170 171 _GLIBCXX_DEBUG_ONLY(assert_valid();) 172} 173 174PB_DS_CLASS_T_DEC 175void 176PB_DS_CLASS_C_DEC:: 177notify_externally_resized(size_type new_size) 178{ 179 m_resize_needed = false; 180 size_type new_grow_size = size_type(m_load_max * new_size - 1); 181 size_type new_shrink_size = size_type(m_load_min * new_size ); 182 if (new_grow_size >= m_next_grow_size) 183 { 184 _GLIBCXX_DEBUG_ASSERT(new_shrink_size > m_next_shrink_size); 185 m_next_grow_size = new_grow_size; 186 _GLIBCXX_DEBUG_ONLY(assert_valid();) 187 188#ifdef PB_DS_HT_MAP_RESIZE_TRACE_ 189 std::cerr << "hlcrt::notify_externally_resized1 " << 190 static_cast<unsigned long>(new_size) << " " << 191 static_cast<unsigned long>(m_load_min) << " " << 192 static_cast<unsigned long>(m_load_max) << " " << 193 static_cast<unsigned long>(m_next_shrink_size) << " " << 194 static_cast<unsigned long>(m_next_grow_size) << " " << std::endl; 195#endif 196 return; 197 } 198 199 _GLIBCXX_DEBUG_ASSERT(new_shrink_size <= m_next_shrink_size); 200 m_next_shrink_size = new_shrink_size; 201 202#ifdef PB_DS_HT_MAP_RESIZE_TRACE_ 203 std::cerr << "hlcrt::notify_externally_resized2 " << 204 static_cast<unsigned long>(new_size) << " " << 205 static_cast<unsigned long>(m_load_min) << " " << 206 static_cast<unsigned long>(m_load_max) << " " << 207 static_cast<unsigned long>(m_next_shrink_size) << " " << 208 static_cast<unsigned long>(m_next_grow_size) << " " << std::endl; 209#endif 210 211 _GLIBCXX_DEBUG_ONLY(assert_valid();) 212} 213 214PB_DS_CLASS_T_DEC 215void 216PB_DS_CLASS_C_DEC:: 217notify_cleared() 218{ 219 _GLIBCXX_DEBUG_ONLY(assert_valid();) 220 size_base::set_size(0); 221 m_resize_needed = (0 < m_next_shrink_size); 222 _GLIBCXX_DEBUG_ONLY(assert_valid();) 223} 224 225PB_DS_CLASS_T_DEC 226void 227PB_DS_CLASS_C_DEC:: 228swap(PB_DS_CLASS_C_DEC& other) 229{ 230 _GLIBCXX_DEBUG_ONLY(assert_valid();) 231 _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 232 233 size_base::swap(other); 234 std::swap(m_load_min, other.m_load_min); 235 std::swap(m_load_max, other.m_load_max); 236 std::swap(m_resize_needed, other.m_resize_needed); 237 std::swap(m_next_grow_size, other.m_next_grow_size); 238 std::swap(m_next_shrink_size, other.m_next_shrink_size); 239 240 _GLIBCXX_DEBUG_ONLY(assert_valid();) 241 _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 242} 243 244PB_DS_CLASS_T_DEC 245inline std::pair<float, float> 246PB_DS_CLASS_C_DEC:: 247get_loads() const 248{ 249 PB_DS_STATIC_ASSERT(access, external_load_access); 250 return std::make_pair(m_load_min, m_load_max); 251} 252 253PB_DS_CLASS_T_DEC 254void 255PB_DS_CLASS_C_DEC:: 256set_loads(std::pair<float, float> load_pair) 257{ 258 PB_DS_STATIC_ASSERT(access, external_load_access); 259 const float old_load_min = m_load_min; 260 const float old_load_max = m_load_max; 261 const size_type old_next_shrink_size = m_next_shrink_size; 262 const size_type old_next_grow_size = m_next_grow_size; 263 const bool old_resize_needed = m_resize_needed; 264 265 try 266 { 267 m_load_min = load_pair.first; 268 m_load_max = load_pair.second; 269 do_resize(static_cast<size_type>(size_base::get_size() / ((m_load_min + m_load_max) / 2))); 270 } 271 catch (...) 272 { 273 m_load_min = old_load_min; 274 m_load_max = old_load_max; 275 m_next_shrink_size = old_next_shrink_size; 276 m_next_grow_size = old_next_grow_size; 277 m_resize_needed = old_resize_needed; 278 __throw_exception_again; 279 } 280} 281 282PB_DS_CLASS_T_DEC 283void 284PB_DS_CLASS_C_DEC:: 285do_resize(size_type) 286{ abort(); } 287 288#ifdef _GLIBCXX_DEBUG 289PB_DS_CLASS_T_DEC 290void 291PB_DS_CLASS_C_DEC:: 292assert_valid() const 293{ 294 _GLIBCXX_DEBUG_ASSERT(m_load_max > m_load_min); 295 _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= m_next_shrink_size); 296} 297#endif 298 299#undef PB_DS_STATIC_ASSERT 300 301