1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING. If not, write to 18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19// MA 02111-1307, USA. 20 21// As a special exception, you may use this file as part of a free 22// software library without restriction. Specifically, if other files 23// instantiate templates or use macros or inline functions from this 24// file, or you compile this file and link it with other files to 25// produce an executable, this file does not by itself cause the 26// resulting executable to be covered by the GNU General Public 27// License. This exception does not however invalidate any other 28// reasons why the executable file might be covered by the GNU General 29// Public License. 30 31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33// Permission to use, copy, modify, sell, and distribute this software 34// is hereby granted without fee, provided that the above copyright 35// notice appears in all copies, and that both that copyright notice 36// and this permission notice appear in supporting documentation. None 37// of the above authors, nor IBM Haifa Research Laboratories, make any 38// representation about the suitability of this software for any 39// purpose. It is provided "as is" without express or implied 40// warranty. 41 42/** 43 * @file cc_hash_max_collision_check_resize_trigger_imp.hpp 44 * Contains a resize trigger implementation. 45 */ 46 47#define PB_DS_STATIC_ASSERT(UNIQUE, E) \ 48 typedef detail::static_assert_dumclass<sizeof(detail::static_assert<(bool)(E)>)> UNIQUE##static_assert_type 49 50PB_DS_CLASS_T_DEC 51PB_DS_CLASS_C_DEC:: 52cc_hash_max_collision_check_resize_trigger(float load) : 53 m_load(load), 54 m_size(0), 55 m_num_col(0), 56 m_max_col(0), 57 m_resize_needed(false) 58{ } 59 60PB_DS_CLASS_T_DEC 61inline void 62PB_DS_CLASS_C_DEC:: 63notify_find_search_start() 64{ } 65 66PB_DS_CLASS_T_DEC 67inline void 68PB_DS_CLASS_C_DEC:: 69notify_find_search_collision() 70{ } 71 72PB_DS_CLASS_T_DEC 73inline void 74PB_DS_CLASS_C_DEC:: 75notify_find_search_end() 76{ } 77 78PB_DS_CLASS_T_DEC 79inline void 80PB_DS_CLASS_C_DEC:: 81notify_insert_search_start() 82{ m_num_col = 0; } 83 84PB_DS_CLASS_T_DEC 85inline void 86PB_DS_CLASS_C_DEC:: 87notify_insert_search_collision() 88{ ++m_num_col; } 89 90PB_DS_CLASS_T_DEC 91inline void 92PB_DS_CLASS_C_DEC:: 93notify_insert_search_end() 94{ calc_resize_needed(); } 95 96PB_DS_CLASS_T_DEC 97inline void 98PB_DS_CLASS_C_DEC:: 99notify_erase_search_start() 100{ } 101 102PB_DS_CLASS_T_DEC 103inline void 104PB_DS_CLASS_C_DEC:: 105notify_erase_search_collision() 106{ } 107 108PB_DS_CLASS_T_DEC 109inline void 110PB_DS_CLASS_C_DEC:: 111notify_erase_search_end() 112{ } 113 114PB_DS_CLASS_T_DEC 115inline void 116PB_DS_CLASS_C_DEC:: 117notify_inserted(size_type) 118{ } 119 120PB_DS_CLASS_T_DEC 121inline void 122PB_DS_CLASS_C_DEC:: 123notify_erased(size_type) 124{ m_resize_needed = true; } 125 126PB_DS_CLASS_T_DEC 127void 128PB_DS_CLASS_C_DEC:: 129notify_cleared() 130{ m_resize_needed = false; } 131 132PB_DS_CLASS_T_DEC 133inline bool 134PB_DS_CLASS_C_DEC:: 135is_resize_needed() const 136{ return m_resize_needed; } 137 138PB_DS_CLASS_T_DEC 139inline bool 140PB_DS_CLASS_C_DEC:: 141is_grow_needed(size_type /*size*/, size_type /*num_used_e*/) const 142{ return m_num_col >= m_max_col; } 143 144PB_DS_CLASS_T_DEC 145void 146PB_DS_CLASS_C_DEC:: 147notify_resized(size_type new_size) 148{ 149 m_size = new_size; 150 151#ifdef PB_DS_HT_MAP_RESIZE_TRACE_ 152 std::cerr << "chmccrt::notify_resized " 153 << static_cast<unsigned long>(new_size) << std::endl; 154#endif 155 156 calc_max_num_coll(); 157 calc_resize_needed(); 158 m_num_col = 0; 159} 160 161PB_DS_CLASS_T_DEC 162void 163PB_DS_CLASS_C_DEC:: 164calc_max_num_coll() 165{ 166 // max_col <-- \sqrt{2 load \ln( 2 m \ln( m ) ) } 167 const double ln_arg = 2 * m_size * ::log(double(m_size)); 168 m_max_col = size_type(::ceil(::sqrt(2 * m_load * ::log(ln_arg)))); 169 170#ifdef PB_DS_HT_MAP_RESIZE_TRACE_ 171 std::cerr << "chmccrt::calc_max_num_coll " 172 << static_cast<unsigned long>(m_size) << " " 173 << static_cast<unsigned long>(m_max_col) << std::endl; 174#endif 175} 176 177PB_DS_CLASS_T_DEC 178void 179PB_DS_CLASS_C_DEC:: 180notify_externally_resized(size_type new_size) 181{ notify_resized(new_size); } 182 183PB_DS_CLASS_T_DEC 184void 185PB_DS_CLASS_C_DEC:: 186swap(PB_DS_CLASS_C_DEC& other) 187{ 188 std::swap(m_load, other.m_load); 189 std::swap(m_size, other.m_size); 190 std::swap(m_num_col, other.m_num_col); 191 std::swap(m_max_col, other.m_max_col); 192 std::swap(m_resize_needed, other.m_resize_needed); 193} 194 195PB_DS_CLASS_T_DEC 196inline float 197PB_DS_CLASS_C_DEC:: 198get_load() const 199{ 200 PB_DS_STATIC_ASSERT(access, external_load_access); 201 return m_load; 202} 203 204PB_DS_CLASS_T_DEC 205inline void 206PB_DS_CLASS_C_DEC:: 207calc_resize_needed() 208{ m_resize_needed = m_resize_needed || m_num_col >= m_max_col; } 209 210PB_DS_CLASS_T_DEC 211void 212PB_DS_CLASS_C_DEC:: 213set_load(float load) 214{ 215 PB_DS_STATIC_ASSERT(access, external_load_access); 216 m_load = load; 217 calc_max_num_coll(); 218 calc_resize_needed(); 219} 220 221#undef PB_DS_STATIC_ASSERT 222