1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file cc_ht_map_.hpp 44169691Skan * Contains an implementation class for cc_ht_map_. 45169691Skan */ 46169691Skan 47169691Skan#include <utility> 48169691Skan#include <iterator> 49169691Skan#include <ext/pb_ds/detail/cond_dealtor.hpp> 50169691Skan#include <ext/pb_ds/tag_and_trait.hpp> 51169691Skan#include <ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp> 52169691Skan#include <ext/pb_ds/detail/types_traits.hpp> 53169691Skan#include <ext/pb_ds/exception.hpp> 54169691Skan#include <ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp> 55169691Skan#ifdef _GLIBCXX_DEBUG 56169691Skan#include <ext/pb_ds/detail/map_debug_base.hpp> 57169691Skan#endif 58169691Skan#ifdef PB_DS_HT_MAP_TRACE_ 59169691Skan#include <iostream> 60169691Skan#endif 61169691Skan#include <debug/debug.h> 62169691Skan 63169691Skannamespace pb_ds 64169691Skan{ 65169691Skan namespace detail 66169691Skan { 67169691Skan 68169691Skan#define PB_DS_CLASS_T_DEC \ 69169691Skan template<typename Key, typename Mapped, typename Hash_Fn, \ 70169691Skan typename Eq_Fn, typename Allocator, bool Store_Hash, \ 71169691Skan typename Comb_Hash_Fn, typename Resize_Policy> 72169691Skan 73169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 74169691Skan#define PB_DS_CLASS_NAME cc_ht_map_data_ 75169691Skan#endif 76169691Skan 77169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 78169691Skan#define PB_DS_CLASS_NAME cc_ht_map_no_data_ 79169691Skan#endif 80169691Skan 81169691Skan#define PB_DS_CLASS_C_DEC \ 82169691Skan PB_DS_CLASS_NAME<Key, Mapped, Hash_Fn, Eq_Fn, Allocator, \ 83169691Skan Store_Hash, Comb_Hash_Fn, Resize_Policy> 84169691Skan 85169691Skan#define PB_DS_HASH_EQ_FN_C_DEC \ 86169691Skan hash_eq_fn<Key, Eq_Fn, Allocator, Store_Hash> 87169691Skan 88169691Skan#define PB_DS_RANGED_HASH_FN_C_DEC \ 89169691Skan ranged_hash_fn<Key, Hash_Fn, Allocator, Comb_Hash_Fn, Store_Hash> 90169691Skan 91169691Skan#define PB_DS_TYPES_TRAITS_C_DEC \ 92169691Skan types_traits<Key, Mapped, Allocator, Store_Hash> 93169691Skan 94169691Skan#ifdef _GLIBCXX_DEBUG 95169691Skan#define PB_DS_MAP_DEBUG_BASE_C_DEC \ 96169691Skan map_debug_base<Key, Eq_Fn, typename Allocator::template rebind<Key>::other::const_reference> 97169691Skan#endif 98169691Skan 99169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 100169691Skan#define PB_DS_V2F(X) (X).first 101169691Skan#define PB_DS_V2S(X) (X).second 102169691Skan#endif 103169691Skan 104169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 105169691Skan#define PB_DS_V2F(X) (X) 106169691Skan#define PB_DS_V2S(X) Mapped_Data() 107169691Skan#endif 108169691Skan 109169691Skan#define PB_DS_STATIC_ASSERT(UNIQUE, E) \ 110169691Skan typedef static_assert_dumclass<sizeof(static_assert<(bool)(E)>)> \ 111169691Skan UNIQUE##static_assert_type 112169691Skan 113169691Skan // <011i$i0|\|-<|-|4i|\|i|\|g |-|4$|-| 74813. 114169691Skan template<typename Key, 115169691Skan typename Mapped, 116169691Skan typename Hash_Fn, 117169691Skan typename Eq_Fn, 118169691Skan typename Allocator, 119169691Skan bool Store_Hash, 120169691Skan typename Comb_Hash_Fn, 121169691Skan typename Resize_Policy > 122169691Skan class PB_DS_CLASS_NAME: 123169691Skan#ifdef _GLIBCXX_DEBUG 124169691Skan protected PB_DS_MAP_DEBUG_BASE_C_DEC, 125169691Skan#endif 126169691Skan public PB_DS_HASH_EQ_FN_C_DEC, 127169691Skan public Resize_Policy, 128169691Skan public PB_DS_RANGED_HASH_FN_C_DEC, 129169691Skan public PB_DS_TYPES_TRAITS_C_DEC 130169691Skan { 131169691Skan private: 132169691Skan typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; 133169691Skan typedef typename traits_base::comp_hash comp_hash; 134169691Skan typedef typename traits_base::value_type value_type_; 135169691Skan typedef typename traits_base::pointer pointer_; 136169691Skan typedef typename traits_base::const_pointer const_pointer_; 137169691Skan typedef typename traits_base::reference reference_; 138169691Skan typedef typename traits_base::const_reference const_reference_; 139169691Skan 140169691Skan struct entry : public traits_base::stored_value_type 141169691Skan { 142169691Skan typename Allocator::template rebind<entry>::other::pointer m_p_next; 143169691Skan }; 144169691Skan 145169691Skan typedef cond_dealtor<entry, Allocator> cond_dealtor_t; 146169691Skan 147169691Skan typedef typename Allocator::template rebind<entry>::other entry_allocator; 148169691Skan typedef typename entry_allocator::pointer entry_pointer; 149169691Skan typedef typename entry_allocator::const_pointer const_entry_pointer; 150169691Skan typedef typename entry_allocator::reference entry_reference; 151169691Skan typedef typename entry_allocator::const_reference const_entry_reference; 152169691Skan 153169691Skan typedef typename Allocator::template rebind<entry_pointer>::other entry_pointer_allocator; 154169691Skan typedef typename entry_pointer_allocator::pointer entry_pointer_array; 155169691Skan 156169691Skan typedef PB_DS_RANGED_HASH_FN_C_DEC ranged_hash_fn_base; 157169691Skan typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base; 158169691Skan typedef Resize_Policy resize_base; 159169691Skan 160169691Skan#ifdef _GLIBCXX_DEBUG 161169691Skan typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base; 162169691Skan#endif 163169691Skan 164169691Skan#define PB_DS_GEN_POS std::pair<entry_pointer, typename Allocator::size_type> 165169691Skan 166169691Skan#include <ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp> 167169691Skan#include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp> 168169691Skan#include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp> 169169691Skan#include <ext/pb_ds/detail/unordered_iterator/iterator.hpp> 170169691Skan 171169691Skan#undef PB_DS_GEN_POS 172169691Skan 173169691Skan public: 174169691Skan typedef Allocator allocator; 175169691Skan typedef typename Allocator::size_type size_type; 176169691Skan typedef typename Allocator::difference_type difference_type; 177169691Skan typedef Hash_Fn hash_fn; 178169691Skan typedef Eq_Fn eq_fn; 179169691Skan typedef Comb_Hash_Fn comb_hash_fn; 180169691Skan typedef Resize_Policy resize_policy; 181169691Skan 182169691Skan enum 183169691Skan { 184169691Skan store_hash = Store_Hash 185169691Skan }; 186169691Skan 187169691Skan typedef typename traits_base::key_type key_type; 188169691Skan typedef typename traits_base::key_pointer key_pointer; 189169691Skan typedef typename traits_base::const_key_pointer const_key_pointer; 190169691Skan typedef typename traits_base::key_reference key_reference; 191169691Skan typedef typename traits_base::const_key_reference const_key_reference; 192169691Skan typedef typename traits_base::mapped_type mapped_type; 193169691Skan typedef typename traits_base::mapped_pointer mapped_pointer; 194169691Skan typedef typename traits_base::const_mapped_pointer const_mapped_pointer; 195169691Skan typedef typename traits_base::mapped_reference mapped_reference; 196169691Skan typedef typename traits_base::const_mapped_reference const_mapped_reference; 197169691Skan typedef typename traits_base::value_type value_type; 198169691Skan typedef typename traits_base::pointer pointer; 199169691Skan typedef typename traits_base::const_pointer const_pointer; 200169691Skan typedef typename traits_base::reference reference; 201169691Skan typedef typename traits_base::const_reference const_reference; 202169691Skan 203169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 204169691Skan typedef point_iterator_ point_iterator; 205169691Skan#endif 206169691Skan 207169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 208169691Skan typedef const_point_iterator_ point_iterator; 209169691Skan#endif 210169691Skan 211169691Skan typedef const_point_iterator_ const_point_iterator; 212169691Skan 213169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 214169691Skan typedef iterator_ iterator; 215169691Skan#endif 216169691Skan 217169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 218169691Skan typedef const_iterator_ iterator; 219169691Skan#endif 220169691Skan 221169691Skan typedef const_iterator_ const_iterator; 222169691Skan 223169691Skan PB_DS_CLASS_NAME(); 224169691Skan 225169691Skan PB_DS_CLASS_NAME(const Hash_Fn&); 226169691Skan 227169691Skan PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&); 228169691Skan 229169691Skan PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&); 230169691Skan 231169691Skan PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&, 232169691Skan const Resize_Policy&); 233169691Skan 234169691Skan PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); 235169691Skan 236169691Skan virtual 237169691Skan ~PB_DS_CLASS_NAME(); 238169691Skan 239169691Skan void 240169691Skan swap(PB_DS_CLASS_C_DEC&); 241169691Skan 242169691Skan template<typename It> 243169691Skan void 244169691Skan copy_from_range(It, It); 245169691Skan 246169691Skan void 247169691Skan initialize(); 248169691Skan 249169691Skan inline size_type 250169691Skan size() const; 251169691Skan 252169691Skan inline size_type 253169691Skan max_size() const; 254169691Skan 255169691Skan inline bool 256169691Skan empty() const; 257169691Skan 258169691Skan Hash_Fn& 259169691Skan get_hash_fn(); 260169691Skan 261169691Skan const Hash_Fn& 262169691Skan get_hash_fn() const; 263169691Skan 264169691Skan Eq_Fn& 265169691Skan get_eq_fn(); 266169691Skan 267169691Skan const Eq_Fn& 268169691Skan get_eq_fn() const; 269169691Skan 270169691Skan Comb_Hash_Fn& 271169691Skan get_comb_hash_fn(); 272169691Skan 273169691Skan const Comb_Hash_Fn& 274169691Skan get_comb_hash_fn() const; 275169691Skan 276169691Skan Resize_Policy& 277169691Skan get_resize_policy(); 278169691Skan 279169691Skan const Resize_Policy& 280169691Skan get_resize_policy() const; 281169691Skan 282169691Skan inline std::pair<point_iterator, bool> 283169691Skan insert(const_reference r_val) 284169691Skan { return insert_imp(r_val, traits_base::m_store_extra_indicator); } 285169691Skan 286169691Skan inline mapped_reference 287169691Skan operator[](const_key_reference r_key) 288169691Skan { 289169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 290169691Skan return (subscript_imp(r_key, traits_base::m_store_extra_indicator)); 291169691Skan#else 292169691Skan insert(r_key); 293169691Skan return traits_base::s_null_mapped; 294169691Skan#endif 295169691Skan } 296169691Skan 297169691Skan inline point_iterator 298169691Skan find(const_key_reference); 299169691Skan 300169691Skan inline const_point_iterator 301169691Skan find(const_key_reference) const; 302169691Skan 303169691Skan inline point_iterator 304169691Skan find_end(); 305169691Skan 306169691Skan inline const_point_iterator 307169691Skan find_end() const; 308169691Skan 309169691Skan inline bool 310169691Skan erase(const_key_reference); 311169691Skan 312169691Skan template<typename Pred> 313169691Skan inline size_type 314169691Skan erase_if(Pred); 315169691Skan 316169691Skan void 317169691Skan clear(); 318169691Skan 319169691Skan inline iterator 320169691Skan begin(); 321169691Skan 322169691Skan inline const_iterator 323169691Skan begin() const; 324169691Skan 325169691Skan inline iterator 326169691Skan end(); 327169691Skan 328169691Skan inline const_iterator 329169691Skan end() const; 330169691Skan 331169691Skan#ifdef _GLIBCXX_DEBUG 332169691Skan void 333169691Skan assert_valid() const; 334169691Skan#endif 335169691Skan 336169691Skan#ifdef PB_DS_HT_MAP_TRACE_ 337169691Skan void 338169691Skan trace() const; 339169691Skan#endif 340169691Skan 341169691Skan private: 342169691Skan void 343169691Skan deallocate_all(); 344169691Skan 345169691Skan inline bool 346169691Skan do_resize_if_needed(); 347169691Skan 348169691Skan inline void 349169691Skan do_resize_if_needed_no_throw(); 350169691Skan 351169691Skan void 352169691Skan resize_imp(size_type new_size); 353169691Skan 354169691Skan void 355169691Skan do_resize(size_type new_size); 356169691Skan 357169691Skan void 358169691Skan resize_imp_no_exceptions(size_type, entry_pointer_array, size_type); 359169691Skan 360169691Skan inline entry_pointer 361169691Skan resize_imp_no_exceptions_reassign_pointer(entry_pointer, entry_pointer_array, false_type); 362169691Skan 363169691Skan inline entry_pointer 364169691Skan resize_imp_no_exceptions_reassign_pointer(entry_pointer, entry_pointer_array, true_type); 365169691Skan 366169691Skan void 367169691Skan deallocate_links_in_list(entry_pointer); 368169691Skan 369169691Skan inline entry_pointer 370169691Skan get_entry(const_reference, false_type); 371169691Skan 372169691Skan inline entry_pointer 373169691Skan get_entry(const_reference, true_type); 374169691Skan 375169691Skan inline void 376169691Skan rels_entry(entry_pointer); 377169691Skan 378169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 379169691Skan inline mapped_reference 380169691Skan subscript_imp(const_key_reference r_key, false_type) 381169691Skan { 382169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 383169691Skan const size_type pos = ranged_hash_fn_base::operator()(r_key); 384169691Skan entry_pointer p_e = m_entries[pos]; 385169691Skan resize_base::notify_insert_search_start(); 386169691Skan 387169691Skan while (p_e != NULL 388169691Skan && !hash_eq_fn_base::operator()(p_e->m_value.first, r_key)) 389169691Skan { 390169691Skan resize_base::notify_insert_search_collision(); 391169691Skan p_e = p_e->m_p_next; 392169691Skan } 393169691Skan 394169691Skan resize_base::notify_insert_search_end(); 395169691Skan if (p_e != NULL) 396169691Skan { 397169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);) 398169691Skan return (p_e->m_value.second); 399169691Skan } 400169691Skan 401169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 402169691Skan return insert_new_imp(value_type(r_key, mapped_type()), pos)->second; 403169691Skan } 404169691Skan 405169691Skan inline mapped_reference 406169691Skan subscript_imp(const_key_reference r_key, true_type) 407169691Skan { 408169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 409169691Skan comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key); 410169691Skan entry_pointer p_e = m_entries[pos_hash_pair.first]; 411169691Skan resize_base::notify_insert_search_start(); 412169691Skan while (p_e != NULL && 413169691Skan !hash_eq_fn_base::operator()(p_e->m_value.first, p_e->m_hash, r_key, pos_hash_pair.second)) 414169691Skan { 415169691Skan resize_base::notify_insert_search_collision(); 416169691Skan p_e = p_e->m_p_next; 417169691Skan } 418169691Skan 419169691Skan resize_base::notify_insert_search_end(); 420169691Skan if (p_e != NULL) 421169691Skan { 422169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);) 423169691Skan return p_e->m_value.second; 424169691Skan } 425169691Skan 426169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 427169691Skan return insert_new_imp(value_type(r_key, mapped_type()), 428169691Skan pos_hash_pair)->second; 429169691Skan } 430169691Skan#endif 431169691Skan 432169691Skan inline std::pair<point_iterator, bool> 433169691Skan insert_imp(const_reference, false_type); 434169691Skan 435169691Skan inline std::pair<point_iterator, bool> 436169691Skan insert_imp(const_reference, true_type); 437169691Skan 438169691Skan inline pointer 439169691Skan insert_new_imp(const_reference r_val, size_type pos) 440169691Skan { 441169691Skan if (do_resize_if_needed()) 442169691Skan pos = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val)); 443169691Skan 444169691Skan // Following lines might throw an exception. 445169691Skan entry_pointer p_e = get_entry(r_val, traits_base::m_no_throw_copies_indicator); 446169691Skan 447169691Skan // At this point no exceptions can be thrown. 448169691Skan p_e->m_p_next = m_entries[pos]; 449169691Skan m_entries[pos] = p_e; 450169691Skan resize_base::notify_inserted(++m_num_used_e); 451169691Skan 452169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(r_val));) 453169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 454169691Skan return &p_e->m_value; 455169691Skan } 456169691Skan 457169691Skan inline pointer 458169691Skan insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair) 459169691Skan { 460169691Skan // Following lines might throw an exception. 461169691Skan if (do_resize_if_needed()) 462169691Skan r_pos_hash_pair = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val)); 463169691Skan 464169691Skan entry_pointer p_e = get_entry(r_val, traits_base::m_no_throw_copies_indicator); 465169691Skan 466169691Skan // At this point no exceptions can be thrown. 467169691Skan p_e->m_hash = r_pos_hash_pair.second; 468169691Skan p_e->m_p_next = m_entries[r_pos_hash_pair.first]; 469169691Skan m_entries[r_pos_hash_pair.first] = p_e; 470169691Skan resize_base::notify_inserted(++m_num_used_e); 471169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(r_val));) 472169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 473169691Skan return &p_e->m_value; 474169691Skan } 475169691Skan 476169691Skan inline pointer 477169691Skan find_key_pointer(const_key_reference r_key, false_type) 478169691Skan { 479169691Skan entry_pointer p_e = m_entries[ranged_hash_fn_base::operator()(r_key)]; 480169691Skan resize_base::notify_find_search_start(); 481169691Skan while (p_e != NULL && 482169691Skan !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) 483169691Skan { 484169691Skan resize_base::notify_find_search_collision(); 485169691Skan p_e = p_e->m_p_next; 486169691Skan } 487169691Skan 488169691Skan resize_base::notify_find_search_end(); 489169691Skan 490169691Skan#ifdef _GLIBCXX_DEBUG 491169691Skan if (p_e == NULL) 492169691Skan map_debug_base::check_key_does_not_exist(r_key); 493169691Skan else 494169691Skan map_debug_base::check_key_exists(r_key); 495169691Skan#endif 496169691Skan return &p_e->m_value; 497169691Skan } 498169691Skan 499169691Skan inline pointer 500169691Skan find_key_pointer(const_key_reference r_key, true_type) 501169691Skan { 502169691Skan comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key); 503169691Skan entry_pointer p_e = m_entries[pos_hash_pair.first]; 504169691Skan resize_base::notify_find_search_start(); 505169691Skan while (p_e != NULL && 506169691Skan !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), 507169691Skan p_e->m_hash, 508169691Skan r_key, pos_hash_pair.second)) 509169691Skan { 510169691Skan resize_base::notify_find_search_collision(); 511169691Skan p_e = p_e->m_p_next; 512169691Skan } 513169691Skan 514169691Skan resize_base::notify_find_search_end(); 515169691Skan 516169691Skan#ifdef _GLIBCXX_DEBUG 517169691Skan if (p_e == NULL) 518169691Skan map_debug_base::check_key_does_not_exist(r_key); 519169691Skan else 520169691Skan map_debug_base::check_key_exists(r_key); 521169691Skan#endif 522169691Skan return &p_e->m_value; 523169691Skan } 524169691Skan 525169691Skan inline bool 526169691Skan erase_in_pos_imp(const_key_reference, size_type); 527169691Skan 528169691Skan inline bool 529169691Skan erase_in_pos_imp(const_key_reference, const comp_hash&); 530169691Skan 531169691Skan inline void 532169691Skan erase_entry_pointer(entry_pointer&); 533169691Skan 534169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 535169691Skan void 536169691Skan inc_it_state(pointer& r_p_value, 537169691Skan std::pair<entry_pointer, size_type>& r_pos) const 538169691Skan { 539169691Skan inc_it_state((const_mapped_pointer& )r_p_value, r_pos); 540169691Skan } 541169691Skan#endif 542169691Skan 543169691Skan void 544169691Skan inc_it_state(const_pointer& r_p_value, 545169691Skan std::pair<entry_pointer, size_type>& r_pos) const 546169691Skan { 547169691Skan _GLIBCXX_DEBUG_ASSERT(r_p_value != NULL); 548169691Skan r_pos.first = r_pos.first->m_p_next; 549169691Skan if (r_pos.first != NULL) 550169691Skan { 551169691Skan r_p_value = &r_pos.first->m_value; 552169691Skan return; 553169691Skan } 554169691Skan 555169691Skan for (++r_pos.second; r_pos.second < m_num_e; ++r_pos.second) 556169691Skan if (m_entries[r_pos.second] != NULL) 557169691Skan { 558169691Skan r_pos.first = m_entries[r_pos.second]; 559169691Skan r_p_value = &r_pos.first->m_value; 560169691Skan return; 561169691Skan } 562169691Skan r_p_value = NULL; 563169691Skan } 564169691Skan 565169691Skan void 566169691Skan get_start_it_state(pointer& r_p_value, 567169691Skan std::pair<entry_pointer, size_type>& r_pos) const 568169691Skan { 569169691Skan for (r_pos.second = 0; r_pos.second < m_num_e; ++r_pos.second) 570169691Skan if (m_entries[r_pos.second] != NULL) 571169691Skan { 572169691Skan r_pos.first = m_entries[r_pos.second]; 573169691Skan r_p_value = &r_pos.first->m_value; 574169691Skan return; 575169691Skan } 576169691Skan r_p_value = NULL; 577169691Skan } 578169691Skan 579169691Skan#ifdef _GLIBCXX_DEBUG 580169691Skan void 581169691Skan assert_entry_pointer_array_valid(const entry_pointer_array) const; 582169691Skan 583169691Skan void 584169691Skan assert_entry_pointer_valid(const entry_pointer, true_type) const; 585169691Skan 586169691Skan void 587169691Skan assert_entry_pointer_valid(const entry_pointer, false_type) const; 588169691Skan#endif 589169691Skan 590169691Skan#ifdef PB_DS_HT_MAP_TRACE_ 591169691Skan void 592169691Skan trace_list(const_entry_pointer) const; 593169691Skan#endif 594169691Skan 595169691Skan private: 596169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 597169691Skan friend class iterator_; 598169691Skan#endif 599169691Skan 600169691Skan friend class const_iterator_; 601169691Skan 602169691Skan static entry_allocator s_entry_allocator; 603169691Skan static entry_pointer_allocator s_entry_pointer_allocator; 604169691Skan static iterator s_end_it; 605169691Skan static const_iterator s_const_end_it; 606169691Skan static point_iterator s_find_end_it; 607169691Skan static const_point_iterator s_const_find_end_it; 608169691Skan 609169691Skan size_type m_num_e; 610169691Skan size_type m_num_used_e; 611169691Skan entry_pointer_array m_entries; 612169691Skan 613169691Skan enum 614169691Skan { 615169691Skan store_hash_ok = !Store_Hash 616169691Skan || !is_same<Hash_Fn, pb_ds::null_hash_fn>::value 617169691Skan }; 618169691Skan 619169691Skan PB_DS_STATIC_ASSERT(sth, store_hash_ok); 620169691Skan }; 621169691Skan 622169691Skan#include <ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp> 623169691Skan#include <ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp> 624169691Skan#include <ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp> 625169691Skan#include <ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp> 626169691Skan#include <ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp> 627169691Skan#include <ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp> 628169691Skan#include <ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp> 629169691Skan#include <ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp> 630169691Skan#include <ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp> 631169691Skan#include <ext/pb_ds/detail/cc_hash_table_map_/insert_fn_imps.hpp> 632169691Skan#include <ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp> 633169691Skan 634169691Skan#undef PB_DS_CLASS_T_DEC 635169691Skan#undef PB_DS_CLASS_C_DEC 636169691Skan#undef PB_DS_HASH_EQ_FN_C_DEC 637169691Skan#undef PB_DS_RANGED_HASH_FN_C_DEC 638169691Skan#undef PB_DS_TYPES_TRAITS_C_DEC 639169691Skan#undef PB_DS_MAP_DEBUG_BASE_C_DEC 640169691Skan#undef PB_DS_CLASS_NAME 641169691Skan#undef PB_DS_V2F 642169691Skan#undef PB_DS_V2S 643169691Skan#undef PB_DS_STATIC_ASSERT 644169691Skan 645169691Skan } // namespace detail 646169691Skan} // namespace pb_ds 647169691Skan 648