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 55namespace 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:: 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:: 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:: 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:: 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:: 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:: 139 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:: 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:: 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:: 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:: 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:: 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:: 225 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:: 234 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:: 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:: 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:: 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:: 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:: 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:: 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:: 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:: 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