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