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