libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 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 ranged_probe_fn.hpp 00038 * Contains a unified ranged probe functor, allowing the probe tables to deal with 00039 * a single class for ranged probeing. 00040 */ 00041 00042 #ifndef PB_DS_RANGED_PROBE_FN_HPP 00043 #define PB_DS_RANGED_PROBE_FN_HPP 00044 00045 #include <utility> 00046 #include <debug/debug.h> 00047 00048 namespace __gnu_pbds 00049 { 00050 namespace detail 00051 { 00052 /// Primary template. 00053 template<typename Key, typename Hash_Fn, typename _Alloc, 00054 typename Comb_Probe_Fn, typename Probe_Fn, bool Store_Hash> 00055 class ranged_probe_fn; 00056 00057 #define PB_DS_CLASS_T_DEC \ 00058 template<typename Key, typename Hash_Fn, typename _Alloc, \ 00059 typename Comb_Probe_Fn, typename Probe_Fn> 00060 00061 #define PB_DS_CLASS_C_DEC \ 00062 ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, false> 00063 00064 /** 00065 * Specialization 1 00066 * The client supplies a probe function and a ranged probe 00067 * function, and requests that hash values not be stored. 00068 **/ 00069 template<typename Key, typename Hash_Fn, typename _Alloc, 00070 typename Comb_Probe_Fn, typename Probe_Fn> 00071 class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, 00072 Probe_Fn, false> 00073 : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn 00074 { 00075 protected: 00076 typedef typename _Alloc::size_type size_type; 00077 typedef Comb_Probe_Fn comb_probe_fn_base; 00078 typedef Hash_Fn hash_fn_base; 00079 typedef Probe_Fn probe_fn_base; 00080 typedef typename _Alloc::template rebind<Key>::other key_allocator; 00081 typedef typename key_allocator::const_reference key_const_reference; 00082 00083 ranged_probe_fn(size_type); 00084 00085 ranged_probe_fn(size_type, const Hash_Fn&); 00086 00087 ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&); 00088 00089 ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, 00090 const Probe_Fn&); 00091 00092 void 00093 swap(PB_DS_CLASS_C_DEC&); 00094 00095 void 00096 notify_resized(size_type); 00097 00098 inline size_type 00099 operator()(key_const_reference) const; 00100 00101 inline size_type 00102 operator()(key_const_reference, size_type, size_type) const; 00103 }; 00104 00105 PB_DS_CLASS_T_DEC 00106 PB_DS_CLASS_C_DEC:: 00107 ranged_probe_fn(size_type size) 00108 { Comb_Probe_Fn::notify_resized(size); } 00109 00110 PB_DS_CLASS_T_DEC 00111 PB_DS_CLASS_C_DEC:: 00112 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) 00113 : Hash_Fn(r_hash_fn) 00114 { Comb_Probe_Fn::notify_resized(size); } 00115 00116 PB_DS_CLASS_T_DEC 00117 PB_DS_CLASS_C_DEC:: 00118 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 00119 const Comb_Probe_Fn& r_comb_probe_fn) 00120 : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn) 00121 { comb_probe_fn_base::notify_resized(size); } 00122 00123 PB_DS_CLASS_T_DEC 00124 PB_DS_CLASS_C_DEC:: 00125 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 00126 const Comb_Probe_Fn& r_comb_probe_fn, 00127 const Probe_Fn& r_probe_fn) 00128 : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn) 00129 { comb_probe_fn_base::notify_resized(size); } 00130 00131 PB_DS_CLASS_T_DEC 00132 void 00133 PB_DS_CLASS_C_DEC:: 00134 swap(PB_DS_CLASS_C_DEC& other) 00135 { 00136 comb_probe_fn_base::swap(other); 00137 std::swap((Hash_Fn& )(*this), (Hash_Fn&)other); 00138 } 00139 00140 PB_DS_CLASS_T_DEC 00141 void 00142 PB_DS_CLASS_C_DEC:: 00143 notify_resized(size_type size) 00144 { comb_probe_fn_base::notify_resized(size); } 00145 00146 PB_DS_CLASS_T_DEC 00147 inline typename PB_DS_CLASS_C_DEC::size_type 00148 PB_DS_CLASS_C_DEC:: 00149 operator()(key_const_reference r_key) const 00150 { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); } 00151 00152 PB_DS_CLASS_T_DEC 00153 inline typename PB_DS_CLASS_C_DEC::size_type 00154 PB_DS_CLASS_C_DEC:: 00155 operator()(key_const_reference, size_type hash, size_type i) const 00156 { 00157 return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); 00158 } 00159 00160 #undef PB_DS_CLASS_T_DEC 00161 #undef PB_DS_CLASS_C_DEC 00162 00163 #define PB_DS_CLASS_T_DEC \ 00164 template<typename Key, typename Hash_Fn, typename _Alloc, \ 00165 typename Comb_Probe_Fn, typename Probe_Fn> 00166 00167 #define PB_DS_CLASS_C_DEC \ 00168 ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, true> 00169 00170 /** 00171 * Specialization 2- The client supplies a probe function and a ranged 00172 * probe function, and requests that hash values not be stored. 00173 **/ 00174 template<typename Key, typename Hash_Fn, typename _Alloc, 00175 typename Comb_Probe_Fn, typename Probe_Fn> 00176 class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, 00177 Probe_Fn, true> 00178 : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn 00179 { 00180 protected: 00181 typedef typename _Alloc::size_type size_type; 00182 typedef std::pair<size_type, size_type> comp_hash; 00183 typedef Comb_Probe_Fn comb_probe_fn_base; 00184 typedef Hash_Fn hash_fn_base; 00185 typedef Probe_Fn probe_fn_base; 00186 typedef typename _Alloc::template rebind<Key>::other key_allocator; 00187 typedef typename key_allocator::const_reference key_const_reference; 00188 00189 ranged_probe_fn(size_type); 00190 00191 ranged_probe_fn(size_type, const Hash_Fn&); 00192 00193 ranged_probe_fn(size_type, const Hash_Fn&, 00194 const Comb_Probe_Fn&); 00195 00196 ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, 00197 const Probe_Fn&); 00198 00199 void 00200 swap(PB_DS_CLASS_C_DEC&); 00201 00202 void 00203 notify_resized(size_type); 00204 00205 inline comp_hash 00206 operator()(key_const_reference) const; 00207 00208 inline size_type 00209 operator()(key_const_reference, size_type, size_type) const; 00210 00211 inline size_type 00212 operator()(key_const_reference, size_type) const; 00213 }; 00214 00215 PB_DS_CLASS_T_DEC 00216 PB_DS_CLASS_C_DEC:: 00217 ranged_probe_fn(size_type size) 00218 { Comb_Probe_Fn::notify_resized(size); } 00219 00220 PB_DS_CLASS_T_DEC 00221 PB_DS_CLASS_C_DEC:: 00222 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) 00223 : Hash_Fn(r_hash_fn) 00224 { Comb_Probe_Fn::notify_resized(size); } 00225 00226 PB_DS_CLASS_T_DEC 00227 PB_DS_CLASS_C_DEC:: 00228 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 00229 const Comb_Probe_Fn& r_comb_probe_fn) 00230 : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn) 00231 { comb_probe_fn_base::notify_resized(size); } 00232 00233 PB_DS_CLASS_T_DEC 00234 PB_DS_CLASS_C_DEC:: 00235 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 00236 const Comb_Probe_Fn& r_comb_probe_fn, 00237 const Probe_Fn& r_probe_fn) 00238 : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn) 00239 { comb_probe_fn_base::notify_resized(size); } 00240 00241 PB_DS_CLASS_T_DEC 00242 void 00243 PB_DS_CLASS_C_DEC:: 00244 swap(PB_DS_CLASS_C_DEC& other) 00245 { 00246 comb_probe_fn_base::swap(other); 00247 std::swap((Hash_Fn& )(*this), (Hash_Fn& )other); 00248 } 00249 00250 PB_DS_CLASS_T_DEC 00251 void 00252 PB_DS_CLASS_C_DEC:: 00253 notify_resized(size_type size) 00254 { comb_probe_fn_base::notify_resized(size); } 00255 00256 PB_DS_CLASS_T_DEC 00257 inline typename PB_DS_CLASS_C_DEC::comp_hash 00258 PB_DS_CLASS_C_DEC:: 00259 operator()(key_const_reference r_key) const 00260 { 00261 const size_type hash = hash_fn_base::operator()(r_key); 00262 return std::make_pair(comb_probe_fn_base::operator()(hash), hash); 00263 } 00264 00265 PB_DS_CLASS_T_DEC 00266 inline typename PB_DS_CLASS_C_DEC::size_type 00267 PB_DS_CLASS_C_DEC:: 00268 operator()(key_const_reference, size_type hash, size_type i) const 00269 { 00270 return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); 00271 } 00272 00273 PB_DS_CLASS_T_DEC 00274 inline typename PB_DS_CLASS_C_DEC::size_type 00275 PB_DS_CLASS_C_DEC:: 00276 operator() 00277 #ifdef _GLIBCXX_DEBUG 00278 (key_const_reference r_key, size_type hash) const 00279 #else 00280 (key_const_reference /*r_key*/, size_type hash) const 00281 #endif 00282 { 00283 _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key)); 00284 return hash; 00285 } 00286 00287 #undef PB_DS_CLASS_T_DEC 00288 #undef PB_DS_CLASS_C_DEC 00289 00290 /** 00291 * Specialization 3 and 4 00292 * The client does not supply a hash function or probe function, 00293 * and requests that hash values not be stored. 00294 **/ 00295 template<typename Key, typename _Alloc, typename Comb_Probe_Fn> 00296 class ranged_probe_fn<Key, null_type, _Alloc, Comb_Probe_Fn, 00297 null_type, false> 00298 : public Comb_Probe_Fn 00299 { 00300 protected: 00301 typedef typename _Alloc::size_type size_type; 00302 typedef Comb_Probe_Fn comb_probe_fn_base; 00303 typedef typename _Alloc::template rebind<Key>::other key_allocator; 00304 typedef typename key_allocator::const_reference key_const_reference; 00305 00306 ranged_probe_fn(size_type size) 00307 { Comb_Probe_Fn::notify_resized(size); } 00308 00309 ranged_probe_fn(size_type, const Comb_Probe_Fn& r_comb_probe_fn) 00310 : Comb_Probe_Fn(r_comb_probe_fn) 00311 { } 00312 00313 ranged_probe_fn(size_type, const null_type&, 00314 const Comb_Probe_Fn& r_comb_probe_fn, 00315 const null_type&) 00316 : Comb_Probe_Fn(r_comb_probe_fn) 00317 { } 00318 00319 void 00320 swap(ranged_probe_fn& other) 00321 { comb_probe_fn_base::swap(other); } 00322 }; 00323 } // namespace detail 00324 } // namespace __gnu_pbds 00325 00326 #endif 00327