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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 gp_ht_map_.hpp
  44  * Contains an implementation class for gp_ht_map_.
  45  */
  46
  47 #include <ext/pb_ds/tag_and_trait.hpp>
  48 #include <ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp>
  49 #include <ext/pb_ds/detail/types_traits.hpp>
  50 #include <ext/pb_ds/exception.hpp>
  51 #include <ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp>
  52 #include <utility>
  53 #ifdef PB_DS_HT_MAP_TRACE_
  54 #include <iostream>
  55 #endif
  56 #ifdef _GLIBCXX_DEBUG
  57 #include <ext/pb_ds/detail/map_debug_base.hpp>
  58 #endif
  59 #include <debug/debug.h>
  60
  61 namespace pb_ds
  62 {
  63   namespace detail
  64   {
  65
  66 #define PB_DS_CLASS_T_DEC                                               \
  67     template<                                                           \
  68                                                 typename Key,           \
  69                                                 typename Mapped,        \
  70                                                 class Hash_Fn,          \
  71                                                 class Eq_Fn,            \
  72                                                 class Allocator,        \
  73                                                 bool Store_Hash,        \
  74                                                 class Comb_Probe_Fn,    \
  75                                                 class Probe_Fn,         \
  76                                                 class Resize_Policy>
  77
  78 #ifdef PB_DS_DATA_TRUE_INDICATOR
  79 #define PB_DS_CLASS_NAME gp_ht_map_data_
  80 #endif
  81
  82 #ifdef PB_DS_DATA_FALSE_INDICATOR
  83 #define PB_DS_CLASS_NAME gp_ht_map_no_data_
  84 #endif
  85
  86 #define PB_DS_CLASS_C_DEC                                       \
  87     PB_DS_CLASS_NAME<                                           \
  88                                                 Key,            \
  89                                                 Mapped,         \
  90                                                 Hash_Fn,        \
  91                                                 Eq_Fn,          \
  92                                                 Allocator,      \
  93                                                 Store_Hash,     \
  94                                                 Comb_Probe_Fn,  \
  95                                                 Probe_Fn,       \
  96                                                 Resize_Policy>
  97
  98 #define PB_DS_HASH_EQ_FN_C_DEC                                  \
  99     hash_eq_fn<                                 \
 100                                                 Key,            \
 101                                                 Eq_Fn,          \
 102                                                 Allocator,      \
 103                                                 Store_Hash>
 104
 105 #define PB_DS_RANGED_PROBE_FN_C_DEC                                     \
 106     ranged_probe_fn<                                    \
 107                                                         Key,            \
 108                                                         Hash_Fn,        \
 109                                                         Allocator,      \
 110                                                         Comb_Probe_Fn,  \
 111                                                         Probe_Fn,       \
 112                                                         Store_Hash>
 113
 114 #define PB_DS_TYPES_TRAITS_C_DEC                                \
 115     types_traits<                                               \
 116                                                 Key,            \
 117                                                 Mapped,         \
 118                                                 Allocator,      \
 119                                                 Store_Hash>
 120
 121 #ifdef _GLIBCXX_DEBUG
 122 #define PB_DS_MAP_DEBUG_BASE_C_DEC                                      \
 123     map_debug_base<Key, Eq_Fn, typename Allocator::template rebind<Key>::other::const_reference>
 124 #endif
 125
 126 #ifdef PB_DS_DATA_TRUE_INDICATOR
 127 #define PB_DS_V2F(X) (X).first
 128 #define PB_DS_V2S(X) (X).second
 129 #endif
 130
 131 #ifdef PB_DS_DATA_FALSE_INDICATOR
 132 #define PB_DS_V2F(X) (X)
 133 #define PB_DS_V2S(X) Mapped()
 134 #endif
 135
 136 #define PB_DS_STATIC_ASSERT(UNIQUE, E)                                  \
 137     typedef                                                             \
 138     static_assert_dumclass<                             \
 139                                                                         sizeof(static_assert<(bool)(E)>)> \
 140     UNIQUE##static_assert_type
 141
 142     template<typename Key,
 143              typename Mapped,
 144              class Hash_Fn,
 145              class Eq_Fn,
 146              class Allocator,
 147              bool Store_Hash,
 148              class Comb_Probe_Fn,
 149              class Probe_Fn,
 150              class Resize_Policy>
 151     class PB_DS_CLASS_NAME :
 152 #ifdef _GLIBCXX_DEBUG
 153       protected PB_DS_MAP_DEBUG_BASE_C_DEC,
 154 #endif
 155       public PB_DS_HASH_EQ_FN_C_DEC,
 156       public Resize_Policy,
 157       public PB_DS_RANGED_PROBE_FN_C_DEC,
 158       public PB_DS_TYPES_TRAITS_C_DEC
 159     {
 160
 161     private:
 162
 163       typedef
 164       typename PB_DS_TYPES_TRAITS_C_DEC::store_extra_false_type
 165       store_hash_false_type;
 166
 167       typedef
 168       typename PB_DS_TYPES_TRAITS_C_DEC::store_extra_true_type
 169       store_hash_true_type;
 170
 171       typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type_;
 172
 173       typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer_;
 174
 175       typedef
 176       typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer
 177       const_pointer_;
 178
 179       typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference_;
 180
 181       typedef
 182       typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
 183       const_reference_;
 184
 185 #define PB_DS_GEN_POS                           \
 186       typename Allocator::size_type
 187
 188 #include <ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp>
 189 #include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp>
 190 #include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp>
 191 #include <ext/pb_ds/detail/unordered_iterator/iterator.hpp>
 192
 193 #undef PB_DS_GEN_POS
 194
 195     public:
 196
 197       typedef typename Allocator::size_type size_type;
 198
 199       typedef typename Allocator::difference_type difference_type;
 200
 201       typedef Hash_Fn hash_fn;
 202
 203       typedef Eq_Fn eq_fn;
 204
 205       typedef Allocator allocator;
 206
 207       typedef Probe_Fn probe_fn;
 208
 209       typedef Comb_Probe_Fn comb_probe_fn;
 210
 211       typedef Resize_Policy resize_policy;
 212
 213       enum
 214         {
 215           store_hash = Store_Hash
 216         };
 217
 218       typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type;
 219
 220       typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer;
 221
 222       typedef
 223       typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer
 224       const_key_pointer;
 225
 226       typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference;
 227
 228       typedef
 229       typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference
 230       const_key_reference;
 231
 232       typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type;
 233
 234       typedef
 235       typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer
 236       mapped_pointer;
 237
 238       typedef
 239       typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer
 240       const_mapped_pointer;
 241
 242       typedef
 243       typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference
 244       mapped_reference;
 245
 246       typedef
 247       typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference
 248       const_mapped_reference;
 249
 250       typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type;
 251
 252       typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer;
 253
 254       typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer;
 255
 256       typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference;
 257
 258       typedef
 259       typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
 260       const_reference;
 261
 262 #ifdef PB_DS_DATA_TRUE_INDICATOR
 263       typedef point_iterator_ point_iterator;
 264 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
 265
 266 #ifdef PB_DS_DATA_FALSE_INDICATOR
 267       typedef const_point_iterator_ point_iterator;
 268 #endif // #ifdef PB_DS_DATA_FALSE_INDICATOR
 269
 270       typedef const_point_iterator_ const_point_iterator;
 271
 272 #ifdef PB_DS_DATA_TRUE_INDICATOR
 273       typedef iterator_ iterator;
 274 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
 275
 276 #ifdef PB_DS_DATA_FALSE_INDICATOR
 277       typedef const_iterator_ iterator;
 278 #endif // #ifdef PB_DS_DATA_FALSE_INDICATOR
 279
 280       typedef const_iterator_ const_iterator;
 281
 282     public:
 283
 284       PB_DS_CLASS_NAME();
 285
 286       PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other);
 287
 288       PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn);
 289
 290       PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn);
 291
 292       PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_probe_fn);
 293
 294       PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn);
 295
 296       PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn, const Resize_Policy& r_resize_policy);
 297
 298       template<typename It>
 299       void
 300       copy_from_range(It first_it, It last_it);
 301
 302       virtual
 303       ~PB_DS_CLASS_NAME();
 304
 305       void
 306       swap(PB_DS_CLASS_C_DEC& other);
 307
 308       inline size_type
 309       size() const;
 310
 311       inline size_type
 312       max_size() const;
 313
 314       inline bool
 315       empty() const;
 316
 317       Hash_Fn&
 318       get_hash_fn();
 319
 320       const Hash_Fn&
 321       get_hash_fn() const;
 322
 323       Eq_Fn&
 324       get_eq_fn();
 325
 326       const Eq_Fn&
 327       get_eq_fn() const;
 328
 329       Probe_Fn&
 330       get_probe_fn();
 331
 332       const Probe_Fn&
 333       get_probe_fn() const;
 334
 335       Comb_Probe_Fn&
 336       get_comb_probe_fn();
 337
 338       const Comb_Probe_Fn&
 339       get_comb_probe_fn() const;
 340
 341       Resize_Policy&
 342       get_resize_policy();
 343
 344       const Resize_Policy&
 345       get_resize_policy() const;
 346
 347       inline std::pair<point_iterator, bool>
 348       insert(const_reference r_val)
 349       {
 350         _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
 351
 352           return (insert_imp(r_val, traits_base::m_store_extra_indicator));
 353       }
 354
 355       inline mapped_reference
 356       operator[](const_key_reference r_key)
 357       {
 358 #ifdef PB_DS_DATA_TRUE_INDICATOR
 359         return (subscript_imp(r_key, traits_base::m_store_extra_indicator));
 360 #else // #ifdef PB_DS_DATA_TRUE_INDICATOR
 361         insert(r_key);
 362
 363         return (traits_base::s_null_mapped);
 364 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
 365       }
 366
 367       inline point_iterator
 368       find(const_key_reference r_key);
 369
 370       inline const_point_iterator
 371       find(const_key_reference r_key) const;
 372
 373       inline point_iterator
 374       find_end();
 375
 376       inline const_point_iterator
 377       find_end() const;
 378
 379       inline bool
 380       erase(const_key_reference r_key);
 381
 382       template<typename Pred>
 383       inline size_type
 384       erase_if(Pred prd);
 385
 386       void
 387       clear();
 388
 389       inline iterator
 390       begin();
 391
 392       inline const_iterator
 393       begin() const;
 394
 395       inline iterator
 396       end();
 397
 398       inline const_iterator
 399       end() const;
 400
 401 #ifdef _GLIBCXX_DEBUG
 402       void
 403       assert_valid() const;
 404 #endif
 405
 406 #ifdef PB_DS_HT_MAP_TRACE_
 407       void
 408       trace() const;
 409 #endif
 410
 411     private:
 412       typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
 413
 414       enum ENTRY_STATUS
 415         {
 416           empty_entry_status,
 417           valid_entry_status,
 418           erased_entry_status
 419         };
 420
 421       typedef char entry_status;
 422
 423       struct entry : public PB_DS_TYPES_TRAITS_C_DEC::stored_value_type
 424       {
 425         entry_status m_stat;
 426       };
 427
 428       typedef
 429       typename Allocator::template rebind<entry>::other
 430       entry_allocator;
 431
 432       typedef typename entry_allocator::pointer entry_pointer;
 433
 434       typedef typename entry_allocator::const_pointer const_entry_pointer;
 435
 436       typedef typename entry_allocator::reference entry_reference;
 437
 438       typedef
 439       typename entry_allocator::const_reference
 440       const_entry_reference;
 441
 442       typedef typename entry_allocator::pointer entry_array;
 443
 444       typedef PB_DS_RANGED_PROBE_FN_C_DEC ranged_probe_fn_base;
 445
 446 #ifdef _GLIBCXX_DEBUG
 447       typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base;
 448 #endif
 449
 450       typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base;
 451
 452       typedef Resize_Policy resize_base;
 453
 454 #ifdef PB_DS_DATA_TRUE_INDICATOR
 455       friend class iterator_;
 456 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
 457
 458       friend class const_iterator_;
 459
 460       typedef typename PB_DS_TYPES_TRAITS_C_DEC::comp_hash comp_hash;
 461
 462     private:
 463
 464       void
 465       deallocate_all();
 466
 467       void
 468       initialize();
 469
 470       void
 471       erase_all_valid_entries(entry_array a_entries_resized, size_type size);
 472
 473       inline bool
 474       do_resize_if_needed();
 475
 476       inline void
 477       do_resize_if_needed_no_throw();
 478
 479       void
 480       resize_imp(size_type new_size);
 481
 482       virtual void
 483       do_resize(size_type new_size);
 484
 485       void
 486       resize_imp(entry_array a_entries_resized, size_type old_size);
 487
 488       inline void
 489       resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized, store_hash_false_type);
 490
 491       inline void
 492       resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized, store_hash_true_type);
 493
 494       inline size_type
 495       find_ins_pos(const_key_reference r_key, store_hash_false_type);
 496
 497       inline comp_hash
 498       find_ins_pos(const_key_reference r_key, store_hash_true_type);
 499
 500       inline std::pair<point_iterator, bool>
 501       insert_imp(const_reference r_val, store_hash_false_type);
 502
 503       inline std::pair<point_iterator, bool>
 504       insert_imp(const_reference r_val, store_hash_true_type);
 505
 506       inline pointer
 507       insert_new_imp(const_reference r_val, size_type pos)
 508       {
 509         _GLIBCXX_DEBUG_ASSERT(m_a_entries[pos].m_stat != valid_entry_status);
 510
 511         if (do_resize_if_needed())
 512           pos = find_ins_pos(PB_DS_V2F(r_val),
 513                              traits_base::m_store_extra_indicator);
 514
 515         _GLIBCXX_DEBUG_ASSERT(m_a_entries[pos].m_stat != valid_entry_status);
 516
 517         entry* const p_e = m_a_entries + pos;
 518
 519         new (&p_e->m_value) value_type(r_val);
 520
 521         p_e->m_stat = valid_entry_status;
 522
 523         resize_base::notify_inserted(++m_num_used_e);
 524
 525         _GLIBCXX_DEBUG_ONLY(map_debug_base::
 526                        insert_new(PB_DS_V2F(p_e->m_value));)
 527
 528           _GLIBCXX_DEBUG_ONLY(assert_valid();)
 529
 530           return (&p_e->m_value);
 531       }
 532
 533       inline pointer
 534       insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair)
 535       {
 536         _GLIBCXX_DEBUG_ASSERT(m_a_entries[r_pos_hash_pair.first].m_stat !=
 537                          valid_entry_status);
 538
 539         if (do_resize_if_needed())
 540           r_pos_hash_pair = find_ins_pos(
 541                                          PB_DS_V2F(r_val),
 542                                          traits_base::m_store_extra_indicator);
 543
 544         _GLIBCXX_DEBUG_ASSERT(m_a_entries[r_pos_hash_pair.first].m_stat !=
 545                          valid_entry_status);
 546
 547         entry* const p_e = m_a_entries + r_pos_hash_pair.first;
 548
 549         new (&p_e->m_value) value_type(r_val);
 550
 551         p_e->m_hash = r_pos_hash_pair.second;
 552
 553         p_e->m_stat = valid_entry_status;
 554
 555         resize_base::notify_inserted(++m_num_used_e);
 556
 557         _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(
 558                                                   PB_DS_V2F(p_e->m_value));)
 559
 560           _GLIBCXX_DEBUG_ONLY(assert_valid();)
 561
 562           return (&p_e->m_value);
 563       }
 564
 565 #ifdef PB_DS_DATA_TRUE_INDICATOR
 566       inline mapped_reference
 567       subscript_imp(const_key_reference r_key, store_hash_false_type)
 568       {
 569         _GLIBCXX_DEBUG_ONLY(assert_valid();)
 570
 571           const size_type pos =
 572           find_ins_pos(r_key, traits_base::m_store_extra_indicator);
 573
 574         entry_pointer p_e =& m_a_entries[pos];
 575
 576         if (p_e->m_stat != valid_entry_status)
 577           return (insert_new_imp(
 578                                  value_type(
 579                                             r_key,
 580                                             mapped_type()),
 581                                  pos)->second);
 582
 583         _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);)
 584
 585           return (p_e->m_value.second);
 586       }
 587
 588       inline mapped_reference
 589       subscript_imp(const_key_reference r_key, store_hash_true_type)
 590       {
 591         _GLIBCXX_DEBUG_ONLY(assert_valid();)
 592
 593           comp_hash pos_hash_pair =
 594           find_ins_pos(r_key, traits_base::m_store_extra_indicator);
 595
 596         if (m_a_entries[pos_hash_pair.first].m_stat != valid_entry_status)
 597           return (insert_new_imp(
 598                                  value_type(
 599                                             r_key,
 600                                             mapped_type()),
 601                                  pos_hash_pair)->second);
 602
 603         _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key));
 604
 605         return ((m_a_entries + pos_hash_pair.first)->m_value.second);
 606       }
 607 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
 608
 609       inline pointer
 610       find_key_pointer(const_key_reference r_key, store_hash_false_type)
 611       {
 612         const size_type hash = ranged_probe_fn_base::operator()(r_key);
 613
 614         size_type i;
 615
 616         resize_base::notify_find_search_start();
 617
 618         // Loop until entry is found or until all possible entries accessed.
 619
 620         for (i = 0; i < m_num_e; ++i)
 621           {
 622             const size_type pos =
 623               ranged_probe_fn_base::operator()(                    r_key, hash, i);
 624
 625             entry* const p_e = m_a_entries + pos;
 626
 627             switch(p_e->m_stat)
 628               {
 629               case empty_entry_status:
 630                 {
 631                   resize_base::notify_find_search_end();
 632
 633                   _GLIBCXX_DEBUG_ONLY(map_debug_base::
 634                                  check_key_does_not_exist(r_key);)
 635
 636                     return (NULL);
 637                 }
 638                 break;
 639               case valid_entry_status:
 640                 if (hash_eq_fn_base::operator()(
 641                                                 PB_DS_V2F(p_e->m_value),
 642                                                 r_key))
 643                   {
 644                     resize_base::notify_find_search_end();
 645
 646                     _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);)
 647
 648                       return ((pointer)&p_e->m_value);
 649                   }
 650                 break;
 651               case erased_entry_status:
 652                 break;
 653               default:
 654                 _GLIBCXX_DEBUG_ASSERT(0);
 655               };
 656
 657             resize_base::notify_find_search_collision();
 658           }
 659
 660         _GLIBCXX_DEBUG_ONLY(map_debug_base::
 661                        check_key_does_not_exist(r_key);)
 662
 663           resize_base::notify_find_search_end();
 664
 665         return (NULL);
 666       }
 667
 668       inline pointer
 669       find_key_pointer(const_key_reference r_key, store_hash_true_type)
 670       {
 671         comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(r_key);
 672
 673         size_type i;
 674
 675         resize_base::notify_find_search_start();
 676
 677         // Loop until entry is found or until all possible entries accessed.
 678
 679         for (i = 0; i < m_num_e; ++i)
 680           {
 681             const size_type pos =
 682               ranged_probe_fn_base::operator()(                    r_key, pos_hash_pair.second, i);
 683
 684             entry* const p_e = m_a_entries + pos;
 685
 686             switch(p_e->m_stat)
 687               {
 688               case empty_entry_status:
 689                 {
 690                   resize_base::notify_find_search_end();
 691
 692                   _GLIBCXX_DEBUG_ONLY(map_debug_base::
 693                                  check_key_does_not_exist(r_key);)
 694
 695                     return (NULL);
 696                 }
 697                 break;
 698               case valid_entry_status:
 699                 if (hash_eq_fn_base::operator()(
 700                                                 PB_DS_V2F(p_e->m_value),
 701                                                 p_e->m_hash,
 702                                                 r_key, pos_hash_pair.second))
 703                   {
 704                     resize_base::notify_find_search_end();
 705
 706                     _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);)
 707
 708                       return ((pointer)&p_e->m_value);
 709                   }
 710                 break;
 711               case erased_entry_status:
 712                 break;
 713               default:
 714                 _GLIBCXX_DEBUG_ASSERT(0);
 715               };
 716
 717             resize_base::notify_find_search_collision();
 718           }
 719
 720         _GLIBCXX_DEBUG_ONLY(map_debug_base::
 721                        check_key_does_not_exist(r_key);)
 722
 723           resize_base::notify_find_search_end();
 724
 725         return (NULL);
 726       }
 727
 728       inline bool
 729       erase_imp(const_key_reference r_key,  true_type);
 730
 731       inline bool
 732       erase_imp(const_key_reference r_key,  false_type);
 733
 734       inline void
 735       erase_entry(entry_pointer p_e);
 736
 737 #ifdef PB_DS_DATA_TRUE_INDICATOR
 738       void
 739       inc_it_state(pointer& r_p_value, size_type& r_pos) const
 740       {
 741         inc_it_state((const_mapped_pointer& )r_p_value, r_pos);
 742       }
 743 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
 744
 745       void
 746       inc_it_state(const_pointer& r_p_value, size_type& r_pos) const
 747       {
 748         _GLIBCXX_DEBUG_ASSERT(r_p_value != NULL);
 749
 750         for (++r_pos; r_pos < m_num_e; ++r_pos)
 751           {
 752             const_entry_pointer p_e =& m_a_entries[r_pos];
 753
 754             if (p_e->m_stat == valid_entry_status)
 755               {
 756                 r_p_value =& p_e->m_value;
 757
 758                 return;
 759               }
 760           }
 761
 762         r_p_value = NULL;
 763       }
 764
 765       void
 766       get_start_it_state(const_pointer& r_p_value, size_type& r_pos) const
 767       {
 768         for (r_pos = 0; r_pos < m_num_e; ++r_pos)
 769           {
 770             const_entry_pointer p_e =& m_a_entries[r_pos];
 771
 772             if (p_e->m_stat == valid_entry_status)
 773               {
 774                 r_p_value =& p_e->m_value;
 775
 776                 return;
 777               }
 778           }
 779
 780         r_p_value = NULL;
 781       }
 782
 783       void
 784       get_start_it_state(pointer& r_p_value, size_type& r_pos)
 785       {
 786         for (r_pos = 0; r_pos < m_num_e; ++r_pos)
 787           {
 788             entry_pointer p_e =& m_a_entries[r_pos];
 789
 790             if (p_e->m_stat == valid_entry_status)
 791               {
 792                 r_p_value =& p_e->m_value;
 793
 794                 return;
 795               }
 796           }
 797
 798         r_p_value = NULL;
 799       }
 800
 801 #ifdef _GLIBCXX_DEBUG
 802       void
 803       assert_entry_array_valid(const entry_array a_entries,
 804                                store_hash_false_type) const;
 805
 806       void
 807       assert_entry_array_valid(const entry_array a_entries,
 808                                store_hash_true_type) const;
 809 #endif
 810
 811     private:
 812       static entry_allocator s_entry_allocator;
 813
 814       entry_pointer m_a_entries;
 815
 816       size_type m_num_e;
 817
 818       size_type m_num_used_e;
 819
 820       static iterator s_end_it;
 821
 822       static const_iterator s_const_end_it;
 823
 824       enum
 825         {
 826           store_hash_ok =
 827           !Store_Hash ||
 828           !is_same<
 829           Hash_Fn,
 830           pb_ds::null_hash_fn>::value
 831         };
 832
 833       PB_DS_STATIC_ASSERT(sth, store_hash_ok);
 834     };
 835
 836 #include <ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp>
 837 #include <ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp>
 838 #include <ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp>
 839 #include <ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp>
 840 #include <ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp>
 841 #include <ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp>
 842 #include <ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp>
 843 #include <ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp>
 844 #include <ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp>
 845 #include <ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp>
 846
 847 #undef PB_DS_CLASS_T_DEC
 848
 849 #undef PB_DS_CLASS_C_DEC
 850
 851 #undef PB_DS_HASH_EQ_FN_C_DEC
 852
 853 #undef PB_DS_RANGED_PROBE_FN_C_DEC
 854
 855 #undef PB_DS_TYPES_TRAITS_C_DEC
 856
 857 #undef PB_DS_MAP_DEBUG_BASE_C_DEC
 858
 859 #undef PB_DS_CLASS_NAME
 860
 861 #undef PB_DS_V2F
 862 #undef PB_DS_V2S
 863
 864 #undef PB_DS_STATIC_ASSERT
 865
 866   } // namespace detail
 867 } // namespace pb_ds
 868