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