1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2007, 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 cc_hash_max_collision_check_resize_trigger_imp.hpp 38 * Contains a resize trigger implementation. 39 */ 40 41PB_DS_CLASS_T_DEC 42PB_DS_CLASS_C_DEC:: 43cc_hash_max_collision_check_resize_trigger(float load) : 44 m_load(load), 45 m_size(0), 46 m_num_col(0), 47 m_max_col(0), 48 m_resize_needed(false) 49{ } 50 51PB_DS_CLASS_T_DEC 52inline void 53PB_DS_CLASS_C_DEC:: 54notify_find_search_start() 55{ } 56 57PB_DS_CLASS_T_DEC 58inline void 59PB_DS_CLASS_C_DEC:: 60notify_find_search_collision() 61{ } 62 63PB_DS_CLASS_T_DEC 64inline void 65PB_DS_CLASS_C_DEC:: 66notify_find_search_end() 67{ } 68 69PB_DS_CLASS_T_DEC 70inline void 71PB_DS_CLASS_C_DEC:: 72notify_insert_search_start() 73{ m_num_col = 0; } 74 75PB_DS_CLASS_T_DEC 76inline void 77PB_DS_CLASS_C_DEC:: 78notify_insert_search_collision() 79{ ++m_num_col; } 80 81PB_DS_CLASS_T_DEC 82inline void 83PB_DS_CLASS_C_DEC:: 84notify_insert_search_end() 85{ calc_resize_needed(); } 86 87PB_DS_CLASS_T_DEC 88inline void 89PB_DS_CLASS_C_DEC:: 90notify_erase_search_start() 91{ } 92 93PB_DS_CLASS_T_DEC 94inline void 95PB_DS_CLASS_C_DEC:: 96notify_erase_search_collision() 97{ } 98 99PB_DS_CLASS_T_DEC 100inline void 101PB_DS_CLASS_C_DEC:: 102notify_erase_search_end() 103{ } 104 105PB_DS_CLASS_T_DEC 106inline void 107PB_DS_CLASS_C_DEC:: 108notify_inserted(size_type) 109{ } 110 111PB_DS_CLASS_T_DEC 112inline void 113PB_DS_CLASS_C_DEC:: 114notify_erased(size_type) 115{ m_resize_needed = true; } 116 117PB_DS_CLASS_T_DEC 118void 119PB_DS_CLASS_C_DEC:: 120notify_cleared() 121{ m_resize_needed = false; } 122 123PB_DS_CLASS_T_DEC 124inline bool 125PB_DS_CLASS_C_DEC:: 126is_resize_needed() const 127{ return m_resize_needed; } 128 129PB_DS_CLASS_T_DEC 130inline bool 131PB_DS_CLASS_C_DEC:: 132is_grow_needed(size_type /*size*/, size_type /*num_used_e*/) const 133{ return m_num_col >= m_max_col; } 134 135PB_DS_CLASS_T_DEC 136void 137PB_DS_CLASS_C_DEC:: 138notify_resized(size_type new_size) 139{ 140 m_size = new_size; 141 142#ifdef PB_DS_HT_MAP_RESIZE_TRACE_ 143 std::cerr << "chmccrt::notify_resized " 144 << static_cast<unsigned long>(new_size) << std::endl; 145#endif 146 147 calc_max_num_coll(); 148 calc_resize_needed(); 149 m_num_col = 0; 150} 151 152PB_DS_CLASS_T_DEC 153void 154PB_DS_CLASS_C_DEC:: 155calc_max_num_coll() 156{ 157 // max_col <-- \sqrt{2 load \ln( 2 m \ln( m ) ) } 158 const double ln_arg = 2 * m_size * std::log(double(m_size)); 159 m_max_col = size_type(std::ceil(std::sqrt(2 * m_load * std::log(ln_arg)))); 160 161#ifdef PB_DS_HT_MAP_RESIZE_TRACE_ 162 std::cerr << "chmccrt::calc_max_num_coll " 163 << static_cast<unsigned long>(m_size) << " " 164 << static_cast<unsigned long>(m_max_col) << std::endl; 165#endif 166} 167 168PB_DS_CLASS_T_DEC 169void 170PB_DS_CLASS_C_DEC:: 171notify_externally_resized(size_type new_size) 172{ notify_resized(new_size); } 173 174PB_DS_CLASS_T_DEC 175void 176PB_DS_CLASS_C_DEC:: 177swap(PB_DS_CLASS_C_DEC& other) 178{ 179 std::swap(m_load, other.m_load); 180 std::swap(m_size, other.m_size); 181 std::swap(m_num_col, other.m_num_col); 182 std::swap(m_max_col, other.m_max_col); 183 std::swap(m_resize_needed, other.m_resize_needed); 184} 185 186PB_DS_CLASS_T_DEC 187inline float 188PB_DS_CLASS_C_DEC:: 189get_load() const 190{ 191 PB_DS_STATIC_ASSERT(access, external_load_access); 192 return m_load; 193} 194 195PB_DS_CLASS_T_DEC 196inline void 197PB_DS_CLASS_C_DEC:: 198calc_resize_needed() 199{ m_resize_needed = m_resize_needed || m_num_col >= m_max_col; } 200 201PB_DS_CLASS_T_DEC 202void 203PB_DS_CLASS_C_DEC:: 204set_load(float load) 205{ 206 PB_DS_STATIC_ASSERT(access, external_load_access); 207 m_load = load; 208 calc_max_num_coll(); 209 calc_resize_needed(); 210} 211 212