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