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 41PB_DS_CLASS_T_DEC 42PB_DS_CLASS_C_DEC:: 43hash_standard_resize_policy() 44: m_size(Size_Policy::get_nearest_larger_size(1)) 45{ trigger_policy_base::notify_externally_resized(m_size); } 46 47PB_DS_CLASS_T_DEC 48PB_DS_CLASS_C_DEC:: 49hash_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 53PB_DS_CLASS_T_DEC 54PB_DS_CLASS_C_DEC:: 55hash_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 61PB_DS_CLASS_T_DEC 62PB_DS_CLASS_C_DEC:: 63~hash_standard_resize_policy() 64{ } 65 66PB_DS_CLASS_T_DEC 67void 68PB_DS_CLASS_C_DEC:: 69swap(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 76PB_DS_CLASS_T_DEC 77inline void 78PB_DS_CLASS_C_DEC:: 79notify_find_search_start() 80{ trigger_policy_base::notify_find_search_start(); } 81 82PB_DS_CLASS_T_DEC 83inline void 84PB_DS_CLASS_C_DEC:: 85notify_find_search_collision() 86{ trigger_policy_base::notify_find_search_collision(); } 87 88PB_DS_CLASS_T_DEC 89inline void 90PB_DS_CLASS_C_DEC:: 91notify_find_search_end() 92{ trigger_policy_base::notify_find_search_end(); } 93 94PB_DS_CLASS_T_DEC 95inline void 96PB_DS_CLASS_C_DEC:: 97notify_insert_search_start() 98{ trigger_policy_base::notify_insert_search_start(); } 99 100PB_DS_CLASS_T_DEC 101inline void 102PB_DS_CLASS_C_DEC:: 103notify_insert_search_collision() 104{ trigger_policy_base::notify_insert_search_collision(); } 105 106PB_DS_CLASS_T_DEC 107inline void 108PB_DS_CLASS_C_DEC:: 109notify_insert_search_end() 110{ trigger_policy_base::notify_insert_search_end(); } 111 112PB_DS_CLASS_T_DEC 113inline void 114PB_DS_CLASS_C_DEC:: 115notify_erase_search_start() 116{ trigger_policy_base::notify_erase_search_start(); } 117 118PB_DS_CLASS_T_DEC 119inline void 120PB_DS_CLASS_C_DEC:: 121notify_erase_search_collision() 122{ trigger_policy_base::notify_erase_search_collision(); } 123 124PB_DS_CLASS_T_DEC 125inline void 126PB_DS_CLASS_C_DEC:: 127notify_erase_search_end() 128{ trigger_policy_base::notify_erase_search_end(); } 129 130PB_DS_CLASS_T_DEC 131inline void 132PB_DS_CLASS_C_DEC:: 133notify_inserted(size_type num_e) 134{ trigger_policy_base::notify_inserted(num_e); } 135 136PB_DS_CLASS_T_DEC 137inline void 138PB_DS_CLASS_C_DEC:: 139notify_erased(size_type num_e) 140{ trigger_policy_base::notify_erased(num_e); } 141 142PB_DS_CLASS_T_DEC 143void 144PB_DS_CLASS_C_DEC:: 145notify_cleared() 146{ trigger_policy_base::notify_cleared(); } 147 148PB_DS_CLASS_T_DEC 149inline bool 150PB_DS_CLASS_C_DEC:: 151is_resize_needed() const 152{ return trigger_policy_base::is_resize_needed(); } 153 154PB_DS_CLASS_T_DEC 155typename PB_DS_CLASS_C_DEC::size_type 156PB_DS_CLASS_C_DEC:: 157get_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 164PB_DS_CLASS_T_DEC 165void 166PB_DS_CLASS_C_DEC:: 167notify_resized(size_type new_size) 168{ 169 trigger_policy_base::notify_resized(new_size); 170 m_size = new_size; 171} 172 173PB_DS_CLASS_T_DEC 174inline typename PB_DS_CLASS_C_DEC::size_type 175PB_DS_CLASS_C_DEC:: 176get_actual_size() const 177{ 178 PB_DS_STATIC_ASSERT(access, external_size_access); 179 return m_size; 180} 181 182PB_DS_CLASS_T_DEC 183void 184PB_DS_CLASS_C_DEC:: 185resize(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 218PB_DS_CLASS_T_DEC 219void 220PB_DS_CLASS_C_DEC:: 221do_resize(size_type) 222{ 223 // Do nothing 224} 225 226PB_DS_CLASS_T_DEC 227Trigger_Policy& 228PB_DS_CLASS_C_DEC:: 229get_trigger_policy() 230{ return *this; } 231 232PB_DS_CLASS_T_DEC 233const Trigger_Policy& 234PB_DS_CLASS_C_DEC:: 235get_trigger_policy() const 236{ return *this; } 237 238PB_DS_CLASS_T_DEC 239Size_Policy& 240PB_DS_CLASS_C_DEC:: 241get_size_policy() 242{ return *this; } 243 244PB_DS_CLASS_T_DEC 245const Size_Policy& 246PB_DS_CLASS_C_DEC:: 247get_size_policy() const 248{ return *this; } 249 250