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