]>
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. | |
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/>. | |
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 cc_hash_table_map_/cc_ht_map_.hpp |
36fed23c | 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> | |
2b31bec4 | 49 | #ifdef _GLIBCXX_DEBUG |
6c9bd031 | 50 | #include <ext/pb_ds/detail/debug_map_base.hpp> |
4f4a327e | 51 | #endif |
36fed23c | 52 | #ifdef PB_DS_HT_MAP_TRACE_ |
53 | #include <iostream> | |
4f4a327e | 54 | #endif |
2b31bec4 | 55 | #include <debug/debug.h> |
36fed23c | 56 | |
b34535d7 | 57 | namespace __gnu_pbds |
36fed23c | 58 | { |
59 | namespace detail | |
60 | { | |
4f4a327e | 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 | |
36fed23c | 68 | |
2b31bec4 | 69 | #define PB_DS_CLASS_T_DEC \ |
ce8b0a77 | 70 | template<typename Key, typename Mapped, typename Hash_Fn, \ |
4f4a327e | 71 | typename Eq_Fn, typename _Alloc, bool Store_Hash, \ |
ce8b0a77 | 72 | typename Comb_Hash_Fn, typename Resize_Policy> |
36fed23c | 73 | |
2b31bec4 | 74 | #define PB_DS_CLASS_C_DEC \ |
4f4a327e | 75 | PB_DS_CC_HASH_NAME<Key, Mapped, Hash_Fn, Eq_Fn, _Alloc, \ |
2b31bec4 | 76 | Store_Hash, Comb_Hash_Fn, Resize_Policy> |
77 | ||
78 | #define PB_DS_HASH_EQ_FN_C_DEC \ | |
4f4a327e | 79 | hash_eq_fn<Key, Eq_Fn, _Alloc, Store_Hash> |
2b31bec4 | 80 | |
81 | #define PB_DS_RANGED_HASH_FN_C_DEC \ | |
4f4a327e | 82 | ranged_hash_fn<Key, Hash_Fn, _Alloc, Comb_Hash_Fn, Store_Hash> |
2b31bec4 | 83 | |
4f4a327e | 84 | #define PB_DS_CC_HASH_TRAITS_BASE \ |
85 | types_traits<Key, Mapped, _Alloc, Store_Hash> | |
2b31bec4 | 86 | |
87 | #ifdef _GLIBCXX_DEBUG | |
6c9bd031 | 88 | #define PB_DS_DEBUG_MAP_BASE_C_DEC \ |
4f4a327e | 89 | debug_map_base<Key, Eq_Fn, \ |
90 | typename _Alloc::template rebind<Key>::other::const_reference> | |
2548203e | 91 | #endif |
92 | ||
3f2eba6f | 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 | */ | |
36fed23c | 131 | template<typename Key, |
132 | typename Mapped, | |
ce8b0a77 | 133 | typename Hash_Fn, |
134 | typename Eq_Fn, | |
4f4a327e | 135 | typename _Alloc, |
36fed23c | 136 | bool Store_Hash, |
ce8b0a77 | 137 | typename Comb_Hash_Fn, |
138 | typename Resize_Policy > | |
4f4a327e | 139 | class PB_DS_CC_HASH_NAME: |
2b31bec4 | 140 | #ifdef _GLIBCXX_DEBUG |
6c9bd031 | 141 | protected PB_DS_DEBUG_MAP_BASE_C_DEC, |
4f4a327e | 142 | #endif |
36fed23c | 143 | public PB_DS_HASH_EQ_FN_C_DEC, |
144 | public Resize_Policy, | |
145 | public PB_DS_RANGED_HASH_FN_C_DEC, | |
4f4a327e | 146 | public PB_DS_CC_HASH_TRAITS_BASE |
36fed23c | 147 | { |
36fed23c | 148 | private: |
4f4a327e | 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_; | |
ce8b0a77 | 153 | typedef typename traits_base::const_pointer const_pointer_; |
4f4a327e | 154 | typedef typename traits_base::reference reference_; |
ce8b0a77 | 155 | typedef typename traits_base::const_reference const_reference_; |
ce8b0a77 | 156 | |
4f4a327e | 157 | struct entry : public traits_base::stored_data_type |
36fed23c | 158 | { |
4f4a327e | 159 | typename _Alloc::template rebind<entry>::other::pointer m_p_next; |
36fed23c | 160 | }; |
161 | ||
4f4a327e | 162 | typedef cond_dealtor<entry, _Alloc> cond_dealtor_t; |
36fed23c | 163 | |
4f4a327e | 164 | typedef typename _Alloc::template rebind<entry>::other entry_allocator; |
36fed23c | 165 | typedef typename entry_allocator::pointer entry_pointer; |
36fed23c | 166 | typedef typename entry_allocator::const_pointer const_entry_pointer; |
36fed23c | 167 | typedef typename entry_allocator::reference entry_reference; |
ce8b0a77 | 168 | typedef typename entry_allocator::const_reference const_entry_reference; |
36fed23c | 169 | |
4f4a327e | 170 | typedef typename _Alloc::template rebind<entry_pointer>::other entry_pointer_allocator; |
36fed23c | 171 | typedef typename entry_pointer_allocator::pointer entry_pointer_array; |
172 | ||
ce8b0a77 | 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; | |
36fed23c | 176 | |
ce8b0a77 | 177 | #ifdef _GLIBCXX_DEBUG |
4f4a327e | 178 | typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; |
179 | #endif | |
36fed23c | 180 | |
4f4a327e | 181 | #define PB_DS_GEN_POS std::pair<entry_pointer, typename _Alloc::size_type> |
36fed23c | 182 | |
4f4a327e | 183 | #include <ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp> |
36fed23c | 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: | |
4f4a327e | 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; | |
36fed23c | 198 | |
3f2eba6f | 199 | /// Value stores hash, true or false. |
36fed23c | 200 | enum |
201 | { | |
202 | store_hash = Store_Hash | |
203 | }; | |
204 | ||
ce8b0a77 | 205 | typedef typename traits_base::key_type key_type; |
206 | typedef typename traits_base::key_pointer key_pointer; | |
4f4a327e | 207 | typedef typename traits_base::key_const_pointer key_const_pointer; |
ce8b0a77 | 208 | typedef typename traits_base::key_reference key_reference; |
4f4a327e | 209 | typedef typename traits_base::key_const_reference key_const_reference; |
ce8b0a77 | 210 | typedef typename traits_base::mapped_type mapped_type; |
211 | typedef typename traits_base::mapped_pointer mapped_pointer; | |
4f4a327e | 212 | typedef typename traits_base::mapped_const_pointer mapped_const_pointer; |
ce8b0a77 | 213 | typedef typename traits_base::mapped_reference mapped_reference; |
4f4a327e | 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; | |
ce8b0a77 | 217 | typedef typename traits_base::const_pointer const_pointer; |
4f4a327e | 218 | typedef typename traits_base::reference reference; |
ce8b0a77 | 219 | typedef typename traits_base::const_reference const_reference; |
36fed23c | 220 | |
221 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
4f4a327e | 222 | typedef point_iterator_ point_iterator; |
223 | #endif | |
36fed23c | 224 | |
225 | #ifdef PB_DS_DATA_FALSE_INDICATOR | |
4f4a327e | 226 | typedef point_const_iterator_ point_iterator; |
227 | #endif | |
36fed23c | 228 | |
4f4a327e | 229 | typedef point_const_iterator_ point_const_iterator; |
36fed23c | 230 | |
231 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
4f4a327e | 232 | typedef iterator_ iterator; |
233 | #endif | |
36fed23c | 234 | |
235 | #ifdef PB_DS_DATA_FALSE_INDICATOR | |
4f4a327e | 236 | typedef const_iterator_ iterator; |
237 | #endif | |
36fed23c | 238 | |
4f4a327e | 239 | typedef const_iterator_ const_iterator; |
36fed23c | 240 | |
4f4a327e | 241 | PB_DS_CC_HASH_NAME(); |
36fed23c | 242 | |
4f4a327e | 243 | PB_DS_CC_HASH_NAME(const Hash_Fn&); |
36fed23c | 244 | |
4f4a327e | 245 | PB_DS_CC_HASH_NAME(const Hash_Fn&, const Eq_Fn&); |
36fed23c | 246 | |
4f4a327e | 247 | PB_DS_CC_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&); |
36fed23c | 248 | |
4f4a327e | 249 | PB_DS_CC_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&, |
ce8b0a77 | 250 | const Resize_Policy&); |
36fed23c | 251 | |
4f4a327e | 252 | PB_DS_CC_HASH_NAME(const PB_DS_CLASS_C_DEC&); |
36fed23c | 253 | |
254 | virtual | |
4f4a327e | 255 | ~PB_DS_CC_HASH_NAME(); |
36fed23c | 256 | |
257 | void | |
ce8b0a77 | 258 | swap(PB_DS_CLASS_C_DEC&); |
36fed23c | 259 | |
260 | template<typename It> | |
261 | void | |
ce8b0a77 | 262 | copy_from_range(It, It); |
36fed23c | 263 | |
264 | void | |
265 | initialize(); | |
266 | ||
267 | inline size_type | |
268 | size() const; | |
269 | ||
270 | inline size_type | |
271 | max_size() const; | |
272 | ||
3f2eba6f | 273 | /// True if size() == 0. |
36fed23c | 274 | inline bool |
275 | empty() const; | |
276 | ||
3f2eba6f | 277 | /// Return current hash_fn. |
4f4a327e | 278 | Hash_Fn& |
36fed23c | 279 | get_hash_fn(); |
280 | ||
3f2eba6f | 281 | /// Return current const hash_fn. |
4f4a327e | 282 | const Hash_Fn& |
36fed23c | 283 | get_hash_fn() const; |
284 | ||
3f2eba6f | 285 | /// Return current eq_fn. |
4f4a327e | 286 | Eq_Fn& |
36fed23c | 287 | get_eq_fn(); |
288 | ||
3f2eba6f | 289 | /// Return current const eq_fn. |
4f4a327e | 290 | const Eq_Fn& |
36fed23c | 291 | get_eq_fn() const; |
292 | ||
3f2eba6f | 293 | /// Return current comb_hash_fn. |
4f4a327e | 294 | Comb_Hash_Fn& |
36fed23c | 295 | get_comb_hash_fn(); |
296 | ||
3f2eba6f | 297 | /// Return current const comb_hash_fn. |
4f4a327e | 298 | const Comb_Hash_Fn& |
36fed23c | 299 | get_comb_hash_fn() const; |
300 | ||
3f2eba6f | 301 | /// Return current resize_policy. |
4f4a327e | 302 | Resize_Policy& |
36fed23c | 303 | get_resize_policy(); |
304 | ||
3f2eba6f | 305 | /// Return current const resize_policy. |
4f4a327e | 306 | const Resize_Policy& |
36fed23c | 307 | get_resize_policy() const; |
308 | ||
309 | inline std::pair<point_iterator, bool> | |
310 | insert(const_reference r_val) | |
ce8b0a77 | 311 | { return insert_imp(r_val, traits_base::m_store_extra_indicator); } |
36fed23c | 312 | |
313 | inline mapped_reference | |
4f4a327e | 314 | operator[](key_const_reference r_key) |
36fed23c | 315 | { |
316 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
317 | return (subscript_imp(r_key, traits_base::m_store_extra_indicator)); | |
4f4a327e | 318 | #else |
36fed23c | 319 | insert(r_key); |
4f4a327e | 320 | return traits_base::s_null_type; |
321 | #endif | |
36fed23c | 322 | } |
323 | ||
324 | inline point_iterator | |
4f4a327e | 325 | find(key_const_reference); |
36fed23c | 326 | |
4f4a327e | 327 | inline point_const_iterator |
328 | find(key_const_reference) const; | |
36fed23c | 329 | |
330 | inline point_iterator | |
331 | find_end(); | |
332 | ||
4f4a327e | 333 | inline point_const_iterator |
36fed23c | 334 | find_end() const; |
335 | ||
336 | inline bool | |
4f4a327e | 337 | erase(key_const_reference); |
36fed23c | 338 | |
339 | template<typename Pred> | |
340 | inline size_type | |
ce8b0a77 | 341 | erase_if(Pred); |
36fed23c | 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 | ||
2b31bec4 | 358 | #ifdef _GLIBCXX_DEBUG |
36fed23c | 359 | void |
4f4a327e | 360 | assert_valid(const char*, int) const; |
361 | #endif | |
36fed23c | 362 | |
363 | #ifdef PB_DS_HT_MAP_TRACE_ | |
36fed23c | 364 | void |
365 | trace() const; | |
4f4a327e | 366 | #endif |
36fed23c | 367 | |
368 | private: | |
36fed23c | 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 | |
4f4a327e | 379 | resize_imp(size_type); |
36fed23c | 380 | |
381 | void | |
4f4a327e | 382 | do_resize(size_type); |
36fed23c | 383 | |
384 | void | |
2b31bec4 | 385 | resize_imp_no_exceptions(size_type, entry_pointer_array, size_type); |
36fed23c | 386 | |
387 | inline entry_pointer | |
4f4a327e | 388 | resize_imp_no_exceptions_reassign_pointer(entry_pointer, |
389 | entry_pointer_array, | |
390 | false_type); | |
36fed23c | 391 | |
392 | inline entry_pointer | |
4f4a327e | 393 | resize_imp_no_exceptions_reassign_pointer(entry_pointer, |
394 | entry_pointer_array, | |
395 | true_type); | |
36fed23c | 396 | |
397 | void | |
ce8b0a77 | 398 | deallocate_links_in_list(entry_pointer); |
36fed23c | 399 | |
400 | inline entry_pointer | |
d3533fc3 | 401 | get_entry(const_reference, false_type); |
36fed23c | 402 | |
403 | inline entry_pointer | |
d3533fc3 | 404 | get_entry(const_reference, true_type); |
36fed23c | 405 | |
406 | inline void | |
ce8b0a77 | 407 | rels_entry(entry_pointer); |
36fed23c | 408 | |
409 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
410 | inline mapped_reference | |
4f4a327e | 411 | subscript_imp(key_const_reference r_key, false_type) |
36fed23c | 412 | { |
2548203e | 413 | _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) |
4f4a327e | 414 | const size_type pos = ranged_hash_fn_base::operator()(r_key); |
ce8b0a77 | 415 | entry_pointer p_e = m_entries[pos]; |
36fed23c | 416 | resize_base::notify_insert_search_start(); |
417 | ||
4f4a327e | 418 | while (p_e != 0 |
2b31bec4 | 419 | && !hash_eq_fn_base::operator()(p_e->m_value.first, r_key)) |
36fed23c | 420 | { |
421 | resize_base::notify_insert_search_collision(); | |
36fed23c | 422 | p_e = p_e->m_p_next; |
423 | } | |
424 | ||
425 | resize_base::notify_insert_search_end(); | |
e4bb1925 | 426 | if (p_e != 0) |
36fed23c | 427 | { |
2548203e | 428 | PB_DS_CHECK_KEY_EXISTS(r_key) |
2b31bec4 | 429 | return (p_e->m_value.second); |
36fed23c | 430 | } |
431 | ||
2548203e | 432 | PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) |
2b31bec4 | 433 | return insert_new_imp(value_type(r_key, mapped_type()), pos)->second; |
36fed23c | 434 | } |
435 | ||
436 | inline mapped_reference | |
4f4a327e | 437 | subscript_imp(key_const_reference r_key, true_type) |
36fed23c | 438 | { |
2548203e | 439 | _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) |
2b31bec4 | 440 | comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key); |
ce8b0a77 | 441 | entry_pointer p_e = m_entries[pos_hash_pair.first]; |
36fed23c | 442 | resize_base::notify_insert_search_start(); |
4f4a327e | 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)) | |
36fed23c | 446 | { |
447 | resize_base::notify_insert_search_collision(); | |
36fed23c | 448 | p_e = p_e->m_p_next; |
449 | } | |
450 | ||
451 | resize_base::notify_insert_search_end(); | |
e4bb1925 | 452 | if (p_e != 0) |
36fed23c | 453 | { |
2548203e | 454 | PB_DS_CHECK_KEY_EXISTS(r_key) |
2b31bec4 | 455 | return p_e->m_value.second; |
36fed23c | 456 | } |
457 | ||
2548203e | 458 | PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) |
4f4a327e | 459 | return insert_new_imp(value_type(r_key, mapped_type()), |
ce8b0a77 | 460 | pos_hash_pair)->second; |
36fed23c | 461 | } |
4f4a327e | 462 | #endif |
36fed23c | 463 | |
2b31bec4 | 464 | inline std::pair<point_iterator, bool> |
d3533fc3 | 465 | insert_imp(const_reference, false_type); |
36fed23c | 466 | |
2b31bec4 | 467 | inline std::pair<point_iterator, bool> |
d3533fc3 | 468 | insert_imp(const_reference, true_type); |
36fed23c | 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. | |
4f4a327e | 477 | entry_pointer p_e = get_entry(r_val, |
478 | traits_base::m_no_throw_copies_indicator); | |
36fed23c | 479 | |
480 | // At this point no exceptions can be thrown. | |
ce8b0a77 | 481 | p_e->m_p_next = m_entries[pos]; |
482 | m_entries[pos] = p_e; | |
36fed23c | 483 | resize_base::notify_inserted(++m_num_used_e); |
484 | ||
6c9bd031 | 485 | _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) |
2548203e | 486 | _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) |
2b31bec4 | 487 | return &p_e->m_value; |
36fed23c | 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. | |
36fed23c | 494 | if (do_resize_if_needed()) |
2b31bec4 | 495 | r_pos_hash_pair = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val)); |
36fed23c | 496 | |
4f4a327e | 497 | entry_pointer p_e = get_entry(r_val, |
498 | traits_base::m_no_throw_copies_indicator); | |
36fed23c | 499 | |
500 | // At this point no exceptions can be thrown. | |
36fed23c | 501 | p_e->m_hash = r_pos_hash_pair.second; |
ce8b0a77 | 502 | p_e->m_p_next = m_entries[r_pos_hash_pair.first]; |
503 | m_entries[r_pos_hash_pair.first] = p_e; | |
36fed23c | 504 | resize_base::notify_inserted(++m_num_used_e); |
6c9bd031 | 505 | _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) |
2548203e | 506 | _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) |
2b31bec4 | 507 | return &p_e->m_value; |
36fed23c | 508 | } |
509 | ||
510 | inline pointer | |
4f4a327e | 511 | find_key_pointer(key_const_reference r_key, false_type) |
36fed23c | 512 | { |
ce8b0a77 | 513 | entry_pointer p_e = m_entries[ranged_hash_fn_base::operator()(r_key)]; |
36fed23c | 514 | resize_base::notify_find_search_start(); |
4f4a327e | 515 | while (p_e != 0 && |
36fed23c | 516 | !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) |
517 | { | |
518 | resize_base::notify_find_search_collision(); | |
36fed23c | 519 | p_e = p_e->m_p_next; |
520 | } | |
521 | ||
522 | resize_base::notify_find_search_end(); | |
523 | ||
2b31bec4 | 524 | #ifdef _GLIBCXX_DEBUG |
e4bb1925 | 525 | if (p_e == 0) |
2548203e | 526 | PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) |
36fed23c | 527 | else |
2548203e | 528 | PB_DS_CHECK_KEY_EXISTS(r_key) |
4f4a327e | 529 | #endif |
2b31bec4 | 530 | return &p_e->m_value; |
36fed23c | 531 | } |
532 | ||
533 | inline pointer | |
4f4a327e | 534 | find_key_pointer(key_const_reference r_key, true_type) |
36fed23c | 535 | { |
536 | comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key); | |
ce8b0a77 | 537 | entry_pointer p_e = m_entries[pos_hash_pair.first]; |
36fed23c | 538 | resize_base::notify_find_search_start(); |
4f4a327e | 539 | while (p_e != 0 && |
2b31bec4 | 540 | !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), |
36fed23c | 541 | p_e->m_hash, |
542 | r_key, pos_hash_pair.second)) | |
543 | { | |
544 | resize_base::notify_find_search_collision(); | |
36fed23c | 545 | p_e = p_e->m_p_next; |
546 | } | |
547 | ||
548 | resize_base::notify_find_search_end(); | |
549 | ||
2b31bec4 | 550 | #ifdef _GLIBCXX_DEBUG |
e4bb1925 | 551 | if (p_e == 0) |
2548203e | 552 | PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) |
36fed23c | 553 | else |
2548203e | 554 | PB_DS_CHECK_KEY_EXISTS(r_key) |
4f4a327e | 555 | #endif |
2b31bec4 | 556 | return &p_e->m_value; |
36fed23c | 557 | } |
558 | ||
559 | inline bool | |
4f4a327e | 560 | erase_in_pos_imp(key_const_reference, size_type); |
36fed23c | 561 | |
562 | inline bool | |
4f4a327e | 563 | erase_in_pos_imp(key_const_reference, const comp_hash&); |
36fed23c | 564 | |
565 | inline void | |
ce8b0a77 | 566 | erase_entry_pointer(entry_pointer&); |
36fed23c | 567 | |
568 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
569 | void | |
4f4a327e | 570 | inc_it_state(pointer& r_p_value, |
ce8b0a77 | 571 | std::pair<entry_pointer, size_type>& r_pos) const |
36fed23c | 572 | { |
4f4a327e | 573 | inc_it_state((mapped_const_pointer& )r_p_value, r_pos); |
36fed23c | 574 | } |
4f4a327e | 575 | #endif |
36fed23c | 576 | |
577 | void | |
4f4a327e | 578 | inc_it_state(const_pointer& r_p_value, |
2b31bec4 | 579 | std::pair<entry_pointer, size_type>& r_pos) const |
36fed23c | 580 | { |
e4bb1925 | 581 | _GLIBCXX_DEBUG_ASSERT(r_p_value != 0); |
36fed23c | 582 | r_pos.first = r_pos.first->m_p_next; |
e4bb1925 | 583 | if (r_pos.first != 0) |
36fed23c | 584 | { |
ce8b0a77 | 585 | r_p_value = &r_pos.first->m_value; |
36fed23c | 586 | return; |
587 | } | |
588 | ||
ce8b0a77 | 589 | for (++r_pos.second; r_pos.second < m_num_e; ++r_pos.second) |
e4bb1925 | 590 | if (m_entries[r_pos.second] != 0) |
36fed23c | 591 | { |
ce8b0a77 | 592 | r_pos.first = m_entries[r_pos.second]; |
593 | r_p_value = &r_pos.first->m_value; | |
36fed23c | 594 | return; |
595 | } | |
e4bb1925 | 596 | r_p_value = 0; |
36fed23c | 597 | } |
598 | ||
599 | void | |
4f4a327e | 600 | get_start_it_state(pointer& r_p_value, |
2b31bec4 | 601 | std::pair<entry_pointer, size_type>& r_pos) const |
36fed23c | 602 | { |
ce8b0a77 | 603 | for (r_pos.second = 0; r_pos.second < m_num_e; ++r_pos.second) |
e4bb1925 | 604 | if (m_entries[r_pos.second] != 0) |
36fed23c | 605 | { |
ce8b0a77 | 606 | r_pos.first = m_entries[r_pos.second]; |
607 | r_p_value = &r_pos.first->m_value; | |
36fed23c | 608 | return; |
609 | } | |
e4bb1925 | 610 | r_p_value = 0; |
36fed23c | 611 | } |
612 | ||
2b31bec4 | 613 | #ifdef _GLIBCXX_DEBUG |
36fed23c | 614 | void |
2548203e | 615 | assert_entry_pointer_array_valid(const entry_pointer_array, |
4f4a327e | 616 | const char*, int) const; |
36fed23c | 617 | |
618 | void | |
2548203e | 619 | assert_entry_pointer_valid(const entry_pointer, true_type, |
4f4a327e | 620 | const char*, int) const; |
36fed23c | 621 | |
622 | void | |
2548203e | 623 | assert_entry_pointer_valid(const entry_pointer, false_type, |
4f4a327e | 624 | const char*, int) const; |
625 | #endif | |
36fed23c | 626 | |
627 | #ifdef PB_DS_HT_MAP_TRACE_ | |
36fed23c | 628 | void |
d3533fc3 | 629 | trace_list(const_entry_pointer) const; |
4f4a327e | 630 | #endif |
36fed23c | 631 | |
632 | private: | |
36fed23c | 633 | #ifdef PB_DS_DATA_TRUE_INDICATOR |
634 | friend class iterator_; | |
4f4a327e | 635 | #endif |
36fed23c | 636 | |
637 | friend class const_iterator_; | |
638 | ||
ce8b0a77 | 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; | |
4f4a327e | 644 | static point_const_iterator s_const_find_end_it; |
36fed23c | 645 | |
ce8b0a77 | 646 | size_type m_num_e; |
647 | size_type m_num_used_e; | |
648 | entry_pointer_array m_entries; | |
36fed23c | 649 | |
650 | enum | |
651 | { | |
4f4a327e | 652 | store_hash_ok = !Store_Hash |
653 | || !is_same<Hash_Fn, __gnu_pbds::null_type>::value | |
36fed23c | 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 | |
36fed23c | 672 | #undef PB_DS_CLASS_C_DEC |
36fed23c | 673 | #undef PB_DS_HASH_EQ_FN_C_DEC |
36fed23c | 674 | #undef PB_DS_RANGED_HASH_FN_C_DEC |
4f4a327e | 675 | #undef PB_DS_CC_HASH_TRAITS_BASE |
6c9bd031 | 676 | #undef PB_DS_DEBUG_MAP_BASE_C_DEC |
4f4a327e | 677 | #undef PB_DS_CC_HASH_NAME |
36fed23c | 678 | } // namespace detail |
b34535d7 | 679 | } // namespace __gnu_pbds |