1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file ranged_hash_fn.hpp 44169691Skan * Contains a unified ranged hash functor, allowing the hash tables 45169691Skan * to deal with a single class for ranged hashing. 46169691Skan */ 47169691Skan 48169691Skan#ifndef PB_DS_RANGED_HASH_FN_HPP 49169691Skan#define PB_DS_RANGED_HASH_FN_HPP 50169691Skan 51169691Skan#include <ext/pb_ds/detail/basic_types.hpp> 52169691Skan#include <utility> 53169691Skan#include <debug/debug.h> 54169691Skan 55169691Skannamespace pb_ds 56169691Skan{ 57169691Skan namespace detail 58169691Skan { 59169691Skan template<typename Key, typename Hash_Fn, typename Allocator, 60169691Skan typename Comb_Hash_Fn, bool Store_Hash> 61169691Skan class ranged_hash_fn; 62169691Skan 63169691Skan#define PB_DS_CLASS_T_DEC \ 64169691Skan template<typename Key, typename Hash_Fn, typename Allocator, \ 65169691Skan typename Comb_Hash_Fn> 66169691Skan 67169691Skan#define PB_DS_CLASS_C_DEC \ 68169691Skan ranged_hash_fn<Key, Hash_Fn, Allocator, Comb_Hash_Fn, false> 69169691Skan 70169691Skan /** 71169691Skan * Specialization 1 72169691Skan * The client supplies a hash function and a ranged hash function, 73169691Skan * and requests that hash values not be stored. 74169691Skan **/ 75169691Skan template<typename Key, typename Hash_Fn, typename Allocator, 76169691Skan typename Comb_Hash_Fn> 77169691Skan class ranged_hash_fn< Key, Hash_Fn, Allocator, Comb_Hash_Fn, false> 78169691Skan : public Hash_Fn, public Comb_Hash_Fn 79169691Skan { 80169691Skan protected: 81169691Skan typedef typename Allocator::size_type size_type; 82169691Skan typedef Hash_Fn hash_fn_base; 83169691Skan typedef Comb_Hash_Fn comb_hash_fn_base; 84169691Skan typedef typename Allocator::template rebind< Key>::other key_allocator; 85169691Skan typedef typename key_allocator::const_reference const_key_reference; 86169691Skan 87169691Skan ranged_hash_fn(size_type); 88169691Skan 89169691Skan ranged_hash_fn(size_type, const Hash_Fn&); 90169691Skan 91169691Skan ranged_hash_fn(size_type, const Hash_Fn&, const Comb_Hash_Fn&); 92169691Skan 93169691Skan void 94169691Skan swap(PB_DS_CLASS_C_DEC&); 95169691Skan 96169691Skan void 97169691Skan notify_resized(size_type); 98169691Skan 99169691Skan inline size_type 100169691Skan operator()(const_key_reference) const; 101169691Skan }; 102169691Skan 103169691Skan PB_DS_CLASS_T_DEC 104169691Skan PB_DS_CLASS_C_DEC:: 105169691Skan ranged_hash_fn(size_type size) 106169691Skan { Comb_Hash_Fn::notify_resized(size); } 107169691Skan 108169691Skan PB_DS_CLASS_T_DEC 109169691Skan PB_DS_CLASS_C_DEC:: 110169691Skan ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn) 111169691Skan : Hash_Fn(r_hash_fn) 112169691Skan { Comb_Hash_Fn::notify_resized(size); } 113169691Skan 114169691Skan PB_DS_CLASS_T_DEC 115169691Skan PB_DS_CLASS_C_DEC:: 116169691Skan ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn, 117169691Skan const Comb_Hash_Fn& r_comb_hash_fn) 118169691Skan : Hash_Fn(r_hash_fn), Comb_Hash_Fn(r_comb_hash_fn) 119169691Skan { comb_hash_fn_base::notify_resized(size); } 120169691Skan 121169691Skan PB_DS_CLASS_T_DEC 122169691Skan void 123169691Skan PB_DS_CLASS_C_DEC:: 124169691Skan swap(PB_DS_CLASS_C_DEC& other) 125169691Skan { 126169691Skan comb_hash_fn_base::swap(other); 127169691Skan std::swap((Hash_Fn& )(*this), (Hash_Fn& )other); 128169691Skan } 129169691Skan 130169691Skan PB_DS_CLASS_T_DEC 131169691Skan void 132169691Skan PB_DS_CLASS_C_DEC:: 133169691Skan notify_resized(size_type size) 134169691Skan { comb_hash_fn_base::notify_resized(size); } 135169691Skan 136169691Skan PB_DS_CLASS_T_DEC 137169691Skan inline typename PB_DS_CLASS_C_DEC::size_type 138169691Skan PB_DS_CLASS_C_DEC:: 139169691Skan operator()(const_key_reference r_key) const 140169691Skan { return (comb_hash_fn_base::operator()(hash_fn_base::operator()(r_key)));} 141169691Skan 142169691Skan#undef PB_DS_CLASS_T_DEC 143169691Skan#undef PB_DS_CLASS_C_DEC 144169691Skan 145169691Skan#define PB_DS_CLASS_T_DEC \ 146169691Skan template<typename Key, typename Hash_Fn, typename Allocator, \ 147169691Skan typename Comb_Hash_Fn> 148169691Skan 149169691Skan#define PB_DS_CLASS_C_DEC \ 150169691Skan ranged_hash_fn<Key,Hash_Fn, Allocator, Comb_Hash_Fn, true> 151169691Skan 152169691Skan /** 153169691Skan * Specialization 2 154169691Skan * The client supplies a hash function and a ranged hash function, 155169691Skan * and requests that hash values be stored. 156169691Skan **/ 157169691Skan template<typename Key, typename Hash_Fn, typename Allocator, 158169691Skan typename Comb_Hash_Fn> 159169691Skan class ranged_hash_fn<Key, Hash_Fn, Allocator, Comb_Hash_Fn, true> 160169691Skan : public Hash_Fn, public Comb_Hash_Fn 161169691Skan { 162169691Skan protected: 163169691Skan typedef typename Allocator::size_type size_type; 164169691Skan typedef std::pair<size_type, size_type> comp_hash; 165169691Skan typedef Hash_Fn hash_fn_base; 166169691Skan typedef Comb_Hash_Fn comb_hash_fn_base; 167169691Skan typedef typename Allocator::template rebind<Key>::other key_allocator; 168169691Skan typedef typename key_allocator::const_reference const_key_reference; 169169691Skan 170169691Skan ranged_hash_fn(size_type); 171169691Skan 172169691Skan ranged_hash_fn(size_type, const Hash_Fn&); 173169691Skan 174169691Skan ranged_hash_fn(size_type, const Hash_Fn&, const Comb_Hash_Fn&); 175169691Skan 176169691Skan void 177169691Skan swap(PB_DS_CLASS_C_DEC&); 178169691Skan 179169691Skan void 180169691Skan notify_resized(size_type); 181169691Skan 182169691Skan inline comp_hash 183169691Skan operator()(const_key_reference) const; 184169691Skan 185169691Skan inline comp_hash 186169691Skan operator()(const_key_reference, size_type) const; 187169691Skan }; 188169691Skan 189169691Skan PB_DS_CLASS_T_DEC 190169691Skan PB_DS_CLASS_C_DEC:: 191169691Skan ranged_hash_fn(size_type size) 192169691Skan { Comb_Hash_Fn::notify_resized(size); } 193169691Skan 194169691Skan PB_DS_CLASS_T_DEC 195169691Skan PB_DS_CLASS_C_DEC:: 196169691Skan ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn) : 197169691Skan Hash_Fn(r_hash_fn) 198169691Skan { Comb_Hash_Fn::notify_resized(size); } 199169691Skan 200169691Skan PB_DS_CLASS_T_DEC 201169691Skan PB_DS_CLASS_C_DEC:: 202169691Skan ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn, 203169691Skan const Comb_Hash_Fn& r_comb_hash_fn) 204169691Skan : Hash_Fn(r_hash_fn), Comb_Hash_Fn(r_comb_hash_fn) 205169691Skan { comb_hash_fn_base::notify_resized(size); } 206169691Skan 207169691Skan PB_DS_CLASS_T_DEC 208169691Skan void 209169691Skan PB_DS_CLASS_C_DEC:: 210169691Skan swap(PB_DS_CLASS_C_DEC& other) 211169691Skan { 212169691Skan comb_hash_fn_base::swap(other); 213169691Skan std::swap((Hash_Fn& )(*this), (Hash_Fn& )other); 214169691Skan } 215169691Skan 216169691Skan PB_DS_CLASS_T_DEC 217169691Skan void 218169691Skan PB_DS_CLASS_C_DEC:: 219169691Skan notify_resized(size_type size) 220169691Skan { comb_hash_fn_base::notify_resized(size); } 221169691Skan 222169691Skan PB_DS_CLASS_T_DEC 223169691Skan inline typename PB_DS_CLASS_C_DEC::comp_hash 224169691Skan PB_DS_CLASS_C_DEC:: 225169691Skan operator()(const_key_reference r_key) const 226169691Skan { 227169691Skan const size_type hash = hash_fn_base::operator()(r_key); 228169691Skan return std::make_pair(comb_hash_fn_base::operator()(hash), hash); 229169691Skan } 230169691Skan 231169691Skan PB_DS_CLASS_T_DEC 232169691Skan inline typename PB_DS_CLASS_C_DEC::comp_hash 233169691Skan PB_DS_CLASS_C_DEC:: 234169691Skan operator() 235169691Skan#ifdef _GLIBCXX_DEBUG 236169691Skan (const_key_reference r_key, size_type hash) const 237169691Skan#else 238169691Skan (const_key_reference /*r_key*/, size_type hash) const 239169691Skan#endif 240169691Skan { 241169691Skan _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key)); 242169691Skan return std::make_pair(comb_hash_fn_base::operator()(hash), hash); 243169691Skan } 244169691Skan 245169691Skan#undef PB_DS_CLASS_T_DEC 246169691Skan#undef PB_DS_CLASS_C_DEC 247169691Skan 248169691Skan#define PB_DS_CLASS_T_DEC \ 249169691Skan template<typename Key, typename Allocator, typename Comb_Hash_Fn> 250169691Skan 251169691Skan#define PB_DS_CLASS_C_DEC \ 252169691Skan ranged_hash_fn<Key, null_hash_fn, Allocator, Comb_Hash_Fn, false> 253169691Skan 254169691Skan /** 255169691Skan * Specialization 3 256169691Skan * The client does not supply a hash function (by specifying 257169691Skan * null_hash_fn as the Hash_Fn parameter), and requests that hash 258169691Skan * values not be stored. 259169691Skan **/ 260169691Skan template<typename Key, typename Allocator, typename Comb_Hash_Fn> 261169691Skan class ranged_hash_fn<Key, null_hash_fn, Allocator, Comb_Hash_Fn, false> 262169691Skan : public null_hash_fn, public Comb_Hash_Fn 263169691Skan { 264169691Skan protected: 265169691Skan typedef typename Allocator::size_type size_type; 266169691Skan typedef Comb_Hash_Fn comb_hash_fn_base; 267169691Skan 268169691Skan ranged_hash_fn(size_type); 269169691Skan 270169691Skan ranged_hash_fn(size_type, const Comb_Hash_Fn&); 271169691Skan 272169691Skan ranged_hash_fn(size_type, const null_hash_fn&, const Comb_Hash_Fn&); 273169691Skan 274169691Skan void 275169691Skan swap(PB_DS_CLASS_C_DEC&); 276169691Skan }; 277169691Skan 278169691Skan PB_DS_CLASS_T_DEC 279169691Skan PB_DS_CLASS_C_DEC:: 280169691Skan ranged_hash_fn(size_type size) 281169691Skan { Comb_Hash_Fn::notify_resized(size); } 282169691Skan 283169691Skan PB_DS_CLASS_T_DEC 284169691Skan PB_DS_CLASS_C_DEC:: 285169691Skan ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn) : 286169691Skan Comb_Hash_Fn(r_comb_hash_fn) 287169691Skan { } 288169691Skan 289169691Skan PB_DS_CLASS_T_DEC 290169691Skan PB_DS_CLASS_C_DEC:: 291169691Skan ranged_hash_fn(size_type size, const null_hash_fn& r_null_hash_fn, 292169691Skan const Comb_Hash_Fn& r_comb_hash_fn) 293169691Skan : Comb_Hash_Fn(r_comb_hash_fn) 294169691Skan { } 295169691Skan 296169691Skan PB_DS_CLASS_T_DEC 297169691Skan void 298169691Skan PB_DS_CLASS_C_DEC:: 299169691Skan swap(PB_DS_CLASS_C_DEC& other) 300169691Skan { comb_hash_fn_base::swap(other); } 301169691Skan 302169691Skan#undef PB_DS_CLASS_T_DEC 303169691Skan#undef PB_DS_CLASS_C_DEC 304169691Skan 305169691Skan#define PB_DS_CLASS_T_DEC \ 306169691Skan template<typename Key, typename Allocator, typename Comb_Hash_Fn> 307169691Skan 308169691Skan#define PB_DS_CLASS_C_DEC \ 309169691Skan ranged_hash_fn<Key, null_hash_fn, Allocator, Comb_Hash_Fn, true> 310169691Skan 311169691Skan /** 312169691Skan * Specialization 4 313169691Skan * The client does not supply a hash function (by specifying 314169691Skan * null_hash_fn as the Hash_Fn parameter), and requests that hash 315169691Skan * values be stored. 316169691Skan **/ 317169691Skan template<typename Key, typename Allocator, typename Comb_Hash_Fn> 318169691Skan class ranged_hash_fn<Key, null_hash_fn, Allocator, Comb_Hash_Fn, true> 319169691Skan : public null_hash_fn, public Comb_Hash_Fn 320169691Skan { 321169691Skan protected: 322169691Skan typedef typename Allocator::size_type size_type; 323169691Skan typedef Comb_Hash_Fn comb_hash_fn_base; 324169691Skan 325169691Skan ranged_hash_fn(size_type); 326169691Skan 327169691Skan ranged_hash_fn(size_type, const Comb_Hash_Fn&); 328169691Skan 329169691Skan ranged_hash_fn(size_type, const null_hash_fn&, const Comb_Hash_Fn&); 330169691Skan 331169691Skan void 332169691Skan swap(PB_DS_CLASS_C_DEC&); 333169691Skan }; 334169691Skan 335169691Skan PB_DS_CLASS_T_DEC 336169691Skan PB_DS_CLASS_C_DEC:: 337169691Skan ranged_hash_fn(size_type size) 338169691Skan { Comb_Hash_Fn::notify_resized(size); } 339169691Skan 340169691Skan PB_DS_CLASS_T_DEC 341169691Skan PB_DS_CLASS_C_DEC:: 342169691Skan ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn) 343169691Skan : Comb_Hash_Fn(r_comb_hash_fn) 344169691Skan { } 345169691Skan 346169691Skan PB_DS_CLASS_T_DEC 347169691Skan PB_DS_CLASS_C_DEC:: 348169691Skan ranged_hash_fn(size_type size, const null_hash_fn& r_null_hash_fn, 349169691Skan const Comb_Hash_Fn& r_comb_hash_fn) 350169691Skan : Comb_Hash_Fn(r_comb_hash_fn) 351169691Skan { } 352169691Skan 353169691Skan PB_DS_CLASS_T_DEC 354169691Skan void 355169691Skan PB_DS_CLASS_C_DEC:: 356169691Skan swap(PB_DS_CLASS_C_DEC& other) 357169691Skan { comb_hash_fn_base::swap(other); } 358169691Skan 359169691Skan#undef PB_DS_CLASS_T_DEC 360169691Skan#undef PB_DS_CLASS_C_DEC 361169691Skan 362169691Skan } // namespace detail 363169691Skan} // namespace pb_ds 364169691Skan 365169691Skan#endif 366