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