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