1951a39d68df598db08dfced8b4707755864a0492Ying Wang// -*- C++ -*- 2951a39d68df598db08dfced8b4707755864a0492Ying Wang 343f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh// Copyright (C) 2005, 2006, 2007, 2009, 2010 Free Software Foundation, Inc. 4951a39d68df598db08dfced8b4707755864a0492Ying Wang// 5951a39d68df598db08dfced8b4707755864a0492Ying Wang// This file is part of the GNU ISO C++ Library. This library is free 6951a39d68df598db08dfced8b4707755864a0492Ying Wang// software; you can redistribute it and/or modify it under the terms 7951a39d68df598db08dfced8b4707755864a0492Ying Wang// of the GNU General Public License as published by the Free Software 8951a39d68df598db08dfced8b4707755864a0492Ying Wang// Foundation; either version 3, or (at your option) any later 9951a39d68df598db08dfced8b4707755864a0492Ying Wang// version. 10951a39d68df598db08dfced8b4707755864a0492Ying Wang 11951a39d68df598db08dfced8b4707755864a0492Ying Wang// This library is distributed in the hope that it will be useful, but 12951a39d68df598db08dfced8b4707755864a0492Ying Wang// WITHOUT ANY WARRANTY; without even the implied warranty of 13951a39d68df598db08dfced8b4707755864a0492Ying Wang// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14951a39d68df598db08dfced8b4707755864a0492Ying Wang// General Public License for more details. 15951a39d68df598db08dfced8b4707755864a0492Ying Wang 16951a39d68df598db08dfced8b4707755864a0492Ying Wang// Under Section 7 of GPL version 3, you are granted additional 17951a39d68df598db08dfced8b4707755864a0492Ying Wang// permissions described in the GCC Runtime Library Exception, version 18951a39d68df598db08dfced8b4707755864a0492Ying Wang// 3.1, as published by the Free Software Foundation. 19951a39d68df598db08dfced8b4707755864a0492Ying Wang 20951a39d68df598db08dfced8b4707755864a0492Ying Wang// You should have received a copy of the GNU General Public License and 21951a39d68df598db08dfced8b4707755864a0492Ying Wang// a copy of the GCC Runtime Library Exception along with this program; 22951a39d68df598db08dfced8b4707755864a0492Ying Wang// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23951a39d68df598db08dfced8b4707755864a0492Ying Wang// <http://www.gnu.org/licenses/>. 24951a39d68df598db08dfced8b4707755864a0492Ying Wang 25951a39d68df598db08dfced8b4707755864a0492Ying Wang// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26951a39d68df598db08dfced8b4707755864a0492Ying Wang 27951a39d68df598db08dfced8b4707755864a0492Ying Wang// Permission to use, copy, modify, sell, and distribute this software 28951a39d68df598db08dfced8b4707755864a0492Ying Wang// is hereby granted without fee, provided that the above copyright 29951a39d68df598db08dfced8b4707755864a0492Ying Wang// notice appears in all copies, and that both that copyright notice 30951a39d68df598db08dfced8b4707755864a0492Ying Wang// and this permission notice appear in supporting documentation. None 31951a39d68df598db08dfced8b4707755864a0492Ying Wang// of the above authors, nor IBM Haifa Research Laboratories, make any 32951a39d68df598db08dfced8b4707755864a0492Ying Wang// representation about the suitability of this software for any 33951a39d68df598db08dfced8b4707755864a0492Ying Wang// purpose. It is provided "as is" without express or implied 34951a39d68df598db08dfced8b4707755864a0492Ying Wang// warranty. 35951a39d68df598db08dfced8b4707755864a0492Ying Wang 36951a39d68df598db08dfced8b4707755864a0492Ying Wang/** 37951a39d68df598db08dfced8b4707755864a0492Ying Wang * @file cc_ht_map_.hpp 38951a39d68df598db08dfced8b4707755864a0492Ying Wang * Contains an implementation class for cc_ht_map_. 39951a39d68df598db08dfced8b4707755864a0492Ying Wang */ 40951a39d68df598db08dfced8b4707755864a0492Ying Wang 41951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <utility> 42951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <iterator> 43951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/cond_dealtor.hpp> 44951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/tag_and_trait.hpp> 45951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp> 46951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/types_traits.hpp> 47951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/exception.hpp> 48951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp> 49951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef _GLIBCXX_DEBUG 50951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/debug_map_base.hpp> 51951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 52951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef PB_DS_HT_MAP_TRACE_ 53951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <iostream> 54951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 55951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <debug/debug.h> 56951a39d68df598db08dfced8b4707755864a0492Ying Wang 57951a39d68df598db08dfced8b4707755864a0492Ying Wangnamespace __gnu_pbds 58951a39d68df598db08dfced8b4707755864a0492Ying Wang{ 59951a39d68df598db08dfced8b4707755864a0492Ying Wang namespace detail 60951a39d68df598db08dfced8b4707755864a0492Ying Wang { 61951a39d68df598db08dfced8b4707755864a0492Ying Wang 62951a39d68df598db08dfced8b4707755864a0492Ying Wang#define PB_DS_CLASS_T_DEC \ 63951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename Key, typename Mapped, typename Hash_Fn, \ 64951a39d68df598db08dfced8b4707755864a0492Ying Wang typename Eq_Fn, typename Allocator, bool Store_Hash, \ 65951a39d68df598db08dfced8b4707755864a0492Ying Wang typename Comb_Hash_Fn, typename Resize_Policy> 66951a39d68df598db08dfced8b4707755864a0492Ying Wang 67951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef PB_DS_DATA_TRUE_INDICATOR 68951a39d68df598db08dfced8b4707755864a0492Ying Wang#define PB_DS_CLASS_NAME cc_ht_map_data_ 69951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 70951a39d68df598db08dfced8b4707755864a0492Ying Wang 71951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef PB_DS_DATA_FALSE_INDICATOR 72951a39d68df598db08dfced8b4707755864a0492Ying Wang#define PB_DS_CLASS_NAME cc_ht_map_no_data_ 73951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 74951a39d68df598db08dfced8b4707755864a0492Ying Wang 75951a39d68df598db08dfced8b4707755864a0492Ying Wang#define PB_DS_CLASS_C_DEC \ 76951a39d68df598db08dfced8b4707755864a0492Ying Wang PB_DS_CLASS_NAME<Key, Mapped, Hash_Fn, Eq_Fn, Allocator, \ 77951a39d68df598db08dfced8b4707755864a0492Ying Wang Store_Hash, Comb_Hash_Fn, Resize_Policy> 78951a39d68df598db08dfced8b4707755864a0492Ying Wang 79951a39d68df598db08dfced8b4707755864a0492Ying Wang#define PB_DS_HASH_EQ_FN_C_DEC \ 80951a39d68df598db08dfced8b4707755864a0492Ying Wang hash_eq_fn<Key, Eq_Fn, Allocator, Store_Hash> 81951a39d68df598db08dfced8b4707755864a0492Ying Wang 82951a39d68df598db08dfced8b4707755864a0492Ying Wang#define PB_DS_RANGED_HASH_FN_C_DEC \ 83951a39d68df598db08dfced8b4707755864a0492Ying Wang ranged_hash_fn<Key, Hash_Fn, Allocator, Comb_Hash_Fn, Store_Hash> 84951a39d68df598db08dfced8b4707755864a0492Ying Wang 85951a39d68df598db08dfced8b4707755864a0492Ying Wang#define PB_DS_TYPES_TRAITS_C_DEC \ 86951a39d68df598db08dfced8b4707755864a0492Ying Wang types_traits<Key, Mapped, Allocator, Store_Hash> 87951a39d68df598db08dfced8b4707755864a0492Ying Wang 88951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef _GLIBCXX_DEBUG 89951a39d68df598db08dfced8b4707755864a0492Ying Wang#define PB_DS_DEBUG_MAP_BASE_C_DEC \ 90951a39d68df598db08dfced8b4707755864a0492Ying Wang debug_map_base<Key, Eq_Fn, typename Allocator::template rebind<Key>::other::const_reference> 91951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 92951a39d68df598db08dfced8b4707755864a0492Ying Wang 93951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef PB_DS_DATA_TRUE_INDICATOR 94951a39d68df598db08dfced8b4707755864a0492Ying Wang#define PB_DS_V2F(X) (X).first 95951a39d68df598db08dfced8b4707755864a0492Ying Wang#define PB_DS_V2S(X) (X).second 96951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 97951a39d68df598db08dfced8b4707755864a0492Ying Wang 98951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef PB_DS_DATA_FALSE_INDICATOR 99951a39d68df598db08dfced8b4707755864a0492Ying Wang#define PB_DS_V2F(X) (X) 100951a39d68df598db08dfced8b4707755864a0492Ying Wang#define PB_DS_V2S(X) Mapped_Data() 101951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 102951a39d68df598db08dfced8b4707755864a0492Ying Wang 103951a39d68df598db08dfced8b4707755864a0492Ying Wang // <011i$i0|\|-<|-|4i|\|i|\|g |-|4$|-| 74813. 104951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename Key, 105951a39d68df598db08dfced8b4707755864a0492Ying Wang typename Mapped, 106951a39d68df598db08dfced8b4707755864a0492Ying Wang typename Hash_Fn, 107951a39d68df598db08dfced8b4707755864a0492Ying Wang typename Eq_Fn, 108951a39d68df598db08dfced8b4707755864a0492Ying Wang typename Allocator, 109951a39d68df598db08dfced8b4707755864a0492Ying Wang bool Store_Hash, 110951a39d68df598db08dfced8b4707755864a0492Ying Wang typename Comb_Hash_Fn, 111951a39d68df598db08dfced8b4707755864a0492Ying Wang typename Resize_Policy > 112951a39d68df598db08dfced8b4707755864a0492Ying Wang class PB_DS_CLASS_NAME: 113951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef _GLIBCXX_DEBUG 114951a39d68df598db08dfced8b4707755864a0492Ying Wang protected PB_DS_DEBUG_MAP_BASE_C_DEC, 115951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 116951a39d68df598db08dfced8b4707755864a0492Ying Wang public PB_DS_HASH_EQ_FN_C_DEC, 117951a39d68df598db08dfced8b4707755864a0492Ying Wang public Resize_Policy, 118951a39d68df598db08dfced8b4707755864a0492Ying Wang public PB_DS_RANGED_HASH_FN_C_DEC, 119951a39d68df598db08dfced8b4707755864a0492Ying Wang public PB_DS_TYPES_TRAITS_C_DEC 120951a39d68df598db08dfced8b4707755864a0492Ying Wang { 121951a39d68df598db08dfced8b4707755864a0492Ying Wang private: 122951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; 123951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::comp_hash comp_hash; 124951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::value_type value_type_; 125951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::pointer pointer_; 126951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::const_pointer const_pointer_; 127951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::reference reference_; 128951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::const_reference const_reference_; 129951a39d68df598db08dfced8b4707755864a0492Ying Wang 130951a39d68df598db08dfced8b4707755864a0492Ying Wang struct entry : public traits_base::stored_value_type 131951a39d68df598db08dfced8b4707755864a0492Ying Wang { 132951a39d68df598db08dfced8b4707755864a0492Ying Wang typename Allocator::template rebind<entry>::other::pointer m_p_next; 133951a39d68df598db08dfced8b4707755864a0492Ying Wang }; 134951a39d68df598db08dfced8b4707755864a0492Ying Wang 135951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef cond_dealtor<entry, Allocator> cond_dealtor_t; 136951a39d68df598db08dfced8b4707755864a0492Ying Wang 137951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename Allocator::template rebind<entry>::other entry_allocator; 138951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename entry_allocator::pointer entry_pointer; 139951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename entry_allocator::const_pointer const_entry_pointer; 140951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename entry_allocator::reference entry_reference; 141951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename entry_allocator::const_reference const_entry_reference; 142951a39d68df598db08dfced8b4707755864a0492Ying Wang 143951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename Allocator::template rebind<entry_pointer>::other entry_pointer_allocator; 144951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename entry_pointer_allocator::pointer entry_pointer_array; 145951a39d68df598db08dfced8b4707755864a0492Ying Wang 146951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef PB_DS_RANGED_HASH_FN_C_DEC ranged_hash_fn_base; 147951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base; 148951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef Resize_Policy resize_base; 149951a39d68df598db08dfced8b4707755864a0492Ying Wang 150951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef _GLIBCXX_DEBUG 151951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 152951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 153951a39d68df598db08dfced8b4707755864a0492Ying Wang 154951a39d68df598db08dfced8b4707755864a0492Ying Wang#define PB_DS_GEN_POS std::pair<entry_pointer, typename Allocator::size_type> 155951a39d68df598db08dfced8b4707755864a0492Ying Wang 156951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp> 157951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp> 158951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp> 159951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/unordered_iterator/iterator.hpp> 160951a39d68df598db08dfced8b4707755864a0492Ying Wang 161951a39d68df598db08dfced8b4707755864a0492Ying Wang#undef PB_DS_GEN_POS 162951a39d68df598db08dfced8b4707755864a0492Ying Wang 163951a39d68df598db08dfced8b4707755864a0492Ying Wang public: 164951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef Allocator allocator_type; 165951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename Allocator::size_type size_type; 166951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename Allocator::difference_type difference_type; 167951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef Hash_Fn hash_fn; 168951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef Eq_Fn eq_fn; 169951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef Comb_Hash_Fn comb_hash_fn; 170951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef Resize_Policy resize_policy; 171951a39d68df598db08dfced8b4707755864a0492Ying Wang 172951a39d68df598db08dfced8b4707755864a0492Ying Wang enum 173951a39d68df598db08dfced8b4707755864a0492Ying Wang { 174951a39d68df598db08dfced8b4707755864a0492Ying Wang store_hash = Store_Hash 175951a39d68df598db08dfced8b4707755864a0492Ying Wang }; 176951a39d68df598db08dfced8b4707755864a0492Ying Wang 177951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::key_type key_type; 178951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::key_pointer key_pointer; 179951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::const_key_pointer const_key_pointer; 180951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::key_reference key_reference; 181951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::const_key_reference const_key_reference; 182951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::mapped_type mapped_type; 183951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::mapped_pointer mapped_pointer; 184951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::const_mapped_pointer const_mapped_pointer; 185951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::mapped_reference mapped_reference; 186951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::const_mapped_reference const_mapped_reference; 187951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::value_type value_type; 188951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::pointer pointer; 189951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::const_pointer const_pointer; 190951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::reference reference; 191951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef typename traits_base::const_reference const_reference; 192951a39d68df598db08dfced8b4707755864a0492Ying Wang 193951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef PB_DS_DATA_TRUE_INDICATOR 194951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef point_iterator_ point_iterator; 195951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 196951a39d68df598db08dfced8b4707755864a0492Ying Wang 197951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef PB_DS_DATA_FALSE_INDICATOR 198951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef const_point_iterator_ point_iterator; 199951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 200951a39d68df598db08dfced8b4707755864a0492Ying Wang 201951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef const_point_iterator_ const_point_iterator; 202951a39d68df598db08dfced8b4707755864a0492Ying Wang 203951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef PB_DS_DATA_TRUE_INDICATOR 204951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef iterator_ iterator; 205951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 206951a39d68df598db08dfced8b4707755864a0492Ying Wang 207951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef PB_DS_DATA_FALSE_INDICATOR 208951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef const_iterator_ iterator; 209951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 210951a39d68df598db08dfced8b4707755864a0492Ying Wang 211951a39d68df598db08dfced8b4707755864a0492Ying Wang typedef const_iterator_ const_iterator; 212951a39d68df598db08dfced8b4707755864a0492Ying Wang 213951a39d68df598db08dfced8b4707755864a0492Ying Wang PB_DS_CLASS_NAME(); 214951a39d68df598db08dfced8b4707755864a0492Ying Wang 215951a39d68df598db08dfced8b4707755864a0492Ying Wang PB_DS_CLASS_NAME(const Hash_Fn&); 216951a39d68df598db08dfced8b4707755864a0492Ying Wang 217951a39d68df598db08dfced8b4707755864a0492Ying Wang PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&); 218951a39d68df598db08dfced8b4707755864a0492Ying Wang 219951a39d68df598db08dfced8b4707755864a0492Ying Wang PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&); 220951a39d68df598db08dfced8b4707755864a0492Ying Wang 221951a39d68df598db08dfced8b4707755864a0492Ying Wang PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&, 222951a39d68df598db08dfced8b4707755864a0492Ying Wang const Resize_Policy&); 223951a39d68df598db08dfced8b4707755864a0492Ying Wang 224951a39d68df598db08dfced8b4707755864a0492Ying Wang PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); 225951a39d68df598db08dfced8b4707755864a0492Ying Wang 226951a39d68df598db08dfced8b4707755864a0492Ying Wang virtual 227951a39d68df598db08dfced8b4707755864a0492Ying Wang ~PB_DS_CLASS_NAME(); 228951a39d68df598db08dfced8b4707755864a0492Ying Wang 229951a39d68df598db08dfced8b4707755864a0492Ying Wang void 230951a39d68df598db08dfced8b4707755864a0492Ying Wang swap(PB_DS_CLASS_C_DEC&); 231951a39d68df598db08dfced8b4707755864a0492Ying Wang 232951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename It> 233951a39d68df598db08dfced8b4707755864a0492Ying Wang void 234951a39d68df598db08dfced8b4707755864a0492Ying Wang copy_from_range(It, It); 235951a39d68df598db08dfced8b4707755864a0492Ying Wang 236951a39d68df598db08dfced8b4707755864a0492Ying Wang void 237951a39d68df598db08dfced8b4707755864a0492Ying Wang initialize(); 238951a39d68df598db08dfced8b4707755864a0492Ying Wang 239951a39d68df598db08dfced8b4707755864a0492Ying Wang inline size_type 240951a39d68df598db08dfced8b4707755864a0492Ying Wang size() const; 241951a39d68df598db08dfced8b4707755864a0492Ying Wang 242951a39d68df598db08dfced8b4707755864a0492Ying Wang inline size_type 243951a39d68df598db08dfced8b4707755864a0492Ying Wang max_size() const; 244951a39d68df598db08dfced8b4707755864a0492Ying Wang 245951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 246951a39d68df598db08dfced8b4707755864a0492Ying Wang empty() const; 247951a39d68df598db08dfced8b4707755864a0492Ying Wang 248951a39d68df598db08dfced8b4707755864a0492Ying Wang Hash_Fn& 249951a39d68df598db08dfced8b4707755864a0492Ying Wang get_hash_fn(); 250951a39d68df598db08dfced8b4707755864a0492Ying Wang 251951a39d68df598db08dfced8b4707755864a0492Ying Wang const Hash_Fn& 252951a39d68df598db08dfced8b4707755864a0492Ying Wang get_hash_fn() const; 253951a39d68df598db08dfced8b4707755864a0492Ying Wang 254951a39d68df598db08dfced8b4707755864a0492Ying Wang Eq_Fn& 255951a39d68df598db08dfced8b4707755864a0492Ying Wang get_eq_fn(); 256951a39d68df598db08dfced8b4707755864a0492Ying Wang 257951a39d68df598db08dfced8b4707755864a0492Ying Wang const Eq_Fn& 258951a39d68df598db08dfced8b4707755864a0492Ying Wang get_eq_fn() const; 259951a39d68df598db08dfced8b4707755864a0492Ying Wang 260951a39d68df598db08dfced8b4707755864a0492Ying Wang Comb_Hash_Fn& 261951a39d68df598db08dfced8b4707755864a0492Ying Wang get_comb_hash_fn(); 262951a39d68df598db08dfced8b4707755864a0492Ying Wang 263951a39d68df598db08dfced8b4707755864a0492Ying Wang const Comb_Hash_Fn& 264951a39d68df598db08dfced8b4707755864a0492Ying Wang get_comb_hash_fn() const; 265951a39d68df598db08dfced8b4707755864a0492Ying Wang 266951a39d68df598db08dfced8b4707755864a0492Ying Wang Resize_Policy& 267951a39d68df598db08dfced8b4707755864a0492Ying Wang get_resize_policy(); 268951a39d68df598db08dfced8b4707755864a0492Ying Wang 269951a39d68df598db08dfced8b4707755864a0492Ying Wang const Resize_Policy& 270951a39d68df598db08dfced8b4707755864a0492Ying Wang get_resize_policy() const; 271951a39d68df598db08dfced8b4707755864a0492Ying Wang 272951a39d68df598db08dfced8b4707755864a0492Ying Wang inline std::pair<point_iterator, bool> 273951a39d68df598db08dfced8b4707755864a0492Ying Wang insert(const_reference r_val) 274951a39d68df598db08dfced8b4707755864a0492Ying Wang { return insert_imp(r_val, traits_base::m_store_extra_indicator); } 275951a39d68df598db08dfced8b4707755864a0492Ying Wang 276951a39d68df598db08dfced8b4707755864a0492Ying Wang inline mapped_reference 277951a39d68df598db08dfced8b4707755864a0492Ying Wang operator[](const_key_reference r_key) 278951a39d68df598db08dfced8b4707755864a0492Ying Wang { 279951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef PB_DS_DATA_TRUE_INDICATOR 280951a39d68df598db08dfced8b4707755864a0492Ying Wang return (subscript_imp(r_key, traits_base::m_store_extra_indicator)); 281951a39d68df598db08dfced8b4707755864a0492Ying Wang#else 282951a39d68df598db08dfced8b4707755864a0492Ying Wang insert(r_key); 283951a39d68df598db08dfced8b4707755864a0492Ying Wang return traits_base::s_null_mapped; 284951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 285951a39d68df598db08dfced8b4707755864a0492Ying Wang } 286951a39d68df598db08dfced8b4707755864a0492Ying Wang 287951a39d68df598db08dfced8b4707755864a0492Ying Wang inline point_iterator 288951a39d68df598db08dfced8b4707755864a0492Ying Wang find(const_key_reference); 289951a39d68df598db08dfced8b4707755864a0492Ying Wang 290951a39d68df598db08dfced8b4707755864a0492Ying Wang inline const_point_iterator 291951a39d68df598db08dfced8b4707755864a0492Ying Wang find(const_key_reference) const; 292951a39d68df598db08dfced8b4707755864a0492Ying Wang 293951a39d68df598db08dfced8b4707755864a0492Ying Wang inline point_iterator 294951a39d68df598db08dfced8b4707755864a0492Ying Wang find_end(); 295951a39d68df598db08dfced8b4707755864a0492Ying Wang 296951a39d68df598db08dfced8b4707755864a0492Ying Wang inline const_point_iterator 297951a39d68df598db08dfced8b4707755864a0492Ying Wang find_end() const; 298951a39d68df598db08dfced8b4707755864a0492Ying Wang 299951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 300951a39d68df598db08dfced8b4707755864a0492Ying Wang erase(const_key_reference); 301951a39d68df598db08dfced8b4707755864a0492Ying Wang 302951a39d68df598db08dfced8b4707755864a0492Ying Wang template<typename Pred> 303951a39d68df598db08dfced8b4707755864a0492Ying Wang inline size_type 304951a39d68df598db08dfced8b4707755864a0492Ying Wang erase_if(Pred); 305951a39d68df598db08dfced8b4707755864a0492Ying Wang 306951a39d68df598db08dfced8b4707755864a0492Ying Wang void 307951a39d68df598db08dfced8b4707755864a0492Ying Wang clear(); 308951a39d68df598db08dfced8b4707755864a0492Ying Wang 309951a39d68df598db08dfced8b4707755864a0492Ying Wang inline iterator 310951a39d68df598db08dfced8b4707755864a0492Ying Wang begin(); 311951a39d68df598db08dfced8b4707755864a0492Ying Wang 312951a39d68df598db08dfced8b4707755864a0492Ying Wang inline const_iterator 313951a39d68df598db08dfced8b4707755864a0492Ying Wang begin() const; 314951a39d68df598db08dfced8b4707755864a0492Ying Wang 315951a39d68df598db08dfced8b4707755864a0492Ying Wang inline iterator 316951a39d68df598db08dfced8b4707755864a0492Ying Wang end(); 317951a39d68df598db08dfced8b4707755864a0492Ying Wang 318951a39d68df598db08dfced8b4707755864a0492Ying Wang inline const_iterator 319951a39d68df598db08dfced8b4707755864a0492Ying Wang end() const; 320951a39d68df598db08dfced8b4707755864a0492Ying Wang 321951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef _GLIBCXX_DEBUG 322951a39d68df598db08dfced8b4707755864a0492Ying Wang void 323951a39d68df598db08dfced8b4707755864a0492Ying Wang assert_valid() const; 324951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 325951a39d68df598db08dfced8b4707755864a0492Ying Wang 326951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef PB_DS_HT_MAP_TRACE_ 327951a39d68df598db08dfced8b4707755864a0492Ying Wang void 328951a39d68df598db08dfced8b4707755864a0492Ying Wang trace() const; 329951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 330951a39d68df598db08dfced8b4707755864a0492Ying Wang 331951a39d68df598db08dfced8b4707755864a0492Ying Wang private: 332951a39d68df598db08dfced8b4707755864a0492Ying Wang void 333951a39d68df598db08dfced8b4707755864a0492Ying Wang deallocate_all(); 334951a39d68df598db08dfced8b4707755864a0492Ying Wang 335951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 336951a39d68df598db08dfced8b4707755864a0492Ying Wang do_resize_if_needed(); 337951a39d68df598db08dfced8b4707755864a0492Ying Wang 338951a39d68df598db08dfced8b4707755864a0492Ying Wang inline void 339951a39d68df598db08dfced8b4707755864a0492Ying Wang do_resize_if_needed_no_throw(); 340951a39d68df598db08dfced8b4707755864a0492Ying Wang 341951a39d68df598db08dfced8b4707755864a0492Ying Wang void 342951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_imp(size_type new_size); 343951a39d68df598db08dfced8b4707755864a0492Ying Wang 344951a39d68df598db08dfced8b4707755864a0492Ying Wang void 345951a39d68df598db08dfced8b4707755864a0492Ying Wang do_resize(size_type new_size); 346951a39d68df598db08dfced8b4707755864a0492Ying Wang 347951a39d68df598db08dfced8b4707755864a0492Ying Wang void 348951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_imp_no_exceptions(size_type, entry_pointer_array, size_type); 349951a39d68df598db08dfced8b4707755864a0492Ying Wang 350951a39d68df598db08dfced8b4707755864a0492Ying Wang inline entry_pointer 351951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_imp_no_exceptions_reassign_pointer(entry_pointer, entry_pointer_array, false_type); 352951a39d68df598db08dfced8b4707755864a0492Ying Wang 353951a39d68df598db08dfced8b4707755864a0492Ying Wang inline entry_pointer 354951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_imp_no_exceptions_reassign_pointer(entry_pointer, entry_pointer_array, true_type); 355951a39d68df598db08dfced8b4707755864a0492Ying Wang 356951a39d68df598db08dfced8b4707755864a0492Ying Wang void 357951a39d68df598db08dfced8b4707755864a0492Ying Wang deallocate_links_in_list(entry_pointer); 358951a39d68df598db08dfced8b4707755864a0492Ying Wang 359951a39d68df598db08dfced8b4707755864a0492Ying Wang inline entry_pointer 360951a39d68df598db08dfced8b4707755864a0492Ying Wang get_entry(const_reference, false_type); 361951a39d68df598db08dfced8b4707755864a0492Ying Wang 362951a39d68df598db08dfced8b4707755864a0492Ying Wang inline entry_pointer 363951a39d68df598db08dfced8b4707755864a0492Ying Wang get_entry(const_reference, true_type); 364951a39d68df598db08dfced8b4707755864a0492Ying Wang 365951a39d68df598db08dfced8b4707755864a0492Ying Wang inline void 366951a39d68df598db08dfced8b4707755864a0492Ying Wang rels_entry(entry_pointer); 367951a39d68df598db08dfced8b4707755864a0492Ying Wang 368951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef PB_DS_DATA_TRUE_INDICATOR 369951a39d68df598db08dfced8b4707755864a0492Ying Wang inline mapped_reference 370951a39d68df598db08dfced8b4707755864a0492Ying Wang subscript_imp(const_key_reference r_key, false_type) 371951a39d68df598db08dfced8b4707755864a0492Ying Wang { 372951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_DEBUG_ONLY(assert_valid();) 373951a39d68df598db08dfced8b4707755864a0492Ying Wang const size_type pos = ranged_hash_fn_base::operator()(r_key); 374951a39d68df598db08dfced8b4707755864a0492Ying Wang entry_pointer p_e = m_entries[pos]; 375951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_base::notify_insert_search_start(); 376951a39d68df598db08dfced8b4707755864a0492Ying Wang 37743f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh while (p_e != 0 378951a39d68df598db08dfced8b4707755864a0492Ying Wang && !hash_eq_fn_base::operator()(p_e->m_value.first, r_key)) 379951a39d68df598db08dfced8b4707755864a0492Ying Wang { 380951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_base::notify_insert_search_collision(); 381951a39d68df598db08dfced8b4707755864a0492Ying Wang p_e = p_e->m_p_next; 382951a39d68df598db08dfced8b4707755864a0492Ying Wang } 383951a39d68df598db08dfced8b4707755864a0492Ying Wang 384951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_base::notify_insert_search_end(); 38543f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh if (p_e != 0) 386951a39d68df598db08dfced8b4707755864a0492Ying Wang { 387951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);) 388951a39d68df598db08dfced8b4707755864a0492Ying Wang return (p_e->m_value.second); 389951a39d68df598db08dfced8b4707755864a0492Ying Wang } 390951a39d68df598db08dfced8b4707755864a0492Ying Wang 391951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) 392951a39d68df598db08dfced8b4707755864a0492Ying Wang return insert_new_imp(value_type(r_key, mapped_type()), pos)->second; 393951a39d68df598db08dfced8b4707755864a0492Ying Wang } 394951a39d68df598db08dfced8b4707755864a0492Ying Wang 395951a39d68df598db08dfced8b4707755864a0492Ying Wang inline mapped_reference 396951a39d68df598db08dfced8b4707755864a0492Ying Wang subscript_imp(const_key_reference r_key, true_type) 397951a39d68df598db08dfced8b4707755864a0492Ying Wang { 398951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_DEBUG_ONLY(assert_valid();) 399951a39d68df598db08dfced8b4707755864a0492Ying Wang comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key); 400951a39d68df598db08dfced8b4707755864a0492Ying Wang entry_pointer p_e = m_entries[pos_hash_pair.first]; 401951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_base::notify_insert_search_start(); 40243f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh while (p_e != 0 && 403951a39d68df598db08dfced8b4707755864a0492Ying Wang !hash_eq_fn_base::operator()(p_e->m_value.first, p_e->m_hash, r_key, pos_hash_pair.second)) 404951a39d68df598db08dfced8b4707755864a0492Ying Wang { 405951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_base::notify_insert_search_collision(); 406951a39d68df598db08dfced8b4707755864a0492Ying Wang p_e = p_e->m_p_next; 407951a39d68df598db08dfced8b4707755864a0492Ying Wang } 408951a39d68df598db08dfced8b4707755864a0492Ying Wang 409951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_base::notify_insert_search_end(); 41043f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh if (p_e != 0) 411951a39d68df598db08dfced8b4707755864a0492Ying Wang { 412951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);) 413951a39d68df598db08dfced8b4707755864a0492Ying Wang return p_e->m_value.second; 414951a39d68df598db08dfced8b4707755864a0492Ying Wang } 415951a39d68df598db08dfced8b4707755864a0492Ying Wang 416951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) 417951a39d68df598db08dfced8b4707755864a0492Ying Wang return insert_new_imp(value_type(r_key, mapped_type()), 418951a39d68df598db08dfced8b4707755864a0492Ying Wang pos_hash_pair)->second; 419951a39d68df598db08dfced8b4707755864a0492Ying Wang } 420951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 421951a39d68df598db08dfced8b4707755864a0492Ying Wang 422951a39d68df598db08dfced8b4707755864a0492Ying Wang inline std::pair<point_iterator, bool> 423951a39d68df598db08dfced8b4707755864a0492Ying Wang insert_imp(const_reference, false_type); 424951a39d68df598db08dfced8b4707755864a0492Ying Wang 425951a39d68df598db08dfced8b4707755864a0492Ying Wang inline std::pair<point_iterator, bool> 426951a39d68df598db08dfced8b4707755864a0492Ying Wang insert_imp(const_reference, true_type); 427951a39d68df598db08dfced8b4707755864a0492Ying Wang 428951a39d68df598db08dfced8b4707755864a0492Ying Wang inline pointer 429951a39d68df598db08dfced8b4707755864a0492Ying Wang insert_new_imp(const_reference r_val, size_type pos) 430951a39d68df598db08dfced8b4707755864a0492Ying Wang { 431951a39d68df598db08dfced8b4707755864a0492Ying Wang if (do_resize_if_needed()) 432951a39d68df598db08dfced8b4707755864a0492Ying Wang pos = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val)); 433951a39d68df598db08dfced8b4707755864a0492Ying Wang 434951a39d68df598db08dfced8b4707755864a0492Ying Wang // Following lines might throw an exception. 435951a39d68df598db08dfced8b4707755864a0492Ying Wang entry_pointer p_e = get_entry(r_val, traits_base::m_no_throw_copies_indicator); 436951a39d68df598db08dfced8b4707755864a0492Ying Wang 437951a39d68df598db08dfced8b4707755864a0492Ying Wang // At this point no exceptions can be thrown. 438951a39d68df598db08dfced8b4707755864a0492Ying Wang p_e->m_p_next = m_entries[pos]; 439951a39d68df598db08dfced8b4707755864a0492Ying Wang m_entries[pos] = p_e; 440951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_base::notify_inserted(++m_num_used_e); 441951a39d68df598db08dfced8b4707755864a0492Ying Wang 442951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) 443951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_DEBUG_ONLY(assert_valid();) 444951a39d68df598db08dfced8b4707755864a0492Ying Wang return &p_e->m_value; 445951a39d68df598db08dfced8b4707755864a0492Ying Wang } 446951a39d68df598db08dfced8b4707755864a0492Ying Wang 447951a39d68df598db08dfced8b4707755864a0492Ying Wang inline pointer 448951a39d68df598db08dfced8b4707755864a0492Ying Wang insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair) 449951a39d68df598db08dfced8b4707755864a0492Ying Wang { 450951a39d68df598db08dfced8b4707755864a0492Ying Wang // Following lines might throw an exception. 451951a39d68df598db08dfced8b4707755864a0492Ying Wang if (do_resize_if_needed()) 452951a39d68df598db08dfced8b4707755864a0492Ying Wang r_pos_hash_pair = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val)); 453951a39d68df598db08dfced8b4707755864a0492Ying Wang 454951a39d68df598db08dfced8b4707755864a0492Ying Wang entry_pointer p_e = get_entry(r_val, traits_base::m_no_throw_copies_indicator); 455951a39d68df598db08dfced8b4707755864a0492Ying Wang 456951a39d68df598db08dfced8b4707755864a0492Ying Wang // At this point no exceptions can be thrown. 457951a39d68df598db08dfced8b4707755864a0492Ying Wang p_e->m_hash = r_pos_hash_pair.second; 458951a39d68df598db08dfced8b4707755864a0492Ying Wang p_e->m_p_next = m_entries[r_pos_hash_pair.first]; 459951a39d68df598db08dfced8b4707755864a0492Ying Wang m_entries[r_pos_hash_pair.first] = p_e; 460951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_base::notify_inserted(++m_num_used_e); 461951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) 462951a39d68df598db08dfced8b4707755864a0492Ying Wang _GLIBCXX_DEBUG_ONLY(assert_valid();) 463951a39d68df598db08dfced8b4707755864a0492Ying Wang return &p_e->m_value; 464951a39d68df598db08dfced8b4707755864a0492Ying Wang } 465951a39d68df598db08dfced8b4707755864a0492Ying Wang 466951a39d68df598db08dfced8b4707755864a0492Ying Wang inline pointer 467951a39d68df598db08dfced8b4707755864a0492Ying Wang find_key_pointer(const_key_reference r_key, false_type) 468951a39d68df598db08dfced8b4707755864a0492Ying Wang { 469951a39d68df598db08dfced8b4707755864a0492Ying Wang entry_pointer p_e = m_entries[ranged_hash_fn_base::operator()(r_key)]; 470951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_base::notify_find_search_start(); 47143f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh while (p_e != 0 && 472951a39d68df598db08dfced8b4707755864a0492Ying Wang !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) 473951a39d68df598db08dfced8b4707755864a0492Ying Wang { 474951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_base::notify_find_search_collision(); 475951a39d68df598db08dfced8b4707755864a0492Ying Wang p_e = p_e->m_p_next; 476951a39d68df598db08dfced8b4707755864a0492Ying Wang } 477951a39d68df598db08dfced8b4707755864a0492Ying Wang 478951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_base::notify_find_search_end(); 479951a39d68df598db08dfced8b4707755864a0492Ying Wang 480951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef _GLIBCXX_DEBUG 48143f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh if (p_e == 0) 482951a39d68df598db08dfced8b4707755864a0492Ying Wang debug_base::check_key_does_not_exist(r_key); 483951a39d68df598db08dfced8b4707755864a0492Ying Wang else 484951a39d68df598db08dfced8b4707755864a0492Ying Wang debug_base::check_key_exists(r_key); 485951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 486951a39d68df598db08dfced8b4707755864a0492Ying Wang return &p_e->m_value; 487951a39d68df598db08dfced8b4707755864a0492Ying Wang } 488951a39d68df598db08dfced8b4707755864a0492Ying Wang 489951a39d68df598db08dfced8b4707755864a0492Ying Wang inline pointer 490951a39d68df598db08dfced8b4707755864a0492Ying Wang find_key_pointer(const_key_reference r_key, true_type) 491951a39d68df598db08dfced8b4707755864a0492Ying Wang { 492951a39d68df598db08dfced8b4707755864a0492Ying Wang comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key); 493951a39d68df598db08dfced8b4707755864a0492Ying Wang entry_pointer p_e = m_entries[pos_hash_pair.first]; 494951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_base::notify_find_search_start(); 49543f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh while (p_e != 0 && 496951a39d68df598db08dfced8b4707755864a0492Ying Wang !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), 497951a39d68df598db08dfced8b4707755864a0492Ying Wang p_e->m_hash, 498951a39d68df598db08dfced8b4707755864a0492Ying Wang r_key, pos_hash_pair.second)) 499951a39d68df598db08dfced8b4707755864a0492Ying Wang { 500951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_base::notify_find_search_collision(); 501951a39d68df598db08dfced8b4707755864a0492Ying Wang p_e = p_e->m_p_next; 502951a39d68df598db08dfced8b4707755864a0492Ying Wang } 503951a39d68df598db08dfced8b4707755864a0492Ying Wang 504951a39d68df598db08dfced8b4707755864a0492Ying Wang resize_base::notify_find_search_end(); 505951a39d68df598db08dfced8b4707755864a0492Ying Wang 506951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef _GLIBCXX_DEBUG 50743f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh if (p_e == 0) 508951a39d68df598db08dfced8b4707755864a0492Ying Wang debug_base::check_key_does_not_exist(r_key); 509951a39d68df598db08dfced8b4707755864a0492Ying Wang else 510951a39d68df598db08dfced8b4707755864a0492Ying Wang debug_base::check_key_exists(r_key); 511951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 512951a39d68df598db08dfced8b4707755864a0492Ying Wang return &p_e->m_value; 513951a39d68df598db08dfced8b4707755864a0492Ying Wang } 514951a39d68df598db08dfced8b4707755864a0492Ying Wang 515951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 516951a39d68df598db08dfced8b4707755864a0492Ying Wang erase_in_pos_imp(const_key_reference, size_type); 517951a39d68df598db08dfced8b4707755864a0492Ying Wang 518951a39d68df598db08dfced8b4707755864a0492Ying Wang inline bool 519951a39d68df598db08dfced8b4707755864a0492Ying Wang erase_in_pos_imp(const_key_reference, const comp_hash&); 520951a39d68df598db08dfced8b4707755864a0492Ying Wang 521951a39d68df598db08dfced8b4707755864a0492Ying Wang inline void 522951a39d68df598db08dfced8b4707755864a0492Ying Wang erase_entry_pointer(entry_pointer&); 523951a39d68df598db08dfced8b4707755864a0492Ying Wang 524951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef PB_DS_DATA_TRUE_INDICATOR 525951a39d68df598db08dfced8b4707755864a0492Ying Wang void 526951a39d68df598db08dfced8b4707755864a0492Ying Wang inc_it_state(pointer& r_p_value, 527951a39d68df598db08dfced8b4707755864a0492Ying Wang std::pair<entry_pointer, size_type>& r_pos) const 528951a39d68df598db08dfced8b4707755864a0492Ying Wang { 529951a39d68df598db08dfced8b4707755864a0492Ying Wang inc_it_state((const_mapped_pointer& )r_p_value, r_pos); 530951a39d68df598db08dfced8b4707755864a0492Ying Wang } 531951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 532951a39d68df598db08dfced8b4707755864a0492Ying Wang 533951a39d68df598db08dfced8b4707755864a0492Ying Wang void 534951a39d68df598db08dfced8b4707755864a0492Ying Wang inc_it_state(const_pointer& r_p_value, 535951a39d68df598db08dfced8b4707755864a0492Ying Wang std::pair<entry_pointer, size_type>& r_pos) const 536951a39d68df598db08dfced8b4707755864a0492Ying Wang { 53743f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh _GLIBCXX_DEBUG_ASSERT(r_p_value != 0); 538951a39d68df598db08dfced8b4707755864a0492Ying Wang r_pos.first = r_pos.first->m_p_next; 53943f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh if (r_pos.first != 0) 540951a39d68df598db08dfced8b4707755864a0492Ying Wang { 541951a39d68df598db08dfced8b4707755864a0492Ying Wang r_p_value = &r_pos.first->m_value; 542951a39d68df598db08dfced8b4707755864a0492Ying Wang return; 543951a39d68df598db08dfced8b4707755864a0492Ying Wang } 544951a39d68df598db08dfced8b4707755864a0492Ying Wang 545951a39d68df598db08dfced8b4707755864a0492Ying Wang for (++r_pos.second; r_pos.second < m_num_e; ++r_pos.second) 54643f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh if (m_entries[r_pos.second] != 0) 547951a39d68df598db08dfced8b4707755864a0492Ying Wang { 548951a39d68df598db08dfced8b4707755864a0492Ying Wang r_pos.first = m_entries[r_pos.second]; 549951a39d68df598db08dfced8b4707755864a0492Ying Wang r_p_value = &r_pos.first->m_value; 550951a39d68df598db08dfced8b4707755864a0492Ying Wang return; 551951a39d68df598db08dfced8b4707755864a0492Ying Wang } 55243f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh r_p_value = 0; 553951a39d68df598db08dfced8b4707755864a0492Ying Wang } 554951a39d68df598db08dfced8b4707755864a0492Ying Wang 555951a39d68df598db08dfced8b4707755864a0492Ying Wang void 556951a39d68df598db08dfced8b4707755864a0492Ying Wang get_start_it_state(pointer& r_p_value, 557951a39d68df598db08dfced8b4707755864a0492Ying Wang std::pair<entry_pointer, size_type>& r_pos) const 558951a39d68df598db08dfced8b4707755864a0492Ying Wang { 559951a39d68df598db08dfced8b4707755864a0492Ying Wang for (r_pos.second = 0; r_pos.second < m_num_e; ++r_pos.second) 56043f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh if (m_entries[r_pos.second] != 0) 561951a39d68df598db08dfced8b4707755864a0492Ying Wang { 562951a39d68df598db08dfced8b4707755864a0492Ying Wang r_pos.first = m_entries[r_pos.second]; 563951a39d68df598db08dfced8b4707755864a0492Ying Wang r_p_value = &r_pos.first->m_value; 564951a39d68df598db08dfced8b4707755864a0492Ying Wang return; 565951a39d68df598db08dfced8b4707755864a0492Ying Wang } 56643f272afd56a57640c62c952f9266478bacf0244Andrew Hsieh r_p_value = 0; 567951a39d68df598db08dfced8b4707755864a0492Ying Wang } 568951a39d68df598db08dfced8b4707755864a0492Ying Wang 569951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef _GLIBCXX_DEBUG 570951a39d68df598db08dfced8b4707755864a0492Ying Wang void 571951a39d68df598db08dfced8b4707755864a0492Ying Wang assert_entry_pointer_array_valid(const entry_pointer_array) const; 572951a39d68df598db08dfced8b4707755864a0492Ying Wang 573951a39d68df598db08dfced8b4707755864a0492Ying Wang void 574951a39d68df598db08dfced8b4707755864a0492Ying Wang assert_entry_pointer_valid(const entry_pointer, true_type) const; 575951a39d68df598db08dfced8b4707755864a0492Ying Wang 576951a39d68df598db08dfced8b4707755864a0492Ying Wang void 577951a39d68df598db08dfced8b4707755864a0492Ying Wang assert_entry_pointer_valid(const entry_pointer, false_type) const; 578951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 579951a39d68df598db08dfced8b4707755864a0492Ying Wang 580951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef PB_DS_HT_MAP_TRACE_ 581951a39d68df598db08dfced8b4707755864a0492Ying Wang void 582951a39d68df598db08dfced8b4707755864a0492Ying Wang trace_list(const_entry_pointer) const; 583951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 584951a39d68df598db08dfced8b4707755864a0492Ying Wang 585951a39d68df598db08dfced8b4707755864a0492Ying Wang private: 586951a39d68df598db08dfced8b4707755864a0492Ying Wang#ifdef PB_DS_DATA_TRUE_INDICATOR 587951a39d68df598db08dfced8b4707755864a0492Ying Wang friend class iterator_; 588951a39d68df598db08dfced8b4707755864a0492Ying Wang#endif 589951a39d68df598db08dfced8b4707755864a0492Ying Wang 590951a39d68df598db08dfced8b4707755864a0492Ying Wang friend class const_iterator_; 591951a39d68df598db08dfced8b4707755864a0492Ying Wang 592951a39d68df598db08dfced8b4707755864a0492Ying Wang static entry_allocator s_entry_allocator; 593951a39d68df598db08dfced8b4707755864a0492Ying Wang static entry_pointer_allocator s_entry_pointer_allocator; 594951a39d68df598db08dfced8b4707755864a0492Ying Wang static iterator s_end_it; 595951a39d68df598db08dfced8b4707755864a0492Ying Wang static const_iterator s_const_end_it; 596951a39d68df598db08dfced8b4707755864a0492Ying Wang static point_iterator s_find_end_it; 597951a39d68df598db08dfced8b4707755864a0492Ying Wang static const_point_iterator s_const_find_end_it; 598951a39d68df598db08dfced8b4707755864a0492Ying Wang 599951a39d68df598db08dfced8b4707755864a0492Ying Wang size_type m_num_e; 600951a39d68df598db08dfced8b4707755864a0492Ying Wang size_type m_num_used_e; 601951a39d68df598db08dfced8b4707755864a0492Ying Wang entry_pointer_array m_entries; 602951a39d68df598db08dfced8b4707755864a0492Ying Wang 603951a39d68df598db08dfced8b4707755864a0492Ying Wang enum 604951a39d68df598db08dfced8b4707755864a0492Ying Wang { 605951a39d68df598db08dfced8b4707755864a0492Ying Wang store_hash_ok = !Store_Hash 606951a39d68df598db08dfced8b4707755864a0492Ying Wang || !is_same<Hash_Fn, __gnu_pbds::null_hash_fn>::value 607951a39d68df598db08dfced8b4707755864a0492Ying Wang }; 608951a39d68df598db08dfced8b4707755864a0492Ying Wang 609951a39d68df598db08dfced8b4707755864a0492Ying Wang PB_DS_STATIC_ASSERT(sth, store_hash_ok); 610951a39d68df598db08dfced8b4707755864a0492Ying Wang }; 611951a39d68df598db08dfced8b4707755864a0492Ying Wang 612951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp> 613951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp> 614951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp> 615951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp> 616951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp> 617951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp> 618951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp> 619951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp> 620951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp> 621951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/cc_hash_table_map_/insert_fn_imps.hpp> 622951a39d68df598db08dfced8b4707755864a0492Ying Wang#include <ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp> 623951a39d68df598db08dfced8b4707755864a0492Ying Wang 624951a39d68df598db08dfced8b4707755864a0492Ying Wang#undef PB_DS_CLASS_T_DEC 625951a39d68df598db08dfced8b4707755864a0492Ying Wang#undef PB_DS_CLASS_C_DEC 626951a39d68df598db08dfced8b4707755864a0492Ying Wang#undef PB_DS_HASH_EQ_FN_C_DEC 627951a39d68df598db08dfced8b4707755864a0492Ying Wang#undef PB_DS_RANGED_HASH_FN_C_DEC 628951a39d68df598db08dfced8b4707755864a0492Ying Wang#undef PB_DS_TYPES_TRAITS_C_DEC 629951a39d68df598db08dfced8b4707755864a0492Ying Wang#undef PB_DS_DEBUG_MAP_BASE_C_DEC 630951a39d68df598db08dfced8b4707755864a0492Ying Wang#undef PB_DS_CLASS_NAME 631951a39d68df598db08dfced8b4707755864a0492Ying Wang#undef PB_DS_V2F 632951a39d68df598db08dfced8b4707755864a0492Ying Wang#undef PB_DS_V2S 633951a39d68df598db08dfced8b4707755864a0492Ying Wang 634951a39d68df598db08dfced8b4707755864a0492Ying Wang } // namespace detail 635951a39d68df598db08dfced8b4707755864a0492Ying Wang} // namespace __gnu_pbds 636951a39d68df598db08dfced8b4707755864a0492Ying Wang 637