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