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