1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2018 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 _Alloc::template rebind<Key>::other key_allocator;
81       typedef typename key_allocator::const_reference 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 _Alloc::template rebind<Key>::other key_allocator;
187       typedef typename key_allocator::const_reference 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 _Alloc::template rebind<Key>::other key_allocator;
304       typedef typename key_allocator::const_reference 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 
328