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