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 PB_DS_CLASS_T_DEC 43 PB_DS_CLASS_C_DEC:: 44 hash_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 49 PB_DS_CLASS_T_DEC 50 inline void 51 PB_DS_CLASS_C_DEC:: 52 notify_find_search_start() 53 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 54 55 PB_DS_CLASS_T_DEC 56 inline void 57 PB_DS_CLASS_C_DEC:: 58 notify_find_search_collision() 59 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 60 61 PB_DS_CLASS_T_DEC 62 inline void 63 PB_DS_CLASS_C_DEC:: 64 notify_find_search_end() 65 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 66 67 PB_DS_CLASS_T_DEC 68 inline void 69 PB_DS_CLASS_C_DEC:: 70 notify_insert_search_start() 71 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 72 73 PB_DS_CLASS_T_DEC 74 inline void 75 PB_DS_CLASS_C_DEC:: 76 notify_insert_search_collision() 77 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 78 79 PB_DS_CLASS_T_DEC 80 inline void 81 PB_DS_CLASS_C_DEC:: 82 notify_insert_search_end() 83 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 84 85 PB_DS_CLASS_T_DEC 86 inline void 87 PB_DS_CLASS_C_DEC:: 88 notify_erase_search_start() 89 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 90 91 PB_DS_CLASS_T_DEC 92 inline void 93 PB_DS_CLASS_C_DEC:: 94 notify_erase_search_collision() 95 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 96 97 PB_DS_CLASS_T_DEC 98 inline void 99 PB_DS_CLASS_C_DEC:: 100 notify_erase_search_end() 101 { _GLIBCXX_DEBUG_ONLY(assert_valid();) } 102 103 PB_DS_CLASS_T_DEC 104 inline void 105 PB_DS_CLASS_C_DEC:: 106 notify_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 113 PB_DS_CLASS_T_DEC 114 inline void 115 PB_DS_CLASS_C_DEC:: 116 notify_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 123 PB_DS_CLASS_T_DEC 124 inline bool 125 PB_DS_CLASS_C_DEC:: 126 is_resize_needed() const 127 { 128 _GLIBCXX_DEBUG_ONLY(assert_valid();) 129 return m_resize_needed; 130 } 131 132 PB_DS_CLASS_T_DEC 133 inline bool 134 PB_DS_CLASS_C_DEC:: 135 is_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 141 PB_DS_CLASS_T_DEC 142 PB_DS_CLASS_C_DEC:: 143 ~hash_load_check_resize_trigger() { } 144 145 PB_DS_CLASS_T_DEC 146 void 147 PB_DS_CLASS_C_DEC:: 148 notify_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 166 PB_DS_CLASS_T_DEC 167 void 168 PB_DS_CLASS_C_DEC:: 169 notify_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 200 PB_DS_CLASS_T_DEC 201 void 202 PB_DS_CLASS_C_DEC:: 203 notify_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 211 PB_DS_CLASS_T_DEC 212 void 213 PB_DS_CLASS_C_DEC:: 214 swap(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 230 PB_DS_CLASS_T_DEC 231 inline std::pair<float, float> 232 PB_DS_CLASS_C_DEC:: 233 get_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 239 PB_DS_CLASS_T_DEC 240 void 241 PB_DS_CLASS_C_DEC:: 242 set_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 268 PB_DS_CLASS_T_DEC 269 void 270 PB_DS_CLASS_C_DEC:: 271 do_resize(size_type) 272 { std::abort(); } 273 274 #ifdef _GLIBCXX_DEBUG 275 PB_DS_CLASS_T_DEC 276 void 277 PB_DS_CLASS_C_DEC:: 278 assert_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