]>
Commit | Line | Data |
---|---|---|
1 | // -*- C++ -*- | |
2 | ||
3 | // Copyright (C) 2005-2024 Free Software Foundation, Inc. | |
4 | // | |
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 | |
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 | // 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. | |
19 | ||
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/>. | |
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 | |
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 | |
34 | // warranty. | |
35 | ||
36 | /** | |
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. | |
40 | */ | |
41 | ||
42 | #ifndef PB_DS_RANGED_PROBE_FN_HPP | |
43 | #define PB_DS_RANGED_PROBE_FN_HPP | |
44 | ||
45 | #include <utility> | |
46 | #include <debug/debug.h> | |
47 | ||
48 | namespace __gnu_pbds | |
49 | { | |
50 | namespace detail | |
51 | { | |
52 | /// Primary template. | |
53 | template<typename Key, typename Hash_Fn, typename _Alloc, | |
54 | typename Comb_Probe_Fn, typename Probe_Fn, bool Store_Hash> | |
55 | class ranged_probe_fn; | |
56 | ||
57 | #define PB_DS_CLASS_T_DEC \ | |
58 | template<typename Key, typename Hash_Fn, typename _Alloc, \ | |
59 | typename Comb_Probe_Fn, typename Probe_Fn> | |
60 | ||
61 | #define PB_DS_CLASS_C_DEC \ | |
62 | ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, false> | |
63 | ||
64 | /** | |
65 | * Specialization 1 | |
66 | * The client supplies a probe function and a ranged probe | |
67 | * function, and requests that hash values not be stored. | |
68 | **/ | |
69 | template<typename Key, typename Hash_Fn, typename _Alloc, | |
70 | typename Comb_Probe_Fn, typename Probe_Fn> | |
71 | class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, | |
72 | Probe_Fn, false> | |
73 | : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn | |
74 | { | |
75 | protected: | |
76 | typedef typename _Alloc::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 rebind_traits<_Alloc, Key>::const_reference | |
81 | key_const_reference; | |
82 | ||
83 | ranged_probe_fn(size_type); | |
84 | ||
85 | ranged_probe_fn(size_type, const Hash_Fn&); | |
86 | ||
87 | ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&); | |
88 | ||
89 | ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, | |
90 | const Probe_Fn&); | |
91 | ||
92 | void | |
93 | swap(PB_DS_CLASS_C_DEC&); | |
94 | ||
95 | void | |
96 | notify_resized(size_type); | |
97 | ||
98 | inline size_type | |
99 | operator()(key_const_reference) const; | |
100 | ||
101 | inline size_type | |
102 | operator()(key_const_reference, size_type, size_type) const; | |
103 | }; | |
104 | ||
105 | PB_DS_CLASS_T_DEC | |
106 | PB_DS_CLASS_C_DEC:: | |
107 | ranged_probe_fn(size_type size) | |
108 | { Comb_Probe_Fn::notify_resized(size); } | |
109 | ||
110 | PB_DS_CLASS_T_DEC | |
111 | PB_DS_CLASS_C_DEC:: | |
112 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) | |
113 | : Hash_Fn(r_hash_fn) | |
114 | { Comb_Probe_Fn::notify_resized(size); } | |
115 | ||
116 | PB_DS_CLASS_T_DEC | |
117 | PB_DS_CLASS_C_DEC:: | |
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); } | |
122 | ||
123 | PB_DS_CLASS_T_DEC | |
124 | PB_DS_CLASS_C_DEC:: | |
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); } | |
130 | ||
131 | PB_DS_CLASS_T_DEC | |
132 | void | |
133 | PB_DS_CLASS_C_DEC:: | |
134 | swap(PB_DS_CLASS_C_DEC& other) | |
135 | { | |
136 | comb_probe_fn_base::swap(other); | |
137 | std::swap((Hash_Fn& )(*this), (Hash_Fn&)other); | |
138 | } | |
139 | ||
140 | PB_DS_CLASS_T_DEC | |
141 | void | |
142 | PB_DS_CLASS_C_DEC:: | |
143 | notify_resized(size_type size) | |
144 | { comb_probe_fn_base::notify_resized(size); } | |
145 | ||
146 | PB_DS_CLASS_T_DEC | |
147 | inline typename PB_DS_CLASS_C_DEC::size_type | |
148 | PB_DS_CLASS_C_DEC:: | |
149 | operator()(key_const_reference r_key) const | |
150 | { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); } | |
151 | ||
152 | PB_DS_CLASS_T_DEC | |
153 | inline typename PB_DS_CLASS_C_DEC::size_type | |
154 | PB_DS_CLASS_C_DEC:: | |
155 | operator()(key_const_reference, size_type hash, size_type i) const | |
156 | { | |
157 | return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); | |
158 | } | |
159 | ||
160 | #undef PB_DS_CLASS_T_DEC | |
161 | #undef PB_DS_CLASS_C_DEC | |
162 | ||
163 | #define PB_DS_CLASS_T_DEC \ | |
164 | template<typename Key, typename Hash_Fn, typename _Alloc, \ | |
165 | typename Comb_Probe_Fn, typename Probe_Fn> | |
166 | ||
167 | #define PB_DS_CLASS_C_DEC \ | |
168 | ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, true> | |
169 | ||
170 | /** | |
171 | * Specialization 2- The client supplies a probe function and a ranged | |
172 | * probe function, and requests that hash values not be stored. | |
173 | **/ | |
174 | template<typename Key, typename Hash_Fn, typename _Alloc, | |
175 | typename Comb_Probe_Fn, typename Probe_Fn> | |
176 | class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, | |
177 | Probe_Fn, true> | |
178 | : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn | |
179 | { | |
180 | protected: | |
181 | typedef typename _Alloc::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 rebind_traits<_Alloc, Key>::const_reference | |
187 | key_const_reference; | |
188 | ||
189 | ranged_probe_fn(size_type); | |
190 | ||
191 | ranged_probe_fn(size_type, const Hash_Fn&); | |
192 | ||
193 | ranged_probe_fn(size_type, const Hash_Fn&, | |
194 | const Comb_Probe_Fn&); | |
195 | ||
196 | ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, | |
197 | const Probe_Fn&); | |
198 | ||
199 | void | |
200 | swap(PB_DS_CLASS_C_DEC&); | |
201 | ||
202 | void | |
203 | notify_resized(size_type); | |
204 | ||
205 | inline comp_hash | |
206 | operator()(key_const_reference) const; | |
207 | ||
208 | inline size_type | |
209 | operator()(key_const_reference, size_type, size_type) const; | |
210 | ||
211 | inline size_type | |
212 | operator()(key_const_reference, size_type) const; | |
213 | }; | |
214 | ||
215 | PB_DS_CLASS_T_DEC | |
216 | PB_DS_CLASS_C_DEC:: | |
217 | ranged_probe_fn(size_type size) | |
218 | { Comb_Probe_Fn::notify_resized(size); } | |
219 | ||
220 | PB_DS_CLASS_T_DEC | |
221 | PB_DS_CLASS_C_DEC:: | |
222 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) | |
223 | : Hash_Fn(r_hash_fn) | |
224 | { Comb_Probe_Fn::notify_resized(size); } | |
225 | ||
226 | PB_DS_CLASS_T_DEC | |
227 | PB_DS_CLASS_C_DEC:: | |
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); } | |
232 | ||
233 | PB_DS_CLASS_T_DEC | |
234 | PB_DS_CLASS_C_DEC:: | |
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); } | |
240 | ||
241 | PB_DS_CLASS_T_DEC | |
242 | void | |
243 | PB_DS_CLASS_C_DEC:: | |
244 | swap(PB_DS_CLASS_C_DEC& other) | |
245 | { | |
246 | comb_probe_fn_base::swap(other); | |
247 | std::swap((Hash_Fn& )(*this), (Hash_Fn& )other); | |
248 | } | |
249 | ||
250 | PB_DS_CLASS_T_DEC | |
251 | void | |
252 | PB_DS_CLASS_C_DEC:: | |
253 | notify_resized(size_type size) | |
254 | { comb_probe_fn_base::notify_resized(size); } | |
255 | ||
256 | PB_DS_CLASS_T_DEC | |
257 | inline typename PB_DS_CLASS_C_DEC::comp_hash | |
258 | PB_DS_CLASS_C_DEC:: | |
259 | operator()(key_const_reference r_key) const | |
260 | { | |
261 | const size_type hash = hash_fn_base::operator()(r_key); | |
262 | return std::make_pair(comb_probe_fn_base::operator()(hash), hash); | |
263 | } | |
264 | ||
265 | PB_DS_CLASS_T_DEC | |
266 | inline typename PB_DS_CLASS_C_DEC::size_type | |
267 | PB_DS_CLASS_C_DEC:: | |
268 | operator()(key_const_reference, size_type hash, size_type i) const | |
269 | { | |
270 | return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); | |
271 | } | |
272 | ||
273 | PB_DS_CLASS_T_DEC | |
274 | inline typename PB_DS_CLASS_C_DEC::size_type | |
275 | PB_DS_CLASS_C_DEC:: | |
276 | operator() | |
277 | #ifdef _GLIBCXX_DEBUG | |
278 | (key_const_reference r_key, size_type hash) const | |
279 | #else | |
280 | (key_const_reference /*r_key*/, size_type hash) const | |
281 | #endif | |
282 | { | |
283 | _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key)); | |
284 | return hash; | |
285 | } | |
286 | ||
287 | #undef PB_DS_CLASS_T_DEC | |
288 | #undef PB_DS_CLASS_C_DEC | |
289 | ||
290 | /** | |
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. | |
294 | **/ | |
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 | |
299 | { | |
300 | protected: | |
301 | typedef typename _Alloc::size_type size_type; | |
302 | typedef Comb_Probe_Fn comb_probe_fn_base; | |
303 | typedef typename rebind_traits<_Alloc, Key>::const_reference | |
304 | key_const_reference; | |
305 | ||
306 | ranged_probe_fn(size_type size) | |
307 | { Comb_Probe_Fn::notify_resized(size); } | |
308 | ||
309 | ranged_probe_fn(size_type, const Comb_Probe_Fn& r_comb_probe_fn) | |
310 | : Comb_Probe_Fn(r_comb_probe_fn) | |
311 | { } | |
312 | ||
313 | ranged_probe_fn(size_type, const null_type&, | |
314 | const Comb_Probe_Fn& r_comb_probe_fn, | |
315 | const null_type&) | |
316 | : Comb_Probe_Fn(r_comb_probe_fn) | |
317 | { } | |
318 | ||
319 | void | |
320 | swap(ranged_probe_fn& other) | |
321 | { comb_probe_fn_base::swap(other); } | |
322 | }; | |
323 | } // namespace detail | |
324 | } // namespace __gnu_pbds | |
325 | ||
326 | #endif | |
327 |