1// -*- C++ -*- 2 3// Copyright (C) 2005-2022 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 55namespace __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 rebind_traits<_Alloc, Key>::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 rebind_traits<_Alloc, entry> entry_traits; 173 typedef typename entry_traits::allocator_type entry_allocator; 174 typedef typename entry_traits::pointer entry_pointer; 175 typedef typename entry_traits::const_pointer const_entry_pointer; 176 typedef typename entry_traits::reference entry_reference; 177 typedef typename entry_traits::const_reference const_entry_reference; 178 typedef typename entry_traits::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 _GLIBCXX_NODISCARD 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