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