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