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