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_probe_fn.hpp
44 * Contains a unified ranged probe functor, allowing the probe tables to deal with
45 * a single class for ranged probeing.
48 #ifndef PB_DS_RANGED_PROBE_FN_HPP
49 #define PB_DS_RANGED_PROBE_FN_HPP
51 #include <ext/pb_ds/detail/basic_types.hpp>
59 #ifdef PB_DS_RANGED_PROBE_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_PROBE_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_PROBE_FN_DEBUG
69 template<typename Key,
75 class ranged_probe_fn;
77 #define PB_DS_CLASS_T_DEC \
82 class Comb_Probe_Fn, \
85 #define PB_DS_CLASS_C_DEC \
95 * Specialization 1- The client supplies a probe function and a ranged
96 * probe function, and requests that hash values not be stored.
98 template<typename Key,
103 class ranged_probe_fn<
109 false> : public Hash_Fn,
110 public Comb_Probe_Fn,
114 typedef typename Allocator::size_type size_type;
116 typedef Comb_Probe_Fn comb_probe_fn_base;
118 typedef Hash_Fn hash_fn_base;
120 typedef Probe_Fn probe_fn_base;
122 typedef typename Allocator::template rebind<Key>::other key_allocator;
124 typedef typename key_allocator::const_reference const_key_reference;
127 ranged_probe_fn(size_type size);
129 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn);
131 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn);
133 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn);
136 swap(PB_DS_CLASS_C_DEC& other);
139 notify_resized(size_type size);
142 operator()(const_key_reference r_key) const;
145 operator()(const_key_reference r_key, size_type hash, size_type i) const;
150 ranged_probe_fn(size_type size)
152 Comb_Probe_Fn::notify_resized(size);
157 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) :
160 Comb_Probe_Fn::notify_resized(size);
165 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn) :
167 Comb_Probe_Fn(r_comb_probe_fn)
169 comb_probe_fn_base::notify_resized(size);
174 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn) :
176 Comb_Probe_Fn(r_comb_probe_fn),
179 comb_probe_fn_base::notify_resized(size);
185 swap(PB_DS_CLASS_C_DEC& other)
187 comb_probe_fn_base::swap(other);
189 std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
195 notify_resized(size_type size)
197 comb_probe_fn_base::notify_resized(size);
201 inline typename PB_DS_CLASS_C_DEC::size_type
203 operator()(const_key_reference r_key) const
205 return (comb_probe_fn_base::operator()(
206 hash_fn_base::operator()(r_key)));
210 inline typename PB_DS_CLASS_C_DEC::size_type
212 operator()(const_key_reference /*r_key*/, size_type hash, size_type i) const
214 return (comb_probe_fn_base::operator()(
215 hash + probe_fn_base::operator()(i)));
218 #undef PB_DS_CLASS_T_DEC
219 #undef PB_DS_CLASS_C_DEC
221 #define PB_DS_CLASS_T_DEC \
226 class Comb_Probe_Fn, \
229 #define PB_DS_CLASS_C_DEC \
239 * Specialization 2- The client supplies a probe function and a ranged
240 * probe function, and requests that hash values not be stored.
242 template<typename Key,
247 class ranged_probe_fn<
255 public Comb_Probe_Fn,
259 typedef typename Allocator::size_type size_type;
261 typedef typename comp_hash_<size_type>::comp_hash comp_hash;
263 typedef Comb_Probe_Fn comb_probe_fn_base;
265 typedef Hash_Fn hash_fn_base;
267 typedef Probe_Fn probe_fn_base;
269 typedef typename Allocator::template rebind<Key>::other key_allocator;
271 typedef typename key_allocator::const_reference const_key_reference;
274 ranged_probe_fn(size_type size);
276 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn);
278 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn);
280 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn);
283 swap(PB_DS_CLASS_C_DEC& other);
286 notify_resized(size_type size);
289 operator()(const_key_reference r_key) const;
292 operator()(const_key_reference r_key, size_type hash, size_type i) const;
295 operator()(const_key_reference r_key, size_type hash) const;
300 ranged_probe_fn(size_type size)
302 Comb_Probe_Fn::notify_resized(size);
307 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) :
310 Comb_Probe_Fn::notify_resized(size);
315 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn) :
317 Comb_Probe_Fn(r_comb_probe_fn)
319 comb_probe_fn_base::notify_resized(size);
324 ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn) :
326 Comb_Probe_Fn(r_comb_probe_fn),
329 comb_probe_fn_base::notify_resized(size);
335 swap(PB_DS_CLASS_C_DEC& other)
337 comb_probe_fn_base::swap(other);
339 std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
345 notify_resized(size_type size)
347 comb_probe_fn_base::notify_resized(size);
351 inline typename PB_DS_CLASS_C_DEC::comp_hash
353 operator()(const_key_reference r_key) const
355 const size_type hash = hash_fn_base::operator()(r_key);
357 return (std::make_pair(comb_probe_fn_base::operator()(hash), hash));
361 inline typename PB_DS_CLASS_C_DEC::size_type
363 operator()(const_key_reference /*r_key*/, size_type hash, size_type i) const
365 return (comb_probe_fn_base::operator()(
366 hash + probe_fn_base::operator()(i)));
370 inline typename PB_DS_CLASS_C_DEC::size_type
373 #ifdef PB_DS_RANGED_PROBE_FN_DEBUG
374 (const_key_reference r_key, size_type hash) const
375 #else // #ifdef PB_DS_RANGED_PROBE_FN_DEBUG
376 (const_key_reference /*r_key*/, size_type hash) const
377 #endif // #ifdef PB_DS_RANGED_PROBE_FN_DEBUG
379 PB_DS_DBG_ASSERT(hash == hash_fn_base::operator()(r_key));
384 #undef PB_DS_CLASS_T_DEC
385 #undef PB_DS_CLASS_C_DEC
387 #define PB_DS_CLASS_T_DEC \
388 template<typename Key, class Allocator, class Comb_Probe_Fn>
390 #define PB_DS_CLASS_C_DEC \
400 * Specialization 3 and 4- The client does not supply a hash function or
401 * probe function, and requests that hash values not be stored.
403 template<typename Key, class Allocator, class Comb_Probe_Fn>
404 class ranged_probe_fn<
411 public Comb_Probe_Fn,
416 typedef typename Allocator::size_type size_type;
418 typedef Comb_Probe_Fn comb_probe_fn_base;
420 typedef typename Allocator::template rebind<Key>::other key_allocator;
422 typedef typename key_allocator::const_reference const_key_reference;
425 ranged_probe_fn(size_type size);
427 ranged_probe_fn(size_type size, const Comb_Probe_Fn& r_comb_probe_fn);
429 ranged_probe_fn(size_type size, const null_hash_fn& r_null_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn, const null_probe_fn& r_null_probe_fn);
432 swap(PB_DS_CLASS_C_DEC& other);
437 ranged_probe_fn(size_type size)
439 Comb_Probe_Fn::notify_resized(size);
444 ranged_probe_fn(size_type size, const Comb_Probe_Fn& r_comb_probe_fn) :
445 Comb_Probe_Fn(r_comb_probe_fn)
450 ranged_probe_fn(size_type size, const null_hash_fn& r_null_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn, const null_probe_fn& r_null_probe_fn) :
451 Comb_Probe_Fn(r_comb_probe_fn)
457 swap(PB_DS_CLASS_C_DEC& other)
459 comb_probe_fn_base::swap(other);
462 #undef PB_DS_CLASS_T_DEC
463 #undef PB_DS_CLASS_C_DEC
465 #undef PB_DS_DBG_ASSERT
466 #undef PB_DS_DBG_VERIFY
467 #undef PB_DS_DBG_ONLY
469 } // namespace detail
472 #endif // #ifndef PB_DS_RANGED_PROBE_FN_HPP