libstdc++
ranged_hash_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_hash_fn.hpp
38 * Contains a unified ranged hash functor, allowing the hash tables
39 * to deal with a single class for ranged hashing.
40 */
41
42#ifndef PB_DS_RANGED_HASH_FN_HPP
43#define PB_DS_RANGED_HASH_FN_HPP
44
45#include <utility>
46#include <ext/pb_ds/detail/types_traits.hpp>
47#include <debug/debug.h>
48
49namespace __gnu_pbds
50{
51 namespace detail
52 {
53 /// Primary template.
54 template<typename Key, typename Hash_Fn, typename _Alloc,
55 typename Comb_Hash_Fn, bool Store_Hash>
56 class ranged_hash_fn;
57
58#define PB_DS_CLASS_T_DEC \
59 template<typename Key, typename Hash_Fn, typename _Alloc, \
60 typename Comb_Hash_Fn>
61
62#define PB_DS_CLASS_C_DEC \
63 ranged_hash_fn<Key, Hash_Fn, _Alloc, Comb_Hash_Fn, false>
64
65 /**
66 * Specialization 1
67 * The client supplies a hash function and a ranged hash function,
68 * and requests that hash values not be stored.
69 **/
70 template<typename Key, typename Hash_Fn, typename _Alloc,
71 typename Comb_Hash_Fn>
72 class ranged_hash_fn< Key, Hash_Fn, _Alloc, Comb_Hash_Fn, false>
73 : public Hash_Fn, public Comb_Hash_Fn
74 {
75 protected:
76 typedef typename _Alloc::size_type size_type;
77 typedef Hash_Fn hash_fn_base;
78 typedef Comb_Hash_Fn comb_hash_fn_base;
79 typedef typename rebind_traits<_Alloc, Key>::const_reference
80 key_const_reference;
81
82 ranged_hash_fn(size_type);
83
84 ranged_hash_fn(size_type, const Hash_Fn&);
85
86 ranged_hash_fn(size_type, const Hash_Fn&, const Comb_Hash_Fn&);
87
88 void
89 swap(PB_DS_CLASS_C_DEC&);
90
91 void
92 notify_resized(size_type);
93
94 inline size_type
95 operator()(key_const_reference) const;
96 };
97
98 PB_DS_CLASS_T_DEC
99 PB_DS_CLASS_C_DEC::
100 ranged_hash_fn(size_type size)
101 { Comb_Hash_Fn::notify_resized(size); }
102
103 PB_DS_CLASS_T_DEC
104 PB_DS_CLASS_C_DEC::
105 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn)
106 : Hash_Fn(r_hash_fn)
107 { Comb_Hash_Fn::notify_resized(size); }
108
109 PB_DS_CLASS_T_DEC
110 PB_DS_CLASS_C_DEC::
111 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn,
112 const Comb_Hash_Fn& r_comb_hash_fn)
113 : Hash_Fn(r_hash_fn), Comb_Hash_Fn(r_comb_hash_fn)
114 { comb_hash_fn_base::notify_resized(size); }
115
116 PB_DS_CLASS_T_DEC
117 void
118 PB_DS_CLASS_C_DEC::
119 swap(PB_DS_CLASS_C_DEC& other)
120 {
121 comb_hash_fn_base::swap(other);
122 std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
123 }
124
125 PB_DS_CLASS_T_DEC
126 void
127 PB_DS_CLASS_C_DEC::
128 notify_resized(size_type size)
129 { comb_hash_fn_base::notify_resized(size); }
130
131 PB_DS_CLASS_T_DEC
132 inline typename PB_DS_CLASS_C_DEC::size_type
133 PB_DS_CLASS_C_DEC::
134 operator()(key_const_reference r_key) const
135 { return (comb_hash_fn_base::operator()(hash_fn_base::operator()(r_key)));}
136
137#undef PB_DS_CLASS_T_DEC
138#undef PB_DS_CLASS_C_DEC
139
140#define PB_DS_CLASS_T_DEC \
141 template<typename Key, typename Hash_Fn, typename _Alloc, \
142 typename Comb_Hash_Fn>
143
144#define PB_DS_CLASS_C_DEC \
145 ranged_hash_fn<Key,Hash_Fn, _Alloc, Comb_Hash_Fn, true>
146
147 /**
148 * Specialization 2
149 * The client supplies a hash function and a ranged hash function,
150 * and requests that hash values be stored.
151 **/
152 template<typename Key, typename Hash_Fn, typename _Alloc,
153 typename Comb_Hash_Fn>
154 class ranged_hash_fn<Key, Hash_Fn, _Alloc, Comb_Hash_Fn, true>
155 : public Hash_Fn, public Comb_Hash_Fn
156 {
157 protected:
158 typedef typename _Alloc::size_type size_type;
159 typedef std::pair<size_type, size_type> comp_hash;
160 typedef Hash_Fn hash_fn_base;
161 typedef Comb_Hash_Fn comb_hash_fn_base;
162 typedef typename rebind_traits<_Alloc, Key>::const_reference
163 key_const_reference;
164
165 ranged_hash_fn(size_type);
166
167 ranged_hash_fn(size_type, const Hash_Fn&);
168
169 ranged_hash_fn(size_type, const Hash_Fn&, const Comb_Hash_Fn&);
170
171 void
172 swap(PB_DS_CLASS_C_DEC&);
173
174 void
175 notify_resized(size_type);
176
177 inline comp_hash
178 operator()(key_const_reference) const;
179
180 inline comp_hash
181 operator()(key_const_reference, size_type) const;
182 };
183
184 PB_DS_CLASS_T_DEC
185 PB_DS_CLASS_C_DEC::
186 ranged_hash_fn(size_type size)
187 { Comb_Hash_Fn::notify_resized(size); }
188
189 PB_DS_CLASS_T_DEC
190 PB_DS_CLASS_C_DEC::
191 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn) :
192 Hash_Fn(r_hash_fn)
193 { Comb_Hash_Fn::notify_resized(size); }
194
195 PB_DS_CLASS_T_DEC
196 PB_DS_CLASS_C_DEC::
197 ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn,
198 const Comb_Hash_Fn& r_comb_hash_fn)
199 : Hash_Fn(r_hash_fn), Comb_Hash_Fn(r_comb_hash_fn)
200 { comb_hash_fn_base::notify_resized(size); }
201
202 PB_DS_CLASS_T_DEC
203 void
204 PB_DS_CLASS_C_DEC::
205 swap(PB_DS_CLASS_C_DEC& other)
206 {
207 comb_hash_fn_base::swap(other);
208 std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
209 }
210
211 PB_DS_CLASS_T_DEC
212 void
213 PB_DS_CLASS_C_DEC::
214 notify_resized(size_type size)
215 { comb_hash_fn_base::notify_resized(size); }
216
217 PB_DS_CLASS_T_DEC
218 inline typename PB_DS_CLASS_C_DEC::comp_hash
219 PB_DS_CLASS_C_DEC::
220 operator()(key_const_reference r_key) const
221 {
222 const size_type hash = hash_fn_base::operator()(r_key);
223 return std::make_pair(comb_hash_fn_base::operator()(hash), hash);
224 }
225
226 PB_DS_CLASS_T_DEC
227 inline typename PB_DS_CLASS_C_DEC::comp_hash
228 PB_DS_CLASS_C_DEC::
229 operator()
230#ifdef _GLIBCXX_DEBUG
231 (key_const_reference r_key, size_type hash) const
232#else
233 (key_const_reference /*r_key*/, size_type hash) const
234#endif
235 {
236 _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key));
237 return std::make_pair(comb_hash_fn_base::operator()(hash), hash);
238 }
239
240#undef PB_DS_CLASS_T_DEC
241#undef PB_DS_CLASS_C_DEC
242
243#define PB_DS_CLASS_T_DEC \
244 template<typename Key, typename _Alloc, typename Comb_Hash_Fn>
245
246#define PB_DS_CLASS_C_DEC \
247 ranged_hash_fn<Key, null_type, _Alloc, Comb_Hash_Fn, false>
248
249 /**
250 * Specialization 3
251 * The client does not supply a hash function (by specifying
252 * null_type as the Hash_Fn parameter), and requests that hash
253 * values not be stored.
254 **/
255 template<typename Key, typename _Alloc, typename Comb_Hash_Fn>
256 class ranged_hash_fn<Key, null_type, _Alloc, Comb_Hash_Fn, false>
257 : public Comb_Hash_Fn
258 {
259 protected:
260 typedef typename _Alloc::size_type size_type;
261 typedef Comb_Hash_Fn comb_hash_fn_base;
262
263 ranged_hash_fn(size_type);
264
265 ranged_hash_fn(size_type, const Comb_Hash_Fn&);
266
267 ranged_hash_fn(size_type, const null_type&, const Comb_Hash_Fn&);
268
269 void
270 swap(PB_DS_CLASS_C_DEC&);
271 };
272
273 PB_DS_CLASS_T_DEC
274 PB_DS_CLASS_C_DEC::
275 ranged_hash_fn(size_type size)
276 { Comb_Hash_Fn::notify_resized(size); }
277
278 PB_DS_CLASS_T_DEC
279 PB_DS_CLASS_C_DEC::
280 ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn) :
281 Comb_Hash_Fn(r_comb_hash_fn)
282 { }
283
284 PB_DS_CLASS_T_DEC
285 PB_DS_CLASS_C_DEC::
286 ranged_hash_fn(size_type size, const null_type& r_null_type,
287 const Comb_Hash_Fn& r_comb_hash_fn)
288 : Comb_Hash_Fn(r_comb_hash_fn)
289 { }
290
291 PB_DS_CLASS_T_DEC
292 void
293 PB_DS_CLASS_C_DEC::
294 swap(PB_DS_CLASS_C_DEC& other)
295 { comb_hash_fn_base::swap(other); }
296
297#undef PB_DS_CLASS_T_DEC
298#undef PB_DS_CLASS_C_DEC
299
300#define PB_DS_CLASS_T_DEC \
301 template<typename Key, typename _Alloc, typename Comb_Hash_Fn>
302
303#define PB_DS_CLASS_C_DEC \
304 ranged_hash_fn<Key, null_type, _Alloc, Comb_Hash_Fn, true>
305
306 /**
307 * Specialization 4
308 * The client does not supply a hash function (by specifying
309 * null_type as the Hash_Fn parameter), and requests that hash
310 * values be stored.
311 **/
312 template<typename Key, typename _Alloc, typename Comb_Hash_Fn>
313 class ranged_hash_fn<Key, null_type, _Alloc, Comb_Hash_Fn, true>
314 : public Comb_Hash_Fn
315 {
316 protected:
317 typedef typename _Alloc::size_type size_type;
318 typedef Comb_Hash_Fn comb_hash_fn_base;
319
320 ranged_hash_fn(size_type);
321
322 ranged_hash_fn(size_type, const Comb_Hash_Fn&);
323
324 ranged_hash_fn(size_type, const null_type&, const Comb_Hash_Fn&);
325
326 void
327 swap(PB_DS_CLASS_C_DEC&);
328 };
329
330 PB_DS_CLASS_T_DEC
331 PB_DS_CLASS_C_DEC::
332 ranged_hash_fn(size_type size)
333 { Comb_Hash_Fn::notify_resized(size); }
334
335 PB_DS_CLASS_T_DEC
336 PB_DS_CLASS_C_DEC::
337 ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn)
338 : Comb_Hash_Fn(r_comb_hash_fn)
339 { }
340
341 PB_DS_CLASS_T_DEC
342 PB_DS_CLASS_C_DEC::
343 ranged_hash_fn(size_type size, const null_type& r_null_type,
344 const Comb_Hash_Fn& r_comb_hash_fn)
345 : Comb_Hash_Fn(r_comb_hash_fn)
346 { }
347
348 PB_DS_CLASS_T_DEC
349 void
350 PB_DS_CLASS_C_DEC::
351 swap(PB_DS_CLASS_C_DEC& other)
352 { comb_hash_fn_base::swap(other); }
353
354#undef PB_DS_CLASS_T_DEC
355#undef PB_DS_CLASS_C_DEC
356
357 } // namespace detail
358} // namespace __gnu_pbds
359
360#endif
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