]>
Commit | Line | Data |
---|---|---|
36fed23c | 1 | // -*- C++ -*- |
2 | ||
f1717362 | 3 | // Copyright (C) 2005-2016 Free Software Foundation, Inc. |
36fed23c | 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 | |
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/>. | |
36fed23c | 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 | /** | |
4f4a327e | 37 | * @file gp_hash_table_map_/gp_ht_map_.hpp |
38 | * Contains an implementation class for general probing hash. | |
36fed23c | 39 | */ |
40 | ||
41 | #include <ext/pb_ds/tag_and_trait.hpp> | |
42 | #include <ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp> | |
43 | #include <ext/pb_ds/detail/types_traits.hpp> | |
44 | #include <ext/pb_ds/exception.hpp> | |
45 | #include <ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp> | |
46 | #include <utility> | |
47 | #ifdef PB_DS_HT_MAP_TRACE_ | |
48 | #include <iostream> | |
4f4a327e | 49 | #endif |
2b31bec4 | 50 | #ifdef _GLIBCXX_DEBUG |
6c9bd031 | 51 | #include <ext/pb_ds/detail/debug_map_base.hpp> |
2b31bec4 | 52 | #endif |
53 | #include <debug/debug.h> | |
36fed23c | 54 | |
b34535d7 | 55 | namespace __gnu_pbds |
36fed23c | 56 | { |
57 | namespace detail | |
58 | { | |
36fed23c | 59 | #ifdef PB_DS_DATA_TRUE_INDICATOR |
4f4a327e | 60 | #define PB_DS_GP_HASH_NAME gp_ht_map |
2b31bec4 | 61 | #endif |
36fed23c | 62 | |
63 | #ifdef PB_DS_DATA_FALSE_INDICATOR | |
4f4a327e | 64 | #define PB_DS_GP_HASH_NAME gp_ht_set |
65 | #endif | |
66 | ||
67 | #define PB_DS_CLASS_T_DEC \ | |
68 | template<typename Key, typename Mapped, typename Hash_Fn, typename Eq_Fn, \ | |
69 | typename _Alloc, bool Store_Hash, typename Comb_Probe_Fn, \ | |
70 | typename Probe_Fn, typename Resize_Policy> | |
36fed23c | 71 | |
ce8b0a77 | 72 | #define PB_DS_CLASS_C_DEC \ |
4f4a327e | 73 | PB_DS_GP_HASH_NAME<Key, Mapped, Hash_Fn, Eq_Fn, _Alloc, \ |
74 | Store_Hash, Comb_Probe_Fn, Probe_Fn, Resize_Policy> | |
ce8b0a77 | 75 | |
76 | #define PB_DS_HASH_EQ_FN_C_DEC \ | |
4f4a327e | 77 | hash_eq_fn<Key, Eq_Fn, _Alloc, Store_Hash> |
ce8b0a77 | 78 | |
79 | #define PB_DS_RANGED_PROBE_FN_C_DEC \ | |
4f4a327e | 80 | ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, Store_Hash> |
ce8b0a77 | 81 | |
4f4a327e | 82 | #define PB_DS_GP_HASH_TRAITS_BASE \ |
83 | types_traits<Key, Mapped, _Alloc, Store_Hash> | |
36fed23c | 84 | |
2b31bec4 | 85 | #ifdef _GLIBCXX_DEBUG |
6c9bd031 | 86 | #define PB_DS_DEBUG_MAP_BASE_C_DEC \ |
4f4a327e | 87 | debug_map_base<Key, Eq_Fn, \ |
88 | typename _Alloc::template rebind<Key>::other::const_reference> | |
2548203e | 89 | #endif |
90 | ||
4f4a327e | 91 | |
3f2eba6f | 92 | /** |
93 | * A general-probing hash-based container. | |
94 | * | |
95 | * | |
96 | * @ingroup hash-detail | |
97 | * | |
98 | * @tparam Key Key type. | |
99 | * | |
100 | * @tparam Mapped Map type. | |
101 | * | |
102 | * @tparam Hash_Fn Hashing functor. | |
103 | * Default is __gnu_cxx::hash. | |
104 | * | |
105 | * @tparam Eq_Fn Equal functor. | |
106 | * Default std::equal_to<Key> | |
107 | * | |
108 | * @tparam _Alloc Allocator type. | |
109 | * | |
110 | * @tparam Store_Hash If key type stores extra metadata. | |
111 | * Defaults to false. | |
112 | * | |
113 | * @tparam Comb_Probe_Fn Combining probe functor. | |
114 | * If Hash_Fn is not null_type, then this | |
115 | * is the ranged-probe functor; otherwise, | |
116 | * this is the range-hashing functor. | |
117 | * XXX See Design::Hash-Based Containers::Hash Policies. | |
118 | * Default direct_mask_range_hashing. | |
119 | * | |
120 | * @tparam Probe_Fn Probe functor. | |
121 | * Defaults to linear_probe_fn, | |
122 | * also quadratic_probe_fn. | |
123 | * | |
124 | * @tparam Resize_Policy Resizes hash. | |
125 | * Defaults to hash_standard_resize_policy, | |
126 | * using hash_exponential_size_policy and | |
127 | * hash_load_check_resize_trigger. | |
128 | * | |
129 | * | |
130 | * Bases are: detail::hash_eq_fn, Resize_Policy, detail::ranged_probe_fn, | |
131 | * detail::types_traits. (Optional: detail::debug_map_base.) | |
132 | */ | |
36fed23c | 133 | template<typename Key, |
134 | typename Mapped, | |
ce8b0a77 | 135 | typename Hash_Fn, |
136 | typename Eq_Fn, | |
4f4a327e | 137 | typename _Alloc, |
36fed23c | 138 | bool Store_Hash, |
ce8b0a77 | 139 | typename Comb_Probe_Fn, |
140 | typename Probe_Fn, | |
141 | typename Resize_Policy> | |
4f4a327e | 142 | class PB_DS_GP_HASH_NAME : |
2b31bec4 | 143 | #ifdef _GLIBCXX_DEBUG |
6c9bd031 | 144 | protected PB_DS_DEBUG_MAP_BASE_C_DEC, |
4f4a327e | 145 | #endif |
36fed23c | 146 | public PB_DS_HASH_EQ_FN_C_DEC, |
147 | public Resize_Policy, | |
148 | public PB_DS_RANGED_PROBE_FN_C_DEC, | |
4f4a327e | 149 | public PB_DS_GP_HASH_TRAITS_BASE |
36fed23c | 150 | { |
36fed23c | 151 | private: |
4f4a327e | 152 | typedef PB_DS_GP_HASH_TRAITS_BASE traits_base; |
153 | typedef typename traits_base::value_type value_type_; | |
154 | typedef typename traits_base::pointer pointer_; | |
ce8b0a77 | 155 | typedef typename traits_base::const_pointer const_pointer_; |
4f4a327e | 156 | typedef typename traits_base::reference reference_; |
ce8b0a77 | 157 | typedef typename traits_base::const_reference const_reference_; |
4f4a327e | 158 | typedef typename traits_base::comp_hash comp_hash; |
ce8b0a77 | 159 | |
160 | enum entry_status | |
161 | { | |
162 | empty_entry_status, | |
163 | valid_entry_status, | |
164 | erased_entry_status | |
bdf63028 | 165 | } __attribute__ ((__packed__)); |
36fed23c | 166 | |
4f4a327e | 167 | struct entry : public traits_base::stored_data_type |
ce8b0a77 | 168 | { |
169 | entry_status m_stat; | |
170 | }; | |
36fed23c | 171 | |
4f4a327e | 172 | typedef typename _Alloc::template rebind<entry>::other entry_allocator; |
ce8b0a77 | 173 | typedef typename entry_allocator::pointer entry_pointer; |
174 | typedef typename entry_allocator::const_pointer const_entry_pointer; | |
175 | typedef typename entry_allocator::reference entry_reference; | |
176 | typedef typename entry_allocator::const_reference const_entry_reference; | |
177 | typedef typename entry_allocator::pointer entry_array; | |
36fed23c | 178 | |
4f4a327e | 179 | typedef PB_DS_RANGED_PROBE_FN_C_DEC ranged_probe_fn_base; |
36fed23c | 180 | |
ce8b0a77 | 181 | #ifdef _GLIBCXX_DEBUG |
4f4a327e | 182 | typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; |
183 | #endif | |
36fed23c | 184 | |
4f4a327e | 185 | typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base; |
186 | typedef Resize_Policy resize_base; | |
36fed23c | 187 | |
4f4a327e | 188 | #define PB_DS_GEN_POS typename _Alloc::size_type |
36fed23c | 189 | |
4f4a327e | 190 | #include <ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp> |
36fed23c | 191 | #include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp> |
192 | #include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp> | |
193 | #include <ext/pb_ds/detail/unordered_iterator/iterator.hpp> | |
194 | ||
195 | #undef PB_DS_GEN_POS | |
196 | ||
197 | public: | |
4f4a327e | 198 | typedef _Alloc allocator_type; |
199 | typedef typename _Alloc::size_type size_type; | |
200 | typedef typename _Alloc::difference_type difference_type; | |
201 | typedef Hash_Fn hash_fn; | |
202 | typedef Eq_Fn eq_fn; | |
203 | typedef Probe_Fn probe_fn; | |
204 | typedef Comb_Probe_Fn comb_probe_fn; | |
205 | typedef Resize_Policy resize_policy; | |
36fed23c | 206 | |
3f2eba6f | 207 | /// Value stores hash, true or false. |
36fed23c | 208 | enum |
209 | { | |
210 | store_hash = Store_Hash | |
211 | }; | |
212 | ||
4f4a327e | 213 | typedef typename traits_base::key_type key_type; |
ce8b0a77 | 214 | typedef typename traits_base::key_pointer key_pointer; |
4f4a327e | 215 | typedef typename traits_base::key_const_pointer key_const_pointer; |
ce8b0a77 | 216 | typedef typename traits_base::key_reference key_reference; |
4f4a327e | 217 | typedef typename traits_base::key_const_reference key_const_reference; |
ce8b0a77 | 218 | typedef typename traits_base::mapped_type mapped_type; |
219 | typedef typename traits_base::mapped_pointer mapped_pointer; | |
4f4a327e | 220 | typedef typename traits_base::mapped_const_pointer mapped_const_pointer; |
ce8b0a77 | 221 | typedef typename traits_base::mapped_reference mapped_reference; |
4f4a327e | 222 | typedef typename traits_base::mapped_const_reference mapped_const_reference; |
ce8b0a77 | 223 | typedef typename traits_base::value_type value_type; |
224 | typedef typename traits_base::pointer pointer; | |
225 | typedef typename traits_base::const_pointer const_pointer; | |
226 | typedef typename traits_base::reference reference; | |
227 | typedef typename traits_base::const_reference const_reference; | |
36fed23c | 228 | |
229 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
4f4a327e | 230 | typedef point_iterator_ point_iterator; |
231 | #endif | |
36fed23c | 232 | |
233 | #ifdef PB_DS_DATA_FALSE_INDICATOR | |
4f4a327e | 234 | typedef point_const_iterator_ point_iterator; |
235 | #endif | |
36fed23c | 236 | |
4f4a327e | 237 | typedef point_const_iterator_ point_const_iterator; |
36fed23c | 238 | |
239 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
4f4a327e | 240 | typedef iterator_ iterator; |
241 | #endif | |
36fed23c | 242 | |
243 | #ifdef PB_DS_DATA_FALSE_INDICATOR | |
4f4a327e | 244 | typedef const_iterator_ iterator; |
245 | #endif | |
36fed23c | 246 | |
4f4a327e | 247 | typedef const_iterator_ const_iterator; |
36fed23c | 248 | |
4f4a327e | 249 | PB_DS_GP_HASH_NAME(); |
36fed23c | 250 | |
4f4a327e | 251 | PB_DS_GP_HASH_NAME(const PB_DS_CLASS_C_DEC&); |
36fed23c | 252 | |
4f4a327e | 253 | PB_DS_GP_HASH_NAME(const Hash_Fn&); |
36fed23c | 254 | |
4f4a327e | 255 | PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&); |
36fed23c | 256 | |
4f4a327e | 257 | PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&); |
36fed23c | 258 | |
4f4a327e | 259 | PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&, |
3f2eba6f | 260 | const Probe_Fn&); |
36fed23c | 261 | |
4f4a327e | 262 | PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&, |
3f2eba6f | 263 | const Probe_Fn&, const Resize_Policy&); |
36fed23c | 264 | |
265 | template<typename It> | |
266 | void | |
4f4a327e | 267 | copy_from_range(It, It); |
36fed23c | 268 | |
269 | virtual | |
4f4a327e | 270 | ~PB_DS_GP_HASH_NAME(); |
36fed23c | 271 | |
272 | void | |
4f4a327e | 273 | swap(PB_DS_CLASS_C_DEC&); |
36fed23c | 274 | |
275 | inline size_type | |
276 | size() const; | |
277 | ||
278 | inline size_type | |
279 | max_size() const; | |
280 | ||
3f2eba6f | 281 | /// True if size() == 0. |
36fed23c | 282 | inline bool |
283 | empty() const; | |
284 | ||
3f2eba6f | 285 | /// Return current hash_fn. |
4f4a327e | 286 | Hash_Fn& |
36fed23c | 287 | get_hash_fn(); |
288 | ||
3f2eba6f | 289 | /// Return current const hash_fn. |
4f4a327e | 290 | const Hash_Fn& |
36fed23c | 291 | get_hash_fn() const; |
292 | ||
3f2eba6f | 293 | /// Return current eq_fn. |
4f4a327e | 294 | Eq_Fn& |
36fed23c | 295 | get_eq_fn(); |
296 | ||
3f2eba6f | 297 | /// Return current const eq_fn. |
4f4a327e | 298 | const Eq_Fn& |
36fed23c | 299 | get_eq_fn() const; |
300 | ||
3f2eba6f | 301 | /// Return current probe_fn. |
4f4a327e | 302 | Probe_Fn& |
36fed23c | 303 | get_probe_fn(); |
304 | ||
3f2eba6f | 305 | /// Return current const probe_fn. |
4f4a327e | 306 | const Probe_Fn& |
36fed23c | 307 | get_probe_fn() const; |
308 | ||
3f2eba6f | 309 | /// Return current comb_probe_fn. |
4f4a327e | 310 | Comb_Probe_Fn& |
36fed23c | 311 | get_comb_probe_fn(); |
312 | ||
3f2eba6f | 313 | /// Return current const comb_probe_fn. |
4f4a327e | 314 | const Comb_Probe_Fn& |
36fed23c | 315 | get_comb_probe_fn() const; |
316 | ||
3f2eba6f | 317 | /// Return current resize_policy. |
4f4a327e | 318 | Resize_Policy& |
36fed23c | 319 | get_resize_policy(); |
320 | ||
3f2eba6f | 321 | /// Return current const resize_policy. |
4f4a327e | 322 | const Resize_Policy& |
36fed23c | 323 | get_resize_policy() const; |
324 | ||
325 | inline std::pair<point_iterator, bool> | |
326 | insert(const_reference r_val) | |
327 | { | |
4f4a327e | 328 | _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid(__FILE__, __LINE__);) |
329 | return insert_imp(r_val, traits_base::m_store_extra_indicator); | |
36fed23c | 330 | } |
331 | ||
332 | inline mapped_reference | |
4f4a327e | 333 | operator[](key_const_reference r_key) |
36fed23c | 334 | { |
335 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
ce8b0a77 | 336 | return subscript_imp(r_key, traits_base::m_store_extra_indicator); |
4f4a327e | 337 | #else |
36fed23c | 338 | insert(r_key); |
4f4a327e | 339 | return traits_base::s_null_type; |
ce8b0a77 | 340 | #endif |
36fed23c | 341 | } |
342 | ||
343 | inline point_iterator | |
4f4a327e | 344 | find(key_const_reference); |
36fed23c | 345 | |
4f4a327e | 346 | inline point_const_iterator |
347 | find(key_const_reference) const; | |
36fed23c | 348 | |
349 | inline point_iterator | |
350 | find_end(); | |
351 | ||
4f4a327e | 352 | inline point_const_iterator |
36fed23c | 353 | find_end() const; |
354 | ||
355 | inline bool | |
4f4a327e | 356 | erase(key_const_reference); |
36fed23c | 357 | |
358 | template<typename Pred> | |
3f2eba6f | 359 | inline size_type |
360 | erase_if(Pred); | |
36fed23c | 361 | |
362 | void | |
363 | clear(); | |
364 | ||
365 | inline iterator | |
366 | begin(); | |
367 | ||
368 | inline const_iterator | |
369 | begin() const; | |
370 | ||
371 | inline iterator | |
372 | end(); | |
3f2eba6f | 373 | |
36fed23c | 374 | inline const_iterator |
375 | end() const; | |
376 | ||
2b31bec4 | 377 | #ifdef _GLIBCXX_DEBUG |
36fed23c | 378 | void |
4f4a327e | 379 | assert_valid(const char*, int) const; |
380 | #endif | |
36fed23c | 381 | |
382 | #ifdef PB_DS_HT_MAP_TRACE_ | |
36fed23c | 383 | void |
384 | trace() const; | |
4f4a327e | 385 | #endif |
36fed23c | 386 | |
387 | private: | |
36fed23c | 388 | #ifdef PB_DS_DATA_TRUE_INDICATOR |
389 | friend class iterator_; | |
4f4a327e | 390 | #endif |
36fed23c | 391 | |
392 | friend class const_iterator_; | |
393 | ||
36fed23c | 394 | void |
395 | deallocate_all(); | |
396 | ||
397 | void | |
398 | initialize(); | |
399 | ||
400 | void | |
ce8b0a77 | 401 | erase_all_valid_entries(entry_array, size_type); |
36fed23c | 402 | |
403 | inline bool | |
404 | do_resize_if_needed(); | |
405 | ||
406 | inline void | |
407 | do_resize_if_needed_no_throw(); | |
408 | ||
409 | void | |
ce8b0a77 | 410 | resize_imp(size_type); |
36fed23c | 411 | |
412 | virtual void | |
ce8b0a77 | 413 | do_resize(size_type); |
36fed23c | 414 | |
415 | void | |
ce8b0a77 | 416 | resize_imp(entry_array, size_type); |
36fed23c | 417 | |
418 | inline void | |
d3533fc3 | 419 | resize_imp_reassign(entry_pointer, entry_array, false_type); |
36fed23c | 420 | |
421 | inline void | |
d3533fc3 | 422 | resize_imp_reassign(entry_pointer, entry_array, true_type); |
36fed23c | 423 | |
424 | inline size_type | |
4f4a327e | 425 | find_ins_pos(key_const_reference, false_type); |
36fed23c | 426 | |
427 | inline comp_hash | |
4f4a327e | 428 | find_ins_pos(key_const_reference, true_type); |
36fed23c | 429 | |
430 | inline std::pair<point_iterator, bool> | |
d3533fc3 | 431 | insert_imp(const_reference, false_type); |
36fed23c | 432 | |
433 | inline std::pair<point_iterator, bool> | |
d3533fc3 | 434 | insert_imp(const_reference, true_type); |
36fed23c | 435 | |
436 | inline pointer | |
437 | insert_new_imp(const_reference r_val, size_type pos) | |
438 | { | |
ce8b0a77 | 439 | _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status); |
36fed23c | 440 | |
441 | if (do_resize_if_needed()) | |
442 | pos = find_ins_pos(PB_DS_V2F(r_val), | |
443 | traits_base::m_store_extra_indicator); | |
444 | ||
ce8b0a77 | 445 | _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status); |
ce8b0a77 | 446 | entry* const p_e = m_entries + pos; |
36fed23c | 447 | new (&p_e->m_value) value_type(r_val); |
36fed23c | 448 | p_e->m_stat = valid_entry_status; |
36fed23c | 449 | resize_base::notify_inserted(++m_num_used_e); |
450 | ||
6c9bd031 | 451 | _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(p_e->m_value));) |
2548203e | 452 | _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) |
ce8b0a77 | 453 | return &p_e->m_value; |
36fed23c | 454 | } |
455 | ||
456 | inline pointer | |
457 | insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair) | |
458 | { | |
ce8b0a77 | 459 | _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat != |
3f2eba6f | 460 | valid_entry_status); |
36fed23c | 461 | |
462 | if (do_resize_if_needed()) | |
ce8b0a77 | 463 | r_pos_hash_pair = find_ins_pos(PB_DS_V2F(r_val), |
36fed23c | 464 | traits_base::m_store_extra_indicator); |
465 | ||
ce8b0a77 | 466 | _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat != |
467 | valid_entry_status); | |
36fed23c | 468 | |
ce8b0a77 | 469 | entry* const p_e = m_entries + r_pos_hash_pair.first; |
36fed23c | 470 | new (&p_e->m_value) value_type(r_val); |
36fed23c | 471 | p_e->m_hash = r_pos_hash_pair.second; |
36fed23c | 472 | p_e->m_stat = valid_entry_status; |
473 | ||
474 | resize_base::notify_inserted(++m_num_used_e); | |
475 | ||
6c9bd031 | 476 | _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(p_e->m_value));) |
2548203e | 477 | _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) |
ce8b0a77 | 478 | return &p_e->m_value; |
36fed23c | 479 | } |
480 | ||
481 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
482 | inline mapped_reference | |
4f4a327e | 483 | subscript_imp(key_const_reference key, false_type) |
36fed23c | 484 | { |
2548203e | 485 | _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) |
36fed23c | 486 | |
4f4a327e | 487 | const size_type pos = find_ins_pos(key, |
ce8b0a77 | 488 | traits_base::m_store_extra_indicator); |
36fed23c | 489 | |
ea18d4a3 | 490 | entry_pointer p_e = &m_entries[pos]; |
36fed23c | 491 | if (p_e->m_stat != valid_entry_status) |
ce8b0a77 | 492 | return insert_new_imp(value_type(key, mapped_type()), pos)->second; |
36fed23c | 493 | |
2548203e | 494 | PB_DS_CHECK_KEY_EXISTS(key) |
ce8b0a77 | 495 | return p_e->m_value.second; |
36fed23c | 496 | } |
497 | ||
498 | inline mapped_reference | |
4f4a327e | 499 | subscript_imp(key_const_reference key, true_type) |
36fed23c | 500 | { |
2548203e | 501 | _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) |
36fed23c | 502 | |
4f4a327e | 503 | comp_hash pos_hash_pair = find_ins_pos(key, |
504 | traits_base::m_store_extra_indicator); | |
36fed23c | 505 | |
ce8b0a77 | 506 | if (m_entries[pos_hash_pair.first].m_stat != valid_entry_status) |
507 | return insert_new_imp(value_type(key, mapped_type()), | |
508 | pos_hash_pair)->second; | |
36fed23c | 509 | |
2548203e | 510 | PB_DS_CHECK_KEY_EXISTS(key) |
ce8b0a77 | 511 | return (m_entries + pos_hash_pair.first)->m_value.second; |
36fed23c | 512 | } |
ce8b0a77 | 513 | #endif |
36fed23c | 514 | |
515 | inline pointer | |
4f4a327e | 516 | find_key_pointer(key_const_reference key, false_type) |
36fed23c | 517 | { |
ce8b0a77 | 518 | const size_type hash = ranged_probe_fn_base::operator()(key); |
36fed23c | 519 | resize_base::notify_find_search_start(); |
520 | ||
521 | // Loop until entry is found or until all possible entries accessed. | |
4f4a327e | 522 | for (size_type i = 0; i < m_num_e; ++i) |
36fed23c | 523 | { |
4f4a327e | 524 | const size_type pos = ranged_probe_fn_base::operator()(key, |
525 | hash, i); | |
36fed23c | 526 | |
ce8b0a77 | 527 | entry* const p_e = m_entries + pos; |
528 | switch (p_e->m_stat) | |
36fed23c | 529 | { |
530 | case empty_entry_status: | |
531 | { | |
532 | resize_base::notify_find_search_end(); | |
2548203e | 533 | PB_DS_CHECK_KEY_DOES_NOT_EXIST(key) |
534 | return 0; | |
36fed23c | 535 | } |
536 | break; | |
537 | case valid_entry_status: | |
ce8b0a77 | 538 | if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), key)) |
36fed23c | 539 | { |
540 | resize_base::notify_find_search_end(); | |
2548203e | 541 | PB_DS_CHECK_KEY_EXISTS(key) |
ce8b0a77 | 542 | return pointer(&p_e->m_value); |
36fed23c | 543 | } |
544 | break; | |
545 | case erased_entry_status: | |
546 | break; | |
547 | default: | |
2b31bec4 | 548 | _GLIBCXX_DEBUG_ASSERT(0); |
36fed23c | 549 | }; |
550 | ||
551 | resize_base::notify_find_search_collision(); | |
552 | } | |
553 | ||
2548203e | 554 | PB_DS_CHECK_KEY_DOES_NOT_EXIST(key) |
ce8b0a77 | 555 | resize_base::notify_find_search_end(); |
e4bb1925 | 556 | return 0; |
36fed23c | 557 | } |
558 | ||
559 | inline pointer | |
4f4a327e | 560 | find_key_pointer(key_const_reference key, true_type) |
36fed23c | 561 | { |
ce8b0a77 | 562 | comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(key); |
36fed23c | 563 | resize_base::notify_find_search_start(); |
564 | ||
565 | // Loop until entry is found or until all possible entries accessed. | |
4f4a327e | 566 | for (size_type i = 0; i < m_num_e; ++i) |
36fed23c | 567 | { |
568 | const size_type pos = | |
ce8b0a77 | 569 | ranged_probe_fn_base::operator()(key, pos_hash_pair.second, i); |
36fed23c | 570 | |
ce8b0a77 | 571 | entry* const p_e = m_entries + pos; |
36fed23c | 572 | |
573 | switch(p_e->m_stat) | |
574 | { | |
575 | case empty_entry_status: | |
576 | { | |
577 | resize_base::notify_find_search_end(); | |
2548203e | 578 | PB_DS_CHECK_KEY_DOES_NOT_EXIST(key) |
e4bb1925 | 579 | return 0; |
36fed23c | 580 | } |
581 | break; | |
582 | case valid_entry_status: | |
ce8b0a77 | 583 | if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), |
36fed23c | 584 | p_e->m_hash, |
ce8b0a77 | 585 | key, pos_hash_pair.second)) |
36fed23c | 586 | { |
587 | resize_base::notify_find_search_end(); | |
2548203e | 588 | PB_DS_CHECK_KEY_EXISTS(key) |
ce8b0a77 | 589 | return pointer(&p_e->m_value); |
36fed23c | 590 | } |
591 | break; | |
592 | case erased_entry_status: | |
593 | break; | |
594 | default: | |
2b31bec4 | 595 | _GLIBCXX_DEBUG_ASSERT(0); |
36fed23c | 596 | }; |
597 | ||
598 | resize_base::notify_find_search_collision(); | |
599 | } | |
600 | ||
2548203e | 601 | PB_DS_CHECK_KEY_DOES_NOT_EXIST(key) |
ce8b0a77 | 602 | resize_base::notify_find_search_end(); |
e4bb1925 | 603 | return 0; |
36fed23c | 604 | } |
605 | ||
606 | inline bool | |
4f4a327e | 607 | erase_imp(key_const_reference, true_type); |
36fed23c | 608 | |
609 | inline bool | |
4f4a327e | 610 | erase_imp(key_const_reference, false_type); |
36fed23c | 611 | |
612 | inline void | |
4f4a327e | 613 | erase_entry(entry_pointer); |
36fed23c | 614 | |
615 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
616 | void | |
617 | inc_it_state(pointer& r_p_value, size_type& r_pos) const | |
4f4a327e | 618 | { inc_it_state((mapped_const_pointer& )r_p_value, r_pos); } |
619 | #endif | |
36fed23c | 620 | |
621 | void | |
622 | inc_it_state(const_pointer& r_p_value, size_type& r_pos) const | |
623 | { | |
e4bb1925 | 624 | _GLIBCXX_DEBUG_ASSERT(r_p_value != 0); |
36fed23c | 625 | for (++r_pos; r_pos < m_num_e; ++r_pos) |
626 | { | |
ce8b0a77 | 627 | const_entry_pointer p_e =& m_entries[r_pos]; |
36fed23c | 628 | if (p_e->m_stat == valid_entry_status) |
629 | { | |
630 | r_p_value =& p_e->m_value; | |
36fed23c | 631 | return; |
632 | } | |
633 | } | |
e4bb1925 | 634 | r_p_value = 0; |
36fed23c | 635 | } |
636 | ||
637 | void | |
638 | get_start_it_state(const_pointer& r_p_value, size_type& r_pos) const | |
639 | { | |
640 | for (r_pos = 0; r_pos < m_num_e; ++r_pos) | |
641 | { | |
ce8b0a77 | 642 | const_entry_pointer p_e = &m_entries[r_pos]; |
36fed23c | 643 | if (p_e->m_stat == valid_entry_status) |
644 | { | |
ce8b0a77 | 645 | r_p_value = &p_e->m_value; |
36fed23c | 646 | return; |
647 | } | |
648 | } | |
e4bb1925 | 649 | r_p_value = 0; |
36fed23c | 650 | } |
651 | ||
652 | void | |
653 | get_start_it_state(pointer& r_p_value, size_type& r_pos) | |
654 | { | |
655 | for (r_pos = 0; r_pos < m_num_e; ++r_pos) | |
656 | { | |
ce8b0a77 | 657 | entry_pointer p_e = &m_entries[r_pos]; |
36fed23c | 658 | if (p_e->m_stat == valid_entry_status) |
659 | { | |
ce8b0a77 | 660 | r_p_value = &p_e->m_value; |
36fed23c | 661 | return; |
662 | } | |
663 | } | |
e4bb1925 | 664 | r_p_value = 0; |
36fed23c | 665 | } |
666 | ||
2b31bec4 | 667 | #ifdef _GLIBCXX_DEBUG |
36fed23c | 668 | void |
2548203e | 669 | assert_entry_array_valid(const entry_array, false_type, |
4f4a327e | 670 | const char*, int) const; |
36fed23c | 671 | |
672 | void | |
2548203e | 673 | assert_entry_array_valid(const entry_array, true_type, |
4f4a327e | 674 | const char*, int) const; |
675 | #endif | |
36fed23c | 676 | |
ce8b0a77 | 677 | static entry_allocator s_entry_allocator; |
678 | static iterator s_end_it; | |
679 | static const_iterator s_const_end_it; | |
36fed23c | 680 | |
ce8b0a77 | 681 | size_type m_num_e; |
682 | size_type m_num_used_e; | |
683 | entry_pointer m_entries; | |
36fed23c | 684 | |
685 | enum | |
686 | { | |
4f4a327e | 687 | store_hash_ok = !Store_Hash |
688 | || !is_same<Hash_Fn, __gnu_pbds::null_type>::value | |
36fed23c | 689 | }; |
690 | ||
691 | PB_DS_STATIC_ASSERT(sth, store_hash_ok); | |
692 | }; | |
693 | ||
694 | #include <ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp> | |
695 | #include <ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp> | |
696 | #include <ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp> | |
697 | #include <ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp> | |
698 | #include <ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp> | |
699 | #include <ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp> | |
700 | #include <ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp> | |
701 | #include <ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp> | |
702 | #include <ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp> | |
703 | #include <ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp> | |
704 | ||
705 | #undef PB_DS_CLASS_T_DEC | |
36fed23c | 706 | #undef PB_DS_CLASS_C_DEC |
36fed23c | 707 | #undef PB_DS_HASH_EQ_FN_C_DEC |
36fed23c | 708 | #undef PB_DS_RANGED_PROBE_FN_C_DEC |
4f4a327e | 709 | #undef PB_DS_GP_HASH_TRAITS_BASE |
6c9bd031 | 710 | #undef PB_DS_DEBUG_MAP_BASE_C_DEC |
4f4a327e | 711 | #undef PB_DS_GP_HASH_NAME |
36fed23c | 712 | } // namespace detail |
b34535d7 | 713 | } // namespace __gnu_pbds |