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