]>
Commit | Line | Data |
---|---|---|
df7eb3d5 | 1 | // -*- C++ -*- |
2 | ||
fbd26352 | 3 | // Copyright (C) 2005-2019 Free Software Foundation, Inc. |
df7eb3d5 | 4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
36fed23c | 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 | |
6bc9506f | 8 | // Foundation; either version 3, or (at your option) any later |
36fed23c | 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 | ||
6bc9506f | 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. | |
36fed23c | 19 | |
6bc9506f | 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/>. | |
df7eb3d5 | 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 | |
36fed23c | 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 | |
df7eb3d5 | 32 | // representation about the suitability of this software for any |
36fed23c | 33 | // purpose. It is provided "as is" without express or implied |
34 | // warranty. | |
df7eb3d5 | 35 | |
36 | /** | |
37 | * @file ranged_probe_fn.hpp | |
38 | * Contains a unified ranged probe functor, allowing the probe tables to deal with | |
36fed23c | 39 | * a single class for ranged probeing. |
df7eb3d5 | 40 | */ |
41 | ||
36fed23c | 42 | #ifndef PB_DS_RANGED_PROBE_FN_HPP |
43 | #define PB_DS_RANGED_PROBE_FN_HPP | |
df7eb3d5 | 44 | |
df7eb3d5 | 45 | #include <utility> |
2b31bec4 | 46 | #include <debug/debug.h> |
df7eb3d5 | 47 | |
b34535d7 | 48 | namespace __gnu_pbds |
df7eb3d5 | 49 | { |
df7eb3d5 | 50 | namespace detail |
51 | { | |
3f2eba6f | 52 | /// Primary template. |
4f4a327e | 53 | template<typename Key, typename Hash_Fn, typename _Alloc, |
22b8335e | 54 | typename Comb_Probe_Fn, typename Probe_Fn, bool Store_Hash> |
df7eb3d5 | 55 | class ranged_probe_fn; |
56 | ||
ce8b0a77 | 57 | #define PB_DS_CLASS_T_DEC \ |
4f4a327e | 58 | template<typename Key, typename Hash_Fn, typename _Alloc, \ |
ce8b0a77 | 59 | typename Comb_Probe_Fn, typename Probe_Fn> |
60 | ||
61 | #define PB_DS_CLASS_C_DEC \ | |
4f4a327e | 62 | ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, false> |
df7eb3d5 | 63 | |
64 | /** | |
22b8335e | 65 | * Specialization 1 |
66 | * The client supplies a probe function and a ranged probe | |
67 | * function, and requests that hash values not be stored. | |
df7eb3d5 | 68 | **/ |
4f4a327e | 69 | template<typename Key, typename Hash_Fn, typename _Alloc, |
ce8b0a77 | 70 | typename Comb_Probe_Fn, typename Probe_Fn> |
4f4a327e | 71 | class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, |
ce8b0a77 | 72 | Probe_Fn, false> |
73 | : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn | |
df7eb3d5 | 74 | { |
75 | protected: | |
4f4a327e | 76 | typedef typename _Alloc::size_type size_type; |
36fed23c | 77 | typedef Comb_Probe_Fn comb_probe_fn_base; |
36fed23c | 78 | typedef Hash_Fn hash_fn_base; |
36fed23c | 79 | typedef Probe_Fn probe_fn_base; |
4f4a327e | 80 | typedef typename _Alloc::template rebind<Key>::other key_allocator; |
81 | typedef typename key_allocator::const_reference key_const_reference; | |
df7eb3d5 | 82 | |
22b8335e | 83 | ranged_probe_fn(size_type); |
df7eb3d5 | 84 | |
22b8335e | 85 | ranged_probe_fn(size_type, const Hash_Fn&); |
df7eb3d5 | 86 | |
22b8335e | 87 | ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&); |
df7eb3d5 | 88 | |
22b8335e | 89 | ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, |
90 | const Probe_Fn&); | |
df7eb3d5 | 91 | |
92 | void | |
22b8335e | 93 | swap(PB_DS_CLASS_C_DEC&); |
df7eb3d5 | 94 | |
95 | void | |
22b8335e | 96 | notify_resized(size_type); |
df7eb3d5 | 97 | |
98 | inline size_type | |
4f4a327e | 99 | operator()(key_const_reference) const; |
df7eb3d5 | 100 | |
101 | inline size_type | |
4f4a327e | 102 | operator()(key_const_reference, size_type, size_type) const; |
df7eb3d5 | 103 | }; |
104 | ||
36fed23c | 105 | PB_DS_CLASS_T_DEC |
106 | PB_DS_CLASS_C_DEC:: | |
df7eb3d5 | 107 | ranged_probe_fn(size_type size) |
ce8b0a77 | 108 | { Comb_Probe_Fn::notify_resized(size); } |
df7eb3d5 | 109 | |
36fed23c | 110 | PB_DS_CLASS_T_DEC |
111 | PB_DS_CLASS_C_DEC:: | |
22b8335e | 112 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) |
113 | : Hash_Fn(r_hash_fn) | |
ce8b0a77 | 114 | { Comb_Probe_Fn::notify_resized(size); } |
df7eb3d5 | 115 | |
36fed23c | 116 | PB_DS_CLASS_T_DEC |
117 | PB_DS_CLASS_C_DEC:: | |
22b8335e | 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) | |
ce8b0a77 | 121 | { comb_probe_fn_base::notify_resized(size); } |
df7eb3d5 | 122 | |
36fed23c | 123 | PB_DS_CLASS_T_DEC |
124 | PB_DS_CLASS_C_DEC:: | |
22b8335e | 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) | |
ce8b0a77 | 129 | { comb_probe_fn_base::notify_resized(size); } |
df7eb3d5 | 130 | |
36fed23c | 131 | PB_DS_CLASS_T_DEC |
df7eb3d5 | 132 | void |
36fed23c | 133 | PB_DS_CLASS_C_DEC:: |
134 | swap(PB_DS_CLASS_C_DEC& other) | |
df7eb3d5 | 135 | { |
36fed23c | 136 | comb_probe_fn_base::swap(other); |
ce8b0a77 | 137 | std::swap((Hash_Fn& )(*this), (Hash_Fn&)other); |
df7eb3d5 | 138 | } |
139 | ||
36fed23c | 140 | PB_DS_CLASS_T_DEC |
df7eb3d5 | 141 | void |
36fed23c | 142 | PB_DS_CLASS_C_DEC:: |
df7eb3d5 | 143 | notify_resized(size_type size) |
ce8b0a77 | 144 | { comb_probe_fn_base::notify_resized(size); } |
df7eb3d5 | 145 | |
36fed23c | 146 | PB_DS_CLASS_T_DEC |
147 | inline typename PB_DS_CLASS_C_DEC::size_type | |
148 | PB_DS_CLASS_C_DEC:: | |
4f4a327e | 149 | operator()(key_const_reference r_key) const |
ce8b0a77 | 150 | { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); } |
df7eb3d5 | 151 | |
36fed23c | 152 | PB_DS_CLASS_T_DEC |
153 | inline typename PB_DS_CLASS_C_DEC::size_type | |
154 | PB_DS_CLASS_C_DEC:: | |
4f4a327e | 155 | operator()(key_const_reference, size_type hash, size_type i) const |
df7eb3d5 | 156 | { |
ce8b0a77 | 157 | return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); |
df7eb3d5 | 158 | } |
159 | ||
36fed23c | 160 | #undef PB_DS_CLASS_T_DEC |
161 | #undef PB_DS_CLASS_C_DEC | |
162 | ||
ce8b0a77 | 163 | #define PB_DS_CLASS_T_DEC \ |
4f4a327e | 164 | template<typename Key, typename Hash_Fn, typename _Alloc, \ |
22b8335e | 165 | typename Comb_Probe_Fn, typename Probe_Fn> |
ce8b0a77 | 166 | |
167 | #define PB_DS_CLASS_C_DEC \ | |
4f4a327e | 168 | ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, true> |
df7eb3d5 | 169 | |
170 | /** | |
171 | * Specialization 2- The client supplies a probe function and a ranged | |
36fed23c | 172 | * probe function, and requests that hash values not be stored. |
df7eb3d5 | 173 | **/ |
4f4a327e | 174 | template<typename Key, typename Hash_Fn, typename _Alloc, |
ce8b0a77 | 175 | typename Comb_Probe_Fn, typename Probe_Fn> |
4f4a327e | 176 | class ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, |
ce8b0a77 | 177 | Probe_Fn, true> |
178 | : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn | |
df7eb3d5 | 179 | { |
180 | protected: | |
4f4a327e | 181 | typedef typename _Alloc::size_type size_type; |
22b8335e | 182 | typedef std::pair<size_type, size_type> comp_hash; |
36fed23c | 183 | typedef Comb_Probe_Fn comb_probe_fn_base; |
36fed23c | 184 | typedef Hash_Fn hash_fn_base; |
36fed23c | 185 | typedef Probe_Fn probe_fn_base; |
4f4a327e | 186 | typedef typename _Alloc::template rebind<Key>::other key_allocator; |
187 | typedef typename key_allocator::const_reference key_const_reference; | |
df7eb3d5 | 188 | |
22b8335e | 189 | ranged_probe_fn(size_type); |
df7eb3d5 | 190 | |
22b8335e | 191 | ranged_probe_fn(size_type, const Hash_Fn&); |
df7eb3d5 | 192 | |
22b8335e | 193 | ranged_probe_fn(size_type, const Hash_Fn&, |
194 | const Comb_Probe_Fn&); | |
df7eb3d5 | 195 | |
22b8335e | 196 | ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&, |
197 | const Probe_Fn&); | |
df7eb3d5 | 198 | |
199 | void | |
22b8335e | 200 | swap(PB_DS_CLASS_C_DEC&); |
df7eb3d5 | 201 | |
202 | void | |
22b8335e | 203 | notify_resized(size_type); |
df7eb3d5 | 204 | |
205 | inline comp_hash | |
4f4a327e | 206 | operator()(key_const_reference) const; |
df7eb3d5 | 207 | |
208 | inline size_type | |
4f4a327e | 209 | operator()(key_const_reference, size_type, size_type) const; |
df7eb3d5 | 210 | |
211 | inline size_type | |
4f4a327e | 212 | operator()(key_const_reference, size_type) const; |
df7eb3d5 | 213 | }; |
214 | ||
36fed23c | 215 | PB_DS_CLASS_T_DEC |
216 | PB_DS_CLASS_C_DEC:: | |
df7eb3d5 | 217 | ranged_probe_fn(size_type size) |
2b31bec4 | 218 | { Comb_Probe_Fn::notify_resized(size); } |
df7eb3d5 | 219 | |
36fed23c | 220 | PB_DS_CLASS_T_DEC |
221 | PB_DS_CLASS_C_DEC:: | |
22b8335e | 222 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) |
223 | : Hash_Fn(r_hash_fn) | |
2b31bec4 | 224 | { Comb_Probe_Fn::notify_resized(size); } |
df7eb3d5 | 225 | |
36fed23c | 226 | PB_DS_CLASS_T_DEC |
227 | PB_DS_CLASS_C_DEC:: | |
ce8b0a77 | 228 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, |
22b8335e | 229 | const Comb_Probe_Fn& r_comb_probe_fn) |
230 | : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn) | |
2b31bec4 | 231 | { comb_probe_fn_base::notify_resized(size); } |
df7eb3d5 | 232 | |
36fed23c | 233 | PB_DS_CLASS_T_DEC |
234 | PB_DS_CLASS_C_DEC:: | |
ce8b0a77 | 235 | ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, |
236 | const Comb_Probe_Fn& r_comb_probe_fn, | |
22b8335e | 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) | |
2b31bec4 | 239 | { comb_probe_fn_base::notify_resized(size); } |
df7eb3d5 | 240 | |
36fed23c | 241 | PB_DS_CLASS_T_DEC |
df7eb3d5 | 242 | void |
36fed23c | 243 | PB_DS_CLASS_C_DEC:: |
244 | swap(PB_DS_CLASS_C_DEC& other) | |
df7eb3d5 | 245 | { |
36fed23c | 246 | comb_probe_fn_base::swap(other); |
36fed23c | 247 | std::swap((Hash_Fn& )(*this), (Hash_Fn& )other); |
df7eb3d5 | 248 | } |
249 | ||
36fed23c | 250 | PB_DS_CLASS_T_DEC |
df7eb3d5 | 251 | void |
36fed23c | 252 | PB_DS_CLASS_C_DEC:: |
df7eb3d5 | 253 | notify_resized(size_type size) |
2b31bec4 | 254 | { comb_probe_fn_base::notify_resized(size); } |
df7eb3d5 | 255 | |
36fed23c | 256 | PB_DS_CLASS_T_DEC |
257 | inline typename PB_DS_CLASS_C_DEC::comp_hash | |
258 | PB_DS_CLASS_C_DEC:: | |
4f4a327e | 259 | operator()(key_const_reference r_key) const |
df7eb3d5 | 260 | { |
36fed23c | 261 | const size_type hash = hash_fn_base::operator()(r_key); |
2b31bec4 | 262 | return std::make_pair(comb_probe_fn_base::operator()(hash), hash); |
df7eb3d5 | 263 | } |
264 | ||
36fed23c | 265 | PB_DS_CLASS_T_DEC |
266 | inline typename PB_DS_CLASS_C_DEC::size_type | |
267 | PB_DS_CLASS_C_DEC:: | |
4f4a327e | 268 | operator()(key_const_reference, size_type hash, size_type i) const |
df7eb3d5 | 269 | { |
2b31bec4 | 270 | return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i)); |
df7eb3d5 | 271 | } |
272 | ||
36fed23c | 273 | PB_DS_CLASS_T_DEC |
274 | inline typename PB_DS_CLASS_C_DEC::size_type | |
275 | PB_DS_CLASS_C_DEC:: | |
df7eb3d5 | 276 | operator() |
2b31bec4 | 277 | #ifdef _GLIBCXX_DEBUG |
4f4a327e | 278 | (key_const_reference r_key, size_type hash) const |
2b31bec4 | 279 | #else |
4f4a327e | 280 | (key_const_reference /*r_key*/, size_type hash) const |
2b31bec4 | 281 | #endif |
df7eb3d5 | 282 | { |
2b31bec4 | 283 | _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key)); |
284 | return hash; | |
df7eb3d5 | 285 | } |
286 | ||
36fed23c | 287 | #undef PB_DS_CLASS_T_DEC |
288 | #undef PB_DS_CLASS_C_DEC | |
df7eb3d5 | 289 | |
df7eb3d5 | 290 | /** |
22b8335e | 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. | |
df7eb3d5 | 294 | **/ |
4f4a327e | 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 | |
df7eb3d5 | 299 | { |
300 | protected: | |
4f4a327e | 301 | typedef typename _Alloc::size_type size_type; |
36fed23c | 302 | typedef Comb_Probe_Fn comb_probe_fn_base; |
4f4a327e | 303 | typedef typename _Alloc::template rebind<Key>::other key_allocator; |
304 | typedef typename key_allocator::const_reference key_const_reference; | |
df7eb3d5 | 305 | |
ce8b0a77 | 306 | ranged_probe_fn(size_type size) |
307 | { Comb_Probe_Fn::notify_resized(size); } | |
df7eb3d5 | 308 | |
22b8335e | 309 | ranged_probe_fn(size_type, const Comb_Probe_Fn& r_comb_probe_fn) |
ce8b0a77 | 310 | : Comb_Probe_Fn(r_comb_probe_fn) |
311 | { } | |
df7eb3d5 | 312 | |
4f4a327e | 313 | ranged_probe_fn(size_type, const null_type&, |
ce8b0a77 | 314 | const Comb_Probe_Fn& r_comb_probe_fn, |
4f4a327e | 315 | const null_type&) |
ce8b0a77 | 316 | : Comb_Probe_Fn(r_comb_probe_fn) |
317 | { } | |
df7eb3d5 | 318 | |
319 | void | |
ce8b0a77 | 320 | swap(ranged_probe_fn& other) |
321 | { comb_probe_fn_base::swap(other); } | |
df7eb3d5 | 322 | }; |
df7eb3d5 | 323 | } // namespace detail |
b34535d7 | 324 | } // namespace __gnu_pbds |
df7eb3d5 | 325 | |
2b31bec4 | 326 | #endif |
df7eb3d5 | 327 |