3 // Copyright (C) 2005, 2006, 2009 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
27 // Permission to use, copy, modify, sell, and distribute this software
28 // is hereby granted without fee, provided that the above copyright
29 // notice appears in all copies, and that both that copyright notice
30 // and this permission notice appear in supporting documentation. None
31 // of the above authors, nor IBM Haifa Research Laboratories, make any
32 // representation about the suitability of this software for any
33 // purpose. It is provided "as is" without express or implied
37 * @file ranged_probe_fn.hpp
38 * Contains a unified ranged probe functor, allowing the probe tables to deal with
39 * a single class for ranged probeing.
42 #ifndef PB_DS_RANGED_PROBE_FN_HPP
43 #define PB_DS_RANGED_PROBE_FN_HPP
45 #include <ext/pb_ds/detail/basic_types.hpp>
47 #include <debug/debug.h>
53 template<typename Key
, typename Hash_Fn
, typename Allocator
,
54 typename Comb_Probe_Fn
, typename Probe_Fn
, bool Store_Hash
>
55 class ranged_probe_fn
;
57 #define PB_DS_CLASS_T_DEC \
58 template<typename Key, typename Hash_Fn, typename Allocator, \
59 typename Comb_Probe_Fn, typename Probe_Fn>
61 #define PB_DS_CLASS_C_DEC \
62 ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, false>
66 * The client supplies a probe function and a ranged probe
67 * function, and requests that hash values not be stored.
69 template<typename Key
, typename Hash_Fn
, typename Allocator
,
70 typename Comb_Probe_Fn
, typename Probe_Fn
>
71 class ranged_probe_fn
<Key
, Hash_Fn
, Allocator
, Comb_Probe_Fn
,
73 : public Hash_Fn
, public Comb_Probe_Fn
, public Probe_Fn
76 typedef typename
Allocator::size_type size_type
;
77 typedef Comb_Probe_Fn comb_probe_fn_base
;
78 typedef Hash_Fn hash_fn_base
;
79 typedef Probe_Fn probe_fn_base
;
80 typedef typename
Allocator::template rebind
<Key
>::other key_allocator
;
81 typedef typename
key_allocator::const_reference const_key_reference
;
83 ranged_probe_fn(size_type
);
85 ranged_probe_fn(size_type
, const Hash_Fn
&);
87 ranged_probe_fn(size_type
, const Hash_Fn
&, const Comb_Probe_Fn
&);
89 ranged_probe_fn(size_type
, const Hash_Fn
&, const Comb_Probe_Fn
&,
93 swap(PB_DS_CLASS_C_DEC
&);
96 notify_resized(size_type
);
99 operator()(const_key_reference
) const;
102 operator()(const_key_reference
, size_type
, size_type
) const;
107 ranged_probe_fn(size_type size
)
108 { Comb_Probe_Fn::notify_resized(size
); }
112 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
)
114 { Comb_Probe_Fn::notify_resized(size
); }
118 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
,
119 const Comb_Probe_Fn
& r_comb_probe_fn
)
120 : Hash_Fn(r_hash_fn
), Comb_Probe_Fn(r_comb_probe_fn
)
121 { comb_probe_fn_base::notify_resized(size
); }
125 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
,
126 const Comb_Probe_Fn
& r_comb_probe_fn
,
127 const Probe_Fn
& r_probe_fn
)
128 : Hash_Fn(r_hash_fn
), Comb_Probe_Fn(r_comb_probe_fn
), Probe_Fn(r_probe_fn
)
129 { comb_probe_fn_base::notify_resized(size
); }
134 swap(PB_DS_CLASS_C_DEC
& other
)
136 comb_probe_fn_base::swap(other
);
137 std::swap((Hash_Fn
& )(*this), (Hash_Fn
&)other
);
143 notify_resized(size_type size
)
144 { comb_probe_fn_base::notify_resized(size
); }
147 inline typename
PB_DS_CLASS_C_DEC::size_type
149 operator()(const_key_reference r_key
) const
150 { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key
)); }
153 inline typename
PB_DS_CLASS_C_DEC::size_type
155 operator()(const_key_reference
, size_type hash
, size_type i
) const
157 return comb_probe_fn_base::operator()(hash
+ probe_fn_base::operator()(i
));
160 #undef PB_DS_CLASS_T_DEC
161 #undef PB_DS_CLASS_C_DEC
163 #define PB_DS_CLASS_T_DEC \
164 template<typename Key, typename Hash_Fn, typename Allocator, \
165 typename Comb_Probe_Fn, typename Probe_Fn>
167 #define PB_DS_CLASS_C_DEC \
168 ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, true>
171 * Specialization 2- The client supplies a probe function and a ranged
172 * probe function, and requests that hash values not be stored.
174 template<typename Key
, typename Hash_Fn
, typename Allocator
,
175 typename Comb_Probe_Fn
, typename Probe_Fn
>
176 class ranged_probe_fn
<Key
, Hash_Fn
, Allocator
, Comb_Probe_Fn
,
178 : public Hash_Fn
, public Comb_Probe_Fn
, public Probe_Fn
181 typedef typename
Allocator::size_type size_type
;
182 typedef std::pair
<size_type
, size_type
> comp_hash
;
183 typedef Comb_Probe_Fn comb_probe_fn_base
;
184 typedef Hash_Fn hash_fn_base
;
185 typedef Probe_Fn probe_fn_base
;
186 typedef typename
Allocator::template rebind
<Key
>::other key_allocator
;
187 typedef typename
key_allocator::const_reference const_key_reference
;
189 ranged_probe_fn(size_type
);
191 ranged_probe_fn(size_type
, const Hash_Fn
&);
193 ranged_probe_fn(size_type
, const Hash_Fn
&,
194 const Comb_Probe_Fn
&);
196 ranged_probe_fn(size_type
, const Hash_Fn
&, const Comb_Probe_Fn
&,
200 swap(PB_DS_CLASS_C_DEC
&);
203 notify_resized(size_type
);
206 operator()(const_key_reference
) const;
209 operator()(const_key_reference
, size_type
, size_type
) const;
212 operator()(const_key_reference
, size_type
) const;
217 ranged_probe_fn(size_type size
)
218 { Comb_Probe_Fn::notify_resized(size
); }
222 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
)
224 { Comb_Probe_Fn::notify_resized(size
); }
228 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
,
229 const Comb_Probe_Fn
& r_comb_probe_fn
)
230 : Hash_Fn(r_hash_fn
), Comb_Probe_Fn(r_comb_probe_fn
)
231 { comb_probe_fn_base::notify_resized(size
); }
235 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
,
236 const Comb_Probe_Fn
& r_comb_probe_fn
,
237 const Probe_Fn
& r_probe_fn
)
238 : Hash_Fn(r_hash_fn
), Comb_Probe_Fn(r_comb_probe_fn
), Probe_Fn(r_probe_fn
)
239 { comb_probe_fn_base::notify_resized(size
); }
244 swap(PB_DS_CLASS_C_DEC
& other
)
246 comb_probe_fn_base::swap(other
);
247 std::swap((Hash_Fn
& )(*this), (Hash_Fn
& )other
);
253 notify_resized(size_type size
)
254 { comb_probe_fn_base::notify_resized(size
); }
257 inline typename
PB_DS_CLASS_C_DEC::comp_hash
259 operator()(const_key_reference r_key
) const
261 const size_type hash
= hash_fn_base::operator()(r_key
);
262 return std::make_pair(comb_probe_fn_base::operator()(hash
), hash
);
266 inline typename
PB_DS_CLASS_C_DEC::size_type
268 operator()(const_key_reference
, size_type hash
, size_type i
) const
270 return comb_probe_fn_base::operator()(hash
+ probe_fn_base::operator()(i
));
274 inline typename
PB_DS_CLASS_C_DEC::size_type
277 #ifdef _GLIBCXX_DEBUG
278 (const_key_reference r_key
, size_type hash
) const
280 (const_key_reference
/*r_key*/, size_type hash
) const
283 _GLIBCXX_DEBUG_ASSERT(hash
== hash_fn_base::operator()(r_key
));
287 #undef PB_DS_CLASS_T_DEC
288 #undef PB_DS_CLASS_C_DEC
291 * Specialization 3 and 4
292 * The client does not supply a hash function or probe function,
293 * and requests that hash values not be stored.
295 template<typename Key
, typename Allocator
, typename Comb_Probe_Fn
>
296 class ranged_probe_fn
<Key
, null_hash_fn
, Allocator
, Comb_Probe_Fn
,
297 null_probe_fn
, false>
298 : public Comb_Probe_Fn
, public null_hash_fn
, public null_probe_fn
301 typedef typename
Allocator::size_type size_type
;
302 typedef Comb_Probe_Fn comb_probe_fn_base
;
303 typedef typename
Allocator::template rebind
<Key
>::other key_allocator
;
304 typedef typename
key_allocator::const_reference const_key_reference
;
306 ranged_probe_fn(size_type size
)
307 { Comb_Probe_Fn::notify_resized(size
); }
309 ranged_probe_fn(size_type
, const Comb_Probe_Fn
& r_comb_probe_fn
)
310 : Comb_Probe_Fn(r_comb_probe_fn
)
313 ranged_probe_fn(size_type
, const null_hash_fn
&,
314 const Comb_Probe_Fn
& r_comb_probe_fn
,
315 const null_probe_fn
&)
316 : Comb_Probe_Fn(r_comb_probe_fn
)
320 swap(ranged_probe_fn
& other
)
321 { comb_probe_fn_base::swap(other
); }
323 } // namespace detail
324 } // namespace __gnu_pbds