libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005-2015 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file hash_load_check_resize_trigger_imp.hpp 00038 * Contains a resize trigger implementation. 00039 */ 00040 00041 #define PB_DS_ASSERT_VALID(X) \ 00042 _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);) 00043 00044 PB_DS_CLASS_T_DEC 00045 PB_DS_CLASS_C_DEC:: 00046 hash_load_check_resize_trigger(float load_min, float load_max) 00047 : m_load_min(load_min), m_load_max(load_max), m_next_shrink_size(0), 00048 m_next_grow_size(0), m_resize_needed(false) 00049 { PB_DS_ASSERT_VALID((*this)) } 00050 00051 PB_DS_CLASS_T_DEC 00052 inline void 00053 PB_DS_CLASS_C_DEC:: 00054 notify_find_search_start() 00055 { PB_DS_ASSERT_VALID((*this)) } 00056 00057 PB_DS_CLASS_T_DEC 00058 inline void 00059 PB_DS_CLASS_C_DEC:: 00060 notify_find_search_collision() 00061 { PB_DS_ASSERT_VALID((*this)) } 00062 00063 PB_DS_CLASS_T_DEC 00064 inline void 00065 PB_DS_CLASS_C_DEC:: 00066 notify_find_search_end() 00067 { PB_DS_ASSERT_VALID((*this)) } 00068 00069 PB_DS_CLASS_T_DEC 00070 inline void 00071 PB_DS_CLASS_C_DEC:: 00072 notify_insert_search_start() 00073 { PB_DS_ASSERT_VALID((*this)) } 00074 00075 PB_DS_CLASS_T_DEC 00076 inline void 00077 PB_DS_CLASS_C_DEC:: 00078 notify_insert_search_collision() 00079 { PB_DS_ASSERT_VALID((*this)) } 00080 00081 PB_DS_CLASS_T_DEC 00082 inline void 00083 PB_DS_CLASS_C_DEC:: 00084 notify_insert_search_end() 00085 { PB_DS_ASSERT_VALID((*this)) } 00086 00087 PB_DS_CLASS_T_DEC 00088 inline void 00089 PB_DS_CLASS_C_DEC:: 00090 notify_erase_search_start() 00091 { PB_DS_ASSERT_VALID((*this)) } 00092 00093 PB_DS_CLASS_T_DEC 00094 inline void 00095 PB_DS_CLASS_C_DEC:: 00096 notify_erase_search_collision() 00097 { PB_DS_ASSERT_VALID((*this)) } 00098 00099 PB_DS_CLASS_T_DEC 00100 inline void 00101 PB_DS_CLASS_C_DEC:: 00102 notify_erase_search_end() 00103 { PB_DS_ASSERT_VALID((*this)) } 00104 00105 PB_DS_CLASS_T_DEC 00106 inline void 00107 PB_DS_CLASS_C_DEC:: 00108 notify_inserted(size_type num_entries) 00109 { 00110 m_resize_needed = (num_entries >= m_next_grow_size); 00111 size_base::set_size(num_entries); 00112 PB_DS_ASSERT_VALID((*this)) 00113 } 00114 00115 PB_DS_CLASS_T_DEC 00116 inline void 00117 PB_DS_CLASS_C_DEC:: 00118 notify_erased(size_type num_entries) 00119 { 00120 size_base::set_size(num_entries); 00121 m_resize_needed = num_entries <= m_next_shrink_size; 00122 PB_DS_ASSERT_VALID((*this)) 00123 } 00124 00125 PB_DS_CLASS_T_DEC 00126 inline bool 00127 PB_DS_CLASS_C_DEC:: 00128 is_resize_needed() const 00129 { 00130 PB_DS_ASSERT_VALID((*this)) 00131 return m_resize_needed; 00132 } 00133 00134 PB_DS_CLASS_T_DEC 00135 inline bool 00136 PB_DS_CLASS_C_DEC:: 00137 is_grow_needed(size_type /*size*/, size_type num_entries) const 00138 { 00139 _GLIBCXX_DEBUG_ASSERT(m_resize_needed); 00140 return num_entries >= m_next_grow_size; 00141 } 00142 00143 PB_DS_CLASS_T_DEC 00144 PB_DS_CLASS_C_DEC:: 00145 ~hash_load_check_resize_trigger() { } 00146 00147 PB_DS_CLASS_T_DEC 00148 void 00149 PB_DS_CLASS_C_DEC:: 00150 notify_resized(size_type new_size) 00151 { 00152 m_resize_needed = false; 00153 m_next_grow_size = size_type(m_load_max * new_size - 1); 00154 m_next_shrink_size = size_type(m_load_min * new_size); 00155 00156 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_ 00157 std::cerr << "hlcrt::notify_resized " << std::endl 00158 << "1 " << new_size << std::endl 00159 << "2 " << m_load_min << std::endl 00160 << "3 " << m_load_max << std::endl 00161 << "4 " << m_next_shrink_size << std::endl 00162 << "5 " << m_next_grow_size << std::endl; 00163 #endif 00164 00165 PB_DS_ASSERT_VALID((*this)) 00166 } 00167 00168 PB_DS_CLASS_T_DEC 00169 void 00170 PB_DS_CLASS_C_DEC:: 00171 notify_externally_resized(size_type new_size) 00172 { 00173 m_resize_needed = false; 00174 size_type new_grow_size = size_type(m_load_max * new_size - 1); 00175 size_type new_shrink_size = size_type(m_load_min * new_size); 00176 00177 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_ 00178 std::cerr << "hlcrt::notify_externally_resized " << std::endl 00179 << "1 " << new_size << std::endl 00180 << "2 " << m_load_min << std::endl 00181 << "3 " << m_load_max << std::endl 00182 << "4 " << m_next_shrink_size << std::endl 00183 << "5 " << m_next_grow_size << std::endl 00184 << "6 " << new_shrink_size << std::endl 00185 << "7 " << new_grow_size << std::endl; 00186 #endif 00187 00188 if (new_grow_size >= m_next_grow_size) 00189 { 00190 _GLIBCXX_DEBUG_ASSERT(new_shrink_size >= m_next_shrink_size); 00191 m_next_grow_size = new_grow_size; 00192 } 00193 else 00194 { 00195 _GLIBCXX_DEBUG_ASSERT(new_shrink_size <= m_next_shrink_size); 00196 m_next_shrink_size = new_shrink_size; 00197 } 00198 00199 PB_DS_ASSERT_VALID((*this)) 00200 } 00201 00202 PB_DS_CLASS_T_DEC 00203 void 00204 PB_DS_CLASS_C_DEC:: 00205 notify_cleared() 00206 { 00207 PB_DS_ASSERT_VALID((*this)) 00208 size_base::set_size(0); 00209 m_resize_needed = (0 < m_next_shrink_size); 00210 PB_DS_ASSERT_VALID((*this)) 00211 } 00212 00213 PB_DS_CLASS_T_DEC 00214 void 00215 PB_DS_CLASS_C_DEC:: 00216 swap(PB_DS_CLASS_C_DEC& other) 00217 { 00218 PB_DS_ASSERT_VALID((*this)) 00219 PB_DS_ASSERT_VALID(other) 00220 00221 size_base::swap(other); 00222 std::swap(m_load_min, other.m_load_min); 00223 std::swap(m_load_max, other.m_load_max); 00224 std::swap(m_resize_needed, other.m_resize_needed); 00225 std::swap(m_next_grow_size, other.m_next_grow_size); 00226 std::swap(m_next_shrink_size, other.m_next_shrink_size); 00227 00228 PB_DS_ASSERT_VALID((*this)) 00229 PB_DS_ASSERT_VALID(other) 00230 } 00231 00232 PB_DS_CLASS_T_DEC 00233 inline std::pair<float, float> 00234 PB_DS_CLASS_C_DEC:: 00235 get_loads() const 00236 { 00237 PB_DS_STATIC_ASSERT(access, external_load_access); 00238 return std::make_pair(m_load_min, m_load_max); 00239 } 00240 00241 PB_DS_CLASS_T_DEC 00242 void 00243 PB_DS_CLASS_C_DEC:: 00244 set_loads(std::pair<float, float> load_pair) 00245 { 00246 PB_DS_STATIC_ASSERT(access, external_load_access); 00247 const float old_load_min = m_load_min; 00248 const float old_load_max = m_load_max; 00249 const size_type old_next_shrink_size = m_next_shrink_size; 00250 const size_type old_next_grow_size = m_next_grow_size; 00251 const bool old_resize_needed = m_resize_needed; 00252 00253 __try 00254 { 00255 m_load_min = load_pair.first; 00256 m_load_max = load_pair.second; 00257 do_resize(static_cast<size_type>(size_base::get_size() / ((m_load_min + m_load_max) / 2))); 00258 } 00259 __catch(...) 00260 { 00261 m_load_min = old_load_min; 00262 m_load_max = old_load_max; 00263 m_next_shrink_size = old_next_shrink_size; 00264 m_next_grow_size = old_next_grow_size; 00265 m_resize_needed = old_resize_needed; 00266 __throw_exception_again; 00267 } 00268 } 00269 00270 PB_DS_CLASS_T_DEC 00271 void 00272 PB_DS_CLASS_C_DEC:: 00273 do_resize(size_type) 00274 { std::abort(); } 00275 00276 #ifdef _GLIBCXX_DEBUG 00277 # define PB_DS_DEBUG_VERIFY(_Cond) \ 00278 _GLIBCXX_DEBUG_VERIFY_AT(_Cond, \ 00279 _M_message(#_Cond" assertion from %1;:%2;") \ 00280 ._M_string(__FILE__)._M_integer(__LINE__) \ 00281 ,__file,__line) 00282 00283 PB_DS_CLASS_T_DEC 00284 void 00285 PB_DS_CLASS_C_DEC:: 00286 assert_valid(const char* __file, int __line) const 00287 { 00288 PB_DS_DEBUG_VERIFY(m_load_max > m_load_min); 00289 PB_DS_DEBUG_VERIFY(m_next_grow_size >= m_next_shrink_size); 00290 } 00291 # undef PB_DS_DEBUG_VERIFY 00292 #endif 00293 #undef PB_DS_ASSERT_VALID