libstdc++
ranged_hash_fn.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2020 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 
49 namespace __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
__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