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