1// -*- C++ -*- 2 3// Copyright (C) 2005-2015 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the terms 7// of the GNU General Public License as published by the Free Software 8// Foundation; either version 3, or (at your option) any later 9// version. 10 11// This library is distributed in the hope that it will be useful, but 12// WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14// General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 27// Permission to use, copy, modify, sell, and distribute this software 28// is hereby granted without fee, provided that the above copyright 29// notice appears in all copies, and that both that copyright notice 30// and this permission notice appear in supporting documentation. None 31// of the above authors, nor IBM Haifa Research Laboratories, make any 32// representation about the suitability of this software for any 33// purpose. It is provided "as is" without express or implied 34// warranty. 35 36/** 37 * @file cc_hash_table_map_/cc_ht_map_.hpp 38 * Contains an implementation class for cc_ht_map_. 39 */ 40 41#include <utility> 42#include <iterator> 43#include <ext/pb_ds/detail/cond_dealtor.hpp> 44#include <ext/pb_ds/tag_and_trait.hpp> 45#include <ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp> 46#include <ext/pb_ds/detail/types_traits.hpp> 47#include <ext/pb_ds/exception.hpp> 48#include <ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp> 49#ifdef _GLIBCXX_DEBUG 50#include <ext/pb_ds/detail/debug_map_base.hpp> 51#endif 52#ifdef PB_DS_HT_MAP_TRACE_ 53#include <iostream> 54#endif 55#include <debug/debug.h> 56 57namespace __gnu_pbds 58{ 59 namespace detail 60 { 61#ifdef PB_DS_DATA_TRUE_INDICATOR 62#define PB_DS_CC_HASH_NAME cc_ht_map 63#endif 64 65#ifdef PB_DS_DATA_FALSE_INDICATOR 66#define PB_DS_CC_HASH_NAME cc_ht_set 67#endif 68 69#define PB_DS_CLASS_T_DEC \ 70 template<typename Key, typename Mapped, typename Hash_Fn, \ 71 typename Eq_Fn, typename _Alloc, bool Store_Hash, \ 72 typename Comb_Hash_Fn, typename Resize_Policy> 73 74#define PB_DS_CLASS_C_DEC \ 75 PB_DS_CC_HASH_NAME<Key, Mapped, Hash_Fn, Eq_Fn, _Alloc, \ 76 Store_Hash, Comb_Hash_Fn, Resize_Policy> 77 78#define PB_DS_HASH_EQ_FN_C_DEC \ 79 hash_eq_fn<Key, Eq_Fn, _Alloc, Store_Hash> 80 81#define PB_DS_RANGED_HASH_FN_C_DEC \ 82 ranged_hash_fn<Key, Hash_Fn, _Alloc, Comb_Hash_Fn, Store_Hash> 83 84#define PB_DS_CC_HASH_TRAITS_BASE \ 85 types_traits<Key, Mapped, _Alloc, Store_Hash> 86 87#ifdef _GLIBCXX_DEBUG 88#define PB_DS_DEBUG_MAP_BASE_C_DEC \ 89 debug_map_base<Key, Eq_Fn, \ 90 typename _Alloc::template rebind<Key>::other::const_reference> 91#endif 92 93 94 /** 95 * A collision-chaining hash-based container. 96 * 97 * 98 * @ingroup hash-detail 99 * 100 * @tparam Key Key type. 101 * 102 * @tparam Mapped Map type. 103 * 104 * @tparam Hash_Fn Hashing functor. 105 * Default is __gnu_cxx::hash. 106 * 107 * @tparam Eq_Fn Equal functor. 108 * Default std::equal_to<Key> 109 * 110 * @tparam _Alloc Allocator type. 111 * 112 * @tparam Store_Hash If key type stores extra metadata. 113 * Defaults to false. 114 * 115 * @tparam Comb_Hash_Fn Combining hash functor. 116 * If Hash_Fn is not null_type, then this 117 * is the ranged-hash functor; otherwise, 118 * this is the range-hashing functor. 119 * XXX(See Design::Hash-Based Containers::Hash Policies.) 120 * Default direct_mask_range_hashing. 121 * 122 * @tparam Resize_Policy Resizes hash. 123 * Defaults to hash_standard_resize_policy, 124 * using hash_exponential_size_policy and 125 * hash_load_check_resize_trigger. 126 * 127 * 128 * Bases are: detail::hash_eq_fn, Resize_Policy, detail::ranged_hash_fn, 129 * detail::types_traits. (Optional: detail::debug_map_base.) 130 */ 131 template<typename Key, 132 typename Mapped, 133 typename Hash_Fn, 134 typename Eq_Fn, 135 typename _Alloc, 136 bool Store_Hash, 137 typename Comb_Hash_Fn, 138 typename Resize_Policy > 139 class PB_DS_CC_HASH_NAME: 140#ifdef _GLIBCXX_DEBUG 141 protected PB_DS_DEBUG_MAP_BASE_C_DEC, 142#endif 143 public PB_DS_HASH_EQ_FN_C_DEC, 144 public Resize_Policy, 145 public PB_DS_RANGED_HASH_FN_C_DEC, 146 public PB_DS_CC_HASH_TRAITS_BASE 147 { 148 private: 149 typedef PB_DS_CC_HASH_TRAITS_BASE traits_base; 150 typedef typename traits_base::comp_hash comp_hash; 151 typedef typename traits_base::value_type value_type_; 152 typedef typename traits_base::pointer pointer_; 153 typedef typename traits_base::const_pointer const_pointer_; 154 typedef typename traits_base::reference reference_; 155 typedef typename traits_base::const_reference const_reference_; 156 157 struct entry : public traits_base::stored_data_type 158 { 159 typename _Alloc::template rebind<entry>::other::pointer m_p_next; 160 }; 161 162 typedef cond_dealtor<entry, _Alloc> cond_dealtor_t; 163 164 typedef typename _Alloc::template rebind<entry>::other entry_allocator; 165 typedef typename entry_allocator::pointer entry_pointer; 166 typedef typename entry_allocator::const_pointer const_entry_pointer; 167 typedef typename entry_allocator::reference entry_reference; 168 typedef typename entry_allocator::const_reference const_entry_reference; 169 170 typedef typename _Alloc::template rebind<entry_pointer>::other entry_pointer_allocator; 171 typedef typename entry_pointer_allocator::pointer entry_pointer_array; 172 173 typedef PB_DS_RANGED_HASH_FN_C_DEC ranged_hash_fn_base; 174 typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base; 175 typedef Resize_Policy resize_base; 176 177#ifdef _GLIBCXX_DEBUG 178 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 179#endif 180 181#define PB_DS_GEN_POS std::pair<entry_pointer, typename _Alloc::size_type> 182 183#include <ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp> 184#include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp> 185#include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp> 186#include <ext/pb_ds/detail/unordered_iterator/iterator.hpp> 187 188#undef PB_DS_GEN_POS 189 190 public: 191 typedef _Alloc allocator_type; 192 typedef typename _Alloc::size_type size_type; 193 typedef typename _Alloc::difference_type difference_type; 194 typedef Hash_Fn hash_fn; 195 typedef Eq_Fn eq_fn; 196 typedef Comb_Hash_Fn comb_hash_fn; 197 typedef Resize_Policy resize_policy; 198 199 /// Value stores hash, true or false. 200 enum 201 { 202 store_hash = Store_Hash 203 }; 204 205 typedef typename traits_base::key_type key_type; 206 typedef typename traits_base::key_pointer key_pointer; 207 typedef typename traits_base::key_const_pointer key_const_pointer; 208 typedef typename traits_base::key_reference key_reference; 209 typedef typename traits_base::key_const_reference key_const_reference; 210 typedef typename traits_base::mapped_type mapped_type; 211 typedef typename traits_base::mapped_pointer mapped_pointer; 212 typedef typename traits_base::mapped_const_pointer mapped_const_pointer; 213 typedef typename traits_base::mapped_reference mapped_reference; 214 typedef typename traits_base::mapped_const_reference mapped_const_reference; 215 typedef typename traits_base::value_type value_type; 216 typedef typename traits_base::pointer pointer; 217 typedef typename traits_base::const_pointer const_pointer; 218 typedef typename traits_base::reference reference; 219 typedef typename traits_base::const_reference const_reference; 220 221#ifdef PB_DS_DATA_TRUE_INDICATOR 222 typedef point_iterator_ point_iterator; 223#endif 224 225#ifdef PB_DS_DATA_FALSE_INDICATOR 226 typedef point_const_iterator_ point_iterator; 227#endif 228 229 typedef point_const_iterator_ point_const_iterator; 230 231#ifdef PB_DS_DATA_TRUE_INDICATOR 232 typedef iterator_ iterator; 233#endif 234 235#ifdef PB_DS_DATA_FALSE_INDICATOR 236 typedef const_iterator_ iterator; 237#endif 238 239 typedef const_iterator_ const_iterator; 240 241 PB_DS_CC_HASH_NAME(); 242 243 PB_DS_CC_HASH_NAME(const Hash_Fn&); 244 245 PB_DS_CC_HASH_NAME(const Hash_Fn&, const Eq_Fn&); 246 247 PB_DS_CC_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&); 248 249 PB_DS_CC_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&, 250 const Resize_Policy&); 251 252 PB_DS_CC_HASH_NAME(const PB_DS_CLASS_C_DEC&); 253 254 virtual 255 ~PB_DS_CC_HASH_NAME(); 256 257 void 258 swap(PB_DS_CLASS_C_DEC&); 259 260 template<typename It> 261 void 262 copy_from_range(It, It); 263 264 void 265 initialize(); 266 267 inline size_type 268 size() const; 269 270 inline size_type 271 max_size() const; 272 273 /// True if size() == 0. 274 inline bool 275 empty() const; 276 277 /// Return current hash_fn. 278 Hash_Fn& 279 get_hash_fn(); 280 281 /// Return current const hash_fn. 282 const Hash_Fn& 283 get_hash_fn() const; 284 285 /// Return current eq_fn. 286 Eq_Fn& 287 get_eq_fn(); 288 289 /// Return current const eq_fn. 290 const Eq_Fn& 291 get_eq_fn() const; 292 293 /// Return current comb_hash_fn. 294 Comb_Hash_Fn& 295 get_comb_hash_fn(); 296 297 /// Return current const comb_hash_fn. 298 const Comb_Hash_Fn& 299 get_comb_hash_fn() const; 300 301 /// Return current resize_policy. 302 Resize_Policy& 303 get_resize_policy(); 304 305 /// Return current const resize_policy. 306 const Resize_Policy& 307 get_resize_policy() const; 308 309 inline std::pair<point_iterator, bool> 310 insert(const_reference r_val) 311 { return insert_imp(r_val, traits_base::m_store_extra_indicator); } 312 313 inline mapped_reference 314 operator[](key_const_reference r_key) 315 { 316#ifdef PB_DS_DATA_TRUE_INDICATOR 317 return (subscript_imp(r_key, traits_base::m_store_extra_indicator)); 318#else 319 insert(r_key); 320 return traits_base::s_null_type; 321#endif 322 } 323 324 inline point_iterator 325 find(key_const_reference); 326 327 inline point_const_iterator 328 find(key_const_reference) const; 329 330 inline point_iterator 331 find_end(); 332 333 inline point_const_iterator 334 find_end() const; 335 336 inline bool 337 erase(key_const_reference); 338 339 template<typename Pred> 340 inline size_type 341 erase_if(Pred); 342 343 void 344 clear(); 345 346 inline iterator 347 begin(); 348 349 inline const_iterator 350 begin() const; 351 352 inline iterator 353 end(); 354 355 inline const_iterator 356 end() const; 357 358#ifdef _GLIBCXX_DEBUG 359 void 360 assert_valid(const char*, int) const; 361#endif 362 363#ifdef PB_DS_HT_MAP_TRACE_ 364 void 365 trace() const; 366#endif 367 368 private: 369 void 370 deallocate_all(); 371 372 inline bool 373 do_resize_if_needed(); 374 375 inline void 376 do_resize_if_needed_no_throw(); 377 378 void 379 resize_imp(size_type); 380 381 void 382 do_resize(size_type); 383 384 void 385 resize_imp_no_exceptions(size_type, entry_pointer_array, size_type); 386 387 inline entry_pointer 388 resize_imp_no_exceptions_reassign_pointer(entry_pointer, 389 entry_pointer_array, 390 false_type); 391 392 inline entry_pointer 393 resize_imp_no_exceptions_reassign_pointer(entry_pointer, 394 entry_pointer_array, 395 true_type); 396 397 void 398 deallocate_links_in_list(entry_pointer); 399 400 inline entry_pointer 401 get_entry(const_reference, false_type); 402 403 inline entry_pointer 404 get_entry(const_reference, true_type); 405 406 inline void 407 rels_entry(entry_pointer); 408 409#ifdef PB_DS_DATA_TRUE_INDICATOR 410 inline mapped_reference 411 subscript_imp(key_const_reference r_key, false_type) 412 { 413 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 414 const size_type pos = ranged_hash_fn_base::operator()(r_key); 415 entry_pointer p_e = m_entries[pos]; 416 resize_base::notify_insert_search_start(); 417 418 while (p_e != 0 419 && !hash_eq_fn_base::operator()(p_e->m_value.first, r_key)) 420 { 421 resize_base::notify_insert_search_collision(); 422 p_e = p_e->m_p_next; 423 } 424 425 resize_base::notify_insert_search_end(); 426 if (p_e != 0) 427 { 428 PB_DS_CHECK_KEY_EXISTS(r_key) 429 return (p_e->m_value.second); 430 } 431 432 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 433 return insert_new_imp(value_type(r_key, mapped_type()), pos)->second; 434 } 435 436 inline mapped_reference 437 subscript_imp(key_const_reference r_key, true_type) 438 { 439 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 440 comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key); 441 entry_pointer p_e = m_entries[pos_hash_pair.first]; 442 resize_base::notify_insert_search_start(); 443 while (p_e != 0 && 444 !hash_eq_fn_base::operator()(p_e->m_value.first, p_e->m_hash, 445 r_key, pos_hash_pair.second)) 446 { 447 resize_base::notify_insert_search_collision(); 448 p_e = p_e->m_p_next; 449 } 450 451 resize_base::notify_insert_search_end(); 452 if (p_e != 0) 453 { 454 PB_DS_CHECK_KEY_EXISTS(r_key) 455 return p_e->m_value.second; 456 } 457 458 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 459 return insert_new_imp(value_type(r_key, mapped_type()), 460 pos_hash_pair)->second; 461 } 462#endif 463 464 inline std::pair<point_iterator, bool> 465 insert_imp(const_reference, false_type); 466 467 inline std::pair<point_iterator, bool> 468 insert_imp(const_reference, true_type); 469 470 inline pointer 471 insert_new_imp(const_reference r_val, size_type pos) 472 { 473 if (do_resize_if_needed()) 474 pos = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val)); 475 476 // Following lines might throw an exception. 477 entry_pointer p_e = get_entry(r_val, 478 traits_base::m_no_throw_copies_indicator); 479 480 // At this point no exceptions can be thrown. 481 p_e->m_p_next = m_entries[pos]; 482 m_entries[pos] = p_e; 483 resize_base::notify_inserted(++m_num_used_e); 484 485 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) 486 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 487 return &p_e->m_value; 488 } 489 490 inline pointer 491 insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair) 492 { 493 // Following lines might throw an exception. 494 if (do_resize_if_needed()) 495 r_pos_hash_pair = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val)); 496 497 entry_pointer p_e = get_entry(r_val, 498 traits_base::m_no_throw_copies_indicator); 499 500 // At this point no exceptions can be thrown. 501 p_e->m_hash = r_pos_hash_pair.second; 502 p_e->m_p_next = m_entries[r_pos_hash_pair.first]; 503 m_entries[r_pos_hash_pair.first] = p_e; 504 resize_base::notify_inserted(++m_num_used_e); 505 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) 506 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 507 return &p_e->m_value; 508 } 509 510 inline pointer 511 find_key_pointer(key_const_reference r_key, false_type) 512 { 513 entry_pointer p_e = m_entries[ranged_hash_fn_base::operator()(r_key)]; 514 resize_base::notify_find_search_start(); 515 while (p_e != 0 && 516 !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) 517 { 518 resize_base::notify_find_search_collision(); 519 p_e = p_e->m_p_next; 520 } 521 522 resize_base::notify_find_search_end(); 523 524#ifdef _GLIBCXX_DEBUG 525 if (p_e == 0) 526 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 527 else 528 PB_DS_CHECK_KEY_EXISTS(r_key) 529#endif 530 return &p_e->m_value; 531 } 532 533 inline pointer 534 find_key_pointer(key_const_reference r_key, true_type) 535 { 536 comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key); 537 entry_pointer p_e = m_entries[pos_hash_pair.first]; 538 resize_base::notify_find_search_start(); 539 while (p_e != 0 && 540 !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), 541 p_e->m_hash, 542 r_key, pos_hash_pair.second)) 543 { 544 resize_base::notify_find_search_collision(); 545 p_e = p_e->m_p_next; 546 } 547 548 resize_base::notify_find_search_end(); 549 550#ifdef _GLIBCXX_DEBUG 551 if (p_e == 0) 552 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 553 else 554 PB_DS_CHECK_KEY_EXISTS(r_key) 555#endif 556 return &p_e->m_value; 557 } 558 559 inline bool 560 erase_in_pos_imp(key_const_reference, size_type); 561 562 inline bool 563 erase_in_pos_imp(key_const_reference, const comp_hash&); 564 565 inline void 566 erase_entry_pointer(entry_pointer&); 567 568#ifdef PB_DS_DATA_TRUE_INDICATOR 569 void 570 inc_it_state(pointer& r_p_value, 571 std::pair<entry_pointer, size_type>& r_pos) const 572 { 573 inc_it_state((mapped_const_pointer& )r_p_value, r_pos); 574 } 575#endif 576 577 void 578 inc_it_state(const_pointer& r_p_value, 579 std::pair<entry_pointer, size_type>& r_pos) const 580 { 581 _GLIBCXX_DEBUG_ASSERT(r_p_value != 0); 582 r_pos.first = r_pos.first->m_p_next; 583 if (r_pos.first != 0) 584 { 585 r_p_value = &r_pos.first->m_value; 586 return; 587 } 588 589 for (++r_pos.second; r_pos.second < m_num_e; ++r_pos.second) 590 if (m_entries[r_pos.second] != 0) 591 { 592 r_pos.first = m_entries[r_pos.second]; 593 r_p_value = &r_pos.first->m_value; 594 return; 595 } 596 r_p_value = 0; 597 } 598 599 void 600 get_start_it_state(pointer& r_p_value, 601 std::pair<entry_pointer, size_type>& r_pos) const 602 { 603 for (r_pos.second = 0; r_pos.second < m_num_e; ++r_pos.second) 604 if (m_entries[r_pos.second] != 0) 605 { 606 r_pos.first = m_entries[r_pos.second]; 607 r_p_value = &r_pos.first->m_value; 608 return; 609 } 610 r_p_value = 0; 611 } 612 613#ifdef _GLIBCXX_DEBUG 614 void 615 assert_entry_pointer_array_valid(const entry_pointer_array, 616 const char*, int) const; 617 618 void 619 assert_entry_pointer_valid(const entry_pointer, true_type, 620 const char*, int) const; 621 622 void 623 assert_entry_pointer_valid(const entry_pointer, false_type, 624 const char*, int) const; 625#endif 626 627#ifdef PB_DS_HT_MAP_TRACE_ 628 void 629 trace_list(const_entry_pointer) const; 630#endif 631 632 private: 633#ifdef PB_DS_DATA_TRUE_INDICATOR 634 friend class iterator_; 635#endif 636 637 friend class const_iterator_; 638 639 static entry_allocator s_entry_allocator; 640 static entry_pointer_allocator s_entry_pointer_allocator; 641 static iterator s_end_it; 642 static const_iterator s_const_end_it; 643 static point_iterator s_find_end_it; 644 static point_const_iterator s_const_find_end_it; 645 646 size_type m_num_e; 647 size_type m_num_used_e; 648 entry_pointer_array m_entries; 649 650 enum 651 { 652 store_hash_ok = !Store_Hash 653 || !is_same<Hash_Fn, __gnu_pbds::null_type>::value 654 }; 655 656 PB_DS_STATIC_ASSERT(sth, store_hash_ok); 657 }; 658 659#include <ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp> 660#include <ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp> 661#include <ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp> 662#include <ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp> 663#include <ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp> 664#include <ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp> 665#include <ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp> 666#include <ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp> 667#include <ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp> 668#include <ext/pb_ds/detail/cc_hash_table_map_/insert_fn_imps.hpp> 669#include <ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp> 670 671#undef PB_DS_CLASS_T_DEC 672#undef PB_DS_CLASS_C_DEC 673#undef PB_DS_HASH_EQ_FN_C_DEC 674#undef PB_DS_RANGED_HASH_FN_C_DEC 675#undef PB_DS_CC_HASH_TRAITS_BASE 676#undef PB_DS_DEBUG_MAP_BASE_C_DEC 677#undef PB_DS_CC_HASH_NAME 678 } // namespace detail 679} // namespace __gnu_pbds 680