libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2007, 2008, 2009 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_standard_resize_policy_imp.hpp 00038 * Contains a resize policy implementation. 00039 */ 00040 00041 PB_DS_CLASS_T_DEC 00042 PB_DS_CLASS_C_DEC:: 00043 hash_standard_resize_policy() 00044 : m_size(Size_Policy::get_nearest_larger_size(1)) 00045 { trigger_policy_base::notify_externally_resized(m_size); } 00046 00047 PB_DS_CLASS_T_DEC 00048 PB_DS_CLASS_C_DEC:: 00049 hash_standard_resize_policy(const Size_Policy& r_size_policy) 00050 : Size_Policy(r_size_policy), m_size(Size_Policy::get_nearest_larger_size(1)) 00051 { trigger_policy_base::notify_externally_resized(m_size); } 00052 00053 PB_DS_CLASS_T_DEC 00054 PB_DS_CLASS_C_DEC:: 00055 hash_standard_resize_policy(const Size_Policy& r_size_policy, 00056 const Trigger_Policy& r_trigger_policy) 00057 : Size_Policy(r_size_policy), Trigger_Policy(r_trigger_policy), 00058 m_size(Size_Policy::get_nearest_larger_size(1)) 00059 { trigger_policy_base::notify_externally_resized(m_size); } 00060 00061 PB_DS_CLASS_T_DEC 00062 PB_DS_CLASS_C_DEC:: 00063 ~hash_standard_resize_policy() 00064 { } 00065 00066 PB_DS_CLASS_T_DEC 00067 void 00068 PB_DS_CLASS_C_DEC:: 00069 swap(PB_DS_CLASS_C_DEC& other) 00070 { 00071 trigger_policy_base::swap(other); 00072 size_policy_base::swap(other); 00073 std::swap(m_size, other.m_size); 00074 } 00075 00076 PB_DS_CLASS_T_DEC 00077 inline void 00078 PB_DS_CLASS_C_DEC:: 00079 notify_find_search_start() 00080 { trigger_policy_base::notify_find_search_start(); } 00081 00082 PB_DS_CLASS_T_DEC 00083 inline void 00084 PB_DS_CLASS_C_DEC:: 00085 notify_find_search_collision() 00086 { trigger_policy_base::notify_find_search_collision(); } 00087 00088 PB_DS_CLASS_T_DEC 00089 inline void 00090 PB_DS_CLASS_C_DEC:: 00091 notify_find_search_end() 00092 { trigger_policy_base::notify_find_search_end(); } 00093 00094 PB_DS_CLASS_T_DEC 00095 inline void 00096 PB_DS_CLASS_C_DEC:: 00097 notify_insert_search_start() 00098 { trigger_policy_base::notify_insert_search_start(); } 00099 00100 PB_DS_CLASS_T_DEC 00101 inline void 00102 PB_DS_CLASS_C_DEC:: 00103 notify_insert_search_collision() 00104 { trigger_policy_base::notify_insert_search_collision(); } 00105 00106 PB_DS_CLASS_T_DEC 00107 inline void 00108 PB_DS_CLASS_C_DEC:: 00109 notify_insert_search_end() 00110 { trigger_policy_base::notify_insert_search_end(); } 00111 00112 PB_DS_CLASS_T_DEC 00113 inline void 00114 PB_DS_CLASS_C_DEC:: 00115 notify_erase_search_start() 00116 { trigger_policy_base::notify_erase_search_start(); } 00117 00118 PB_DS_CLASS_T_DEC 00119 inline void 00120 PB_DS_CLASS_C_DEC:: 00121 notify_erase_search_collision() 00122 { trigger_policy_base::notify_erase_search_collision(); } 00123 00124 PB_DS_CLASS_T_DEC 00125 inline void 00126 PB_DS_CLASS_C_DEC:: 00127 notify_erase_search_end() 00128 { trigger_policy_base::notify_erase_search_end(); } 00129 00130 PB_DS_CLASS_T_DEC 00131 inline void 00132 PB_DS_CLASS_C_DEC:: 00133 notify_inserted(size_type num_e) 00134 { trigger_policy_base::notify_inserted(num_e); } 00135 00136 PB_DS_CLASS_T_DEC 00137 inline void 00138 PB_DS_CLASS_C_DEC:: 00139 notify_erased(size_type num_e) 00140 { trigger_policy_base::notify_erased(num_e); } 00141 00142 PB_DS_CLASS_T_DEC 00143 void 00144 PB_DS_CLASS_C_DEC:: 00145 notify_cleared() 00146 { trigger_policy_base::notify_cleared(); } 00147 00148 PB_DS_CLASS_T_DEC 00149 inline bool 00150 PB_DS_CLASS_C_DEC:: 00151 is_resize_needed() const 00152 { return trigger_policy_base::is_resize_needed(); } 00153 00154 PB_DS_CLASS_T_DEC 00155 typename PB_DS_CLASS_C_DEC::size_type 00156 PB_DS_CLASS_C_DEC:: 00157 get_new_size(size_type size, size_type num_used_e) const 00158 { 00159 if (trigger_policy_base::is_grow_needed(size, num_used_e)) 00160 return size_policy_base::get_nearest_larger_size(size); 00161 return size_policy_base::get_nearest_smaller_size(size); 00162 } 00163 00164 PB_DS_CLASS_T_DEC 00165 void 00166 PB_DS_CLASS_C_DEC:: 00167 notify_resized(size_type new_size) 00168 { 00169 trigger_policy_base::notify_resized(new_size); 00170 m_size = new_size; 00171 } 00172 00173 PB_DS_CLASS_T_DEC 00174 inline typename PB_DS_CLASS_C_DEC::size_type 00175 PB_DS_CLASS_C_DEC:: 00176 get_actual_size() const 00177 { 00178 PB_DS_STATIC_ASSERT(access, external_size_access); 00179 return m_size; 00180 } 00181 00182 PB_DS_CLASS_T_DEC 00183 void 00184 PB_DS_CLASS_C_DEC:: 00185 resize(size_type new_size) 00186 { 00187 PB_DS_STATIC_ASSERT(access, external_size_access); 00188 size_type actual_size = size_policy_base::get_nearest_larger_size(1); 00189 while (actual_size < new_size) 00190 { 00191 const size_type pot = size_policy_base::get_nearest_larger_size(actual_size); 00192 00193 if (pot == actual_size && pot < new_size) 00194 __throw_resize_error(); 00195 actual_size = pot; 00196 } 00197 00198 if (actual_size > 0) 00199 --actual_size; 00200 00201 const size_type old_size = m_size; 00202 __try 00203 { 00204 do_resize(actual_size - 1); 00205 } 00206 __catch(insert_error& ) 00207 { 00208 m_size = old_size; 00209 __throw_resize_error(); 00210 } 00211 __catch(...) 00212 { 00213 m_size = old_size; 00214 __throw_exception_again; 00215 } 00216 } 00217 00218 PB_DS_CLASS_T_DEC 00219 void 00220 PB_DS_CLASS_C_DEC:: 00221 do_resize(size_type) 00222 { 00223 // Do nothing 00224 } 00225 00226 PB_DS_CLASS_T_DEC 00227 Trigger_Policy& 00228 PB_DS_CLASS_C_DEC:: 00229 get_trigger_policy() 00230 { return *this; } 00231 00232 PB_DS_CLASS_T_DEC 00233 const Trigger_Policy& 00234 PB_DS_CLASS_C_DEC:: 00235 get_trigger_policy() const 00236 { return *this; } 00237 00238 PB_DS_CLASS_T_DEC 00239 Size_Policy& 00240 PB_DS_CLASS_C_DEC:: 00241 get_size_policy() 00242 { return *this; } 00243 00244 PB_DS_CLASS_T_DEC 00245 const Size_Policy& 00246 PB_DS_CLASS_C_DEC:: 00247 get_size_policy() const 00248 { return *this; } 00249