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