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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2015 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
  55 namespace __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 _Alloc::template rebind<Key>::other::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 typename _Alloc::template rebind<entry>::other entry_allocator;
 173       typedef typename entry_allocator::pointer entry_pointer;
 174       typedef typename entry_allocator::const_pointer const_entry_pointer;
 175       typedef typename entry_allocator::reference entry_reference;
 176       typedef typename entry_allocator::const_reference const_entry_reference;
 177       typedef typename entry_allocator::pointer entry_array;
 178
 179       typedef PB_DS_RANGED_PROBE_FN_C_DEC       ranged_probe_fn_base;
 180
 181 #ifdef _GLIBCXX_DEBUG
 182       typedef PB_DS_DEBUG_MAP_BASE_C_DEC        debug_base;
 183 #endif
 184
 185       typedef PB_DS_HASH_EQ_FN_C_DEC            hash_eq_fn_base;
 186       typedef Resize_Policy                     resize_base;
 187
 188 #define PB_DS_GEN_POS typename _Alloc::size_type
 189
 190 #include <ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp>
 191 #include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp>
 192 #include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp>
 193 #include <ext/pb_ds/detail/unordered_iterator/iterator.hpp>
 194
 195 #undef PB_DS_GEN_POS
 196
 197     public:
 198       typedef _Alloc                            allocator_type;
 199       typedef typename _Alloc::size_type        size_type;
 200       typedef typename _Alloc::difference_type  difference_type;
 201       typedef Hash_Fn                           hash_fn;
 202       typedef Eq_Fn                             eq_fn;
 203       typedef Probe_Fn                          probe_fn;
 204       typedef Comb_Probe_Fn                     comb_probe_fn;
 205       typedef Resize_Policy                     resize_policy;
 206
 207       /// Value stores hash, true or false.
 208       enum
 209         {
 210           store_hash = Store_Hash
 211         };
 212
 213       typedef typename traits_base::key_type    key_type;
 214       typedef typename traits_base::key_pointer key_pointer;
 215       typedef typename traits_base::key_const_pointer key_const_pointer;
 216       typedef typename traits_base::key_reference key_reference;
 217       typedef typename traits_base::key_const_reference key_const_reference;
 218       typedef typename traits_base::mapped_type mapped_type;
 219       typedef typename traits_base::mapped_pointer mapped_pointer;
 220       typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
 221       typedef typename traits_base::mapped_reference mapped_reference;
 222       typedef typename traits_base::mapped_const_reference mapped_const_reference;
 223       typedef typename traits_base::value_type value_type;
 224       typedef typename traits_base::pointer pointer;
 225       typedef typename traits_base::const_pointer const_pointer;
 226       typedef typename traits_base::reference reference;
 227       typedef typename traits_base::const_reference const_reference;
 228
 229 #ifdef PB_DS_DATA_TRUE_INDICATOR
 230       typedef point_iterator_                   point_iterator;
 231 #endif
 232
 233 #ifdef PB_DS_DATA_FALSE_INDICATOR
 234       typedef point_const_iterator_             point_iterator;
 235 #endif
 236
 237       typedef point_const_iterator_             point_const_iterator;
 238
 239 #ifdef PB_DS_DATA_TRUE_INDICATOR
 240       typedef iterator_                         iterator;
 241 #endif
 242
 243 #ifdef PB_DS_DATA_FALSE_INDICATOR
 244       typedef const_iterator_                   iterator;
 245 #endif
 246
 247       typedef const_iterator_                   const_iterator;
 248
 249       PB_DS_GP_HASH_NAME();
 250
 251       PB_DS_GP_HASH_NAME(const PB_DS_CLASS_C_DEC&);
 252
 253       PB_DS_GP_HASH_NAME(const Hash_Fn&);
 254
 255       PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&);
 256
 257       PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&);
 258
 259       PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&,
 260                          const Probe_Fn&);
 261
 262       PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&,
 263                          const Probe_Fn&, const Resize_Policy&);
 264
 265       template<typename It>
 266       void
 267       copy_from_range(It, It);
 268
 269       virtual
 270       ~PB_DS_GP_HASH_NAME();
 271
 272       void
 273       swap(PB_DS_CLASS_C_DEC&);
 274
 275       inline size_type
 276       size() const;
 277
 278       inline size_type
 279       max_size() const;
 280
 281       /// True if size() == 0.
 282       inline bool
 283       empty() const;
 284
 285       /// Return current hash_fn.
 286       Hash_Fn&
 287       get_hash_fn();
 288
 289       /// Return current const hash_fn.
 290       const Hash_Fn&
 291       get_hash_fn() const;
 292
 293       /// Return current eq_fn.
 294       Eq_Fn&
 295       get_eq_fn();
 296
 297       /// Return current const eq_fn.
 298       const Eq_Fn&
 299       get_eq_fn() const;
 300
 301       /// Return current probe_fn.
 302       Probe_Fn&
 303       get_probe_fn();
 304
 305       /// Return current const probe_fn.
 306       const Probe_Fn&
 307       get_probe_fn() const;
 308
 309       /// Return current comb_probe_fn.
 310       Comb_Probe_Fn&
 311       get_comb_probe_fn();
 312
 313       /// Return current const comb_probe_fn.
 314       const Comb_Probe_Fn&
 315       get_comb_probe_fn() const;
 316
 317       /// Return current resize_policy.
 318       Resize_Policy&
 319       get_resize_policy();
 320
 321       /// Return current const resize_policy.
 322       const Resize_Policy&
 323       get_resize_policy() const;
 324
 325       inline std::pair<point_iterator, bool>
 326       insert(const_reference r_val)
 327       {
 328        _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid(__FILE__, __LINE__);)
 329         return insert_imp(r_val, traits_base::m_store_extra_indicator);
 330       }
 331
 332       inline mapped_reference
 333       operator[](key_const_reference r_key)
 334       {
 335 #ifdef PB_DS_DATA_TRUE_INDICATOR
 336         return subscript_imp(r_key, traits_base::m_store_extra_indicator);
 337 #else
 338         insert(r_key);
 339         return traits_base::s_null_type;
 340 #endif
 341       }
 342
 343       inline point_iterator
 344       find(key_const_reference);
 345
 346       inline point_const_iterator
 347       find(key_const_reference) const;
 348
 349       inline point_iterator
 350       find_end();
 351
 352       inline point_const_iterator
 353       find_end() const;
 354
 355       inline bool
 356       erase(key_const_reference);
 357
 358       template<typename Pred>
 359         inline size_type
 360         erase_if(Pred);
 361
 362       void
 363       clear();
 364
 365       inline iterator
 366       begin();
 367
 368       inline const_iterator
 369       begin() const;
 370
 371       inline iterator
 372       end();
 373
 374       inline const_iterator
 375       end() const;
 376
 377 #ifdef _GLIBCXX_DEBUG
 378       void
 379       assert_valid(const char*, int) const;
 380 #endif
 381
 382 #ifdef PB_DS_HT_MAP_TRACE_
 383       void
 384       trace() const;
 385 #endif
 386
 387     private:
 388 #ifdef PB_DS_DATA_TRUE_INDICATOR
 389       friend class iterator_;
 390 #endif
 391
 392       friend class const_iterator_;
 393
 394       void
 395       deallocate_all();
 396
 397       void
 398       initialize();
 399
 400       void
 401       erase_all_valid_entries(entry_array, size_type);
 402
 403       inline bool
 404       do_resize_if_needed();
 405
 406       inline void
 407       do_resize_if_needed_no_throw();
 408
 409       void
 410       resize_imp(size_type);
 411
 412       virtual void
 413       do_resize(size_type);
 414
 415       void
 416       resize_imp(entry_array, size_type);
 417
 418       inline void
 419       resize_imp_reassign(entry_pointer, entry_array, false_type);
 420
 421       inline void
 422       resize_imp_reassign(entry_pointer, entry_array, true_type);
 423
 424       inline size_type
 425       find_ins_pos(key_const_reference, false_type);
 426
 427       inline comp_hash
 428       find_ins_pos(key_const_reference, true_type);
 429
 430       inline std::pair<point_iterator, bool>
 431       insert_imp(const_reference, false_type);
 432
 433       inline std::pair<point_iterator, bool>
 434       insert_imp(const_reference, true_type);
 435
 436       inline pointer
 437       insert_new_imp(const_reference r_val, size_type pos)
 438       {
 439         _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status);
 440
 441         if (do_resize_if_needed())
 442           pos = find_ins_pos(PB_DS_V2F(r_val),
 443                              traits_base::m_store_extra_indicator);
 444
 445         _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status);
 446         entry* const p_e = m_entries + pos;
 447         new (&p_e->m_value) value_type(r_val);
 448         p_e->m_stat = valid_entry_status;
 449         resize_base::notify_inserted(++m_num_used_e);
 450
 451         _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(p_e->m_value));)
 452         _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
 453         return &p_e->m_value;
 454       }
 455
 456       inline pointer
 457       insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair)
 458       {
 459         _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat !=
 460                               valid_entry_status);
 461
 462         if (do_resize_if_needed())
 463           r_pos_hash_pair = find_ins_pos(PB_DS_V2F(r_val),
 464                                          traits_base::m_store_extra_indicator);
 465
 466         _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat !=
 467                               valid_entry_status);
 468
 469         entry* const p_e = m_entries + r_pos_hash_pair.first;
 470         new (&p_e->m_value) value_type(r_val);
 471         p_e->m_hash = r_pos_hash_pair.second;
 472         p_e->m_stat = valid_entry_status;
 473
 474         resize_base::notify_inserted(++m_num_used_e);
 475
 476         _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(p_e->m_value));)
 477         _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
 478         return &p_e->m_value;
 479       }
 480
 481 #ifdef PB_DS_DATA_TRUE_INDICATOR
 482       inline mapped_reference
 483       subscript_imp(key_const_reference key, false_type)
 484       {
 485         _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
 486
 487         const size_type pos = find_ins_pos(key,
 488                                          traits_base::m_store_extra_indicator);
 489
 490         entry_pointer p_e = &m_entries[pos];
 491         if (p_e->m_stat != valid_entry_status)
 492           return insert_new_imp(value_type(key, mapped_type()), pos)->second;
 493
 494         PB_DS_CHECK_KEY_EXISTS(key)
 495         return p_e->m_value.second;
 496       }
 497
 498       inline mapped_reference
 499       subscript_imp(key_const_reference key, true_type)
 500       {
 501         _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
 502
 503         comp_hash pos_hash_pair = find_ins_pos(key,
 504                                          traits_base::m_store_extra_indicator);
 505
 506         if (m_entries[pos_hash_pair.first].m_stat != valid_entry_status)
 507           return insert_new_imp(value_type(key, mapped_type()),
 508                                  pos_hash_pair)->second;
 509
 510         PB_DS_CHECK_KEY_EXISTS(key)
 511         return (m_entries + pos_hash_pair.first)->m_value.second;
 512       }
 513 #endif
 514
 515       inline pointer
 516       find_key_pointer(key_const_reference key, false_type)
 517       {
 518         const size_type hash = ranged_probe_fn_base::operator()(key);
 519         resize_base::notify_find_search_start();
 520
 521         // Loop until entry is found or until all possible entries accessed.
 522         for (size_type i = 0; i < m_num_e; ++i)
 523           {
 524             const size_type pos = ranged_probe_fn_base::operator()(key,
 525                                                                    hash, i);
 526
 527             entry* const p_e = m_entries + pos;
 528             switch (p_e->m_stat)
 529               {
 530               case empty_entry_status:
 531                 {
 532                   resize_base::notify_find_search_end();
 533                   PB_DS_CHECK_KEY_DOES_NOT_EXIST(key)
 534                   return 0;
 535                 }
 536                 break;
 537               case valid_entry_status:
 538                 if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), key))
 539                   {
 540                     resize_base::notify_find_search_end();
 541                     PB_DS_CHECK_KEY_EXISTS(key)
 542                     return pointer(&p_e->m_value);
 543                   }
 544                 break;
 545               case erased_entry_status:
 546                 break;
 547               default:
 548                 _GLIBCXX_DEBUG_ASSERT(0);
 549               };
 550
 551             resize_base::notify_find_search_collision();
 552           }
 553
 554         PB_DS_CHECK_KEY_DOES_NOT_EXIST(key)
 555         resize_base::notify_find_search_end();
 556         return 0;
 557       }
 558
 559       inline pointer
 560       find_key_pointer(key_const_reference key, true_type)
 561       {
 562         comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(key);
 563         resize_base::notify_find_search_start();
 564
 565         // Loop until entry is found or until all possible entries accessed.
 566         for (size_type i = 0; i < m_num_e; ++i)
 567           {
 568             const size_type pos =
 569               ranged_probe_fn_base::operator()(key, pos_hash_pair.second, i);
 570
 571             entry* const p_e = m_entries + pos;
 572
 573             switch(p_e->m_stat)
 574               {
 575               case empty_entry_status:
 576                 {
 577                   resize_base::notify_find_search_end();
 578                   PB_DS_CHECK_KEY_DOES_NOT_EXIST(key)
 579                   return 0;
 580                 }
 581                 break;
 582               case valid_entry_status:
 583                 if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value),
 584                                                 p_e->m_hash,
 585                                                 key, pos_hash_pair.second))
 586                   {
 587                     resize_base::notify_find_search_end();
 588                     PB_DS_CHECK_KEY_EXISTS(key)
 589                     return pointer(&p_e->m_value);
 590                   }
 591                 break;
 592               case erased_entry_status:
 593                 break;
 594               default:
 595                 _GLIBCXX_DEBUG_ASSERT(0);
 596               };
 597
 598             resize_base::notify_find_search_collision();
 599           }
 600
 601         PB_DS_CHECK_KEY_DOES_NOT_EXIST(key)
 602         resize_base::notify_find_search_end();
 603         return 0;
 604       }
 605
 606       inline bool
 607       erase_imp(key_const_reference, true_type);
 608
 609       inline bool
 610       erase_imp(key_const_reference, false_type);
 611
 612       inline void
 613       erase_entry(entry_pointer);
 614
 615 #ifdef PB_DS_DATA_TRUE_INDICATOR
 616       void
 617       inc_it_state(pointer& r_p_value, size_type& r_pos) const
 618       { inc_it_state((mapped_const_pointer& )r_p_value, r_pos); }
 619 #endif
 620
 621       void
 622       inc_it_state(const_pointer& r_p_value, size_type& r_pos) const
 623       {
 624         _GLIBCXX_DEBUG_ASSERT(r_p_value != 0);
 625         for (++r_pos; r_pos < m_num_e; ++r_pos)
 626           {
 627             const_entry_pointer p_e =& m_entries[r_pos];
 628             if (p_e->m_stat == valid_entry_status)
 629               {
 630                 r_p_value =& p_e->m_value;
 631                 return;
 632               }
 633           }
 634         r_p_value = 0;
 635       }
 636
 637       void
 638       get_start_it_state(const_pointer& r_p_value, size_type& r_pos) const
 639       {
 640         for (r_pos = 0; r_pos < m_num_e; ++r_pos)
 641           {
 642             const_entry_pointer p_e = &m_entries[r_pos];
 643             if (p_e->m_stat == valid_entry_status)
 644               {
 645                 r_p_value = &p_e->m_value;
 646                 return;
 647               }
 648           }
 649         r_p_value = 0;
 650       }
 651
 652       void
 653       get_start_it_state(pointer& r_p_value, size_type& r_pos)
 654       {
 655         for (r_pos = 0; r_pos < m_num_e; ++r_pos)
 656           {
 657             entry_pointer p_e = &m_entries[r_pos];
 658             if (p_e->m_stat == valid_entry_status)
 659               {
 660                 r_p_value = &p_e->m_value;
 661                 return;
 662               }
 663           }
 664         r_p_value = 0;
 665       }
 666
 667 #ifdef _GLIBCXX_DEBUG
 668       void
 669       assert_entry_array_valid(const entry_array, false_type,
 670                                const char*, int) const;
 671
 672       void
 673       assert_entry_array_valid(const entry_array, true_type,
 674                                const char*, int) const;
 675 #endif
 676
 677       static entry_allocator    s_entry_allocator;
 678       static iterator           s_end_it;
 679       static const_iterator     s_const_end_it;
 680
 681       size_type                 m_num_e;
 682       size_type                 m_num_used_e;
 683       entry_pointer             m_entries;
 684
 685       enum
 686         {
 687           store_hash_ok = !Store_Hash
 688                           || !is_same<Hash_Fn, __gnu_pbds::null_type>::value
 689         };
 690
 691       PB_DS_STATIC_ASSERT(sth, store_hash_ok);
 692     };
 693
 694 #include <ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp>
 695 #include <ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp>
 696 #include <ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp>
 697 #include <ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp>
 698 #include <ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp>
 699 #include <ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp>
 700 #include <ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp>
 701 #include <ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp>
 702 #include <ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp>
 703 #include <ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp>
 704
 705 #undef PB_DS_CLASS_T_DEC
 706 #undef PB_DS_CLASS_C_DEC
 707 #undef PB_DS_HASH_EQ_FN_C_DEC
 708 #undef PB_DS_RANGED_PROBE_FN_C_DEC
 709 #undef PB_DS_GP_HASH_TRAITS_BASE
 710 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
 711 #undef PB_DS_GP_HASH_NAME
 712   } // namespace detail
 713 } // namespace __gnu_pbds