libstdc++
ranged_probe_fn.hpp
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2005-2021 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
48namespace __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
std::swap
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
Definition: any:428
__gnu_pbds
GNU extensions for policy-based data structures for public use.
Definition: assoc_container.hpp:52
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:213
__gnu_pbds::null_type
Represents no type, or absence of type, for template tricks.
Definition: tag_and_trait.hpp:210