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 42 #define PB_DS_ASSERT_VALID(X) \ 43 _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);) 44 45 PB_DS_CLASS_T_DEC 46 PB_DS_CLASS_C_DEC:: 47 hash_load_check_resize_trigger(float load_min, float load_max) 48 : m_load_min(load_min), m_load_max(load_max), m_next_shrink_size(0), 49 m_next_grow_size(0), m_resize_needed(false) 50 { PB_DS_ASSERT_VALID((*this)) } 51 52 PB_DS_CLASS_T_DEC 53 inline void 54 PB_DS_CLASS_C_DEC:: 55 notify_find_search_start() 56 { PB_DS_ASSERT_VALID((*this)) } 57 58 PB_DS_CLASS_T_DEC 59 inline void 60 PB_DS_CLASS_C_DEC:: 61 notify_find_search_collision() 62 { PB_DS_ASSERT_VALID((*this)) } 63 64 PB_DS_CLASS_T_DEC 65 inline void 66 PB_DS_CLASS_C_DEC:: 67 notify_find_search_end() 68 { PB_DS_ASSERT_VALID((*this)) } 69 70 PB_DS_CLASS_T_DEC 71 inline void 72 PB_DS_CLASS_C_DEC:: 73 notify_insert_search_start() 74 { PB_DS_ASSERT_VALID((*this)) } 75 76 PB_DS_CLASS_T_DEC 77 inline void 78 PB_DS_CLASS_C_DEC:: 79 notify_insert_search_collision() 80 { PB_DS_ASSERT_VALID((*this)) } 81 82 PB_DS_CLASS_T_DEC 83 inline void 84 PB_DS_CLASS_C_DEC:: 85 notify_insert_search_end() 86 { PB_DS_ASSERT_VALID((*this)) } 87 88 PB_DS_CLASS_T_DEC 89 inline void 90 PB_DS_CLASS_C_DEC:: 91 notify_erase_search_start() 92 { PB_DS_ASSERT_VALID((*this)) } 93 94 PB_DS_CLASS_T_DEC 95 inline void 96 PB_DS_CLASS_C_DEC:: 97 notify_erase_search_collision() 98 { PB_DS_ASSERT_VALID((*this)) } 99 100 PB_DS_CLASS_T_DEC 101 inline void 102 PB_DS_CLASS_C_DEC:: 103 notify_erase_search_end() 104 { PB_DS_ASSERT_VALID((*this)) } 105 106 PB_DS_CLASS_T_DEC 107 inline void 108 PB_DS_CLASS_C_DEC:: 109 notify_inserted(size_type num_entries) 110 { 111 m_resize_needed = (num_entries >= m_next_grow_size); 112 size_base::set_size(num_entries); 113 PB_DS_ASSERT_VALID((*this)) 114 } 115 116 PB_DS_CLASS_T_DEC 117 inline void 118 PB_DS_CLASS_C_DEC:: 119 notify_erased(size_type num_entries) 120 { 121 size_base::set_size(num_entries); 122 m_resize_needed = num_entries <= m_next_shrink_size; 123 PB_DS_ASSERT_VALID((*this)) 124 } 125 126 PB_DS_CLASS_T_DEC 127 inline bool 128 PB_DS_CLASS_C_DEC:: 129 is_resize_needed() const 130 { 131 PB_DS_ASSERT_VALID((*this)) 132 return m_resize_needed; 133 } 134 135 PB_DS_CLASS_T_DEC 136 inline bool 137 PB_DS_CLASS_C_DEC:: 138 is_grow_needed(size_type /*size*/, size_type num_entries) const 139 { 140 _GLIBCXX_DEBUG_ASSERT(m_resize_needed); 141 return num_entries >= m_next_grow_size; 142 } 143 144 PB_DS_CLASS_T_DEC 145 PB_DS_CLASS_C_DEC:: 146 ~hash_load_check_resize_trigger() { } 147 148 PB_DS_CLASS_T_DEC 149 void 150 PB_DS_CLASS_C_DEC:: 151 notify_resized(size_type new_size) 152 { 153 m_resize_needed = false; 154 m_next_grow_size = size_type(m_load_max * new_size - 1); 155 m_next_shrink_size = size_type(m_load_min * new_size); 156 157 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_ 158 std::cerr << "hlcrt::notify_resized " << std::endl 159 << "1 " << new_size << std::endl 160 << "2 " << m_load_min << std::endl 161 << "3 " << m_load_max << std::endl 162 << "4 " << m_next_shrink_size << std::endl 163 << "5 " << m_next_grow_size << std::endl; 164 #endif 165 166 PB_DS_ASSERT_VALID((*this)) 167 } 168 169 PB_DS_CLASS_T_DEC 170 void 171 PB_DS_CLASS_C_DEC:: 172 notify_externally_resized(size_type new_size) 173 { 174 m_resize_needed = false; 175 size_type new_grow_size = size_type(m_load_max * new_size - 1); 176 size_type new_shrink_size = size_type(m_load_min * new_size); 177 178 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_ 179 std::cerr << "hlcrt::notify_externally_resized " << std::endl 180 << "1 " << new_size << std::endl 181 << "2 " << m_load_min << std::endl 182 << "3 " << m_load_max << std::endl 183 << "4 " << m_next_shrink_size << std::endl 184 << "5 " << m_next_grow_size << std::endl 185 << "6 " << new_shrink_size << std::endl 186 << "7 " << new_grow_size << std::endl; 187 #endif 188 189 if (new_grow_size >= m_next_grow_size) 190 { 191 _GLIBCXX_DEBUG_ASSERT(new_shrink_size >= m_next_shrink_size); 192 m_next_grow_size = new_grow_size; 193 } 194 else 195 { 196 _GLIBCXX_DEBUG_ASSERT(new_shrink_size <= m_next_shrink_size); 197 m_next_shrink_size = new_shrink_size; 198 } 199 200 PB_DS_ASSERT_VALID((*this)) 201 } 202 203 PB_DS_CLASS_T_DEC 204 void 205 PB_DS_CLASS_C_DEC:: 206 notify_cleared() 207 { 208 PB_DS_ASSERT_VALID((*this)) 209 size_base::set_size(0); 210 m_resize_needed = (0 < m_next_shrink_size); 211 PB_DS_ASSERT_VALID((*this)) 212 } 213 214 PB_DS_CLASS_T_DEC 215 void 216 PB_DS_CLASS_C_DEC:: 217 swap(PB_DS_CLASS_C_DEC& other) 218 { 219 PB_DS_ASSERT_VALID((*this)) 220 PB_DS_ASSERT_VALID(other) 221 222 size_base::swap(other); 223 std::swap(m_load_min, other.m_load_min); 224 std::swap(m_load_max, other.m_load_max); 225 std::swap(m_resize_needed, other.m_resize_needed); 226 std::swap(m_next_grow_size, other.m_next_grow_size); 227 std::swap(m_next_shrink_size, other.m_next_shrink_size); 228 229 PB_DS_ASSERT_VALID((*this)) 230 PB_DS_ASSERT_VALID(other) 231 } 232 233 PB_DS_CLASS_T_DEC 234 inline std::pair<float, float> 235 PB_DS_CLASS_C_DEC:: 236 get_loads() const 237 { 238 PB_DS_STATIC_ASSERT(access, external_load_access); 239 return std::make_pair(m_load_min, m_load_max); 240 } 241 242 PB_DS_CLASS_T_DEC 243 void 244 PB_DS_CLASS_C_DEC:: 245 set_loads(std::pair<float, float> load_pair) 246 { 247 PB_DS_STATIC_ASSERT(access, external_load_access); 248 const float old_load_min = m_load_min; 249 const float old_load_max = m_load_max; 250 const size_type old_next_shrink_size = m_next_shrink_size; 251 const size_type old_next_grow_size = m_next_grow_size; 252 const bool old_resize_needed = m_resize_needed; 253 254 __try 255 { 256 m_load_min = load_pair.first; 257 m_load_max = load_pair.second; 258 do_resize(static_cast<size_type>(size_base::get_size() / ((m_load_min + m_load_max) / 2))); 259 } 260 __catch(...) 261 { 262 m_load_min = old_load_min; 263 m_load_max = old_load_max; 264 m_next_shrink_size = old_next_shrink_size; 265 m_next_grow_size = old_next_grow_size; 266 m_resize_needed = old_resize_needed; 267 __throw_exception_again; 268 } 269 } 270 271 PB_DS_CLASS_T_DEC 272 void 273 PB_DS_CLASS_C_DEC:: 274 do_resize(size_type) 275 { std::abort(); } 276 277 #ifdef _GLIBCXX_DEBUG 278 # define PB_DS_DEBUG_VERIFY(_Cond) \ 279 _GLIBCXX_DEBUG_VERIFY_AT(_Cond, \ 280 _M_message(#_Cond" assertion from %1;:%2;") \ 281 ._M_string(__FILE__)._M_integer(__LINE__) \ 282 ,__file,__line) 283 284 PB_DS_CLASS_T_DEC 285 void 286 PB_DS_CLASS_C_DEC:: 287 assert_valid(const char* __file, int __line) const 288 { 289 PB_DS_DEBUG_VERIFY(m_load_max > m_load_min); 290 PB_DS_DEBUG_VERIFY(m_next_grow_size >= m_next_shrink_size); 291 } 292 # undef PB_DS_DEBUG_VERIFY 293 #endif 294 #undef PB_DS_ASSERT_VALID 295