]>
Commit | Line | Data |
---|---|---|
fd1e1726 BK |
1 | // -*- C++ -*- |
2 | ||
748086b7 | 3 | // Copyright (C) 2005, 2006, 2009 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 | { | |
a345e45d | 52 | template<typename Key, typename Hash_Fn, typename _Alloc, |
1f1a03ef | 53 | typename Comb_Probe_Fn, typename Probe_Fn, bool Store_Hash> |
fd1e1726 BK |
54 | class ranged_probe_fn; |
55 | ||
3441f106 | 56 | #define PB_DS_CLASS_T_DEC \ |
a345e45d | 57 | template<typename Key, typename Hash_Fn, typename _Alloc, \ |
3441f106 BK |
58 | typename Comb_Probe_Fn, typename Probe_Fn> |
59 | ||
60 | #define PB_DS_CLASS_C_DEC \ | |
a345e45d | 61 | ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, false> |
fd1e1726 BK |
62 | |
63 | /** | |
1f1a03ef BK |
64 | * Specialization 1 |
65 | * The client supplies a probe function and a ranged probe | |
66 | * function, and requests that hash values not be stored. | |
fd1e1726 | 67 | **/ |
a345e45d | 68 | template<typename Key, typename Hash_Fn, typename _Alloc, |
3441f106 | 69 | typename Comb_Probe_Fn, typename Probe_Fn> |
a345e45d | 70 | class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, |
3441f106 BK |
71 | Probe_Fn, false> |
72 | : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn | |
fd1e1726 BK |
73 | { |
74 | protected: | |
a345e45d | 75 | typedef typename _Alloc::size_type size_type; |
4569a895 | 76 | typedef Comb_Probe_Fn comb_probe_fn_base; |
4569a895 | 77 | typedef Hash_Fn hash_fn_base; |
4569a895 | 78 | typedef Probe_Fn probe_fn_base; |
a345e45d BK |
79 | typedef typename _Alloc::template rebind<Key>::other key_allocator; |
80 | typedef typename key_allocator::const_reference key_const_reference; | |
fd1e1726 | 81 | |
1f1a03ef | 82 | ranged_probe_fn(size_type); |
fd1e1726 | 83 | |
1f1a03ef | 84 | ranged_probe_fn(size_type, const Hash_Fn&); |
fd1e1726 | 85 | |
1f1a03ef | 86 | ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&); |
fd1e1726 | 87 | |
1f1a03ef BK |
88 | ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, |
89 | const Probe_Fn&); | |
fd1e1726 BK |
90 | |
91 | void | |
1f1a03ef | 92 | swap(PB_DS_CLASS_C_DEC&); |
fd1e1726 BK |
93 | |
94 | void | |
1f1a03ef | 95 | notify_resized(size_type); |
fd1e1726 BK |
96 | |
97 | inline size_type | |
a345e45d | 98 | operator()(key_const_reference) const; |
fd1e1726 BK |
99 | |
100 | inline size_type | |
a345e45d | 101 | operator()(key_const_reference, size_type, size_type) const; |
fd1e1726 BK |
102 | }; |
103 | ||
4569a895 AT |
104 | PB_DS_CLASS_T_DEC |
105 | PB_DS_CLASS_C_DEC:: | |
fd1e1726 | 106 | ranged_probe_fn(size_type size) |
3441f106 | 107 | { Comb_Probe_Fn::notify_resized(size); } |
fd1e1726 | 108 | |
4569a895 AT |
109 | PB_DS_CLASS_T_DEC |
110 | PB_DS_CLASS_C_DEC:: | |
1f1a03ef BK |
111 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) |
112 | : Hash_Fn(r_hash_fn) | |
3441f106 | 113 | { Comb_Probe_Fn::notify_resized(size); } |
fd1e1726 | 114 | |
4569a895 AT |
115 | PB_DS_CLASS_T_DEC |
116 | PB_DS_CLASS_C_DEC:: | |
1f1a03ef BK |
117 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, |
118 | const Comb_Probe_Fn& r_comb_probe_fn) | |
119 | : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn) | |
3441f106 | 120 | { comb_probe_fn_base::notify_resized(size); } |
fd1e1726 | 121 | |
4569a895 AT |
122 | PB_DS_CLASS_T_DEC |
123 | PB_DS_CLASS_C_DEC:: | |
1f1a03ef BK |
124 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, |
125 | const Comb_Probe_Fn& r_comb_probe_fn, | |
126 | const Probe_Fn& r_probe_fn) | |
127 | : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn) | |
3441f106 | 128 | { comb_probe_fn_base::notify_resized(size); } |
fd1e1726 | 129 | |
4569a895 | 130 | PB_DS_CLASS_T_DEC |
fd1e1726 | 131 | void |
4569a895 AT |
132 | PB_DS_CLASS_C_DEC:: |
133 | swap(PB_DS_CLASS_C_DEC& other) | |
fd1e1726 | 134 | { |
4569a895 | 135 | comb_probe_fn_base::swap(other); |
3441f106 | 136 | std::swap((Hash_Fn& )(*this), (Hash_Fn&)other); |
fd1e1726 BK |
137 | } |
138 | ||
4569a895 | 139 | PB_DS_CLASS_T_DEC |
fd1e1726 | 140 | void |
4569a895 | 141 | PB_DS_CLASS_C_DEC:: |
fd1e1726 | 142 | notify_resized(size_type size) |
3441f106 | 143 | { comb_probe_fn_base::notify_resized(size); } |
fd1e1726 | 144 | |
4569a895 AT |
145 | PB_DS_CLASS_T_DEC |
146 | inline typename PB_DS_CLASS_C_DEC::size_type | |
147 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 148 | operator()(key_const_reference r_key) const |
3441f106 | 149 | { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); } |
fd1e1726 | 150 | |
4569a895 AT |
151 | PB_DS_CLASS_T_DEC |
152 | inline typename PB_DS_CLASS_C_DEC::size_type | |
153 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 154 | operator()(key_const_reference, size_type hash, size_type i) const |
fd1e1726 | 155 | { |
3441f106 | 156 | return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); |
fd1e1726 BK |
157 | } |
158 | ||
4569a895 AT |
159 | #undef PB_DS_CLASS_T_DEC |
160 | #undef PB_DS_CLASS_C_DEC | |
161 | ||
3441f106 | 162 | #define PB_DS_CLASS_T_DEC \ |
a345e45d | 163 | template<typename Key, typename Hash_Fn, typename _Alloc, \ |
1f1a03ef | 164 | typename Comb_Probe_Fn, typename Probe_Fn> |
3441f106 BK |
165 | |
166 | #define PB_DS_CLASS_C_DEC \ | |
a345e45d | 167 | ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, true> |
fd1e1726 BK |
168 | |
169 | /** | |
170 | * Specialization 2- The client supplies a probe function and a ranged | |
4569a895 | 171 | * probe function, and requests that hash values not be stored. |
fd1e1726 | 172 | **/ |
a345e45d | 173 | template<typename Key, typename Hash_Fn, typename _Alloc, |
3441f106 | 174 | typename Comb_Probe_Fn, typename Probe_Fn> |
a345e45d | 175 | class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, |
3441f106 BK |
176 | Probe_Fn, true> |
177 | : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn | |
fd1e1726 BK |
178 | { |
179 | protected: | |
a345e45d | 180 | typedef typename _Alloc::size_type size_type; |
1f1a03ef | 181 | typedef std::pair<size_type, size_type> comp_hash; |
4569a895 | 182 | typedef Comb_Probe_Fn comb_probe_fn_base; |
4569a895 | 183 | typedef Hash_Fn hash_fn_base; |
4569a895 | 184 | typedef Probe_Fn probe_fn_base; |
a345e45d BK |
185 | typedef typename _Alloc::template rebind<Key>::other key_allocator; |
186 | typedef typename key_allocator::const_reference key_const_reference; | |
fd1e1726 | 187 | |
1f1a03ef | 188 | ranged_probe_fn(size_type); |
fd1e1726 | 189 | |
1f1a03ef | 190 | ranged_probe_fn(size_type, const Hash_Fn&); |
fd1e1726 | 191 | |
1f1a03ef BK |
192 | ranged_probe_fn(size_type, const Hash_Fn&, |
193 | const Comb_Probe_Fn&); | |
fd1e1726 | 194 | |
1f1a03ef BK |
195 | ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, |
196 | const Probe_Fn&); | |
fd1e1726 BK |
197 | |
198 | void | |
1f1a03ef | 199 | swap(PB_DS_CLASS_C_DEC&); |
fd1e1726 BK |
200 | |
201 | void | |
1f1a03ef | 202 | notify_resized(size_type); |
fd1e1726 BK |
203 | |
204 | inline comp_hash | |
a345e45d | 205 | operator()(key_const_reference) const; |
fd1e1726 BK |
206 | |
207 | inline size_type | |
a345e45d | 208 | operator()(key_const_reference, size_type, size_type) const; |
fd1e1726 BK |
209 | |
210 | inline size_type | |
a345e45d | 211 | operator()(key_const_reference, size_type) const; |
fd1e1726 BK |
212 | }; |
213 | ||
4569a895 AT |
214 | PB_DS_CLASS_T_DEC |
215 | PB_DS_CLASS_C_DEC:: | |
fd1e1726 | 216 | ranged_probe_fn(size_type size) |
47bea7b8 | 217 | { Comb_Probe_Fn::notify_resized(size); } |
fd1e1726 | 218 | |
4569a895 AT |
219 | PB_DS_CLASS_T_DEC |
220 | PB_DS_CLASS_C_DEC:: | |
1f1a03ef BK |
221 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) |
222 | : Hash_Fn(r_hash_fn) | |
47bea7b8 | 223 | { Comb_Probe_Fn::notify_resized(size); } |
fd1e1726 | 224 | |
4569a895 AT |
225 | PB_DS_CLASS_T_DEC |
226 | PB_DS_CLASS_C_DEC:: | |
3441f106 | 227 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, |
1f1a03ef BK |
228 | const Comb_Probe_Fn& r_comb_probe_fn) |
229 | : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn) | |
47bea7b8 | 230 | { comb_probe_fn_base::notify_resized(size); } |
fd1e1726 | 231 | |
4569a895 AT |
232 | PB_DS_CLASS_T_DEC |
233 | PB_DS_CLASS_C_DEC:: | |
3441f106 BK |
234 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, |
235 | const Comb_Probe_Fn& r_comb_probe_fn, | |
1f1a03ef BK |
236 | const Probe_Fn& r_probe_fn) |
237 | : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn) | |
47bea7b8 | 238 | { comb_probe_fn_base::notify_resized(size); } |
fd1e1726 | 239 | |
4569a895 | 240 | PB_DS_CLASS_T_DEC |
fd1e1726 | 241 | void |
4569a895 AT |
242 | PB_DS_CLASS_C_DEC:: |
243 | swap(PB_DS_CLASS_C_DEC& other) | |
fd1e1726 | 244 | { |
4569a895 | 245 | comb_probe_fn_base::swap(other); |
4569a895 | 246 | std::swap((Hash_Fn& )(*this), (Hash_Fn& )other); |
fd1e1726 BK |
247 | } |
248 | ||
4569a895 | 249 | PB_DS_CLASS_T_DEC |
fd1e1726 | 250 | void |
4569a895 | 251 | PB_DS_CLASS_C_DEC:: |
fd1e1726 | 252 | notify_resized(size_type size) |
47bea7b8 | 253 | { comb_probe_fn_base::notify_resized(size); } |
fd1e1726 | 254 | |
4569a895 AT |
255 | PB_DS_CLASS_T_DEC |
256 | inline typename PB_DS_CLASS_C_DEC::comp_hash | |
257 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 258 | operator()(key_const_reference r_key) const |
fd1e1726 | 259 | { |
4569a895 | 260 | const size_type hash = hash_fn_base::operator()(r_key); |
47bea7b8 | 261 | return std::make_pair(comb_probe_fn_base::operator()(hash), hash); |
fd1e1726 BK |
262 | } |
263 | ||
4569a895 AT |
264 | PB_DS_CLASS_T_DEC |
265 | inline typename PB_DS_CLASS_C_DEC::size_type | |
266 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 267 | operator()(key_const_reference, size_type hash, size_type i) const |
fd1e1726 | 268 | { |
47bea7b8 | 269 | return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); |
fd1e1726 BK |
270 | } |
271 | ||
4569a895 AT |
272 | PB_DS_CLASS_T_DEC |
273 | inline typename PB_DS_CLASS_C_DEC::size_type | |
274 | PB_DS_CLASS_C_DEC:: | |
fd1e1726 | 275 | operator() |
47bea7b8 | 276 | #ifdef _GLIBCXX_DEBUG |
a345e45d | 277 | (key_const_reference r_key, size_type hash) const |
47bea7b8 | 278 | #else |
a345e45d | 279 | (key_const_reference /*r_key*/, size_type hash) const |
47bea7b8 | 280 | #endif |
fd1e1726 | 281 | { |
47bea7b8 BK |
282 | _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key)); |
283 | return hash; | |
fd1e1726 BK |
284 | } |
285 | ||
4569a895 AT |
286 | #undef PB_DS_CLASS_T_DEC |
287 | #undef PB_DS_CLASS_C_DEC | |
fd1e1726 | 288 | |
fd1e1726 | 289 | /** |
1f1a03ef BK |
290 | * Specialization 3 and 4 |
291 | * The client does not supply a hash function or probe function, | |
292 | * and requests that hash values not be stored. | |
fd1e1726 | 293 | **/ |
a345e45d BK |
294 | template<typename Key, typename _Alloc, typename Comb_Probe_Fn> |
295 | class ranged_probe_fn<Key, null_type, _Alloc, Comb_Probe_Fn, | |
296 | null_type, false> | |
297 | : public Comb_Probe_Fn | |
fd1e1726 BK |
298 | { |
299 | protected: | |
a345e45d | 300 | typedef typename _Alloc::size_type size_type; |
4569a895 | 301 | typedef Comb_Probe_Fn comb_probe_fn_base; |
a345e45d BK |
302 | typedef typename _Alloc::template rebind<Key>::other key_allocator; |
303 | typedef typename key_allocator::const_reference key_const_reference; | |
fd1e1726 | 304 | |
3441f106 BK |
305 | ranged_probe_fn(size_type size) |
306 | { Comb_Probe_Fn::notify_resized(size); } | |
fd1e1726 | 307 | |
1f1a03ef | 308 | ranged_probe_fn(size_type, const Comb_Probe_Fn& r_comb_probe_fn) |
3441f106 BK |
309 | : Comb_Probe_Fn(r_comb_probe_fn) |
310 | { } | |
fd1e1726 | 311 | |
a345e45d | 312 | ranged_probe_fn(size_type, const null_type&, |
3441f106 | 313 | const Comb_Probe_Fn& r_comb_probe_fn, |
a345e45d | 314 | const null_type&) |
3441f106 BK |
315 | : Comb_Probe_Fn(r_comb_probe_fn) |
316 | { } | |
fd1e1726 BK |
317 | |
318 | void | |
3441f106 BK |
319 | swap(ranged_probe_fn& other) |
320 | { comb_probe_fn_base::swap(other); } | |
fd1e1726 | 321 | }; |
fd1e1726 | 322 | } // namespace detail |
5e11f978 | 323 | } // namespace __gnu_pbds |
fd1e1726 | 324 | |
47bea7b8 | 325 | #endif |
fd1e1726 | 326 |