1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2013 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 ranged_probe_fn.hpp 38 * Contains a unified ranged probe functor, allowing the probe tables to deal with 39 * a single class for ranged probeing. 40 */ 41 42 #ifndef PB_DS_RANGED_PROBE_FN_HPP 43 #define PB_DS_RANGED_PROBE_FN_HPP 44 45 #include <utility> 46 #include <debug/debug.h> 47 48 namespace __gnu_pbds 49 { 50 namespace detail 51 { 52 /// Primary template. 53 template<typename Key, typename Hash_Fn, typename _Alloc, 54 typename Comb_Probe_Fn, typename Probe_Fn, bool Store_Hash> 55 class ranged_probe_fn; 56 57 #define PB_DS_CLASS_T_DEC \ 58 template<typename Key, typename Hash_Fn, typename _Alloc, \ 59 typename Comb_Probe_Fn, typename Probe_Fn> 60 61 #define PB_DS_CLASS_C_DEC \ 62 ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, false> 63 64 /** 65 * Specialization 1 66 * The client supplies a probe function and a ranged probe 67 * function, and requests that hash values not be stored. 68 **/ 69 template<typename Key, typename Hash_Fn, typename _Alloc, 70 typename Comb_Probe_Fn, typename Probe_Fn> 71 class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, 72 Probe_Fn, false> 73 : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn 74 { 75 protected: 76 typedef typename _Alloc::size_type size_type; 77 typedef Comb_Probe_Fn comb_probe_fn_base; 78 typedef Hash_Fn hash_fn_base; 79 typedef Probe_Fn probe_fn_base; 80 typedef typename _Alloc::template rebind<Key>::other key_allocator; 81 typedef typename key_allocator::const_reference key_const_reference; 82 83 ranged_probe_fn(size_type); 84 85 ranged_probe_fn(size_type, const Hash_Fn&); 86 87 ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&); 88 89 ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, 90 const Probe_Fn&); 91 92 void 93 swap(PB_DS_CLASS_C_DEC&); 94 95 void 96 notify_resized(size_type); 97 98 inline size_type 99 operator()(key_const_reference) const; 100 101 inline size_type 102 operator()(key_const_reference, size_type, size_type) const; 103 }; 104 105 PB_DS_CLASS_T_DEC 106 PB_DS_CLASS_C_DEC:: 107 ranged_probe_fn(size_type size) 108 { Comb_Probe_Fn::notify_resized(size); } 109 110 PB_DS_CLASS_T_DEC 111 PB_DS_CLASS_C_DEC:: 112 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) 113 : Hash_Fn(r_hash_fn) 114 { Comb_Probe_Fn::notify_resized(size); } 115 116 PB_DS_CLASS_T_DEC 117 PB_DS_CLASS_C_DEC:: 118 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 119 const Comb_Probe_Fn& r_comb_probe_fn) 120 : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn) 121 { comb_probe_fn_base::notify_resized(size); } 122 123 PB_DS_CLASS_T_DEC 124 PB_DS_CLASS_C_DEC:: 125 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 126 const Comb_Probe_Fn& r_comb_probe_fn, 127 const Probe_Fn& r_probe_fn) 128 : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn) 129 { comb_probe_fn_base::notify_resized(size); } 130 131 PB_DS_CLASS_T_DEC 132 void 133 PB_DS_CLASS_C_DEC:: 134 swap(PB_DS_CLASS_C_DEC& other) 135 { 136 comb_probe_fn_base::swap(other); 137 std::swap((Hash_Fn& )(*this), (Hash_Fn&)other); 138 } 139 140 PB_DS_CLASS_T_DEC 141 void 142 PB_DS_CLASS_C_DEC:: 143 notify_resized(size_type size) 144 { comb_probe_fn_base::notify_resized(size); } 145 146 PB_DS_CLASS_T_DEC 147 inline typename PB_DS_CLASS_C_DEC::size_type 148 PB_DS_CLASS_C_DEC:: 149 operator()(key_const_reference r_key) const 150 { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); } 151 152 PB_DS_CLASS_T_DEC 153 inline typename PB_DS_CLASS_C_DEC::size_type 154 PB_DS_CLASS_C_DEC:: 155 operator()(key_const_reference, size_type hash, size_type i) const 156 { 157 return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); 158 } 159 160 #undef PB_DS_CLASS_T_DEC 161 #undef PB_DS_CLASS_C_DEC 162 163 #define PB_DS_CLASS_T_DEC \ 164 template<typename Key, typename Hash_Fn, typename _Alloc, \ 165 typename Comb_Probe_Fn, typename Probe_Fn> 166 167 #define PB_DS_CLASS_C_DEC \ 168 ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, true> 169 170 /** 171 * Specialization 2- The client supplies a probe function and a ranged 172 * probe function, and requests that hash values not be stored. 173 **/ 174 template<typename Key, typename Hash_Fn, typename _Alloc, 175 typename Comb_Probe_Fn, typename Probe_Fn> 176 class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, 177 Probe_Fn, true> 178 : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn 179 { 180 protected: 181 typedef typename _Alloc::size_type size_type; 182 typedef std::pair<size_type, size_type> comp_hash; 183 typedef Comb_Probe_Fn comb_probe_fn_base; 184 typedef Hash_Fn hash_fn_base; 185 typedef Probe_Fn probe_fn_base; 186 typedef typename _Alloc::template rebind<Key>::other key_allocator; 187 typedef typename key_allocator::const_reference key_const_reference; 188 189 ranged_probe_fn(size_type); 190 191 ranged_probe_fn(size_type, const Hash_Fn&); 192 193 ranged_probe_fn(size_type, const Hash_Fn&, 194 const Comb_Probe_Fn&); 195 196 ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, 197 const Probe_Fn&); 198 199 void 200 swap(PB_DS_CLASS_C_DEC&); 201 202 void 203 notify_resized(size_type); 204 205 inline comp_hash 206 operator()(key_const_reference) const; 207 208 inline size_type 209 operator()(key_const_reference, size_type, size_type) const; 210 211 inline size_type 212 operator()(key_const_reference, size_type) const; 213 }; 214 215 PB_DS_CLASS_T_DEC 216 PB_DS_CLASS_C_DEC:: 217 ranged_probe_fn(size_type size) 218 { Comb_Probe_Fn::notify_resized(size); } 219 220 PB_DS_CLASS_T_DEC 221 PB_DS_CLASS_C_DEC:: 222 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) 223 : Hash_Fn(r_hash_fn) 224 { Comb_Probe_Fn::notify_resized(size); } 225 226 PB_DS_CLASS_T_DEC 227 PB_DS_CLASS_C_DEC:: 228 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 229 const Comb_Probe_Fn& r_comb_probe_fn) 230 : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn) 231 { comb_probe_fn_base::notify_resized(size); } 232 233 PB_DS_CLASS_T_DEC 234 PB_DS_CLASS_C_DEC:: 235 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, 236 const Comb_Probe_Fn& r_comb_probe_fn, 237 const Probe_Fn& r_probe_fn) 238 : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn) 239 { comb_probe_fn_base::notify_resized(size); } 240 241 PB_DS_CLASS_T_DEC 242 void 243 PB_DS_CLASS_C_DEC:: 244 swap(PB_DS_CLASS_C_DEC& other) 245 { 246 comb_probe_fn_base::swap(other); 247 std::swap((Hash_Fn& )(*this), (Hash_Fn& )other); 248 } 249 250 PB_DS_CLASS_T_DEC 251 void 252 PB_DS_CLASS_C_DEC:: 253 notify_resized(size_type size) 254 { comb_probe_fn_base::notify_resized(size); } 255 256 PB_DS_CLASS_T_DEC 257 inline typename PB_DS_CLASS_C_DEC::comp_hash 258 PB_DS_CLASS_C_DEC:: 259 operator()(key_const_reference r_key) const 260 { 261 const size_type hash = hash_fn_base::operator()(r_key); 262 return std::make_pair(comb_probe_fn_base::operator()(hash), hash); 263 } 264 265 PB_DS_CLASS_T_DEC 266 inline typename PB_DS_CLASS_C_DEC::size_type 267 PB_DS_CLASS_C_DEC:: 268 operator()(key_const_reference, size_type hash, size_type i) const 269 { 270 return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); 271 } 272 273 PB_DS_CLASS_T_DEC 274 inline typename PB_DS_CLASS_C_DEC::size_type 275 PB_DS_CLASS_C_DEC:: 276 operator() 277 #ifdef _GLIBCXX_DEBUG 278 (key_const_reference r_key, size_type hash) const 279 #else 280 (key_const_reference /*r_key*/, size_type hash) const 281 #endif 282 { 283 _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key)); 284 return hash; 285 } 286 287 #undef PB_DS_CLASS_T_DEC 288 #undef PB_DS_CLASS_C_DEC 289 290 /** 291 * Specialization 3 and 4 292 * The client does not supply a hash function or probe function, 293 * and requests that hash values not be stored. 294 **/ 295 template<typename Key, typename _Alloc, typename Comb_Probe_Fn> 296 class ranged_probe_fn<Key, null_type, _Alloc, Comb_Probe_Fn, 297 null_type, false> 298 : public Comb_Probe_Fn 299 { 300 protected: 301 typedef typename _Alloc::size_type size_type; 302 typedef Comb_Probe_Fn comb_probe_fn_base; 303 typedef typename _Alloc::template rebind<Key>::other key_allocator; 304 typedef typename key_allocator::const_reference key_const_reference; 305 306 ranged_probe_fn(size_type size) 307 { Comb_Probe_Fn::notify_resized(size); } 308 309 ranged_probe_fn(size_type, const Comb_Probe_Fn& r_comb_probe_fn) 310 : Comb_Probe_Fn(r_comb_probe_fn) 311 { } 312 313 ranged_probe_fn(size_type, const null_type&, 314 const Comb_Probe_Fn& r_comb_probe_fn, 315 const null_type&) 316 : Comb_Probe_Fn(r_comb_probe_fn) 317 { } 318 319 void 320 swap(ranged_probe_fn& other) 321 { comb_probe_fn_base::swap(other); } 322 }; 323 } // namespace detail 324 } // namespace __gnu_pbds 325 326 #endif 327 328
