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 41 PB_DS_CLASS_T_DEC 42 PB_DS_CLASS_C_DEC:: 43 cc_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 51 PB_DS_CLASS_T_DEC 52 inline void 53 PB_DS_CLASS_C_DEC:: 54 notify_find_search_start() 55 { } 56 57 PB_DS_CLASS_T_DEC 58 inline void 59 PB_DS_CLASS_C_DEC:: 60 notify_find_search_collision() 61 { } 62 63 PB_DS_CLASS_T_DEC 64 inline void 65 PB_DS_CLASS_C_DEC:: 66 notify_find_search_end() 67 { } 68 69 PB_DS_CLASS_T_DEC 70 inline void 71 PB_DS_CLASS_C_DEC:: 72 notify_insert_search_start() 73 { m_num_col = 0; } 74 75 PB_DS_CLASS_T_DEC 76 inline void 77 PB_DS_CLASS_C_DEC:: 78 notify_insert_search_collision() 79 { ++m_num_col; } 80 81 PB_DS_CLASS_T_DEC 82 inline void 83 PB_DS_CLASS_C_DEC:: 84 notify_insert_search_end() 85 { calc_resize_needed(); } 86 87 PB_DS_CLASS_T_DEC 88 inline void 89 PB_DS_CLASS_C_DEC:: 90 notify_erase_search_start() 91 { } 92 93 PB_DS_CLASS_T_DEC 94 inline void 95 PB_DS_CLASS_C_DEC:: 96 notify_erase_search_collision() 97 { } 98 99 PB_DS_CLASS_T_DEC 100 inline void 101 PB_DS_CLASS_C_DEC:: 102 notify_erase_search_end() 103 { } 104 105 PB_DS_CLASS_T_DEC 106 inline void 107 PB_DS_CLASS_C_DEC:: 108 notify_inserted(size_type) 109 { } 110 111 PB_DS_CLASS_T_DEC 112 inline void 113 PB_DS_CLASS_C_DEC:: 114 notify_erased(size_type) 115 { m_resize_needed = true; } 116 117 PB_DS_CLASS_T_DEC 118 void 119 PB_DS_CLASS_C_DEC:: 120 notify_cleared() 121 { m_resize_needed = false; } 122 123 PB_DS_CLASS_T_DEC 124 inline bool 125 PB_DS_CLASS_C_DEC:: 126 is_resize_needed() const 127 { return m_resize_needed; } 128 129 PB_DS_CLASS_T_DEC 130 inline bool 131 PB_DS_CLASS_C_DEC:: 132 is_grow_needed(size_type /*size*/, size_type /*num_used_e*/) const 133 { return m_num_col >= m_max_col; } 134 135 PB_DS_CLASS_T_DEC 136 void 137 PB_DS_CLASS_C_DEC:: 138 notify_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 152 PB_DS_CLASS_T_DEC 153 void 154 PB_DS_CLASS_C_DEC:: 155 calc_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 168 PB_DS_CLASS_T_DEC 169 void 170 PB_DS_CLASS_C_DEC:: 171 notify_externally_resized(size_type new_size) 172 { notify_resized(new_size); } 173 174 PB_DS_CLASS_T_DEC 175 void 176 PB_DS_CLASS_C_DEC:: 177 swap(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 186 PB_DS_CLASS_T_DEC 187 inline float 188 PB_DS_CLASS_C_DEC:: 189 get_load() const 190 { 191 PB_DS_STATIC_ASSERT(access, external_load_access); 192 return m_load; 193 } 194 195 PB_DS_CLASS_T_DEC 196 inline void 197 PB_DS_CLASS_C_DEC:: 198 calc_resize_needed() 199 { m_resize_needed = m_resize_needed || m_num_col >= m_max_col; } 200 201 PB_DS_CLASS_T_DEC 202 void 203 PB_DS_CLASS_C_DEC:: 204 set_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
