Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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
  714.