libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2007 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file cc_ht_map_.hpp
  44  * Contains an implementation class for cc_ht_map_.
  45  */
  46
  47 #include <utility>
  48 #include <iterator>
  49 #include <ext/pb_ds/detail/cond_dealtor.hpp>
  50 #include <ext/pb_ds/tag_and_trait.hpp>
  51 #include <ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp>
  52 #include <ext/pb_ds/detail/types_traits.hpp>
  53 #include <ext/pb_ds/exception.hpp>
  54 #include <ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp>
  55 #ifdef _GLIBCXX_DEBUG
  56 #include <ext/pb_ds/detail/debug_map_base.hpp>
  57 #endif
  58 #ifdef PB_DS_HT_MAP_TRACE_
  59 #include <iostream>
  60 #endif
  61 #include <debug/debug.h>
  62
  63 namespace __gnu_pbds
  64 {
  65   namespace detail
  66   {
  67
  68 #define PB_DS_CLASS_T_DEC \
  69     template<typename Key, typename Mapped, typename Hash_Fn, \
  70              typename Eq_Fn, typename Allocator, bool Store_Hash, \
  71              typename Comb_Hash_Fn, typename Resize_Policy>
  72
  73 #ifdef PB_DS_DATA_TRUE_INDICATOR
  74 #define PB_DS_CLASS_NAME cc_ht_map_data_
  75 #endif
  76
  77 #ifdef PB_DS_DATA_FALSE_INDICATOR
  78 #define PB_DS_CLASS_NAME cc_ht_map_no_data_
  79 #endif
  80
  81 #define PB_DS_CLASS_C_DEC \
  82     PB_DS_CLASS_NAME<Key, Mapped, Hash_Fn, Eq_Fn, Allocator,    \
  83                      Store_Hash, Comb_Hash_Fn, Resize_Policy>
  84
  85 #define PB_DS_HASH_EQ_FN_C_DEC \
  86     hash_eq_fn<Key, Eq_Fn, Allocator, Store_Hash>
  87
  88 #define PB_DS_RANGED_HASH_FN_C_DEC \
  89     ranged_hash_fn<Key, Hash_Fn, Allocator, Comb_Hash_Fn, Store_Hash>
  90
  91 #define PB_DS_TYPES_TRAITS_C_DEC \
  92     types_traits<Key, Mapped, Allocator, Store_Hash>
  93
  94 #ifdef _GLIBCXX_DEBUG
  95 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
  96     debug_map_base<Key, Eq_Fn, typename Allocator::template rebind<Key>::other::const_reference>
  97 #endif
  98
  99 #ifdef PB_DS_DATA_TRUE_INDICATOR
 100 #define PB_DS_V2F(X) (X).first
 101 #define PB_DS_V2S(X) (X).second
 102 #endif
 103
 104 #ifdef PB_DS_DATA_FALSE_INDICATOR
 105 #define PB_DS_V2F(X) (X)
 106 #define PB_DS_V2S(X) Mapped_Data()
 107 #endif
 108
 109     // <011i$i0|\|-<|-|4i|\|i|\|g |-|4$|-| 74813.
 110     template<typename Key,
 111              typename Mapped,
 112              typename Hash_Fn,
 113              typename Eq_Fn,
 114              typename Allocator,
 115              bool Store_Hash,
 116              typename Comb_Hash_Fn,
 117              typename Resize_Policy >
 118     class PB_DS_CLASS_NAME:
 119 #ifdef _GLIBCXX_DEBUG
 120       protected PB_DS_DEBUG_MAP_BASE_C_DEC,
 121 #endif
 122       public PB_DS_HASH_EQ_FN_C_DEC,
 123       public Resize_Policy,
 124       public PB_DS_RANGED_HASH_FN_C_DEC,
 125       public PB_DS_TYPES_TRAITS_C_DEC
 126     {
 127     private:
 128       typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
 129       typedef typename traits_base::comp_hash comp_hash;
 130       typedef typename traits_base::value_type value_type_;
 131       typedef typename traits_base::pointer pointer_;
 132       typedef typename traits_base::const_pointer const_pointer_;
 133       typedef typename traits_base::reference reference_;
 134       typedef typename traits_base::const_reference const_reference_;
 135
 136       struct entry : public traits_base::stored_value_type
 137       {
 138         typename Allocator::template rebind<entry>::other::pointer m_p_next;
 139       };
 140
 141       typedef cond_dealtor<entry, Allocator> cond_dealtor_t;
 142
 143       typedef typename Allocator::template rebind<entry>::other entry_allocator;
 144       typedef typename entry_allocator::pointer entry_pointer;
 145       typedef typename entry_allocator::const_pointer const_entry_pointer;
 146       typedef typename entry_allocator::reference entry_reference;
 147       typedef typename entry_allocator::const_reference const_entry_reference;
 148
 149       typedef typename Allocator::template rebind<entry_pointer>::other entry_pointer_allocator;
 150       typedef typename entry_pointer_allocator::pointer entry_pointer_array;
 151
 152       typedef PB_DS_RANGED_HASH_FN_C_DEC ranged_hash_fn_base;
 153       typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base;
 154       typedef Resize_Policy resize_base;
 155
 156 #ifdef _GLIBCXX_DEBUG
 157       typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
 158 #endif
 159
 160 #define PB_DS_GEN_POS std::pair<entry_pointer, typename Allocator::size_type>
 161
 162 #include <ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp>
 163 #include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp>
 164 #include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp>
 165 #include <ext/pb_ds/detail/unordered_iterator/iterator.hpp>
 166
 167 #undef PB_DS_GEN_POS
 168
 169     public:
 170       typedef Allocator allocator;
 171       typedef typename Allocator::size_type size_type;
 172       typedef typename Allocator::difference_type difference_type;
 173       typedef Hash_Fn hash_fn;
 174       typedef Eq_Fn eq_fn;
 175       typedef Comb_Hash_Fn comb_hash_fn;
 176       typedef Resize_Policy resize_policy;
 177
 178       enum
 179         {
 180           store_hash = Store_Hash
 181         };
 182
 183       typedef typename traits_base::key_type key_type;
 184       typedef typename traits_base::key_pointer key_pointer;
 185       typedef typename traits_base::const_key_pointer const_key_pointer;
 186       typedef typename traits_base::key_reference key_reference;
 187       typedef typename traits_base::const_key_reference const_key_reference;
 188       typedef typename traits_base::mapped_type mapped_type;
 189       typedef typename traits_base::mapped_pointer mapped_pointer;
 190       typedef typename traits_base::const_mapped_pointer const_mapped_pointer;
 191       typedef typename traits_base::mapped_reference mapped_reference;
 192       typedef typename traits_base::const_mapped_reference const_mapped_reference;
 193       typedef typename traits_base::value_type value_type;
 194       typedef typename traits_base::pointer pointer;
 195       typedef typename traits_base::const_pointer const_pointer;
 196       typedef typename traits_base::reference reference;
 197       typedef typename traits_base::const_reference const_reference;
 198
 199 #ifdef PB_DS_DATA_TRUE_INDICATOR
 200       typedef point_iterator_ point_iterator;
 201 #endif
 202
 203 #ifdef PB_DS_DATA_FALSE_INDICATOR
 204       typedef const_point_iterator_ point_iterator;
 205 #endif
 206
 207       typedef const_point_iterator_ const_point_iterator;
 208
 209 #ifdef PB_DS_DATA_TRUE_INDICATOR
 210       typedef iterator_ iterator;
 211 #endif
 212
 213 #ifdef PB_DS_DATA_FALSE_INDICATOR
 214       typedef const_iterator_ iterator;
 215 #endif
 216
 217       typedef const_iterator_ const_iterator;
 218
 219       PB_DS_CLASS_NAME();
 220
 221       PB_DS_CLASS_NAME(const Hash_Fn&);
 222
 223       PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&);
 224
 225       PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&);
 226
 227       PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&,
 228                        const Resize_Policy&);
 229
 230       PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&);
 231
 232       virtual
 233       ~PB_DS_CLASS_NAME();
 234
 235       void
 236       swap(PB_DS_CLASS_C_DEC&);
 237
 238       template<typename It>
 239       void
 240       copy_from_range(It, It);
 241
 242       void
 243       initialize();
 244
 245       inline size_type
 246       size() const;
 247
 248       inline size_type
 249       max_size() const;
 250
 251       inline bool
 252       empty() const;
 253
 254       Hash_Fn&
 255       get_hash_fn();
 256
 257       const Hash_Fn&
 258       get_hash_fn() const;
 259
 260       Eq_Fn&
 261       get_eq_fn();
 262
 263       const Eq_Fn&
 264       get_eq_fn() const;
 265
 266       Comb_Hash_Fn&
 267       get_comb_hash_fn();
 268
 269       const Comb_Hash_Fn&
 270       get_comb_hash_fn() const;
 271
 272       Resize_Policy&
 273       get_resize_policy();
 274
 275       const Resize_Policy&
 276       get_resize_policy() const;
 277
 278       inline std::pair<point_iterator, bool>
 279       insert(const_reference r_val)
 280       { return insert_imp(r_val, traits_base::m_store_extra_indicator); }
 281
 282       inline mapped_reference
 283       operator[](const_key_reference r_key)
 284       {
 285 #ifdef PB_DS_DATA_TRUE_INDICATOR
 286         return (subscript_imp(r_key, traits_base::m_store_extra_indicator));
 287 #else
 288         insert(r_key);
 289         return traits_base::s_null_mapped;
 290 #endif
 291       }
 292
 293       inline point_iterator
 294       find(const_key_reference);
 295
 296       inline const_point_iterator
 297       find(const_key_reference) const;
 298
 299       inline point_iterator
 300       find_end();
 301
 302       inline const_point_iterator
 303       find_end() const;
 304
 305       inline bool
 306       erase(const_key_reference);
 307
 308       template<typename Pred>
 309       inline size_type
 310       erase_if(Pred);
 311
 312       void
 313       clear();
 314
 315       inline iterator
 316       begin();
 317
 318       inline const_iterator
 319       begin() const;
 320
 321       inline iterator
 322       end();
 323
 324       inline const_iterator
 325       end() const;
 326
 327 #ifdef _GLIBCXX_DEBUG
 328       void
 329       assert_valid() const;
 330 #endif
 331
 332 #ifdef PB_DS_HT_MAP_TRACE_
 333       void
 334       trace() const;
 335 #endif
 336
 337     private:
 338       void
 339       deallocate_all();
 340
 341       inline bool
 342       do_resize_if_needed();
 343
 344       inline void
 345       do_resize_if_needed_no_throw();
 346
 347       void
 348       resize_imp(size_type new_size);
 349
 350       void
 351       do_resize(size_type new_size);
 352
 353       void
 354       resize_imp_no_exceptions(size_type, entry_pointer_array, size_type);
 355
 356       inline entry_pointer
 357       resize_imp_no_exceptions_reassign_pointer(entry_pointer, entry_pointer_array, false_type);
 358
 359       inline entry_pointer
 360       resize_imp_no_exceptions_reassign_pointer(entry_pointer, entry_pointer_array, true_type);
 361
 362       void
 363       deallocate_links_in_list(entry_pointer);
 364
 365       inline entry_pointer
 366       get_entry(const_reference, false_type);
 367
 368       inline entry_pointer
 369       get_entry(const_reference, true_type);
 370
 371       inline void
 372       rels_entry(entry_pointer);
 373
 374 #ifdef PB_DS_DATA_TRUE_INDICATOR
 375       inline mapped_reference
 376       subscript_imp(const_key_reference r_key, false_type)
 377       {
 378         _GLIBCXX_DEBUG_ONLY(assert_valid();)
 379         const size_type pos = ranged_hash_fn_base::operator()(r_key);
 380         entry_pointer p_e = m_entries[pos];
 381         resize_base::notify_insert_search_start();
 382
 383         while (p_e != NULL
 384                && !hash_eq_fn_base::operator()(p_e->m_value.first, r_key))
 385           {
 386             resize_base::notify_insert_search_collision();
 387             p_e = p_e->m_p_next;
 388           }
 389
 390         resize_base::notify_insert_search_end();
 391         if (p_e != NULL)
 392           {
 393             _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);)
 394             return (p_e->m_value.second);
 395           }
 396
 397         _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);)
 398         return insert_new_imp(value_type(r_key, mapped_type()), pos)->second;
 399       }
 400
 401       inline mapped_reference
 402       subscript_imp(const_key_reference r_key, true_type)
 403       {
 404         _GLIBCXX_DEBUG_ONLY(assert_valid();)
 405         comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key);
 406         entry_pointer p_e = m_entries[pos_hash_pair.first];
 407         resize_base::notify_insert_search_start();
 408         while (p_e != NULL &&
 409                !hash_eq_fn_base::operator()(p_e->m_value.first, p_e->m_hash, r_key, pos_hash_pair.second))
 410           {
 411             resize_base::notify_insert_search_collision();
 412             p_e = p_e->m_p_next;
 413           }
 414
 415         resize_base::notify_insert_search_end();
 416         if (p_e != NULL)
 417           {
 418             _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);)
 419             return p_e->m_value.second;
 420           }
 421
 422         _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);)
 423         return insert_new_imp(value_type(r_key, mapped_type()),
 424                               pos_hash_pair)->second;
 425       }
 426 #endif
 427
 428       inline std::pair<point_iterator, bool>
 429       insert_imp(const_reference, false_type);
 430
 431       inline std::pair<point_iterator, bool>
 432       insert_imp(const_reference, true_type);
 433
 434       inline pointer
 435       insert_new_imp(const_reference r_val, size_type pos)
 436       {
 437         if (do_resize_if_needed())
 438           pos = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val));
 439
 440         // Following lines might throw an exception.
 441         entry_pointer p_e = get_entry(r_val, traits_base::m_no_throw_copies_indicator);
 442
 443         // At this point no exceptions can be thrown.
 444         p_e->m_p_next = m_entries[pos];
 445         m_entries[pos] = p_e;
 446         resize_base::notify_inserted(++m_num_used_e);
 447
 448         _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));)
 449         _GLIBCXX_DEBUG_ONLY(assert_valid();)
 450         return &p_e->m_value;
 451       }
 452
 453       inline pointer
 454       insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair)
 455       {
 456         // Following lines might throw an exception.
 457         if (do_resize_if_needed())
 458           r_pos_hash_pair = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val));
 459
 460         entry_pointer p_e = get_entry(r_val, traits_base::m_no_throw_copies_indicator);
 461
 462         // At this point no exceptions can be thrown.
 463         p_e->m_hash = r_pos_hash_pair.second;
 464         p_e->m_p_next = m_entries[r_pos_hash_pair.first];
 465         m_entries[r_pos_hash_pair.first] = p_e;
 466         resize_base::notify_inserted(++m_num_used_e);
 467         _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));)
 468         _GLIBCXX_DEBUG_ONLY(assert_valid();)
 469         return &p_e->m_value;
 470       }
 471
 472       inline pointer
 473       find_key_pointer(const_key_reference r_key, false_type)
 474       {
 475         entry_pointer p_e = m_entries[ranged_hash_fn_base::operator()(r_key)];
 476         resize_base::notify_find_search_start();
 477         while (p_e != NULL &&
 478                !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key))
 479           {
 480             resize_base::notify_find_search_collision();
 481             p_e = p_e->m_p_next;
 482           }
 483
 484         resize_base::notify_find_search_end();
 485
 486 #ifdef _GLIBCXX_DEBUG
 487         if (p_e == NULL)
 488           debug_base::check_key_does_not_exist(r_key);
 489         else
 490           debug_base::check_key_exists(r_key);
 491 #endif
 492         return &p_e->m_value;
 493       }
 494
 495       inline pointer
 496       find_key_pointer(const_key_reference r_key, true_type)
 497       {
 498         comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key);
 499         entry_pointer p_e = m_entries[pos_hash_pair.first];
 500         resize_base::notify_find_search_start();
 501         while (p_e != NULL &&
 502                !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value),
 503                                             p_e->m_hash,
 504                                             r_key, pos_hash_pair.second))
 505           {
 506             resize_base::notify_find_search_collision();
 507             p_e = p_e->m_p_next;
 508           }
 509
 510         resize_base::notify_find_search_end();
 511
 512 #ifdef _GLIBCXX_DEBUG
 513         if (p_e == NULL)
 514           debug_base::check_key_does_not_exist(r_key);
 515         else
 516           debug_base::check_key_exists(r_key);
 517 #endif
 518         return &p_e->m_value;
 519       }
 520
 521       inline bool
 522       erase_in_pos_imp(const_key_reference, size_type);
 523
 524       inline bool
 525       erase_in_pos_imp(const_key_reference, const comp_hash&);
 526
 527       inline void
 528       erase_entry_pointer(entry_pointer&);
 529
 530 #ifdef PB_DS_DATA_TRUE_INDICATOR
 531       void
 532       inc_it_state(pointer& r_p_value,
 533                    std::pair<entry_pointer, size_type>& r_pos) const
 534       {
 535         inc_it_state((const_mapped_pointer& )r_p_value, r_pos);
 536       }
 537 #endif
 538
 539       void
 540       inc_it_state(const_pointer& r_p_value,
 541                    std::pair<entry_pointer, size_type>& r_pos) const
 542       {
 543         _GLIBCXX_DEBUG_ASSERT(r_p_value != NULL);
 544         r_pos.first = r_pos.first->m_p_next;
 545         if (r_pos.first != NULL)
 546           {
 547             r_p_value = &r_pos.first->m_value;
 548             return;
 549           }
 550
 551         for (++r_pos.second; r_pos.second < m_num_e; ++r_pos.second)
 552           if (m_entries[r_pos.second] != NULL)
 553             {
 554               r_pos.first = m_entries[r_pos.second];
 555               r_p_value = &r_pos.first->m_value;
 556               return;
 557             }
 558         r_p_value = NULL;
 559       }
 560
 561       void
 562       get_start_it_state(pointer& r_p_value,
 563                          std::pair<entry_pointer, size_type>& r_pos) const
 564       {
 565         for (r_pos.second = 0; r_pos.second < m_num_e; ++r_pos.second)
 566           if (m_entries[r_pos.second] != NULL)
 567             {
 568               r_pos.first = m_entries[r_pos.second];
 569               r_p_value = &r_pos.first->m_value;
 570               return;
 571             }
 572         r_p_value = NULL;
 573       }
 574
 575 #ifdef _GLIBCXX_DEBUG
 576       void
 577       assert_entry_pointer_array_valid(const entry_pointer_array) const;
 578
 579       void
 580       assert_entry_pointer_valid(const entry_pointer, true_type) const;
 581
 582       void
 583       assert_entry_pointer_valid(const entry_pointer, false_type) const;
 584 #endif
 585
 586 #ifdef PB_DS_HT_MAP_TRACE_
 587       void
 588       trace_list(const_entry_pointer) const;
 589 #endif
 590
 591     private:
 592 #ifdef PB_DS_DATA_TRUE_INDICATOR
 593       friend class iterator_;
 594 #endif
 595
 596       friend class const_iterator_;
 597
 598       static entry_allocator            s_entry_allocator;
 599       static entry_pointer_allocator    s_entry_pointer_allocator;
 600       static iterator                   s_end_it;
 601       static const_iterator             s_const_end_it;
 602       static point_iterator             s_find_end_it;
 603       static const_point_iterator       s_const_find_end_it;
 604
 605       size_type                         m_num_e;
 606       size_type                         m_num_used_e;
 607       entry_pointer_array               m_entries;
 608
 609       enum
 610         {
 611           store_hash_ok = !Store_Hash
 612                           || !is_same<Hash_Fn, __gnu_pbds::null_hash_fn>::value
 613         };
 614
 615       PB_DS_STATIC_ASSERT(sth, store_hash_ok);
 616     };
 617
 618 #include <ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp>
 619 #include <ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp>
 620 #include <ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp>
 621 #include <ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp>
 622 #include <ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp>
 623 #include <ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp>
 624 #include <ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp>
 625 #include <ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp>
 626 #include <ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp>
 627 #include <ext/pb_ds/detail/cc_hash_table_map_/insert_fn_imps.hpp>
 628 #include <ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp>
 629
 630 #undef PB_DS_CLASS_T_DEC
 631 #undef PB_DS_CLASS_C_DEC
 632 #undef PB_DS_HASH_EQ_FN_C_DEC
 633 #undef PB_DS_RANGED_HASH_FN_C_DEC
 634 #undef PB_DS_TYPES_TRAITS_C_DEC
 635 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
 636 #undef PB_DS_CLASS_NAME
 637 #undef PB_DS_V2F
 638 #undef PB_DS_V2S
 639
 640   } // namespace detail
 641 } // namespace __gnu_pbds
 642