3 // Copyright (C) 2005 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
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
30 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
32 // Permission to use, copy, modify, sell, and distribute this software
33 // is hereby granted without fee, provided that the above copyright
34 // notice appears in all copies, and that both that copyright notice and
35 // this permission notice appear in supporting documentation. None of
36 // the above authors, nor IBM Haifa Research Laboratories, make any
37 // representation about the suitability of this software for any
38 // purpose. It is provided "as is" without express or implied warranty.
41 * @file ranged_probe_fn.hpp
42 * Contains a unified ranged probe functor, allowing the probe tables to deal with
43 * a single class for ranged probeing.
46 #ifndef RANGED_PROBE_FN_HPP
47 #define RANGED_PROBE_FN_HPP
49 #include <ext/pb_assoc/hash_policy.hpp>
58 #ifdef PB_ASSOC_RANGED_PROBE_FN_DEBUG
59 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
60 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
61 #define PB_ASSOC_DBG_ONLY(X) X
62 #else // #ifdef PB_ASSOC_RANGED_PROBE_FN_DEBUG
63 #define PB_ASSOC_DBG_ASSERT(X)
64 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
65 #define PB_ASSOC_DBG_ONLY(X) ;
66 #endif // #ifdef PB_ASSOC_RANGED_PROBE_FN_DEBUG
68 template<typename Key
,
74 class ranged_probe_fn
;
76 #define PB_ASSOC_CLASS_T_DEC \
81 class Comb_Probe_Fn, \
84 #define PB_ASSOC_CLASS_C_DEC \
94 * Specialization 1- The client supplies a probe function and a ranged
95 * probe function, and requests that hash values not be stored.
97 template<typename Key
,
102 class ranged_probe_fn
<
108 false> : public Hash_Fn
,
109 public Comb_Probe_Fn
,
113 typedef typename
Allocator::size_type size_type
;
115 typedef Comb_Probe_Fn my_comb_probe_fn_base
;
117 typedef Hash_Fn my_hash_fn_base
;
119 typedef Probe_Fn my_probe_fn_base
;
121 typedef typename
Allocator::template rebind
< Key
>::other key_allocator
;
123 typedef typename
key_allocator::const_reference const_key_reference
;
126 ranged_probe_fn(size_type size
);
128 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
);
130 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
, const Comb_Probe_Fn
& r_comb_probe_fn
);
132 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
);
135 swap(PB_ASSOC_CLASS_C_DEC
& r_other
);
138 notify_resized(size_type size
);
141 operator()(const_key_reference r_key
) const;
144 operator()(const_key_reference r_key
, size_type hash
, size_type i
) const;
148 PB_ASSOC_CLASS_C_DEC::
149 ranged_probe_fn(size_type size
)
151 Comb_Probe_Fn::notify_resized(size
);
155 PB_ASSOC_CLASS_C_DEC::
156 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
) :
159 Comb_Probe_Fn::notify_resized(size
);
163 PB_ASSOC_CLASS_C_DEC::
164 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
, const Comb_Probe_Fn
& r_comb_probe_fn
) :
166 Comb_Probe_Fn(r_comb_probe_fn
)
168 my_comb_probe_fn_base::notify_resized(size
);
172 PB_ASSOC_CLASS_C_DEC::
173 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
) :
175 Comb_Probe_Fn(r_comb_probe_fn
),
178 my_comb_probe_fn_base::notify_resized(size
);
183 PB_ASSOC_CLASS_C_DEC::
184 swap(PB_ASSOC_CLASS_C_DEC
& r_other
)
186 my_comb_probe_fn_base::swap(r_other
);
188 std::swap((Hash_Fn
& )(*this), (Hash_Fn
& )r_other
);
193 PB_ASSOC_CLASS_C_DEC::
194 notify_resized(size_type size
)
196 my_comb_probe_fn_base::notify_resized(size
);
200 inline typename
PB_ASSOC_CLASS_C_DEC::size_type
201 PB_ASSOC_CLASS_C_DEC::
202 operator()(const_key_reference r_key
) const
204 return (my_comb_probe_fn_base::operator()(
205 my_hash_fn_base::operator()(r_key
)));
209 inline typename
PB_ASSOC_CLASS_C_DEC::size_type
210 PB_ASSOC_CLASS_C_DEC::
211 operator()(const_key_reference r_key
, size_type hash
, size_type i
) const
213 return (my_comb_probe_fn_base::operator()(
214 hash
+ my_probe_fn_base::operator()(r_key
, i
)));
217 #undef PB_ASSOC_CLASS_T_DEC
218 #undef PB_ASSOC_CLASS_C_DEC
220 #define PB_ASSOC_CLASS_T_DEC \
225 class Comb_Probe_Fn, \
228 #define PB_ASSOC_CLASS_C_DEC \
238 * Specialization 2- The client supplies a probe function and a ranged
239 * probe function, and requests that hash values be stored.
241 template<typename Key
,
246 class ranged_probe_fn
<
254 public Comb_Probe_Fn
,
258 typedef typename
Allocator::size_type size_type
;
260 typedef std::pair
<size_type
, size_type
> comp_hash
;
262 typedef Comb_Probe_Fn my_comb_probe_fn_base
;
264 typedef Hash_Fn my_hash_fn_base
;
266 typedef Probe_Fn my_probe_fn_base
;
268 typedef typename
Allocator::template rebind
<Key
>::other key_allocator
;
270 typedef typename
key_allocator::const_reference const_key_reference
;
273 ranged_probe_fn(size_type size
);
275 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
);
277 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
, const Comb_Probe_Fn
& r_comb_probe_fn
);
279 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
);
282 swap(PB_ASSOC_CLASS_C_DEC
& r_other
);
285 notify_resized(size_type size
);
288 operator()(const_key_reference r_key
) const;
291 operator()(const_key_reference r_key
, size_type hash
, size_type i
) const;
294 operator()(const_key_reference r_key
, size_type hash
) const;
298 PB_ASSOC_CLASS_C_DEC::
299 ranged_probe_fn(size_type size
)
301 Comb_Probe_Fn::notify_resized(size
);
305 PB_ASSOC_CLASS_C_DEC::
306 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
) :
309 Comb_Probe_Fn::notify_resized(size
);
313 PB_ASSOC_CLASS_C_DEC::
314 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
, const Comb_Probe_Fn
& r_comb_probe_fn
) :
316 Comb_Probe_Fn(r_comb_probe_fn
)
318 my_comb_probe_fn_base::notify_resized(size
);
322 PB_ASSOC_CLASS_C_DEC::
323 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
) :
325 Comb_Probe_Fn(r_comb_probe_fn
),
328 my_comb_probe_fn_base::notify_resized(size
);
333 PB_ASSOC_CLASS_C_DEC::
334 swap(PB_ASSOC_CLASS_C_DEC
& r_other
)
336 my_comb_probe_fn_base::swap(r_other
);
338 std::swap((Hash_Fn
& )(*this), (Hash_Fn
& )r_other
);
343 PB_ASSOC_CLASS_C_DEC::
344 notify_resized(size_type size
)
346 my_comb_probe_fn_base::notify_resized(size
);
350 inline typename
PB_ASSOC_CLASS_C_DEC::comp_hash
351 PB_ASSOC_CLASS_C_DEC::
352 operator()(const_key_reference r_key
) const
354 const size_type hash
= my_hash_fn_base::operator()(r_key
);
356 return (std::make_pair(my_comb_probe_fn_base::operator()(hash
), hash
));
360 inline typename
PB_ASSOC_CLASS_C_DEC::size_type
361 PB_ASSOC_CLASS_C_DEC::
362 operator()(const_key_reference r_key
, size_type hash
, size_type i
) const
364 return (my_comb_probe_fn_base::operator()(
365 hash
+ my_probe_fn_base::operator()(r_key
, i
)));
369 inline typename
PB_ASSOC_CLASS_C_DEC::size_type
370 PB_ASSOC_CLASS_C_DEC::
372 #ifdef PB_ASSOC_RANGED_PROBE_FN_DEBUG
373 (const_key_reference r_key
, size_type hash
) const
374 #else // #ifdef PB_ASSOC_RANGED_PROBE_FN_DEBUG
375 (const_key_reference
/*r_key*/, size_type hash
) const
376 #endif // #ifdef PB_ASSOC_RANGED_PROBE_FN_DEBUG
378 PB_ASSOC_DBG_ASSERT(hash
== my_hash_fn_base::operator()(r_key
));
383 #undef PB_ASSOC_CLASS_T_DEC
384 #undef PB_ASSOC_CLASS_C_DEC
386 #define PB_ASSOC_CLASS_T_DEC \
387 template<typename Key, class Allocator, class Comb_Probe_Fn>
389 #define PB_ASSOC_CLASS_C_DEC \
399 * Specialization 3 and 4- The client does not supply a hash function or
400 * probe function, and requests that hash values not be stored.
402 template<typename Key
, class Allocator
, class Comb_Probe_Fn
>
403 class ranged_probe_fn
<
410 public Comb_Probe_Fn
,
415 typedef typename
Allocator::size_type size_type
;
417 typedef Comb_Probe_Fn my_comb_probe_fn_base
;
419 typedef typename
Allocator::template rebind
<Key
>::other key_allocator
;
421 typedef typename
key_allocator::const_reference const_key_reference
;
424 ranged_probe_fn(size_type size
);
426 ranged_probe_fn(size_type size
, const Comb_Probe_Fn
& r_comb_probe_fn
);
428 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
);
431 swap(PB_ASSOC_CLASS_C_DEC
& r_other
);
435 PB_ASSOC_CLASS_C_DEC::
436 ranged_probe_fn(size_type size
)
438 Comb_Probe_Fn::notify_resized(size
);
442 PB_ASSOC_CLASS_C_DEC::
443 ranged_probe_fn(size_type size
, const Comb_Probe_Fn
& r_comb_probe_fn
) :
444 Comb_Probe_Fn(r_comb_probe_fn
)
448 PB_ASSOC_CLASS_C_DEC::
449 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
) :
450 Comb_Probe_Fn(r_comb_probe_fn
)
455 PB_ASSOC_CLASS_C_DEC::
456 swap(PB_ASSOC_CLASS_C_DEC
& r_other
)
458 my_comb_probe_fn_base::swap(r_other
);
461 #undef PB_ASSOC_CLASS_T_DEC
462 #undef PB_ASSOC_CLASS_C_DEC
464 #undef PB_ASSOC_DBG_ASSERT
465 #undef PB_ASSOC_DBG_VERIFY
466 #undef PB_ASSOC_DBG_ONLY
468 } // namespace detail
470 } // namespace pb_assoc
472 #endif // #ifndef RANGED_PROBE_FN_HPP