]>
Commit | Line | Data |
---|---|---|
fd1e1726 BK |
1 | // -*- C++ -*- |
2 | ||
405feeb8 | 3 | // Copyright (C) 2005-2013 Free Software Foundation, Inc. |
fd1e1726 BK |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
4569a895 AT |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
9 | // version. |
10 | ||
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. | |
15 | ||
748086b7 JJ |
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. | |
4569a895 | 19 | |
748086b7 JJ |
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/>. | |
fd1e1726 BK |
24 | |
25 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
26 | ||
27 | // Permission to use, copy, modify, sell, and distribute this software | |
28 | // is hereby granted without fee, provided that the above copyright | |
4569a895 AT |
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 | |
fd1e1726 | 32 | // representation about the suitability of this software for any |
4569a895 AT |
33 | // purpose. It is provided "as is" without express or implied |
34 | // warranty. | |
fd1e1726 BK |
35 | |
36 | /** | |
37 | * @file ranged_probe_fn.hpp | |
38 | * Contains a unified ranged probe functor, allowing the probe tables to deal with | |
4569a895 | 39 | * a single class for ranged probeing. |
fd1e1726 BK |
40 | */ |
41 | ||
4569a895 AT |
42 | #ifndef PB_DS_RANGED_PROBE_FN_HPP |
43 | #define PB_DS_RANGED_PROBE_FN_HPP | |
fd1e1726 | 44 | |
fd1e1726 | 45 | #include <utility> |
47bea7b8 | 46 | #include <debug/debug.h> |
fd1e1726 | 47 | |
5e11f978 | 48 | namespace __gnu_pbds |
fd1e1726 | 49 | { |
fd1e1726 BK |
50 | namespace detail |
51 | { | |
30a96b3b | 52 | /// Primary template. |
a345e45d | 53 | template<typename Key, typename Hash_Fn, typename _Alloc, |
1f1a03ef | 54 | typename Comb_Probe_Fn, typename Probe_Fn, bool Store_Hash> |
fd1e1726 BK |
55 | class ranged_probe_fn; |
56 | ||
3441f106 | 57 | #define PB_DS_CLASS_T_DEC \ |
a345e45d | 58 | template<typename Key, typename Hash_Fn, typename _Alloc, \ |
3441f106 BK |
59 | typename Comb_Probe_Fn, typename Probe_Fn> |
60 | ||
61 | #define PB_DS_CLASS_C_DEC \ | |
a345e45d | 62 | ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, false> |
fd1e1726 BK |
63 | |
64 | /** | |
1f1a03ef BK |
65 | * Specialization 1 |
66 | * The client supplies a probe function and a ranged probe | |
67 | * function, and requests that hash values not be stored. | |
fd1e1726 | 68 | **/ |
a345e45d | 69 | template<typename Key, typename Hash_Fn, typename _Alloc, |
3441f106 | 70 | typename Comb_Probe_Fn, typename Probe_Fn> |
a345e45d | 71 | class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, |
3441f106 BK |
72 | Probe_Fn, false> |
73 | : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn | |
fd1e1726 BK |
74 | { |
75 | protected: | |
a345e45d | 76 | typedef typename _Alloc::size_type size_type; |
4569a895 | 77 | typedef Comb_Probe_Fn comb_probe_fn_base; |
4569a895 | 78 | typedef Hash_Fn hash_fn_base; |
4569a895 | 79 | typedef Probe_Fn probe_fn_base; |
a345e45d BK |
80 | typedef typename _Alloc::template rebind<Key>::other key_allocator; |
81 | typedef typename key_allocator::const_reference key_const_reference; | |
fd1e1726 | 82 | |
1f1a03ef | 83 | ranged_probe_fn(size_type); |
fd1e1726 | 84 | |
1f1a03ef | 85 | ranged_probe_fn(size_type, const Hash_Fn&); |
fd1e1726 | 86 | |
1f1a03ef | 87 | ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&); |
fd1e1726 | 88 | |
1f1a03ef BK |
89 | ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, |
90 | const Probe_Fn&); | |
fd1e1726 BK |
91 | |
92 | void | |
1f1a03ef | 93 | swap(PB_DS_CLASS_C_DEC&); |
fd1e1726 BK |
94 | |
95 | void | |
1f1a03ef | 96 | notify_resized(size_type); |
fd1e1726 BK |
97 | |
98 | inline size_type | |
a345e45d | 99 | operator()(key_const_reference) const; |
fd1e1726 BK |
100 | |
101 | inline size_type | |
a345e45d | 102 | operator()(key_const_reference, size_type, size_type) const; |
fd1e1726 BK |
103 | }; |
104 | ||
4569a895 AT |
105 | PB_DS_CLASS_T_DEC |
106 | PB_DS_CLASS_C_DEC:: | |
fd1e1726 | 107 | ranged_probe_fn(size_type size) |
3441f106 | 108 | { Comb_Probe_Fn::notify_resized(size); } |
fd1e1726 | 109 | |
4569a895 AT |
110 | PB_DS_CLASS_T_DEC |
111 | PB_DS_CLASS_C_DEC:: | |
1f1a03ef BK |
112 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) |
113 | : Hash_Fn(r_hash_fn) | |
3441f106 | 114 | { Comb_Probe_Fn::notify_resized(size); } |
fd1e1726 | 115 | |
4569a895 AT |
116 | PB_DS_CLASS_T_DEC |
117 | PB_DS_CLASS_C_DEC:: | |
1f1a03ef BK |
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) | |
3441f106 | 121 | { comb_probe_fn_base::notify_resized(size); } |
fd1e1726 | 122 | |
4569a895 AT |
123 | PB_DS_CLASS_T_DEC |
124 | PB_DS_CLASS_C_DEC:: | |
1f1a03ef BK |
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) | |
3441f106 | 129 | { comb_probe_fn_base::notify_resized(size); } |
fd1e1726 | 130 | |
4569a895 | 131 | PB_DS_CLASS_T_DEC |
fd1e1726 | 132 | void |
4569a895 AT |
133 | PB_DS_CLASS_C_DEC:: |
134 | swap(PB_DS_CLASS_C_DEC& other) | |
fd1e1726 | 135 | { |
4569a895 | 136 | comb_probe_fn_base::swap(other); |
3441f106 | 137 | std::swap((Hash_Fn& )(*this), (Hash_Fn&)other); |
fd1e1726 BK |
138 | } |
139 | ||
4569a895 | 140 | PB_DS_CLASS_T_DEC |
fd1e1726 | 141 | void |
4569a895 | 142 | PB_DS_CLASS_C_DEC:: |
fd1e1726 | 143 | notify_resized(size_type size) |
3441f106 | 144 | { comb_probe_fn_base::notify_resized(size); } |
fd1e1726 | 145 | |
4569a895 AT |
146 | PB_DS_CLASS_T_DEC |
147 | inline typename PB_DS_CLASS_C_DEC::size_type | |
148 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 149 | operator()(key_const_reference r_key) const |
3441f106 | 150 | { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); } |
fd1e1726 | 151 | |
4569a895 AT |
152 | PB_DS_CLASS_T_DEC |
153 | inline typename PB_DS_CLASS_C_DEC::size_type | |
154 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 155 | operator()(key_const_reference, size_type hash, size_type i) const |
fd1e1726 | 156 | { |
3441f106 | 157 | return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); |
fd1e1726 BK |
158 | } |
159 | ||
4569a895 AT |
160 | #undef PB_DS_CLASS_T_DEC |
161 | #undef PB_DS_CLASS_C_DEC | |
162 | ||
3441f106 | 163 | #define PB_DS_CLASS_T_DEC \ |
a345e45d | 164 | template<typename Key, typename Hash_Fn, typename _Alloc, \ |
1f1a03ef | 165 | typename Comb_Probe_Fn, typename Probe_Fn> |
3441f106 BK |
166 | |
167 | #define PB_DS_CLASS_C_DEC \ | |
a345e45d | 168 | ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, true> |
fd1e1726 BK |
169 | |
170 | /** | |
171 | * Specialization 2- The client supplies a probe function and a ranged | |
4569a895 | 172 | * probe function, and requests that hash values not be stored. |
fd1e1726 | 173 | **/ |
a345e45d | 174 | template<typename Key, typename Hash_Fn, typename _Alloc, |
3441f106 | 175 | typename Comb_Probe_Fn, typename Probe_Fn> |
a345e45d | 176 | class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, |
3441f106 BK |
177 | Probe_Fn, true> |
178 | : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn | |
fd1e1726 BK |
179 | { |
180 | protected: | |
a345e45d | 181 | typedef typename _Alloc::size_type size_type; |
1f1a03ef | 182 | typedef std::pair<size_type, size_type> comp_hash; |
4569a895 | 183 | typedef Comb_Probe_Fn comb_probe_fn_base; |
4569a895 | 184 | typedef Hash_Fn hash_fn_base; |
4569a895 | 185 | typedef Probe_Fn probe_fn_base; |
a345e45d BK |
186 | typedef typename _Alloc::template rebind<Key>::other key_allocator; |
187 | typedef typename key_allocator::const_reference key_const_reference; | |
fd1e1726 | 188 | |
1f1a03ef | 189 | ranged_probe_fn(size_type); |
fd1e1726 | 190 | |
1f1a03ef | 191 | ranged_probe_fn(size_type, const Hash_Fn&); |
fd1e1726 | 192 | |
1f1a03ef BK |
193 | ranged_probe_fn(size_type, const Hash_Fn&, |
194 | const Comb_Probe_Fn&); | |
fd1e1726 | 195 | |
1f1a03ef BK |
196 | ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, |
197 | const Probe_Fn&); | |
fd1e1726 BK |
198 | |
199 | void | |
1f1a03ef | 200 | swap(PB_DS_CLASS_C_DEC&); |
fd1e1726 BK |
201 | |
202 | void | |
1f1a03ef | 203 | notify_resized(size_type); |
fd1e1726 BK |
204 | |
205 | inline comp_hash | |
a345e45d | 206 | operator()(key_const_reference) const; |
fd1e1726 BK |
207 | |
208 | inline size_type | |
a345e45d | 209 | operator()(key_const_reference, size_type, size_type) const; |
fd1e1726 BK |
210 | |
211 | inline size_type | |
a345e45d | 212 | operator()(key_const_reference, size_type) const; |
fd1e1726 BK |
213 | }; |
214 | ||
4569a895 AT |
215 | PB_DS_CLASS_T_DEC |
216 | PB_DS_CLASS_C_DEC:: | |
fd1e1726 | 217 | ranged_probe_fn(size_type size) |
47bea7b8 | 218 | { Comb_Probe_Fn::notify_resized(size); } |
fd1e1726 | 219 | |
4569a895 AT |
220 | PB_DS_CLASS_T_DEC |
221 | PB_DS_CLASS_C_DEC:: | |
1f1a03ef BK |
222 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) |
223 | : Hash_Fn(r_hash_fn) | |
47bea7b8 | 224 | { Comb_Probe_Fn::notify_resized(size); } |
fd1e1726 | 225 | |
4569a895 AT |
226 | PB_DS_CLASS_T_DEC |
227 | PB_DS_CLASS_C_DEC:: | |
3441f106 | 228 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, |
1f1a03ef BK |
229 | const Comb_Probe_Fn& r_comb_probe_fn) |
230 | : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn) | |
47bea7b8 | 231 | { comb_probe_fn_base::notify_resized(size); } |
fd1e1726 | 232 | |
4569a895 AT |
233 | PB_DS_CLASS_T_DEC |
234 | PB_DS_CLASS_C_DEC:: | |
3441f106 BK |
235 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, |
236 | const Comb_Probe_Fn& r_comb_probe_fn, | |
1f1a03ef BK |
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) | |
47bea7b8 | 239 | { comb_probe_fn_base::notify_resized(size); } |
fd1e1726 | 240 | |
4569a895 | 241 | PB_DS_CLASS_T_DEC |
fd1e1726 | 242 | void |
4569a895 AT |
243 | PB_DS_CLASS_C_DEC:: |
244 | swap(PB_DS_CLASS_C_DEC& other) | |
fd1e1726 | 245 | { |
4569a895 | 246 | comb_probe_fn_base::swap(other); |
4569a895 | 247 | std::swap((Hash_Fn& )(*this), (Hash_Fn& )other); |
fd1e1726 BK |
248 | } |
249 | ||
4569a895 | 250 | PB_DS_CLASS_T_DEC |
fd1e1726 | 251 | void |
4569a895 | 252 | PB_DS_CLASS_C_DEC:: |
fd1e1726 | 253 | notify_resized(size_type size) |
47bea7b8 | 254 | { comb_probe_fn_base::notify_resized(size); } |
fd1e1726 | 255 | |
4569a895 AT |
256 | PB_DS_CLASS_T_DEC |
257 | inline typename PB_DS_CLASS_C_DEC::comp_hash | |
258 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 259 | operator()(key_const_reference r_key) const |
fd1e1726 | 260 | { |
4569a895 | 261 | const size_type hash = hash_fn_base::operator()(r_key); |
47bea7b8 | 262 | return std::make_pair(comb_probe_fn_base::operator()(hash), hash); |
fd1e1726 BK |
263 | } |
264 | ||
4569a895 AT |
265 | PB_DS_CLASS_T_DEC |
266 | inline typename PB_DS_CLASS_C_DEC::size_type | |
267 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 268 | operator()(key_const_reference, size_type hash, size_type i) const |
fd1e1726 | 269 | { |
47bea7b8 | 270 | return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); |
fd1e1726 BK |
271 | } |
272 | ||
4569a895 AT |
273 | PB_DS_CLASS_T_DEC |
274 | inline typename PB_DS_CLASS_C_DEC::size_type | |
275 | PB_DS_CLASS_C_DEC:: | |
fd1e1726 | 276 | operator() |
47bea7b8 | 277 | #ifdef _GLIBCXX_DEBUG |
a345e45d | 278 | (key_const_reference r_key, size_type hash) const |
47bea7b8 | 279 | #else |
a345e45d | 280 | (key_const_reference /*r_key*/, size_type hash) const |
47bea7b8 | 281 | #endif |
fd1e1726 | 282 | { |
47bea7b8 BK |
283 | _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key)); |
284 | return hash; | |
fd1e1726 BK |
285 | } |
286 | ||
4569a895 AT |
287 | #undef PB_DS_CLASS_T_DEC |
288 | #undef PB_DS_CLASS_C_DEC | |
fd1e1726 | 289 | |
fd1e1726 | 290 | /** |
1f1a03ef BK |
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. | |
fd1e1726 | 294 | **/ |
a345e45d BK |
295 | template<typename Key, typename _Alloc, typename Comb_Probe_Fn> |
296 | class ranged_probe_fn<Key, null_type, _Alloc, Comb_Probe_Fn, | |
297 | null_type, false> | |
298 | : public Comb_Probe_Fn | |
fd1e1726 BK |
299 | { |
300 | protected: | |
a345e45d | 301 | typedef typename _Alloc::size_type size_type; |
4569a895 | 302 | typedef Comb_Probe_Fn comb_probe_fn_base; |
a345e45d BK |
303 | typedef typename _Alloc::template rebind<Key>::other key_allocator; |
304 | typedef typename key_allocator::const_reference key_const_reference; | |
fd1e1726 | 305 | |
3441f106 BK |
306 | ranged_probe_fn(size_type size) |
307 | { Comb_Probe_Fn::notify_resized(size); } | |
fd1e1726 | 308 | |
1f1a03ef | 309 | ranged_probe_fn(size_type, const Comb_Probe_Fn& r_comb_probe_fn) |
3441f106 BK |
310 | : Comb_Probe_Fn(r_comb_probe_fn) |
311 | { } | |
fd1e1726 | 312 | |
a345e45d | 313 | ranged_probe_fn(size_type, const null_type&, |
3441f106 | 314 | const Comb_Probe_Fn& r_comb_probe_fn, |
a345e45d | 315 | const null_type&) |
3441f106 BK |
316 | : Comb_Probe_Fn(r_comb_probe_fn) |
317 | { } | |
fd1e1726 BK |
318 | |
319 | void | |
3441f106 BK |
320 | swap(ranged_probe_fn& other) |
321 | { comb_probe_fn_base::swap(other); } | |
fd1e1726 | 322 | }; |
fd1e1726 | 323 | } // namespace detail |
5e11f978 | 324 | } // namespace __gnu_pbds |
fd1e1726 | 325 | |
47bea7b8 | 326 | #endif |
fd1e1726 | 327 |