1// -*- C++ -*-
2
3// Copyright (C) 2005-2015 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 _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