3 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
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 2, or (at your option) any later
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.
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
33 // Permission to use, copy, modify, sell, and distribute this software
34 // is hereby granted without fee, provided that the above copyright
35 // notice appears in all copies, and that both that copyright notice
36 // and this permission notice appear in supporting documentation. None
37 // of the above authors, nor IBM Haifa Research Laboratories, make any
38 // representation about the suitability of this software for any
39 // purpose. It is provided "as is" without express or implied
43 * @file ranged_probe_fn.hpp
44 * Contains a unified ranged probe functor, allowing the probe tables to deal with
45 * a single class for ranged probeing.
48 #ifndef PB_DS_RANGED_PROBE_FN_HPP
49 #define PB_DS_RANGED_PROBE_FN_HPP
51 #include <ext/pb_ds/detail/basic_types.hpp>
53 #include <debug/debug.h>
59 template<typename Key
,
62 typename Comb_Probe_Fn
,
65 class ranged_probe_fn
;
67 #define PB_DS_CLASS_T_DEC \
68 template<typename Key, typename Hash_Fn, typename Allocator, \
69 typename Comb_Probe_Fn, typename Probe_Fn>
71 #define PB_DS_CLASS_C_DEC \
72 ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, false>
75 * Specialization 1- The client supplies a probe function and a ranged
76 * probe function, and requests that hash values not be stored.
78 template<typename Key
, typename Hash_Fn
, typename Allocator
,
79 typename Comb_Probe_Fn
, typename Probe_Fn
>
80 class ranged_probe_fn
<Key
, Hash_Fn
, Allocator
, Comb_Probe_Fn
,
82 : public Hash_Fn
, public Comb_Probe_Fn
, public Probe_Fn
85 typedef typename
Allocator::size_type size_type
;
87 typedef Comb_Probe_Fn comb_probe_fn_base
;
89 typedef Hash_Fn hash_fn_base
;
91 typedef Probe_Fn probe_fn_base
;
93 typedef typename
Allocator::template rebind
<Key
>::other key_allocator
;
95 typedef typename
key_allocator::const_reference const_key_reference
;
98 ranged_probe_fn(size_type size
);
100 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
);
102 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
, const Comb_Probe_Fn
& r_comb_probe_fn
);
104 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
, const Comb_Probe_Fn
& r_comb_probe_fn
, const Probe_Fn
& r_probe_fn
);
107 swap(PB_DS_CLASS_C_DEC
& other
);
110 notify_resized(size_type size
);
113 operator()(const_key_reference r_key
) const;
116 operator()(const_key_reference r_key
, size_type hash
, size_type i
) const;
121 ranged_probe_fn(size_type size
)
122 { Comb_Probe_Fn::notify_resized(size
); }
126 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
) :
128 { Comb_Probe_Fn::notify_resized(size
); }
132 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
, const Comb_Probe_Fn
& r_comb_probe_fn
) :
134 Comb_Probe_Fn(r_comb_probe_fn
)
135 { comb_probe_fn_base::notify_resized(size
); }
139 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
, const Comb_Probe_Fn
& r_comb_probe_fn
, const Probe_Fn
& r_probe_fn
) :
141 Comb_Probe_Fn(r_comb_probe_fn
),
143 { comb_probe_fn_base::notify_resized(size
); }
148 swap(PB_DS_CLASS_C_DEC
& other
)
150 comb_probe_fn_base::swap(other
);
151 std::swap((Hash_Fn
& )(*this), (Hash_Fn
&)other
);
157 notify_resized(size_type size
)
158 { comb_probe_fn_base::notify_resized(size
); }
161 inline typename
PB_DS_CLASS_C_DEC::size_type
163 operator()(const_key_reference r_key
) const
164 { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key
)); }
167 inline typename
PB_DS_CLASS_C_DEC::size_type
169 operator()(const_key_reference
, size_type hash
, size_type i
) const
171 return comb_probe_fn_base::operator()(hash
+ probe_fn_base::operator()(i
));
174 #undef PB_DS_CLASS_T_DEC
175 #undef PB_DS_CLASS_C_DEC
177 #define PB_DS_CLASS_T_DEC \
178 template<typename Key, class Hash_Fn, class Allocator, \
179 class Comb_Probe_Fn, class Probe_Fn>
181 #define PB_DS_CLASS_C_DEC \
182 ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, true>
185 * Specialization 2- The client supplies a probe function and a ranged
186 * probe function, and requests that hash values not be stored.
188 template<typename Key
, typename Hash_Fn
, typename Allocator
,
189 typename Comb_Probe_Fn
, typename Probe_Fn
>
190 class ranged_probe_fn
<Key
, Hash_Fn
, Allocator
, Comb_Probe_Fn
,
192 : public Hash_Fn
, public Comb_Probe_Fn
, public Probe_Fn
195 typedef typename
Allocator::size_type size_type
;
197 typedef typename comp_hash_
<size_type
>::comp_hash comp_hash
;
199 typedef Comb_Probe_Fn comb_probe_fn_base
;
201 typedef Hash_Fn hash_fn_base
;
203 typedef Probe_Fn probe_fn_base
;
205 typedef typename
Allocator::template rebind
<Key
>::other key_allocator
;
207 typedef typename
key_allocator::const_reference const_key_reference
;
209 ranged_probe_fn(size_type size
);
211 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
);
213 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
,
214 const Comb_Probe_Fn
& r_comb_probe_fn
);
216 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
,
217 const Comb_Probe_Fn
& r_comb_probe_fn
,
218 const Probe_Fn
& r_probe_fn
);
221 swap(PB_DS_CLASS_C_DEC
& other
);
224 notify_resized(size_type size
);
227 operator()(const_key_reference r_key
) const;
230 operator()(const_key_reference r_key
, size_type hash
, size_type i
) const;
233 operator()(const_key_reference r_key
, size_type hash
) const;
238 ranged_probe_fn(size_type size
)
239 { Comb_Probe_Fn::notify_resized(size
); }
243 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
) :
245 { Comb_Probe_Fn::notify_resized(size
); }
249 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
,
250 const Comb_Probe_Fn
& r_comb_probe_fn
) :
252 Comb_Probe_Fn(r_comb_probe_fn
)
253 { comb_probe_fn_base::notify_resized(size
); }
257 ranged_probe_fn(size_type size
, const Hash_Fn
& r_hash_fn
,
258 const Comb_Probe_Fn
& r_comb_probe_fn
,
259 const Probe_Fn
& r_probe_fn
) :
261 Comb_Probe_Fn(r_comb_probe_fn
),
263 { comb_probe_fn_base::notify_resized(size
); }
268 swap(PB_DS_CLASS_C_DEC
& other
)
270 comb_probe_fn_base::swap(other
);
271 std::swap((Hash_Fn
& )(*this), (Hash_Fn
& )other
);
277 notify_resized(size_type size
)
278 { comb_probe_fn_base::notify_resized(size
); }
281 inline typename
PB_DS_CLASS_C_DEC::comp_hash
283 operator()(const_key_reference r_key
) const
285 const size_type hash
= hash_fn_base::operator()(r_key
);
286 return std::make_pair(comb_probe_fn_base::operator()(hash
), hash
);
290 inline typename
PB_DS_CLASS_C_DEC::size_type
292 operator()(const_key_reference
, size_type hash
, size_type i
) const
294 return comb_probe_fn_base::operator()(hash
+ probe_fn_base::operator()(i
));
298 inline typename
PB_DS_CLASS_C_DEC::size_type
301 #ifdef _GLIBCXX_DEBUG
302 (const_key_reference r_key
, size_type hash
) const
304 (const_key_reference
/*r_key*/, size_type hash
) const
307 _GLIBCXX_DEBUG_ASSERT(hash
== hash_fn_base::operator()(r_key
));
311 #undef PB_DS_CLASS_T_DEC
312 #undef PB_DS_CLASS_C_DEC
315 * Specialization 3 and 4- The client does not supply a hash function or
316 * probe function, and requests that hash values not be stored.
318 template<typename Key
, typename Allocator
, typename Comb_Probe_Fn
>
319 class ranged_probe_fn
<Key
, null_hash_fn
, Allocator
, Comb_Probe_Fn
,
320 null_probe_fn
, false>
321 : public Comb_Probe_Fn
, public null_hash_fn
, public null_probe_fn
324 typedef typename
Allocator::size_type size_type
;
326 typedef Comb_Probe_Fn comb_probe_fn_base
;
328 typedef typename
Allocator::template rebind
<Key
>::other key_allocator
;
330 typedef typename
key_allocator::const_reference const_key_reference
;
332 ranged_probe_fn(size_type size
)
333 { Comb_Probe_Fn::notify_resized(size
); }
335 ranged_probe_fn(size_type size
, const Comb_Probe_Fn
& r_comb_probe_fn
)
336 : Comb_Probe_Fn(r_comb_probe_fn
)
339 ranged_probe_fn(size_type size
, const null_hash_fn
& r_null_hash_fn
,
340 const Comb_Probe_Fn
& r_comb_probe_fn
,
341 const null_probe_fn
& r_null_probe_fn
)
342 : Comb_Probe_Fn(r_comb_probe_fn
)
346 swap(ranged_probe_fn
& other
)
347 { comb_probe_fn_base::swap(other
); }
349 } // namespace detail