libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2007, 2009 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file cc_hash_max_collision_check_resize_trigger_imp.hpp 00038 * Contains a resize trigger implementation. 00039 */ 00040 00041 PB_DS_CLASS_T_DEC 00042 PB_DS_CLASS_C_DEC:: 00043 cc_hash_max_collision_check_resize_trigger(float load) : 00044 m_load(load), 00045 m_size(0), 00046 m_num_col(0), 00047 m_max_col(0), 00048 m_resize_needed(false) 00049 { } 00050 00051 PB_DS_CLASS_T_DEC 00052 inline void 00053 PB_DS_CLASS_C_DEC:: 00054 notify_find_search_start() 00055 { } 00056 00057 PB_DS_CLASS_T_DEC 00058 inline void 00059 PB_DS_CLASS_C_DEC:: 00060 notify_find_search_collision() 00061 { } 00062 00063 PB_DS_CLASS_T_DEC 00064 inline void 00065 PB_DS_CLASS_C_DEC:: 00066 notify_find_search_end() 00067 { } 00068 00069 PB_DS_CLASS_T_DEC 00070 inline void 00071 PB_DS_CLASS_C_DEC:: 00072 notify_insert_search_start() 00073 { m_num_col = 0; } 00074 00075 PB_DS_CLASS_T_DEC 00076 inline void 00077 PB_DS_CLASS_C_DEC:: 00078 notify_insert_search_collision() 00079 { ++m_num_col; } 00080 00081 PB_DS_CLASS_T_DEC 00082 inline void 00083 PB_DS_CLASS_C_DEC:: 00084 notify_insert_search_end() 00085 { calc_resize_needed(); } 00086 00087 PB_DS_CLASS_T_DEC 00088 inline void 00089 PB_DS_CLASS_C_DEC:: 00090 notify_erase_search_start() 00091 { } 00092 00093 PB_DS_CLASS_T_DEC 00094 inline void 00095 PB_DS_CLASS_C_DEC:: 00096 notify_erase_search_collision() 00097 { } 00098 00099 PB_DS_CLASS_T_DEC 00100 inline void 00101 PB_DS_CLASS_C_DEC:: 00102 notify_erase_search_end() 00103 { } 00104 00105 PB_DS_CLASS_T_DEC 00106 inline void 00107 PB_DS_CLASS_C_DEC:: 00108 notify_inserted(size_type) 00109 { } 00110 00111 PB_DS_CLASS_T_DEC 00112 inline void 00113 PB_DS_CLASS_C_DEC:: 00114 notify_erased(size_type) 00115 { m_resize_needed = true; } 00116 00117 PB_DS_CLASS_T_DEC 00118 void 00119 PB_DS_CLASS_C_DEC:: 00120 notify_cleared() 00121 { m_resize_needed = false; } 00122 00123 PB_DS_CLASS_T_DEC 00124 inline bool 00125 PB_DS_CLASS_C_DEC:: 00126 is_resize_needed() const 00127 { return m_resize_needed; } 00128 00129 PB_DS_CLASS_T_DEC 00130 inline bool 00131 PB_DS_CLASS_C_DEC:: 00132 is_grow_needed(size_type /*size*/, size_type /*num_used_e*/) const 00133 { return m_num_col >= m_max_col; } 00134 00135 PB_DS_CLASS_T_DEC 00136 void 00137 PB_DS_CLASS_C_DEC:: 00138 notify_resized(size_type new_size) 00139 { 00140 m_size = new_size; 00141 00142 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_ 00143 std::cerr << "chmccrt::notify_resized " 00144 << static_cast<unsigned long>(new_size) << std::endl; 00145 #endif 00146 00147 calc_max_num_coll(); 00148 calc_resize_needed(); 00149 m_num_col = 0; 00150 } 00151 00152 PB_DS_CLASS_T_DEC 00153 void 00154 PB_DS_CLASS_C_DEC:: 00155 calc_max_num_coll() 00156 { 00157 // max_col <-- \sqrt{2 load \ln( 2 m \ln( m ) ) } 00158 const double ln_arg = 2 * m_size * std::log(double(m_size)); 00159 m_max_col = size_type(std::ceil(std::sqrt(2 * m_load * std::log(ln_arg)))); 00160 00161 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_ 00162 std::cerr << "chmccrt::calc_max_num_coll " 00163 << static_cast<unsigned long>(m_size) << " " 00164 << static_cast<unsigned long>(m_max_col) << std::endl; 00165 #endif 00166 } 00167 00168 PB_DS_CLASS_T_DEC 00169 void 00170 PB_DS_CLASS_C_DEC:: 00171 notify_externally_resized(size_type new_size) 00172 { notify_resized(new_size); } 00173 00174 PB_DS_CLASS_T_DEC 00175 void 00176 PB_DS_CLASS_C_DEC:: 00177 swap(PB_DS_CLASS_C_DEC& other) 00178 { 00179 std::swap(m_load, other.m_load); 00180 std::swap(m_size, other.m_size); 00181 std::swap(m_num_col, other.m_num_col); 00182 std::swap(m_max_col, other.m_max_col); 00183 std::swap(m_resize_needed, other.m_resize_needed); 00184 } 00185 00186 PB_DS_CLASS_T_DEC 00187 inline float 00188 PB_DS_CLASS_C_DEC:: 00189 get_load() const 00190 { 00191 PB_DS_STATIC_ASSERT(access, external_load_access); 00192 return m_load; 00193 } 00194 00195 PB_DS_CLASS_T_DEC 00196 inline void 00197 PB_DS_CLASS_C_DEC:: 00198 calc_resize_needed() 00199 { m_resize_needed = m_resize_needed || m_num_col >= m_max_col; } 00200 00201 PB_DS_CLASS_T_DEC 00202 void 00203 PB_DS_CLASS_C_DEC:: 00204 set_load(float load) 00205 { 00206 PB_DS_STATIC_ASSERT(access, external_load_access); 00207 m_load = load; 00208 calc_max_num_coll(); 00209 calc_resize_needed(); 00210 } 00211