1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2007, 2008, 2009 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_standard_resize_policy_imp.hpp 38 * Contains a resize policy implementation. 39 */ 40 41 PB_DS_CLASS_T_DEC 42 PB_DS_CLASS_C_DEC:: 43 hash_standard_resize_policy() 44 : m_size(Size_Policy::get_nearest_larger_size(1)) 45 { trigger_policy_base::notify_externally_resized(m_size); } 46 47 PB_DS_CLASS_T_DEC 48 PB_DS_CLASS_C_DEC:: 49 hash_standard_resize_policy(const Size_Policy& r_size_policy) 50 : Size_Policy(r_size_policy), m_size(Size_Policy::get_nearest_larger_size(1)) 51 { trigger_policy_base::notify_externally_resized(m_size); } 52 53 PB_DS_CLASS_T_DEC 54 PB_DS_CLASS_C_DEC:: 55 hash_standard_resize_policy(const Size_Policy& r_size_policy, 56 const Trigger_Policy& r_trigger_policy) 57 : Size_Policy(r_size_policy), Trigger_Policy(r_trigger_policy), 58 m_size(Size_Policy::get_nearest_larger_size(1)) 59 { trigger_policy_base::notify_externally_resized(m_size); } 60 61 PB_DS_CLASS_T_DEC 62 PB_DS_CLASS_C_DEC:: 63 ~hash_standard_resize_policy() 64 { } 65 66 PB_DS_CLASS_T_DEC 67 void 68 PB_DS_CLASS_C_DEC:: 69 swap(PB_DS_CLASS_C_DEC& other) 70 { 71 trigger_policy_base::swap(other); 72 size_policy_base::swap(other); 73 std::swap(m_size, other.m_size); 74 } 75 76 PB_DS_CLASS_T_DEC 77 inline void 78 PB_DS_CLASS_C_DEC:: 79 notify_find_search_start() 80 { trigger_policy_base::notify_find_search_start(); } 81 82 PB_DS_CLASS_T_DEC 83 inline void 84 PB_DS_CLASS_C_DEC:: 85 notify_find_search_collision() 86 { trigger_policy_base::notify_find_search_collision(); } 87 88 PB_DS_CLASS_T_DEC 89 inline void 90 PB_DS_CLASS_C_DEC:: 91 notify_find_search_end() 92 { trigger_policy_base::notify_find_search_end(); } 93 94 PB_DS_CLASS_T_DEC 95 inline void 96 PB_DS_CLASS_C_DEC:: 97 notify_insert_search_start() 98 { trigger_policy_base::notify_insert_search_start(); } 99 100 PB_DS_CLASS_T_DEC 101 inline void 102 PB_DS_CLASS_C_DEC:: 103 notify_insert_search_collision() 104 { trigger_policy_base::notify_insert_search_collision(); } 105 106 PB_DS_CLASS_T_DEC 107 inline void 108 PB_DS_CLASS_C_DEC:: 109 notify_insert_search_end() 110 { trigger_policy_base::notify_insert_search_end(); } 111 112 PB_DS_CLASS_T_DEC 113 inline void 114 PB_DS_CLASS_C_DEC:: 115 notify_erase_search_start() 116 { trigger_policy_base::notify_erase_search_start(); } 117 118 PB_DS_CLASS_T_DEC 119 inline void 120 PB_DS_CLASS_C_DEC:: 121 notify_erase_search_collision() 122 { trigger_policy_base::notify_erase_search_collision(); } 123 124 PB_DS_CLASS_T_DEC 125 inline void 126 PB_DS_CLASS_C_DEC:: 127 notify_erase_search_end() 128 { trigger_policy_base::notify_erase_search_end(); } 129 130 PB_DS_CLASS_T_DEC 131 inline void 132 PB_DS_CLASS_C_DEC:: 133 notify_inserted(size_type num_e) 134 { trigger_policy_base::notify_inserted(num_e); } 135 136 PB_DS_CLASS_T_DEC 137 inline void 138 PB_DS_CLASS_C_DEC:: 139 notify_erased(size_type num_e) 140 { trigger_policy_base::notify_erased(num_e); } 141 142 PB_DS_CLASS_T_DEC 143 void 144 PB_DS_CLASS_C_DEC:: 145 notify_cleared() 146 { trigger_policy_base::notify_cleared(); } 147 148 PB_DS_CLASS_T_DEC 149 inline bool 150 PB_DS_CLASS_C_DEC:: 151 is_resize_needed() const 152 { return trigger_policy_base::is_resize_needed(); } 153 154 PB_DS_CLASS_T_DEC 155 typename PB_DS_CLASS_C_DEC::size_type 156 PB_DS_CLASS_C_DEC:: 157 get_new_size(size_type size, size_type num_used_e) const 158 { 159 if (trigger_policy_base::is_grow_needed(size, num_used_e)) 160 return size_policy_base::get_nearest_larger_size(size); 161 return size_policy_base::get_nearest_smaller_size(size); 162 } 163 164 PB_DS_CLASS_T_DEC 165 void 166 PB_DS_CLASS_C_DEC:: 167 notify_resized(size_type new_size) 168 { 169 trigger_policy_base::notify_resized(new_size); 170 m_size = new_size; 171 } 172 173 PB_DS_CLASS_T_DEC 174 inline typename PB_DS_CLASS_C_DEC::size_type 175 PB_DS_CLASS_C_DEC:: 176 get_actual_size() const 177 { 178 PB_DS_STATIC_ASSERT(access, external_size_access); 179 return m_size; 180 } 181 182 PB_DS_CLASS_T_DEC 183 void 184 PB_DS_CLASS_C_DEC:: 185 resize(size_type new_size) 186 { 187 PB_DS_STATIC_ASSERT(access, external_size_access); 188 size_type actual_size = size_policy_base::get_nearest_larger_size(1); 189 while (actual_size < new_size) 190 { 191 const size_type pot = size_policy_base::get_nearest_larger_size(actual_size); 192 193 if (pot == actual_size && pot < new_size) 194 __throw_resize_error(); 195 actual_size = pot; 196 } 197 198 if (actual_size > 0) 199 --actual_size; 200 201 const size_type old_size = m_size; 202 __try 203 { 204 do_resize(actual_size - 1); 205 } 206 __catch(insert_error& ) 207 { 208 m_size = old_size; 209 __throw_resize_error(); 210 } 211 __catch(...) 212 { 213 m_size = old_size; 214 __throw_exception_again; 215 } 216 } 217 218 PB_DS_CLASS_T_DEC 219 void 220 PB_DS_CLASS_C_DEC:: 221 do_resize(size_type) 222 { 223 // Do nothing 224 } 225 226 PB_DS_CLASS_T_DEC 227 Trigger_Policy& 228 PB_DS_CLASS_C_DEC:: 229 get_trigger_policy() 230 { return *this; } 231 232 PB_DS_CLASS_T_DEC 233 const Trigger_Policy& 234 PB_DS_CLASS_C_DEC:: 235 get_trigger_policy() const 236 { return *this; } 237 238 PB_DS_CLASS_T_DEC 239 Size_Policy& 240 PB_DS_CLASS_C_DEC:: 241 get_size_policy() 242 { return *this; } 243 244 PB_DS_CLASS_T_DEC 245 const Size_Policy& 246 PB_DS_CLASS_C_DEC:: 247 get_size_policy() const 248 { return *this; } 249 250