1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2007, 2009, 2010 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_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 62#define PB_DS_CLASS_T_DEC \ 63 template<typename Key, typename Mapped, typename Hash_Fn, \ 64 typename Eq_Fn, typename Allocator, bool Store_Hash, \ 65 typename Comb_Hash_Fn, typename Resize_Policy> 66 67#ifdef PB_DS_DATA_TRUE_INDICATOR 68#define PB_DS_CLASS_NAME cc_ht_map_data_ 69#endif 70 71#ifdef PB_DS_DATA_FALSE_INDICATOR 72#define PB_DS_CLASS_NAME cc_ht_map_no_data_ 73#endif 74 75#define PB_DS_CLASS_C_DEC \ 76 PB_DS_CLASS_NAME<Key, Mapped, Hash_Fn, Eq_Fn, Allocator, \ 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, Allocator, Store_Hash> 81 82#define PB_DS_RANGED_HASH_FN_C_DEC \ 83 ranged_hash_fn<Key, Hash_Fn, Allocator, Comb_Hash_Fn, Store_Hash> 84 85#define PB_DS_TYPES_TRAITS_C_DEC \ 86 types_traits<Key, Mapped, Allocator, Store_Hash> 87 88#ifdef _GLIBCXX_DEBUG 89#define PB_DS_DEBUG_MAP_BASE_C_DEC \ 90 debug_map_base<Key, Eq_Fn, typename Allocator::template rebind<Key>::other::const_reference> 91#endif 92 93#ifdef PB_DS_DATA_TRUE_INDICATOR 94#define PB_DS_V2F(X) (X).first 95#define PB_DS_V2S(X) (X).second 96#endif 97 98#ifdef PB_DS_DATA_FALSE_INDICATOR 99#define PB_DS_V2F(X) (X) 100#define PB_DS_V2S(X) Mapped_Data() 101#endif 102 103 // <011i$i0|\|-<|-|4i|\|i|\|g |-|4$|-| 74813. 104 template<typename Key, 105 typename Mapped, 106 typename Hash_Fn, 107 typename Eq_Fn, 108 typename Allocator, 109 bool Store_Hash, 110 typename Comb_Hash_Fn, 111 typename Resize_Policy > 112 class PB_DS_CLASS_NAME: 113#ifdef _GLIBCXX_DEBUG 114 protected PB_DS_DEBUG_MAP_BASE_C_DEC, 115#endif 116 public PB_DS_HASH_EQ_FN_C_DEC, 117 public Resize_Policy, 118 public PB_DS_RANGED_HASH_FN_C_DEC, 119 public PB_DS_TYPES_TRAITS_C_DEC 120 { 121 private: 122 typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; 123 typedef typename traits_base::comp_hash comp_hash; 124 typedef typename traits_base::value_type value_type_; 125 typedef typename traits_base::pointer pointer_; 126 typedef typename traits_base::const_pointer const_pointer_; 127 typedef typename traits_base::reference reference_; 128 typedef typename traits_base::const_reference const_reference_; 129 130 struct entry : public traits_base::stored_value_type 131 { 132 typename Allocator::template rebind<entry>::other::pointer m_p_next; 133 }; 134 135 typedef cond_dealtor<entry, Allocator> cond_dealtor_t; 136 137 typedef typename Allocator::template rebind<entry>::other entry_allocator; 138 typedef typename entry_allocator::pointer entry_pointer; 139 typedef typename entry_allocator::const_pointer const_entry_pointer; 140 typedef typename entry_allocator::reference entry_reference; 141 typedef typename entry_allocator::const_reference const_entry_reference; 142 143 typedef typename Allocator::template rebind<entry_pointer>::other entry_pointer_allocator; 144 typedef typename entry_pointer_allocator::pointer entry_pointer_array; 145 146 typedef PB_DS_RANGED_HASH_FN_C_DEC ranged_hash_fn_base; 147 typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base; 148 typedef Resize_Policy resize_base; 149 150#ifdef _GLIBCXX_DEBUG 151 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 152#endif 153 154#define PB_DS_GEN_POS std::pair<entry_pointer, typename Allocator::size_type> 155 156#include <ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp> 157#include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp> 158#include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp> 159#include <ext/pb_ds/detail/unordered_iterator/iterator.hpp> 160 161#undef PB_DS_GEN_POS 162 163 public: 164 typedef Allocator allocator_type; 165 typedef typename Allocator::size_type size_type; 166 typedef typename Allocator::difference_type difference_type; 167 typedef Hash_Fn hash_fn; 168 typedef Eq_Fn eq_fn; 169 typedef Comb_Hash_Fn comb_hash_fn; 170 typedef Resize_Policy resize_policy; 171 172 enum 173 { 174 store_hash = Store_Hash 175 }; 176 177 typedef typename traits_base::key_type key_type; 178 typedef typename traits_base::key_pointer key_pointer; 179 typedef typename traits_base::const_key_pointer const_key_pointer; 180 typedef typename traits_base::key_reference key_reference; 181 typedef typename traits_base::const_key_reference const_key_reference; 182 typedef typename traits_base::mapped_type mapped_type; 183 typedef typename traits_base::mapped_pointer mapped_pointer; 184 typedef typename traits_base::const_mapped_pointer const_mapped_pointer; 185 typedef typename traits_base::mapped_reference mapped_reference; 186 typedef typename traits_base::const_mapped_reference const_mapped_reference; 187 typedef typename traits_base::value_type value_type; 188 typedef typename traits_base::pointer pointer; 189 typedef typename traits_base::const_pointer const_pointer; 190 typedef typename traits_base::reference reference; 191 typedef typename traits_base::const_reference const_reference; 192 193#ifdef PB_DS_DATA_TRUE_INDICATOR 194 typedef point_iterator_ point_iterator; 195#endif 196 197#ifdef PB_DS_DATA_FALSE_INDICATOR 198 typedef const_point_iterator_ point_iterator; 199#endif 200 201 typedef const_point_iterator_ const_point_iterator; 202 203#ifdef PB_DS_DATA_TRUE_INDICATOR 204 typedef iterator_ iterator; 205#endif 206 207#ifdef PB_DS_DATA_FALSE_INDICATOR 208 typedef const_iterator_ iterator; 209#endif 210 211 typedef const_iterator_ const_iterator; 212 213 PB_DS_CLASS_NAME(); 214 215 PB_DS_CLASS_NAME(const Hash_Fn&); 216 217 PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&); 218 219 PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&); 220 221 PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&, 222 const Resize_Policy&); 223 224 PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); 225 226 virtual 227 ~PB_DS_CLASS_NAME(); 228 229 void 230 swap(PB_DS_CLASS_C_DEC&); 231 232 template<typename It> 233 void 234 copy_from_range(It, It); 235 236 void 237 initialize(); 238 239 inline size_type 240 size() const; 241 242 inline size_type 243 max_size() const; 244 245 inline bool 246 empty() const; 247 248 Hash_Fn& 249 get_hash_fn(); 250 251 const Hash_Fn& 252 get_hash_fn() const; 253 254 Eq_Fn& 255 get_eq_fn(); 256 257 const Eq_Fn& 258 get_eq_fn() const; 259 260 Comb_Hash_Fn& 261 get_comb_hash_fn(); 262 263 const Comb_Hash_Fn& 264 get_comb_hash_fn() const; 265 266 Resize_Policy& 267 get_resize_policy(); 268 269 const Resize_Policy& 270 get_resize_policy() const; 271 272 inline std::pair<point_iterator, bool> 273 insert(const_reference r_val) 274 { return insert_imp(r_val, traits_base::m_store_extra_indicator); } 275 276 inline mapped_reference 277 operator[](const_key_reference r_key) 278 { 279#ifdef PB_DS_DATA_TRUE_INDICATOR 280 return (subscript_imp(r_key, traits_base::m_store_extra_indicator)); 281#else 282 insert(r_key); 283 return traits_base::s_null_mapped; 284#endif 285 } 286 287 inline point_iterator 288 find(const_key_reference); 289 290 inline const_point_iterator 291 find(const_key_reference) const; 292 293 inline point_iterator 294 find_end(); 295 296 inline const_point_iterator 297 find_end() const; 298 299 inline bool 300 erase(const_key_reference); 301 302 template<typename Pred> 303 inline size_type 304 erase_if(Pred); 305 306 void 307 clear(); 308 309 inline iterator 310 begin(); 311 312 inline const_iterator 313 begin() const; 314 315 inline iterator 316 end(); 317 318 inline const_iterator 319 end() const; 320 321#ifdef _GLIBCXX_DEBUG 322 void 323 assert_valid() const; 324#endif 325 326#ifdef PB_DS_HT_MAP_TRACE_ 327 void 328 trace() const; 329#endif 330 331 private: 332 void 333 deallocate_all(); 334 335 inline bool 336 do_resize_if_needed(); 337 338 inline void 339 do_resize_if_needed_no_throw(); 340 341 void 342 resize_imp(size_type new_size); 343 344 void 345 do_resize(size_type new_size); 346 347 void 348 resize_imp_no_exceptions(size_type, entry_pointer_array, size_type); 349 350 inline entry_pointer 351 resize_imp_no_exceptions_reassign_pointer(entry_pointer, entry_pointer_array, false_type); 352 353 inline entry_pointer 354 resize_imp_no_exceptions_reassign_pointer(entry_pointer, entry_pointer_array, true_type); 355 356 void 357 deallocate_links_in_list(entry_pointer); 358 359 inline entry_pointer 360 get_entry(const_reference, false_type); 361 362 inline entry_pointer 363 get_entry(const_reference, true_type); 364 365 inline void 366 rels_entry(entry_pointer); 367 368#ifdef PB_DS_DATA_TRUE_INDICATOR 369 inline mapped_reference 370 subscript_imp(const_key_reference r_key, false_type) 371 { 372 _GLIBCXX_DEBUG_ONLY(assert_valid();) 373 const size_type pos = ranged_hash_fn_base::operator()(r_key); 374 entry_pointer p_e = m_entries[pos]; 375 resize_base::notify_insert_search_start(); 376 377 while (p_e != 0 378 && !hash_eq_fn_base::operator()(p_e->m_value.first, r_key)) 379 { 380 resize_base::notify_insert_search_collision(); 381 p_e = p_e->m_p_next; 382 } 383 384 resize_base::notify_insert_search_end(); 385 if (p_e != 0) 386 { 387 _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);) 388 return (p_e->m_value.second); 389 } 390 391 _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) 392 return insert_new_imp(value_type(r_key, mapped_type()), pos)->second; 393 } 394 395 inline mapped_reference 396 subscript_imp(const_key_reference r_key, true_type) 397 { 398 _GLIBCXX_DEBUG_ONLY(assert_valid();) 399 comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key); 400 entry_pointer p_e = m_entries[pos_hash_pair.first]; 401 resize_base::notify_insert_search_start(); 402 while (p_e != 0 && 403 !hash_eq_fn_base::operator()(p_e->m_value.first, p_e->m_hash, r_key, pos_hash_pair.second)) 404 { 405 resize_base::notify_insert_search_collision(); 406 p_e = p_e->m_p_next; 407 } 408 409 resize_base::notify_insert_search_end(); 410 if (p_e != 0) 411 { 412 _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);) 413 return p_e->m_value.second; 414 } 415 416 _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) 417 return insert_new_imp(value_type(r_key, mapped_type()), 418 pos_hash_pair)->second; 419 } 420#endif 421 422 inline std::pair<point_iterator, bool> 423 insert_imp(const_reference, false_type); 424 425 inline std::pair<point_iterator, bool> 426 insert_imp(const_reference, true_type); 427 428 inline pointer 429 insert_new_imp(const_reference r_val, size_type pos) 430 { 431 if (do_resize_if_needed()) 432 pos = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val)); 433 434 // Following lines might throw an exception. 435 entry_pointer p_e = get_entry(r_val, traits_base::m_no_throw_copies_indicator); 436 437 // At this point no exceptions can be thrown. 438 p_e->m_p_next = m_entries[pos]; 439 m_entries[pos] = p_e; 440 resize_base::notify_inserted(++m_num_used_e); 441 442 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) 443 _GLIBCXX_DEBUG_ONLY(assert_valid();) 444 return &p_e->m_value; 445 } 446 447 inline pointer 448 insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair) 449 { 450 // Following lines might throw an exception. 451 if (do_resize_if_needed()) 452 r_pos_hash_pair = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val)); 453 454 entry_pointer p_e = get_entry(r_val, traits_base::m_no_throw_copies_indicator); 455 456 // At this point no exceptions can be thrown. 457 p_e->m_hash = r_pos_hash_pair.second; 458 p_e->m_p_next = m_entries[r_pos_hash_pair.first]; 459 m_entries[r_pos_hash_pair.first] = p_e; 460 resize_base::notify_inserted(++m_num_used_e); 461 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) 462 _GLIBCXX_DEBUG_ONLY(assert_valid();) 463 return &p_e->m_value; 464 } 465 466 inline pointer 467 find_key_pointer(const_key_reference r_key, false_type) 468 { 469 entry_pointer p_e = m_entries[ranged_hash_fn_base::operator()(r_key)]; 470 resize_base::notify_find_search_start(); 471 while (p_e != 0 && 472 !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) 473 { 474 resize_base::notify_find_search_collision(); 475 p_e = p_e->m_p_next; 476 } 477 478 resize_base::notify_find_search_end(); 479 480#ifdef _GLIBCXX_DEBUG 481 if (p_e == 0) 482 debug_base::check_key_does_not_exist(r_key); 483 else 484 debug_base::check_key_exists(r_key); 485#endif 486 return &p_e->m_value; 487 } 488 489 inline pointer 490 find_key_pointer(const_key_reference r_key, true_type) 491 { 492 comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key); 493 entry_pointer p_e = m_entries[pos_hash_pair.first]; 494 resize_base::notify_find_search_start(); 495 while (p_e != 0 && 496 !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), 497 p_e->m_hash, 498 r_key, pos_hash_pair.second)) 499 { 500 resize_base::notify_find_search_collision(); 501 p_e = p_e->m_p_next; 502 } 503 504 resize_base::notify_find_search_end(); 505 506#ifdef _GLIBCXX_DEBUG 507 if (p_e == 0) 508 debug_base::check_key_does_not_exist(r_key); 509 else 510 debug_base::check_key_exists(r_key); 511#endif 512 return &p_e->m_value; 513 } 514 515 inline bool 516 erase_in_pos_imp(const_key_reference, size_type); 517 518 inline bool 519 erase_in_pos_imp(const_key_reference, const comp_hash&); 520 521 inline void 522 erase_entry_pointer(entry_pointer&); 523 524#ifdef PB_DS_DATA_TRUE_INDICATOR 525 void 526 inc_it_state(pointer& r_p_value, 527 std::pair<entry_pointer, size_type>& r_pos) const 528 { 529 inc_it_state((const_mapped_pointer& )r_p_value, r_pos); 530 } 531#endif 532 533 void 534 inc_it_state(const_pointer& r_p_value, 535 std::pair<entry_pointer, size_type>& r_pos) const 536 { 537 _GLIBCXX_DEBUG_ASSERT(r_p_value != 0); 538 r_pos.first = r_pos.first->m_p_next; 539 if (r_pos.first != 0) 540 { 541 r_p_value = &r_pos.first->m_value; 542 return; 543 } 544 545 for (++r_pos.second; r_pos.second < m_num_e; ++r_pos.second) 546 if (m_entries[r_pos.second] != 0) 547 { 548 r_pos.first = m_entries[r_pos.second]; 549 r_p_value = &r_pos.first->m_value; 550 return; 551 } 552 r_p_value = 0; 553 } 554 555 void 556 get_start_it_state(pointer& r_p_value, 557 std::pair<entry_pointer, size_type>& r_pos) const 558 { 559 for (r_pos.second = 0; r_pos.second < m_num_e; ++r_pos.second) 560 if (m_entries[r_pos.second] != 0) 561 { 562 r_pos.first = m_entries[r_pos.second]; 563 r_p_value = &r_pos.first->m_value; 564 return; 565 } 566 r_p_value = 0; 567 } 568 569#ifdef _GLIBCXX_DEBUG 570 void 571 assert_entry_pointer_array_valid(const entry_pointer_array) const; 572 573 void 574 assert_entry_pointer_valid(const entry_pointer, true_type) const; 575 576 void 577 assert_entry_pointer_valid(const entry_pointer, false_type) const; 578#endif 579 580#ifdef PB_DS_HT_MAP_TRACE_ 581 void 582 trace_list(const_entry_pointer) const; 583#endif 584 585 private: 586#ifdef PB_DS_DATA_TRUE_INDICATOR 587 friend class iterator_; 588#endif 589 590 friend class const_iterator_; 591 592 static entry_allocator s_entry_allocator; 593 static entry_pointer_allocator s_entry_pointer_allocator; 594 static iterator s_end_it; 595 static const_iterator s_const_end_it; 596 static point_iterator s_find_end_it; 597 static const_point_iterator s_const_find_end_it; 598 599 size_type m_num_e; 600 size_type m_num_used_e; 601 entry_pointer_array m_entries; 602 603 enum 604 { 605 store_hash_ok = !Store_Hash 606 || !is_same<Hash_Fn, __gnu_pbds::null_hash_fn>::value 607 }; 608 609 PB_DS_STATIC_ASSERT(sth, store_hash_ok); 610 }; 611 612#include <ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp> 613#include <ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp> 614#include <ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp> 615#include <ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp> 616#include <ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp> 617#include <ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp> 618#include <ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp> 619#include <ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp> 620#include <ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp> 621#include <ext/pb_ds/detail/cc_hash_table_map_/insert_fn_imps.hpp> 622#include <ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp> 623 624#undef PB_DS_CLASS_T_DEC 625#undef PB_DS_CLASS_C_DEC 626#undef PB_DS_HASH_EQ_FN_C_DEC 627#undef PB_DS_RANGED_HASH_FN_C_DEC 628#undef PB_DS_TYPES_TRAITS_C_DEC 629#undef PB_DS_DEBUG_MAP_BASE_C_DEC 630#undef PB_DS_CLASS_NAME 631#undef PB_DS_V2F 632#undef PB_DS_V2S 633 634 } // namespace detail 635} // namespace __gnu_pbds 636 637