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