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