3 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
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
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.
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.
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
31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
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
43 * @file ranged_hash_fn.hpp
44 * Contains a unified ranged hash functor, allowing the hash tables to deal with
45 * a single class for ranged hashing.
48 #ifndef PB_DS_RANGED_HASH_FN_HPP
49 #define PB_DS_RANGED_HASH_FN_HPP
51 #include <ext/pb_ds/detail/basic_types.hpp>
59 #ifdef PB_DS_RANGED_HASH_FN_DEBUG
60 #define PB_DS_DBG_ASSERT(X) assert(X)
61 #define PB_DS_DBG_VERIFY(X) assert(X)
62 #define PB_DS_DBG_ONLY(X) X
63 #else // #ifdef PB_DS_RANGED_HASH_FN_DEBUG
64 #define PB_DS_DBG_ASSERT(X)
65 #define PB_DS_DBG_VERIFY(X) {if((X)==0);}
66 #define PB_DS_DBG_ONLY(X) ;
67 #endif // #ifdef PB_DS_RANGED_HASH_FN_DEBUG
69 template<typename Key,
76 #define PB_DS_CLASS_T_DEC \
83 #define PB_DS_CLASS_C_DEC \
92 * Specialization 1- The client supplies a hash function and a ranged
93 * hash function, and requests that hash values not be stored.
95 template<typename Key,
104 false> : public Hash_Fn,
108 typedef typename Allocator::size_type size_type;
110 typedef Hash_Fn hash_fn_base;
112 typedef Comb_Hash_Fn comb_hash_fn_base;
114 typedef typename Allocator::template rebind< Key>::other key_allocator;
116 typedef typename key_allocator::const_reference const_key_reference;
119 ranged_hash_fn(size_type size);
121 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn);
123 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn);
126 swap(PB_DS_CLASS_C_DEC& other);
129 notify_resized(size_type size);
132 operator()(const_key_reference r_key) const;
137 ranged_hash_fn(size_type size)
139 Comb_Hash_Fn::notify_resized(size);
144 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn) :
147 Comb_Hash_Fn::notify_resized(size);
152 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn) :
154 Comb_Hash_Fn(r_comb_hash_fn)
156 comb_hash_fn_base::notify_resized(size);
162 swap(PB_DS_CLASS_C_DEC& other)
164 comb_hash_fn_base::swap(other);
166 std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
172 notify_resized(size_type size)
174 comb_hash_fn_base::notify_resized(size);
178 inline typename PB_DS_CLASS_C_DEC::size_type
180 operator()(const_key_reference r_key) const
182 return (comb_hash_fn_base::operator()(
183 hash_fn_base::operator()(r_key)));
186 #undef PB_DS_CLASS_T_DEC
187 #undef PB_DS_CLASS_C_DEC
189 #define PB_DS_CLASS_T_DEC \
196 #define PB_DS_CLASS_C_DEC \
205 * Specialization 2- The client supplies a hash function and a ranged
206 * hash function, and requests that hash values be stored.
208 template<typename Key,
212 class ranged_hash_fn<
222 typedef typename Allocator::size_type size_type;
224 typedef typename comp_hash_< size_type>::comp_hash comp_hash;
226 typedef Hash_Fn hash_fn_base;
228 typedef Comb_Hash_Fn comb_hash_fn_base;
230 typedef typename Allocator::template rebind< Key>::other key_allocator;
232 typedef typename key_allocator::const_reference const_key_reference;
235 ranged_hash_fn(size_type size);
237 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn);
239 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn);
242 swap(PB_DS_CLASS_C_DEC& other);
245 notify_resized(size_type size);
248 operator()(const_key_reference r_key) const;
251 operator()(const_key_reference r_key, size_type hash) const;
256 ranged_hash_fn(size_type size)
258 Comb_Hash_Fn::notify_resized(size);
263 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn) :
266 Comb_Hash_Fn::notify_resized(size);
271 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn) :
273 Comb_Hash_Fn(r_comb_hash_fn)
275 comb_hash_fn_base::notify_resized(size);
281 swap(PB_DS_CLASS_C_DEC& other)
283 comb_hash_fn_base::swap(other);
285 std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
291 notify_resized(size_type size)
293 comb_hash_fn_base::notify_resized(size);
297 inline typename PB_DS_CLASS_C_DEC::comp_hash
299 operator()(const_key_reference r_key) const
301 const size_type hash = hash_fn_base::operator()(r_key);
303 return (std::make_pair(comb_hash_fn_base::operator()(hash), hash));
307 inline typename PB_DS_CLASS_C_DEC::comp_hash
310 #ifdef PB_DS_RANGED_HASH_FN_DEBUG
311 (const_key_reference r_key, size_type hash) const
312 #else // #ifdef PB_DS_RANGED_HASH_FN_DEBUG
313 (const_key_reference /*r_key*/, size_type hash) const
314 #endif // #ifdef PB_DS_RANGED_HASH_FN_DEBUG
316 PB_DS_DBG_ASSERT(hash == hash_fn_base::operator()(r_key));
318 return (std::make_pair(comb_hash_fn_base::operator()(hash), hash));
321 #undef PB_DS_CLASS_T_DEC
322 #undef PB_DS_CLASS_C_DEC
324 #define PB_DS_CLASS_T_DEC \
325 template<typename Key, class Allocator, class Comb_Hash_Fn>
327 #define PB_DS_CLASS_C_DEC \
336 * Specialization 3- The client does not supply a hash function
337 * (by specifying null_hash_fn as the Hash_Fn parameter),
338 * and requests that hash values not be stored.
341 template<typename Key, class Allocator, class Comb_Hash_Fn>
342 class ranged_hash_fn<
353 typedef typename Allocator::size_type size_type;
355 typedef Comb_Hash_Fn comb_hash_fn_base;
358 ranged_hash_fn(size_type size);
360 ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn);
362 ranged_hash_fn(size_type size, const null_hash_fn & r_null_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn);
365 swap(PB_DS_CLASS_C_DEC& other);
370 ranged_hash_fn(size_type size)
372 Comb_Hash_Fn::notify_resized(size);
377 ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn) :
378 Comb_Hash_Fn(r_comb_hash_fn)
383 ranged_hash_fn(size_type size, const null_hash_fn& r_null_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn) :
384 Comb_Hash_Fn(r_comb_hash_fn)
390 swap(PB_DS_CLASS_C_DEC& other)
392 comb_hash_fn_base::swap(other);
395 #undef PB_DS_CLASS_T_DEC
396 #undef PB_DS_CLASS_C_DEC
398 #define PB_DS_CLASS_T_DEC \
399 template<typename Key, class Allocator, class Comb_Hash_Fn>
401 #define PB_DS_CLASS_C_DEC \
410 * Specialization 4- The client does not supply a hash function
411 * (by specifying null_hash_fn as the Hash_Fn parameter),
412 * and requests that hash values be stored.
415 template<typename Key, class Allocator, class Comb_Hash_Fn>
416 class ranged_hash_fn<
426 typedef typename Allocator::size_type size_type;
428 typedef Comb_Hash_Fn comb_hash_fn_base;
431 ranged_hash_fn(size_type size);
433 ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn);
435 ranged_hash_fn(size_type size, const null_hash_fn & r_null_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn);
438 swap(PB_DS_CLASS_C_DEC& other);
443 ranged_hash_fn(size_type size)
445 Comb_Hash_Fn::notify_resized(size);
450 ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn) :
451 Comb_Hash_Fn(r_comb_hash_fn)
456 ranged_hash_fn(size_type size, const null_hash_fn & r_null_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn) :
457 Comb_Hash_Fn(r_comb_hash_fn)
463 swap(PB_DS_CLASS_C_DEC& other)
465 comb_hash_fn_base::swap(other);
468 #undef PB_DS_CLASS_T_DEC
469 #undef PB_DS_CLASS_C_DEC
471 #undef PB_DS_DBG_ASSERT
472 #undef PB_DS_DBG_VERIFY
473 #undef PB_DS_DBG_ONLY
475 } // namespace detail
478 #endif // #ifndef PB_DS_RANGED_HASH_FN_HPP