1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License 17 // along with this library; see the file COPYING. If not, write to 18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19 // MA 02111-1307, USA. 20 21 // As a special exception, you may use this file as part of a free 22 // software library without restriction. Specifically, if other files 23 // instantiate templates or use macros or inline functions from this 24 // file, or you compile this file and link it with other files to 25 // produce an executable, this file does not by itself cause the 26 // resulting executable to be covered by the GNU General Public 27 // License. This exception does not however invalidate any other 28 // reasons why the executable file might be covered by the GNU General 29 // Public License. 30 31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33 // Permission to use, copy, modify, sell, and distribute this software 34 // is hereby granted without fee, provided that the above copyright 35 // notice appears in all copies, and that both that copyright notice 36 // and this permission notice appear in supporting documentation. None 37 // of the above authors, nor IBM Haifa Research Laboratories, make any 38 // representation about the suitability of this software for any 39 // purpose. It is provided "as is" without express or implied 40 // warranty. 41 42 /** 43 * @file ranged_hash_fn.hpp 44 * Contains a unified ranged hash functor, allowing the hash tables 45 * to deal with a single class for ranged hashing. 46 */ 47 48 #ifndef PB_DS_RANGED_HASH_FN_HPP 49 #define PB_DS_RANGED_HASH_FN_HPP 50 51 #include <ext/pb_ds/detail/basic_types.hpp> 52 #include <utility> 53 #include <debug/debug.h> 54 55 namespace pb_ds 56 { 57 namespace detail 58 { 59 template<typename Key, typename Hash_Fn, typename Allocator, 60 typename Comb_Hash_Fn, bool Store_Hash> 61 class ranged_hash_fn; 62 63 #define PB_DS_CLASS_T_DEC \ 64 template<typename Key, typename Hash_Fn, typename Allocator, \ 65 typename Comb_Hash_Fn> 66 67 #define PB_DS_CLASS_C_DEC \ 68 ranged_hash_fn<Key, Hash_Fn, Allocator, Comb_Hash_Fn, false> 69 70 /** 71 * Specialization 1 72 * The client supplies a hash function and a ranged hash function, 73 * and requests that hash values not be stored. 74 **/ 75 template<typename Key, typename Hash_Fn, typename Allocator, 76 typename Comb_Hash_Fn> 77 class ranged_hash_fn< Key, Hash_Fn, Allocator, Comb_Hash_Fn, false> 78 : public Hash_Fn, public Comb_Hash_Fn 79 { 80 protected: 81 typedef typename Allocator::size_type size_type; 82 typedef Hash_Fn hash_fn_base; 83 typedef Comb_Hash_Fn comb_hash_fn_base; 84 typedef typename Allocator::template rebind< Key>::other key_allocator; 85 typedef typename key_allocator::const_reference const_key_reference; 86 87 ranged_hash_fn(size_type); 88 89 ranged_hash_fn(size_type, const Hash_Fn&); 90 91 ranged_hash_fn(size_type, const Hash_Fn&, const Comb_Hash_Fn&); 92 93 void 94 swap(PB_DS_CLASS_C_DEC&); 95 96 void 97 notify_resized(size_type); 98 99 inline size_type 100 operator()(const_key_reference) const; 101 }; 102 103 PB_DS_CLASS_T_DEC 104 PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size)105 ranged_hash_fn(size_type size) 106 { Comb_Hash_Fn::notify_resized(size); } 107 108 PB_DS_CLASS_T_DEC 109 PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size,const Hash_Fn & r_hash_fn)110 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn) 111 : Hash_Fn(r_hash_fn) 112 { Comb_Hash_Fn::notify_resized(size); } 113 114 PB_DS_CLASS_T_DEC 115 PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size,const Hash_Fn & r_hash_fn,const Comb_Hash_Fn & r_comb_hash_fn)116 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn, 117 const Comb_Hash_Fn& r_comb_hash_fn) 118 : Hash_Fn(r_hash_fn), Comb_Hash_Fn(r_comb_hash_fn) 119 { comb_hash_fn_base::notify_resized(size); } 120 121 PB_DS_CLASS_T_DEC 122 void 123 PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC & other)124 swap(PB_DS_CLASS_C_DEC& other) 125 { 126 comb_hash_fn_base::swap(other); 127 std::swap((Hash_Fn& )(*this), (Hash_Fn& )other); 128 } 129 130 PB_DS_CLASS_T_DEC 131 void 132 PB_DS_CLASS_C_DEC:: notify_resized(size_type size)133 notify_resized(size_type size) 134 { comb_hash_fn_base::notify_resized(size); } 135 136 PB_DS_CLASS_T_DEC 137 inline typename PB_DS_CLASS_C_DEC::size_type 138 PB_DS_CLASS_C_DEC:: operator ()(const_key_reference r_key) const139 operator()(const_key_reference r_key) const 140 { return (comb_hash_fn_base::operator()(hash_fn_base::operator()(r_key)));} 141 142 #undef PB_DS_CLASS_T_DEC 143 #undef PB_DS_CLASS_C_DEC 144 145 #define PB_DS_CLASS_T_DEC \ 146 template<typename Key, typename Hash_Fn, typename Allocator, \ 147 typename Comb_Hash_Fn> 148 149 #define PB_DS_CLASS_C_DEC \ 150 ranged_hash_fn<Key,Hash_Fn, Allocator, Comb_Hash_Fn, true> 151 152 /** 153 * Specialization 2 154 * The client supplies a hash function and a ranged hash function, 155 * and requests that hash values be stored. 156 **/ 157 template<typename Key, typename Hash_Fn, typename Allocator, 158 typename Comb_Hash_Fn> 159 class ranged_hash_fn<Key, Hash_Fn, Allocator, Comb_Hash_Fn, true> 160 : public Hash_Fn, public Comb_Hash_Fn 161 { 162 protected: 163 typedef typename Allocator::size_type size_type; 164 typedef std::pair<size_type, size_type> comp_hash; 165 typedef Hash_Fn hash_fn_base; 166 typedef Comb_Hash_Fn comb_hash_fn_base; 167 typedef typename Allocator::template rebind<Key>::other key_allocator; 168 typedef typename key_allocator::const_reference const_key_reference; 169 170 ranged_hash_fn(size_type); 171 172 ranged_hash_fn(size_type, const Hash_Fn&); 173 174 ranged_hash_fn(size_type, const Hash_Fn&, const Comb_Hash_Fn&); 175 176 void 177 swap(PB_DS_CLASS_C_DEC&); 178 179 void 180 notify_resized(size_type); 181 182 inline comp_hash 183 operator()(const_key_reference) const; 184 185 inline comp_hash 186 operator()(const_key_reference, size_type) const; 187 }; 188 189 PB_DS_CLASS_T_DEC 190 PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size)191 ranged_hash_fn(size_type size) 192 { Comb_Hash_Fn::notify_resized(size); } 193 194 PB_DS_CLASS_T_DEC 195 PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size,const Hash_Fn & r_hash_fn)196 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn) : 197 Hash_Fn(r_hash_fn) 198 { Comb_Hash_Fn::notify_resized(size); } 199 200 PB_DS_CLASS_T_DEC 201 PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size,const Hash_Fn & r_hash_fn,const Comb_Hash_Fn & r_comb_hash_fn)202 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn, 203 const Comb_Hash_Fn& r_comb_hash_fn) 204 : Hash_Fn(r_hash_fn), Comb_Hash_Fn(r_comb_hash_fn) 205 { comb_hash_fn_base::notify_resized(size); } 206 207 PB_DS_CLASS_T_DEC 208 void 209 PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC & other)210 swap(PB_DS_CLASS_C_DEC& other) 211 { 212 comb_hash_fn_base::swap(other); 213 std::swap((Hash_Fn& )(*this), (Hash_Fn& )other); 214 } 215 216 PB_DS_CLASS_T_DEC 217 void 218 PB_DS_CLASS_C_DEC:: notify_resized(size_type size)219 notify_resized(size_type size) 220 { comb_hash_fn_base::notify_resized(size); } 221 222 PB_DS_CLASS_T_DEC 223 inline typename PB_DS_CLASS_C_DEC::comp_hash 224 PB_DS_CLASS_C_DEC:: operator ()(const_key_reference r_key) const225 operator()(const_key_reference r_key) const 226 { 227 const size_type hash = hash_fn_base::operator()(r_key); 228 return std::make_pair(comb_hash_fn_base::operator()(hash), hash); 229 } 230 231 PB_DS_CLASS_T_DEC 232 inline typename PB_DS_CLASS_C_DEC::comp_hash 233 PB_DS_CLASS_C_DEC:: operator ()(const_key_reference r_key,size_type hash) const234 operator() 235 #ifdef _GLIBCXX_DEBUG 236 (const_key_reference r_key, size_type hash) const 237 #else 238 (const_key_reference /*r_key*/, size_type hash) const 239 #endif 240 { 241 _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key)); 242 return std::make_pair(comb_hash_fn_base::operator()(hash), hash); 243 } 244 245 #undef PB_DS_CLASS_T_DEC 246 #undef PB_DS_CLASS_C_DEC 247 248 #define PB_DS_CLASS_T_DEC \ 249 template<typename Key, typename Allocator, typename Comb_Hash_Fn> 250 251 #define PB_DS_CLASS_C_DEC \ 252 ranged_hash_fn<Key, null_hash_fn, Allocator, Comb_Hash_Fn, false> 253 254 /** 255 * Specialization 3 256 * The client does not supply a hash function (by specifying 257 * null_hash_fn as the Hash_Fn parameter), and requests that hash 258 * values not be stored. 259 **/ 260 template<typename Key, typename Allocator, typename Comb_Hash_Fn> 261 class ranged_hash_fn<Key, null_hash_fn, Allocator, Comb_Hash_Fn, false> 262 : public null_hash_fn, public Comb_Hash_Fn 263 { 264 protected: 265 typedef typename Allocator::size_type size_type; 266 typedef Comb_Hash_Fn comb_hash_fn_base; 267 268 ranged_hash_fn(size_type); 269 270 ranged_hash_fn(size_type, const Comb_Hash_Fn&); 271 272 ranged_hash_fn(size_type, const null_hash_fn&, const Comb_Hash_Fn&); 273 274 void 275 swap(PB_DS_CLASS_C_DEC&); 276 }; 277 278 PB_DS_CLASS_T_DEC 279 PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size)280 ranged_hash_fn(size_type size) 281 { Comb_Hash_Fn::notify_resized(size); } 282 283 PB_DS_CLASS_T_DEC 284 PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size,const Comb_Hash_Fn & r_comb_hash_fn)285 ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn) : 286 Comb_Hash_Fn(r_comb_hash_fn) 287 { } 288 289 PB_DS_CLASS_T_DEC 290 PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size,const null_hash_fn & r_null_hash_fn,const Comb_Hash_Fn & r_comb_hash_fn)291 ranged_hash_fn(size_type size, const null_hash_fn& r_null_hash_fn, 292 const Comb_Hash_Fn& r_comb_hash_fn) 293 : Comb_Hash_Fn(r_comb_hash_fn) 294 { } 295 296 PB_DS_CLASS_T_DEC 297 void 298 PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC & other)299 swap(PB_DS_CLASS_C_DEC& other) 300 { comb_hash_fn_base::swap(other); } 301 302 #undef PB_DS_CLASS_T_DEC 303 #undef PB_DS_CLASS_C_DEC 304 305 #define PB_DS_CLASS_T_DEC \ 306 template<typename Key, typename Allocator, typename Comb_Hash_Fn> 307 308 #define PB_DS_CLASS_C_DEC \ 309 ranged_hash_fn<Key, null_hash_fn, Allocator, Comb_Hash_Fn, true> 310 311 /** 312 * Specialization 4 313 * The client does not supply a hash function (by specifying 314 * null_hash_fn as the Hash_Fn parameter), and requests that hash 315 * values be stored. 316 **/ 317 template<typename Key, typename Allocator, typename Comb_Hash_Fn> 318 class ranged_hash_fn<Key, null_hash_fn, Allocator, Comb_Hash_Fn, true> 319 : public null_hash_fn, public Comb_Hash_Fn 320 { 321 protected: 322 typedef typename Allocator::size_type size_type; 323 typedef Comb_Hash_Fn comb_hash_fn_base; 324 325 ranged_hash_fn(size_type); 326 327 ranged_hash_fn(size_type, const Comb_Hash_Fn&); 328 329 ranged_hash_fn(size_type, const null_hash_fn&, const Comb_Hash_Fn&); 330 331 void 332 swap(PB_DS_CLASS_C_DEC&); 333 }; 334 335 PB_DS_CLASS_T_DEC 336 PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size)337 ranged_hash_fn(size_type size) 338 { Comb_Hash_Fn::notify_resized(size); } 339 340 PB_DS_CLASS_T_DEC 341 PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size,const Comb_Hash_Fn & r_comb_hash_fn)342 ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn) 343 : Comb_Hash_Fn(r_comb_hash_fn) 344 { } 345 346 PB_DS_CLASS_T_DEC 347 PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size,const null_hash_fn & r_null_hash_fn,const Comb_Hash_Fn & r_comb_hash_fn)348 ranged_hash_fn(size_type size, const null_hash_fn& r_null_hash_fn, 349 const Comb_Hash_Fn& r_comb_hash_fn) 350 : Comb_Hash_Fn(r_comb_hash_fn) 351 { } 352 353 PB_DS_CLASS_T_DEC 354 void 355 PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC & other)356 swap(PB_DS_CLASS_C_DEC& other) 357 { comb_hash_fn_base::swap(other); } 358 359 #undef PB_DS_CLASS_T_DEC 360 #undef PB_DS_CLASS_C_DEC 361 362 } // namespace detail 363 } // namespace pb_ds 364 365 #endif 366