contrib/gcc-4.4/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp

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