163d1a8abSmrg // -*- C++ -*- 263d1a8abSmrg 3*ec02198aSmrg // Copyright (C) 2005-2020 Free Software Foundation, Inc. 463d1a8abSmrg // 563d1a8abSmrg // This file is part of the GNU ISO C++ Library. This library is free 663d1a8abSmrg // software; you can redistribute it and/or modify it under the terms 763d1a8abSmrg // of the GNU General Public License as published by the Free Software 863d1a8abSmrg // Foundation; either version 3, or (at your option) any later 963d1a8abSmrg // version. 1063d1a8abSmrg 1163d1a8abSmrg // This library is distributed in the hope that it will be useful, but 1263d1a8abSmrg // WITHOUT ANY WARRANTY; without even the implied warranty of 1363d1a8abSmrg // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1463d1a8abSmrg // General Public License for more details. 1563d1a8abSmrg 1663d1a8abSmrg // Under Section 7 of GPL version 3, you are granted additional 1763d1a8abSmrg // permissions described in the GCC Runtime Library Exception, version 1863d1a8abSmrg // 3.1, as published by the Free Software Foundation. 1963d1a8abSmrg 2063d1a8abSmrg // You should have received a copy of the GNU General Public License and 2163d1a8abSmrg // a copy of the GCC Runtime Library Exception along with this program; 2263d1a8abSmrg // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2363d1a8abSmrg // <http://www.gnu.org/licenses/>. 2463d1a8abSmrg 2563d1a8abSmrg // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 2663d1a8abSmrg 2763d1a8abSmrg // Permission to use, copy, modify, sell, and distribute this software 2863d1a8abSmrg // is hereby granted without fee, provided that the above copyright 2963d1a8abSmrg // notice appears in all copies, and that both that copyright notice 3063d1a8abSmrg // and this permission notice appear in supporting documentation. None 3163d1a8abSmrg // of the above authors, nor IBM Haifa Research Laboratories, make any 3263d1a8abSmrg // representation about the suitability of this software for any 3363d1a8abSmrg // purpose. It is provided "as is" without express or implied 3463d1a8abSmrg // warranty. 3563d1a8abSmrg 3663d1a8abSmrg /** 3763d1a8abSmrg * @file gp_hash_table_map_/gp_ht_map_.hpp 3863d1a8abSmrg * Contains an implementation class for general probing hash. 3963d1a8abSmrg */ 4063d1a8abSmrg 4163d1a8abSmrg #include <ext/pb_ds/tag_and_trait.hpp> 4263d1a8abSmrg #include <ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp> 4363d1a8abSmrg #include <ext/pb_ds/detail/types_traits.hpp> 4463d1a8abSmrg #include <ext/pb_ds/exception.hpp> 4563d1a8abSmrg #include <ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp> 4663d1a8abSmrg #include <utility> 4763d1a8abSmrg #ifdef PB_DS_HT_MAP_TRACE_ 4863d1a8abSmrg #include <iostream> 4963d1a8abSmrg #endif 5063d1a8abSmrg #ifdef _GLIBCXX_DEBUG 5163d1a8abSmrg #include <ext/pb_ds/detail/debug_map_base.hpp> 5263d1a8abSmrg #endif 5363d1a8abSmrg #include <debug/debug.h> 5463d1a8abSmrg 5563d1a8abSmrg namespace __gnu_pbds 5663d1a8abSmrg { 5763d1a8abSmrg namespace detail 5863d1a8abSmrg { 5963d1a8abSmrg #ifdef PB_DS_DATA_TRUE_INDICATOR 6063d1a8abSmrg #define PB_DS_GP_HASH_NAME gp_ht_map 6163d1a8abSmrg #endif 6263d1a8abSmrg 6363d1a8abSmrg #ifdef PB_DS_DATA_FALSE_INDICATOR 6463d1a8abSmrg #define PB_DS_GP_HASH_NAME gp_ht_set 6563d1a8abSmrg #endif 6663d1a8abSmrg 6763d1a8abSmrg #define PB_DS_CLASS_T_DEC \ 6863d1a8abSmrg template<typename Key, typename Mapped, typename Hash_Fn, typename Eq_Fn, \ 6963d1a8abSmrg typename _Alloc, bool Store_Hash, typename Comb_Probe_Fn, \ 7063d1a8abSmrg typename Probe_Fn, typename Resize_Policy> 7163d1a8abSmrg 7263d1a8abSmrg #define PB_DS_CLASS_C_DEC \ 7363d1a8abSmrg PB_DS_GP_HASH_NAME<Key, Mapped, Hash_Fn, Eq_Fn, _Alloc, \ 7463d1a8abSmrg Store_Hash, Comb_Probe_Fn, Probe_Fn, Resize_Policy> 7563d1a8abSmrg 7663d1a8abSmrg #define PB_DS_HASH_EQ_FN_C_DEC \ 7763d1a8abSmrg hash_eq_fn<Key, Eq_Fn, _Alloc, Store_Hash> 7863d1a8abSmrg 7963d1a8abSmrg #define PB_DS_RANGED_PROBE_FN_C_DEC \ 8063d1a8abSmrg ranged_probe_fn<Key, Hash_Fn, _Alloc, Comb_Probe_Fn, Probe_Fn, Store_Hash> 8163d1a8abSmrg 8263d1a8abSmrg #define PB_DS_GP_HASH_TRAITS_BASE \ 8363d1a8abSmrg types_traits<Key, Mapped, _Alloc, Store_Hash> 8463d1a8abSmrg 8563d1a8abSmrg #ifdef _GLIBCXX_DEBUG 8663d1a8abSmrg #define PB_DS_DEBUG_MAP_BASE_C_DEC \ 8763d1a8abSmrg debug_map_base<Key, Eq_Fn, \ 88*ec02198aSmrg typename rebind_traits<_Alloc, Key>::const_reference> 8963d1a8abSmrg #endif 9063d1a8abSmrg 9163d1a8abSmrg 9263d1a8abSmrg /** 9363d1a8abSmrg * A general-probing hash-based container. 9463d1a8abSmrg * 9563d1a8abSmrg * 9663d1a8abSmrg * @ingroup hash-detail 9763d1a8abSmrg * 9863d1a8abSmrg * @tparam Key Key type. 9963d1a8abSmrg * 10063d1a8abSmrg * @tparam Mapped Map type. 10163d1a8abSmrg * 10263d1a8abSmrg * @tparam Hash_Fn Hashing functor. 10363d1a8abSmrg * Default is __gnu_cxx::hash. 10463d1a8abSmrg * 10563d1a8abSmrg * @tparam Eq_Fn Equal functor. 10663d1a8abSmrg * Default std::equal_to<Key> 10763d1a8abSmrg * 10863d1a8abSmrg * @tparam _Alloc Allocator type. 10963d1a8abSmrg * 11063d1a8abSmrg * @tparam Store_Hash If key type stores extra metadata. 11163d1a8abSmrg * Defaults to false. 11263d1a8abSmrg * 11363d1a8abSmrg * @tparam Comb_Probe_Fn Combining probe functor. 11463d1a8abSmrg * If Hash_Fn is not null_type, then this 11563d1a8abSmrg * is the ranged-probe functor; otherwise, 11663d1a8abSmrg * this is the range-hashing functor. 11763d1a8abSmrg * XXX See Design::Hash-Based Containers::Hash Policies. 11863d1a8abSmrg * Default direct_mask_range_hashing. 11963d1a8abSmrg * 12063d1a8abSmrg * @tparam Probe_Fn Probe functor. 12163d1a8abSmrg * Defaults to linear_probe_fn, 12263d1a8abSmrg * also quadratic_probe_fn. 12363d1a8abSmrg * 12463d1a8abSmrg * @tparam Resize_Policy Resizes hash. 12563d1a8abSmrg * Defaults to hash_standard_resize_policy, 12663d1a8abSmrg * using hash_exponential_size_policy and 12763d1a8abSmrg * hash_load_check_resize_trigger. 12863d1a8abSmrg * 12963d1a8abSmrg * 13063d1a8abSmrg * Bases are: detail::hash_eq_fn, Resize_Policy, detail::ranged_probe_fn, 13163d1a8abSmrg * detail::types_traits. (Optional: detail::debug_map_base.) 13263d1a8abSmrg */ 13363d1a8abSmrg template<typename Key, 13463d1a8abSmrg typename Mapped, 13563d1a8abSmrg typename Hash_Fn, 13663d1a8abSmrg typename Eq_Fn, 13763d1a8abSmrg typename _Alloc, 13863d1a8abSmrg bool Store_Hash, 13963d1a8abSmrg typename Comb_Probe_Fn, 14063d1a8abSmrg typename Probe_Fn, 14163d1a8abSmrg typename Resize_Policy> 14263d1a8abSmrg class PB_DS_GP_HASH_NAME : 14363d1a8abSmrg #ifdef _GLIBCXX_DEBUG 14463d1a8abSmrg protected PB_DS_DEBUG_MAP_BASE_C_DEC, 14563d1a8abSmrg #endif 14663d1a8abSmrg public PB_DS_HASH_EQ_FN_C_DEC, 14763d1a8abSmrg public Resize_Policy, 14863d1a8abSmrg public PB_DS_RANGED_PROBE_FN_C_DEC, 14963d1a8abSmrg public PB_DS_GP_HASH_TRAITS_BASE 15063d1a8abSmrg { 15163d1a8abSmrg private: 15263d1a8abSmrg typedef PB_DS_GP_HASH_TRAITS_BASE traits_base; 15363d1a8abSmrg typedef typename traits_base::value_type value_type_; 15463d1a8abSmrg typedef typename traits_base::pointer pointer_; 15563d1a8abSmrg typedef typename traits_base::const_pointer const_pointer_; 15663d1a8abSmrg typedef typename traits_base::reference reference_; 15763d1a8abSmrg typedef typename traits_base::const_reference const_reference_; 15863d1a8abSmrg typedef typename traits_base::comp_hash comp_hash; 15963d1a8abSmrg 16063d1a8abSmrg enum entry_status 16163d1a8abSmrg { 16263d1a8abSmrg empty_entry_status, 16363d1a8abSmrg valid_entry_status, 16463d1a8abSmrg erased_entry_status 16563d1a8abSmrg } __attribute__ ((__packed__)); 16663d1a8abSmrg 16763d1a8abSmrg struct entry : public traits_base::stored_data_type 16863d1a8abSmrg { 16963d1a8abSmrg entry_status m_stat; 17063d1a8abSmrg }; 17163d1a8abSmrg 172*ec02198aSmrg typedef rebind_traits<_Alloc, entry> entry_traits; 173*ec02198aSmrg typedef typename entry_traits::allocator_type entry_allocator; 174*ec02198aSmrg typedef typename entry_traits::pointer entry_pointer; 175*ec02198aSmrg typedef typename entry_traits::const_pointer const_entry_pointer; 176*ec02198aSmrg typedef typename entry_traits::reference entry_reference; 177*ec02198aSmrg typedef typename entry_traits::const_reference const_entry_reference; 178*ec02198aSmrg typedef typename entry_traits::pointer entry_array; 17963d1a8abSmrg 18063d1a8abSmrg typedef PB_DS_RANGED_PROBE_FN_C_DEC ranged_probe_fn_base; 18163d1a8abSmrg 18263d1a8abSmrg #ifdef _GLIBCXX_DEBUG 18363d1a8abSmrg typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 18463d1a8abSmrg #endif 18563d1a8abSmrg 18663d1a8abSmrg typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base; 18763d1a8abSmrg typedef Resize_Policy resize_base; 18863d1a8abSmrg 18963d1a8abSmrg #define PB_DS_GEN_POS typename _Alloc::size_type 19063d1a8abSmrg 19163d1a8abSmrg #include <ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp> 19263d1a8abSmrg #include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp> 19363d1a8abSmrg #include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp> 19463d1a8abSmrg #include <ext/pb_ds/detail/unordered_iterator/iterator.hpp> 19563d1a8abSmrg 19663d1a8abSmrg #undef PB_DS_GEN_POS 19763d1a8abSmrg 19863d1a8abSmrg public: 19963d1a8abSmrg typedef _Alloc allocator_type; 20063d1a8abSmrg typedef typename _Alloc::size_type size_type; 20163d1a8abSmrg typedef typename _Alloc::difference_type difference_type; 20263d1a8abSmrg typedef Hash_Fn hash_fn; 20363d1a8abSmrg typedef Eq_Fn eq_fn; 20463d1a8abSmrg typedef Probe_Fn probe_fn; 20563d1a8abSmrg typedef Comb_Probe_Fn comb_probe_fn; 20663d1a8abSmrg typedef Resize_Policy resize_policy; 20763d1a8abSmrg 20863d1a8abSmrg /// Value stores hash, true or false. 20963d1a8abSmrg enum 21063d1a8abSmrg { 21163d1a8abSmrg store_hash = Store_Hash 21263d1a8abSmrg }; 21363d1a8abSmrg 21463d1a8abSmrg typedef typename traits_base::key_type key_type; 21563d1a8abSmrg typedef typename traits_base::key_pointer key_pointer; 21663d1a8abSmrg typedef typename traits_base::key_const_pointer key_const_pointer; 21763d1a8abSmrg typedef typename traits_base::key_reference key_reference; 21863d1a8abSmrg typedef typename traits_base::key_const_reference key_const_reference; 21963d1a8abSmrg typedef typename traits_base::mapped_type mapped_type; 22063d1a8abSmrg typedef typename traits_base::mapped_pointer mapped_pointer; 22163d1a8abSmrg typedef typename traits_base::mapped_const_pointer mapped_const_pointer; 22263d1a8abSmrg typedef typename traits_base::mapped_reference mapped_reference; 22363d1a8abSmrg typedef typename traits_base::mapped_const_reference mapped_const_reference; 22463d1a8abSmrg typedef typename traits_base::value_type value_type; 22563d1a8abSmrg typedef typename traits_base::pointer pointer; 22663d1a8abSmrg typedef typename traits_base::const_pointer const_pointer; 22763d1a8abSmrg typedef typename traits_base::reference reference; 22863d1a8abSmrg typedef typename traits_base::const_reference const_reference; 22963d1a8abSmrg 23063d1a8abSmrg #ifdef PB_DS_DATA_TRUE_INDICATOR 23163d1a8abSmrg typedef point_iterator_ point_iterator; 23263d1a8abSmrg #endif 23363d1a8abSmrg 23463d1a8abSmrg #ifdef PB_DS_DATA_FALSE_INDICATOR 23563d1a8abSmrg typedef point_const_iterator_ point_iterator; 23663d1a8abSmrg #endif 23763d1a8abSmrg 23863d1a8abSmrg typedef point_const_iterator_ point_const_iterator; 23963d1a8abSmrg 24063d1a8abSmrg #ifdef PB_DS_DATA_TRUE_INDICATOR 24163d1a8abSmrg typedef iterator_ iterator; 24263d1a8abSmrg #endif 24363d1a8abSmrg 24463d1a8abSmrg #ifdef PB_DS_DATA_FALSE_INDICATOR 24563d1a8abSmrg typedef const_iterator_ iterator; 24663d1a8abSmrg #endif 24763d1a8abSmrg 24863d1a8abSmrg typedef const_iterator_ const_iterator; 24963d1a8abSmrg 25063d1a8abSmrg PB_DS_GP_HASH_NAME(); 25163d1a8abSmrg 25263d1a8abSmrg PB_DS_GP_HASH_NAME(const PB_DS_CLASS_C_DEC&); 25363d1a8abSmrg 25463d1a8abSmrg PB_DS_GP_HASH_NAME(const Hash_Fn&); 25563d1a8abSmrg 25663d1a8abSmrg PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&); 25763d1a8abSmrg 25863d1a8abSmrg PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&); 25963d1a8abSmrg 26063d1a8abSmrg PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&, 26163d1a8abSmrg const Probe_Fn&); 26263d1a8abSmrg 26363d1a8abSmrg PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&, 26463d1a8abSmrg const Probe_Fn&, const Resize_Policy&); 26563d1a8abSmrg 26663d1a8abSmrg template<typename It> 26763d1a8abSmrg void 26863d1a8abSmrg copy_from_range(It, It); 26963d1a8abSmrg 27063d1a8abSmrg virtual 27163d1a8abSmrg ~PB_DS_GP_HASH_NAME(); 27263d1a8abSmrg 27363d1a8abSmrg void 27463d1a8abSmrg swap(PB_DS_CLASS_C_DEC&); 27563d1a8abSmrg 27663d1a8abSmrg inline size_type 27763d1a8abSmrg size() const; 27863d1a8abSmrg 27963d1a8abSmrg inline size_type 28063d1a8abSmrg max_size() const; 28163d1a8abSmrg 28263d1a8abSmrg /// True if size() == 0. 2830fc04c29Smrg _GLIBCXX_NODISCARD inline bool 28463d1a8abSmrg empty() const; 28563d1a8abSmrg 28663d1a8abSmrg /// Return current hash_fn. 28763d1a8abSmrg Hash_Fn& 28863d1a8abSmrg get_hash_fn(); 28963d1a8abSmrg 29063d1a8abSmrg /// Return current const hash_fn. 29163d1a8abSmrg const Hash_Fn& 29263d1a8abSmrg get_hash_fn() const; 29363d1a8abSmrg 29463d1a8abSmrg /// Return current eq_fn. 29563d1a8abSmrg Eq_Fn& 29663d1a8abSmrg get_eq_fn(); 29763d1a8abSmrg 29863d1a8abSmrg /// Return current const eq_fn. 29963d1a8abSmrg const Eq_Fn& 30063d1a8abSmrg get_eq_fn() const; 30163d1a8abSmrg 30263d1a8abSmrg /// Return current probe_fn. 30363d1a8abSmrg Probe_Fn& 30463d1a8abSmrg get_probe_fn(); 30563d1a8abSmrg 30663d1a8abSmrg /// Return current const probe_fn. 30763d1a8abSmrg const Probe_Fn& 30863d1a8abSmrg get_probe_fn() const; 30963d1a8abSmrg 31063d1a8abSmrg /// Return current comb_probe_fn. 31163d1a8abSmrg Comb_Probe_Fn& 31263d1a8abSmrg get_comb_probe_fn(); 31363d1a8abSmrg 31463d1a8abSmrg /// Return current const comb_probe_fn. 31563d1a8abSmrg const Comb_Probe_Fn& 31663d1a8abSmrg get_comb_probe_fn() const; 31763d1a8abSmrg 31863d1a8abSmrg /// Return current resize_policy. 31963d1a8abSmrg Resize_Policy& 32063d1a8abSmrg get_resize_policy(); 32163d1a8abSmrg 32263d1a8abSmrg /// Return current const resize_policy. 32363d1a8abSmrg const Resize_Policy& 32463d1a8abSmrg get_resize_policy() const; 32563d1a8abSmrg 32663d1a8abSmrg inline std::pair<point_iterator, bool> insert(const_reference r_val)32763d1a8abSmrg insert(const_reference r_val) 32863d1a8abSmrg { 32963d1a8abSmrg _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid(__FILE__, __LINE__);) 33063d1a8abSmrg return insert_imp(r_val, traits_base::m_store_extra_indicator); 33163d1a8abSmrg } 33263d1a8abSmrg 33363d1a8abSmrg inline mapped_reference operator [](key_const_reference r_key)33463d1a8abSmrg operator[](key_const_reference r_key) 33563d1a8abSmrg { 33663d1a8abSmrg #ifdef PB_DS_DATA_TRUE_INDICATOR 33763d1a8abSmrg return subscript_imp(r_key, traits_base::m_store_extra_indicator); 33863d1a8abSmrg #else 33963d1a8abSmrg insert(r_key); 34063d1a8abSmrg return traits_base::s_null_type; 34163d1a8abSmrg #endif 34263d1a8abSmrg } 34363d1a8abSmrg 34463d1a8abSmrg inline point_iterator 34563d1a8abSmrg find(key_const_reference); 34663d1a8abSmrg 34763d1a8abSmrg inline point_const_iterator 34863d1a8abSmrg find(key_const_reference) const; 34963d1a8abSmrg 35063d1a8abSmrg inline point_iterator 35163d1a8abSmrg find_end(); 35263d1a8abSmrg 35363d1a8abSmrg inline point_const_iterator 35463d1a8abSmrg find_end() const; 35563d1a8abSmrg 35663d1a8abSmrg inline bool 35763d1a8abSmrg erase(key_const_reference); 35863d1a8abSmrg 35963d1a8abSmrg template<typename Pred> 36063d1a8abSmrg inline size_type 36163d1a8abSmrg erase_if(Pred); 36263d1a8abSmrg 36363d1a8abSmrg void 36463d1a8abSmrg clear(); 36563d1a8abSmrg 36663d1a8abSmrg inline iterator 36763d1a8abSmrg begin(); 36863d1a8abSmrg 36963d1a8abSmrg inline const_iterator 37063d1a8abSmrg begin() const; 37163d1a8abSmrg 37263d1a8abSmrg inline iterator 37363d1a8abSmrg end(); 37463d1a8abSmrg 37563d1a8abSmrg inline const_iterator 37663d1a8abSmrg end() const; 37763d1a8abSmrg 37863d1a8abSmrg #ifdef _GLIBCXX_DEBUG 37963d1a8abSmrg void 38063d1a8abSmrg assert_valid(const char*, int) const; 38163d1a8abSmrg #endif 38263d1a8abSmrg 38363d1a8abSmrg #ifdef PB_DS_HT_MAP_TRACE_ 38463d1a8abSmrg void 38563d1a8abSmrg trace() const; 38663d1a8abSmrg #endif 38763d1a8abSmrg 38863d1a8abSmrg private: 38963d1a8abSmrg #ifdef PB_DS_DATA_TRUE_INDICATOR 39063d1a8abSmrg friend class iterator_; 39163d1a8abSmrg #endif 39263d1a8abSmrg 39363d1a8abSmrg friend class const_iterator_; 39463d1a8abSmrg 39563d1a8abSmrg void 39663d1a8abSmrg deallocate_all(); 39763d1a8abSmrg 39863d1a8abSmrg void 39963d1a8abSmrg initialize(); 40063d1a8abSmrg 40163d1a8abSmrg void 40263d1a8abSmrg erase_all_valid_entries(entry_array, size_type); 40363d1a8abSmrg 40463d1a8abSmrg inline bool 40563d1a8abSmrg do_resize_if_needed(); 40663d1a8abSmrg 40763d1a8abSmrg inline void 40863d1a8abSmrg do_resize_if_needed_no_throw(); 40963d1a8abSmrg 41063d1a8abSmrg void 41163d1a8abSmrg resize_imp(size_type); 41263d1a8abSmrg 41363d1a8abSmrg virtual void 41463d1a8abSmrg do_resize(size_type); 41563d1a8abSmrg 41663d1a8abSmrg void 41763d1a8abSmrg resize_imp(entry_array, size_type); 41863d1a8abSmrg 41963d1a8abSmrg inline void 42063d1a8abSmrg resize_imp_reassign(entry_pointer, entry_array, false_type); 42163d1a8abSmrg 42263d1a8abSmrg inline void 42363d1a8abSmrg resize_imp_reassign(entry_pointer, entry_array, true_type); 42463d1a8abSmrg 42563d1a8abSmrg inline size_type 42663d1a8abSmrg find_ins_pos(key_const_reference, false_type); 42763d1a8abSmrg 42863d1a8abSmrg inline comp_hash 42963d1a8abSmrg find_ins_pos(key_const_reference, true_type); 43063d1a8abSmrg 43163d1a8abSmrg inline std::pair<point_iterator, bool> 43263d1a8abSmrg insert_imp(const_reference, false_type); 43363d1a8abSmrg 43463d1a8abSmrg inline std::pair<point_iterator, bool> 43563d1a8abSmrg insert_imp(const_reference, true_type); 43663d1a8abSmrg 43763d1a8abSmrg inline pointer insert_new_imp(const_reference r_val,size_type pos)43863d1a8abSmrg insert_new_imp(const_reference r_val, size_type pos) 43963d1a8abSmrg { 44063d1a8abSmrg _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status); 44163d1a8abSmrg 44263d1a8abSmrg if (do_resize_if_needed()) 44363d1a8abSmrg pos = find_ins_pos(PB_DS_V2F(r_val), 44463d1a8abSmrg traits_base::m_store_extra_indicator); 44563d1a8abSmrg 44663d1a8abSmrg _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status); 44763d1a8abSmrg entry* const p_e = m_entries + pos; 44863d1a8abSmrg new (&p_e->m_value) value_type(r_val); 44963d1a8abSmrg p_e->m_stat = valid_entry_status; 45063d1a8abSmrg resize_base::notify_inserted(++m_num_used_e); 45163d1a8abSmrg 45263d1a8abSmrg _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(p_e->m_value));) 45363d1a8abSmrg _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 45463d1a8abSmrg return &p_e->m_value; 45563d1a8abSmrg } 45663d1a8abSmrg 45763d1a8abSmrg inline pointer insert_new_imp(const_reference r_val,comp_hash & r_pos_hash_pair)45863d1a8abSmrg insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair) 45963d1a8abSmrg { 46063d1a8abSmrg _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat != 46163d1a8abSmrg valid_entry_status); 46263d1a8abSmrg 46363d1a8abSmrg if (do_resize_if_needed()) 46463d1a8abSmrg r_pos_hash_pair = find_ins_pos(PB_DS_V2F(r_val), 46563d1a8abSmrg traits_base::m_store_extra_indicator); 46663d1a8abSmrg 46763d1a8abSmrg _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat != 46863d1a8abSmrg valid_entry_status); 46963d1a8abSmrg 47063d1a8abSmrg entry* const p_e = m_entries + r_pos_hash_pair.first; 47163d1a8abSmrg new (&p_e->m_value) value_type(r_val); 47263d1a8abSmrg p_e->m_hash = r_pos_hash_pair.second; 47363d1a8abSmrg p_e->m_stat = valid_entry_status; 47463d1a8abSmrg 47563d1a8abSmrg resize_base::notify_inserted(++m_num_used_e); 47663d1a8abSmrg 47763d1a8abSmrg _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(p_e->m_value));) 47863d1a8abSmrg _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 47963d1a8abSmrg return &p_e->m_value; 48063d1a8abSmrg } 48163d1a8abSmrg 48263d1a8abSmrg #ifdef PB_DS_DATA_TRUE_INDICATOR 48363d1a8abSmrg inline mapped_reference subscript_imp(key_const_reference key,false_type)48463d1a8abSmrg subscript_imp(key_const_reference key, false_type) 48563d1a8abSmrg { 48663d1a8abSmrg _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 48763d1a8abSmrg 48863d1a8abSmrg const size_type pos = find_ins_pos(key, 48963d1a8abSmrg traits_base::m_store_extra_indicator); 49063d1a8abSmrg 49163d1a8abSmrg entry_pointer p_e = &m_entries[pos]; 49263d1a8abSmrg if (p_e->m_stat != valid_entry_status) 49363d1a8abSmrg return insert_new_imp(value_type(key, mapped_type()), pos)->second; 49463d1a8abSmrg 49563d1a8abSmrg PB_DS_CHECK_KEY_EXISTS(key) 49663d1a8abSmrg return p_e->m_value.second; 49763d1a8abSmrg } 49863d1a8abSmrg 49963d1a8abSmrg inline mapped_reference subscript_imp(key_const_reference key,true_type)50063d1a8abSmrg subscript_imp(key_const_reference key, true_type) 50163d1a8abSmrg { 50263d1a8abSmrg _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 50363d1a8abSmrg 50463d1a8abSmrg comp_hash pos_hash_pair = find_ins_pos(key, 50563d1a8abSmrg traits_base::m_store_extra_indicator); 50663d1a8abSmrg 50763d1a8abSmrg if (m_entries[pos_hash_pair.first].m_stat != valid_entry_status) 50863d1a8abSmrg return insert_new_imp(value_type(key, mapped_type()), 50963d1a8abSmrg pos_hash_pair)->second; 51063d1a8abSmrg 51163d1a8abSmrg PB_DS_CHECK_KEY_EXISTS(key) 51263d1a8abSmrg return (m_entries + pos_hash_pair.first)->m_value.second; 51363d1a8abSmrg } 51463d1a8abSmrg #endif 51563d1a8abSmrg 51663d1a8abSmrg inline pointer find_key_pointer(key_const_reference key,false_type)51763d1a8abSmrg find_key_pointer(key_const_reference key, false_type) 51863d1a8abSmrg { 51963d1a8abSmrg const size_type hash = ranged_probe_fn_base::operator()(key); 52063d1a8abSmrg resize_base::notify_find_search_start(); 52163d1a8abSmrg 52263d1a8abSmrg // Loop until entry is found or until all possible entries accessed. 52363d1a8abSmrg for (size_type i = 0; i < m_num_e; ++i) 52463d1a8abSmrg { 52563d1a8abSmrg const size_type pos = ranged_probe_fn_base::operator()(key, 52663d1a8abSmrg hash, i); 52763d1a8abSmrg 52863d1a8abSmrg entry* const p_e = m_entries + pos; 52963d1a8abSmrg switch (p_e->m_stat) 53063d1a8abSmrg { 53163d1a8abSmrg case empty_entry_status: 53263d1a8abSmrg { 53363d1a8abSmrg resize_base::notify_find_search_end(); 53463d1a8abSmrg PB_DS_CHECK_KEY_DOES_NOT_EXIST(key) 53563d1a8abSmrg return 0; 53663d1a8abSmrg } 53763d1a8abSmrg break; 53863d1a8abSmrg case valid_entry_status: 53963d1a8abSmrg if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), key)) 54063d1a8abSmrg { 54163d1a8abSmrg resize_base::notify_find_search_end(); 54263d1a8abSmrg PB_DS_CHECK_KEY_EXISTS(key) 54363d1a8abSmrg return pointer(&p_e->m_value); 54463d1a8abSmrg } 54563d1a8abSmrg break; 54663d1a8abSmrg case erased_entry_status: 54763d1a8abSmrg break; 54863d1a8abSmrg default: 54963d1a8abSmrg _GLIBCXX_DEBUG_ASSERT(0); 55063d1a8abSmrg }; 55163d1a8abSmrg 55263d1a8abSmrg resize_base::notify_find_search_collision(); 55363d1a8abSmrg } 55463d1a8abSmrg 55563d1a8abSmrg PB_DS_CHECK_KEY_DOES_NOT_EXIST(key) 55663d1a8abSmrg resize_base::notify_find_search_end(); 55763d1a8abSmrg return 0; 55863d1a8abSmrg } 55963d1a8abSmrg 56063d1a8abSmrg inline pointer find_key_pointer(key_const_reference key,true_type)56163d1a8abSmrg find_key_pointer(key_const_reference key, true_type) 56263d1a8abSmrg { 56363d1a8abSmrg comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(key); 56463d1a8abSmrg resize_base::notify_find_search_start(); 56563d1a8abSmrg 56663d1a8abSmrg // Loop until entry is found or until all possible entries accessed. 56763d1a8abSmrg for (size_type i = 0; i < m_num_e; ++i) 56863d1a8abSmrg { 56963d1a8abSmrg const size_type pos = 57063d1a8abSmrg ranged_probe_fn_base::operator()(key, pos_hash_pair.second, i); 57163d1a8abSmrg 57263d1a8abSmrg entry* const p_e = m_entries + pos; 57363d1a8abSmrg 57463d1a8abSmrg switch(p_e->m_stat) 57563d1a8abSmrg { 57663d1a8abSmrg case empty_entry_status: 57763d1a8abSmrg { 57863d1a8abSmrg resize_base::notify_find_search_end(); 57963d1a8abSmrg PB_DS_CHECK_KEY_DOES_NOT_EXIST(key) 58063d1a8abSmrg return 0; 58163d1a8abSmrg } 58263d1a8abSmrg break; 58363d1a8abSmrg case valid_entry_status: 58463d1a8abSmrg if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), 58563d1a8abSmrg p_e->m_hash, 58663d1a8abSmrg key, pos_hash_pair.second)) 58763d1a8abSmrg { 58863d1a8abSmrg resize_base::notify_find_search_end(); 58963d1a8abSmrg PB_DS_CHECK_KEY_EXISTS(key) 59063d1a8abSmrg return pointer(&p_e->m_value); 59163d1a8abSmrg } 59263d1a8abSmrg break; 59363d1a8abSmrg case erased_entry_status: 59463d1a8abSmrg break; 59563d1a8abSmrg default: 59663d1a8abSmrg _GLIBCXX_DEBUG_ASSERT(0); 59763d1a8abSmrg }; 59863d1a8abSmrg 59963d1a8abSmrg resize_base::notify_find_search_collision(); 60063d1a8abSmrg } 60163d1a8abSmrg 60263d1a8abSmrg PB_DS_CHECK_KEY_DOES_NOT_EXIST(key) 60363d1a8abSmrg resize_base::notify_find_search_end(); 60463d1a8abSmrg return 0; 60563d1a8abSmrg } 60663d1a8abSmrg 60763d1a8abSmrg inline bool 60863d1a8abSmrg erase_imp(key_const_reference, true_type); 60963d1a8abSmrg 61063d1a8abSmrg inline bool 61163d1a8abSmrg erase_imp(key_const_reference, false_type); 61263d1a8abSmrg 61363d1a8abSmrg inline void 61463d1a8abSmrg erase_entry(entry_pointer); 61563d1a8abSmrg 61663d1a8abSmrg #ifdef PB_DS_DATA_TRUE_INDICATOR 61763d1a8abSmrg void inc_it_state(pointer & r_p_value,size_type & r_pos) const61863d1a8abSmrg inc_it_state(pointer& r_p_value, size_type& r_pos) const 61963d1a8abSmrg { inc_it_state((mapped_const_pointer& )r_p_value, r_pos); } 62063d1a8abSmrg #endif 62163d1a8abSmrg 62263d1a8abSmrg void inc_it_state(const_pointer & r_p_value,size_type & r_pos) const62363d1a8abSmrg inc_it_state(const_pointer& r_p_value, size_type& r_pos) const 62463d1a8abSmrg { 62563d1a8abSmrg _GLIBCXX_DEBUG_ASSERT(r_p_value != 0); 62663d1a8abSmrg for (++r_pos; r_pos < m_num_e; ++r_pos) 62763d1a8abSmrg { 62863d1a8abSmrg const_entry_pointer p_e =& m_entries[r_pos]; 62963d1a8abSmrg if (p_e->m_stat == valid_entry_status) 63063d1a8abSmrg { 63163d1a8abSmrg r_p_value =& p_e->m_value; 63263d1a8abSmrg return; 63363d1a8abSmrg } 63463d1a8abSmrg } 63563d1a8abSmrg r_p_value = 0; 63663d1a8abSmrg } 63763d1a8abSmrg 63863d1a8abSmrg void get_start_it_state(const_pointer & r_p_value,size_type & r_pos) const63963d1a8abSmrg get_start_it_state(const_pointer& r_p_value, size_type& r_pos) const 64063d1a8abSmrg { 64163d1a8abSmrg for (r_pos = 0; r_pos < m_num_e; ++r_pos) 64263d1a8abSmrg { 64363d1a8abSmrg const_entry_pointer p_e = &m_entries[r_pos]; 64463d1a8abSmrg if (p_e->m_stat == valid_entry_status) 64563d1a8abSmrg { 64663d1a8abSmrg r_p_value = &p_e->m_value; 64763d1a8abSmrg return; 64863d1a8abSmrg } 64963d1a8abSmrg } 65063d1a8abSmrg r_p_value = 0; 65163d1a8abSmrg } 65263d1a8abSmrg 65363d1a8abSmrg void get_start_it_state(pointer & r_p_value,size_type & r_pos)65463d1a8abSmrg get_start_it_state(pointer& r_p_value, size_type& r_pos) 65563d1a8abSmrg { 65663d1a8abSmrg for (r_pos = 0; r_pos < m_num_e; ++r_pos) 65763d1a8abSmrg { 65863d1a8abSmrg entry_pointer p_e = &m_entries[r_pos]; 65963d1a8abSmrg if (p_e->m_stat == valid_entry_status) 66063d1a8abSmrg { 66163d1a8abSmrg r_p_value = &p_e->m_value; 66263d1a8abSmrg return; 66363d1a8abSmrg } 66463d1a8abSmrg } 66563d1a8abSmrg r_p_value = 0; 66663d1a8abSmrg } 66763d1a8abSmrg 66863d1a8abSmrg #ifdef _GLIBCXX_DEBUG 66963d1a8abSmrg void 67063d1a8abSmrg assert_entry_array_valid(const entry_array, false_type, 67163d1a8abSmrg const char*, int) const; 67263d1a8abSmrg 67363d1a8abSmrg void 67463d1a8abSmrg assert_entry_array_valid(const entry_array, true_type, 67563d1a8abSmrg const char*, int) const; 67663d1a8abSmrg #endif 67763d1a8abSmrg 67863d1a8abSmrg static entry_allocator s_entry_allocator; 67963d1a8abSmrg static iterator s_end_it; 68063d1a8abSmrg static const_iterator s_const_end_it; 68163d1a8abSmrg 68263d1a8abSmrg size_type m_num_e; 68363d1a8abSmrg size_type m_num_used_e; 68463d1a8abSmrg entry_pointer m_entries; 68563d1a8abSmrg 68663d1a8abSmrg enum 68763d1a8abSmrg { 68863d1a8abSmrg store_hash_ok = !Store_Hash 68963d1a8abSmrg || !is_same<Hash_Fn, __gnu_pbds::null_type>::value 69063d1a8abSmrg }; 69163d1a8abSmrg 69263d1a8abSmrg PB_DS_STATIC_ASSERT(sth, store_hash_ok); 69363d1a8abSmrg }; 69463d1a8abSmrg 69563d1a8abSmrg #include <ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp> 69663d1a8abSmrg #include <ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp> 69763d1a8abSmrg #include <ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp> 69863d1a8abSmrg #include <ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp> 69963d1a8abSmrg #include <ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp> 70063d1a8abSmrg #include <ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp> 70163d1a8abSmrg #include <ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp> 70263d1a8abSmrg #include <ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp> 70363d1a8abSmrg #include <ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp> 70463d1a8abSmrg #include <ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp> 70563d1a8abSmrg 70663d1a8abSmrg #undef PB_DS_CLASS_T_DEC 70763d1a8abSmrg #undef PB_DS_CLASS_C_DEC 70863d1a8abSmrg #undef PB_DS_HASH_EQ_FN_C_DEC 70963d1a8abSmrg #undef PB_DS_RANGED_PROBE_FN_C_DEC 71063d1a8abSmrg #undef PB_DS_GP_HASH_TRAITS_BASE 71163d1a8abSmrg #undef PB_DS_DEBUG_MAP_BASE_C_DEC 71263d1a8abSmrg #undef PB_DS_GP_HASH_NAME 71363d1a8abSmrg } // namespace detail 71463d1a8abSmrg } // namespace __gnu_pbds 715