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 gp_ht_map_.hpp 44 * Contains an implementation class for gp_ht_map_. 45 */ 46 47#include <ext/pb_ds/tag_and_trait.hpp> 48#include <ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp> 49#include <ext/pb_ds/detail/types_traits.hpp> 50#include <ext/pb_ds/exception.hpp> 51#include <ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp> 52#include <utility> 53#ifdef PB_DS_HT_MAP_TRACE_ 54#include <iostream> 55#endif 56#ifdef _GLIBCXX_DEBUG 57#include <ext/pb_ds/detail/map_debug_base.hpp> 58#endif 59#include <debug/debug.h> 60 61namespace pb_ds 62{ 63 namespace detail 64 { 65#define PB_DS_CLASS_T_DEC \ 66 template<typename Key, typename Mapped, typename Hash_Fn, typename Eq_Fn, \ 67 typename Allocator, bool Store_Hash, typename Comb_Probe_Fn, \ 68 typename Probe_Fn, typename Resize_Policy> 69 70#ifdef PB_DS_DATA_TRUE_INDICATOR 71#define PB_DS_CLASS_NAME gp_ht_map_data_ 72#endif 73 74#ifdef PB_DS_DATA_FALSE_INDICATOR 75#define PB_DS_CLASS_NAME gp_ht_map_no_data_ 76#endif 77 78#define PB_DS_CLASS_C_DEC \ 79 PB_DS_CLASS_NAME<Key, Mapped, Hash_Fn, Eq_Fn, Allocator, \ 80 Store_Hash, Comb_Probe_Fn, Probe_Fn, Resize_Policy> 81 82#define PB_DS_HASH_EQ_FN_C_DEC \ 83 hash_eq_fn<Key, Eq_Fn, Allocator, Store_Hash> 84 85#define PB_DS_RANGED_PROBE_FN_C_DEC \ 86 ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, Store_Hash> 87 88#define PB_DS_TYPES_TRAITS_C_DEC \ 89 types_traits<Key, Mapped, Allocator, Store_Hash> 90 91#ifdef _GLIBCXX_DEBUG 92#define PB_DS_MAP_DEBUG_BASE_C_DEC \ 93 map_debug_base<Key, Eq_Fn, typename Allocator::template rebind<Key>::other::const_reference> 94#endif 95 96#ifdef PB_DS_DATA_TRUE_INDICATOR 97#define PB_DS_V2F(X) (X).first 98#define PB_DS_V2S(X) (X).second 99#endif 100 101#ifdef PB_DS_DATA_FALSE_INDICATOR 102#define PB_DS_V2F(X) (X) 103#define PB_DS_V2S(X) Mapped() 104#endif 105 106#define PB_DS_STATIC_ASSERT(UNIQUE, E) \ 107 typedef static_assert_dumclass<sizeof(static_assert<(bool)(E)>)> \ 108 UNIQUE##static_assert_type 109 110 template<typename Key, 111 typename Mapped, 112 typename Hash_Fn, 113 typename Eq_Fn, 114 typename Allocator, 115 bool Store_Hash, 116 typename Comb_Probe_Fn, 117 typename Probe_Fn, 118 typename Resize_Policy> 119 class PB_DS_CLASS_NAME : 120#ifdef _GLIBCXX_DEBUG 121 protected PB_DS_MAP_DEBUG_BASE_C_DEC, 122#endif 123 public PB_DS_HASH_EQ_FN_C_DEC, 124 public Resize_Policy, 125 public PB_DS_RANGED_PROBE_FN_C_DEC, 126 public PB_DS_TYPES_TRAITS_C_DEC 127 { 128 private: 129 typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; 130 typedef typename traits_base::value_type value_type_; 131 typedef typename traits_base::pointer pointer_; 132 typedef typename traits_base::const_pointer const_pointer_; 133 typedef typename traits_base::reference reference_; 134 typedef typename traits_base::const_reference const_reference_; 135 typedef typename traits_base::comp_hash comp_hash; 136 137 enum entry_status 138 { 139 empty_entry_status, 140 valid_entry_status, 141 erased_entry_status 142 } __attribute__ ((packed)); 143 144 struct entry : public traits_base::stored_value_type 145 { 146 entry_status m_stat; 147 }; 148 149 typedef typename Allocator::template rebind<entry>::other entry_allocator; 150 typedef typename entry_allocator::pointer entry_pointer; 151 typedef typename entry_allocator::const_pointer const_entry_pointer; 152 typedef typename entry_allocator::reference entry_reference; 153 typedef typename entry_allocator::const_reference const_entry_reference; 154 typedef typename entry_allocator::pointer entry_array; 155 156 typedef PB_DS_RANGED_PROBE_FN_C_DEC ranged_probe_fn_base; 157 158#ifdef _GLIBCXX_DEBUG 159 typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base; 160#endif 161 162 typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base; 163 typedef Resize_Policy resize_base; 164 165#define PB_DS_GEN_POS typename Allocator::size_type 166 167#include <ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp> 168#include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp> 169#include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp> 170#include <ext/pb_ds/detail/unordered_iterator/iterator.hpp> 171 172#undef PB_DS_GEN_POS 173 174 public: 175 typedef Allocator allocator; 176 typedef typename Allocator::size_type size_type; 177 typedef typename Allocator::difference_type difference_type; 178 typedef Hash_Fn hash_fn; 179 typedef Eq_Fn eq_fn; 180 typedef Probe_Fn probe_fn; 181 typedef Comb_Probe_Fn comb_probe_fn; 182 typedef Resize_Policy resize_policy; 183 184 enum 185 { 186 store_hash = Store_Hash 187 }; 188 189 typedef typename traits_base::key_type key_type; 190 typedef typename traits_base::key_pointer key_pointer; 191 typedef typename traits_base::const_key_pointer const_key_pointer; 192 typedef typename traits_base::key_reference key_reference; 193 typedef typename traits_base::const_key_reference const_key_reference; 194 typedef typename traits_base::mapped_type mapped_type; 195 typedef typename traits_base::mapped_pointer mapped_pointer; 196 typedef typename traits_base::const_mapped_pointer const_mapped_pointer; 197 typedef typename traits_base::mapped_reference mapped_reference; 198 typedef typename traits_base::const_mapped_reference const_mapped_reference; 199 typedef typename traits_base::value_type value_type; 200 typedef typename traits_base::pointer pointer; 201 typedef typename traits_base::const_pointer const_pointer; 202 typedef typename traits_base::reference reference; 203 typedef typename traits_base::const_reference const_reference; 204 205#ifdef PB_DS_DATA_TRUE_INDICATOR 206 typedef point_iterator_ point_iterator; 207#endif 208 209#ifdef PB_DS_DATA_FALSE_INDICATOR 210 typedef const_point_iterator_ point_iterator; 211#endif 212 213 typedef const_point_iterator_ const_point_iterator; 214 215#ifdef PB_DS_DATA_TRUE_INDICATOR 216 typedef iterator_ iterator; 217#endif 218 219#ifdef PB_DS_DATA_FALSE_INDICATOR 220 typedef const_iterator_ iterator; 221#endif 222 223 typedef const_iterator_ const_iterator; 224 225 PB_DS_CLASS_NAME(); 226 227 PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); 228 229 PB_DS_CLASS_NAME(const Hash_Fn&); 230 231 PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&); 232 233 PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&); 234 235 PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&, 236 const Probe_Fn&); 237 238 PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&, 239 const Probe_Fn&, const Resize_Policy&); 240 241 template<typename It> 242 void 243 copy_from_range(It first_it, It last_it); 244 245 virtual 246 ~PB_DS_CLASS_NAME(); 247 248 void 249 swap(PB_DS_CLASS_C_DEC& other); 250 251 inline size_type 252 size() const; 253 254 inline size_type 255 max_size() const; 256 257 inline bool 258 empty() const; 259 260 Hash_Fn& 261 get_hash_fn(); 262 263 const Hash_Fn& 264 get_hash_fn() const; 265 266 Eq_Fn& 267 get_eq_fn(); 268 269 const Eq_Fn& 270 get_eq_fn() const; 271 272 Probe_Fn& 273 get_probe_fn(); 274 275 const Probe_Fn& 276 get_probe_fn() const; 277 278 Comb_Probe_Fn& 279 get_comb_probe_fn(); 280 281 const Comb_Probe_Fn& 282 get_comb_probe_fn() const; 283 284 Resize_Policy& 285 get_resize_policy(); 286 287 const Resize_Policy& 288 get_resize_policy() const; 289 290 inline std::pair<point_iterator, bool> 291 insert(const_reference r_val) 292 { 293 _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) 294 return insert_imp(r_val, traits_base::m_store_extra_indicator); 295 } 296 297 inline mapped_reference 298 operator[](const_key_reference r_key) 299 { 300#ifdef PB_DS_DATA_TRUE_INDICATOR 301 return subscript_imp(r_key, traits_base::m_store_extra_indicator); 302#else 303 insert(r_key); 304 return traits_base::s_null_mapped; 305#endif 306 } 307 308 inline point_iterator 309 find(const_key_reference r_key); 310 311 inline const_point_iterator 312 find(const_key_reference r_key) const; 313 314 inline point_iterator 315 find_end(); 316 317 inline const_point_iterator 318 find_end() const; 319 320 inline bool 321 erase(const_key_reference r_key); 322 323 template<typename Pred> 324 inline size_type 325 erase_if(Pred prd); 326 327 void 328 clear(); 329 330 inline iterator 331 begin(); 332 333 inline const_iterator 334 begin() const; 335 336 inline iterator 337 end(); 338 339 inline const_iterator 340 end() const; 341 342#ifdef _GLIBCXX_DEBUG 343 void 344 assert_valid() const; 345#endif 346 347#ifdef PB_DS_HT_MAP_TRACE_ 348 void 349 trace() const; 350#endif 351 352 private: 353#ifdef PB_DS_DATA_TRUE_INDICATOR 354 friend class iterator_; 355#endif 356 357 friend class const_iterator_; 358 359 void 360 deallocate_all(); 361 362 void 363 initialize(); 364 365 void 366 erase_all_valid_entries(entry_array, size_type); 367 368 inline bool 369 do_resize_if_needed(); 370 371 inline void 372 do_resize_if_needed_no_throw(); 373 374 void 375 resize_imp(size_type); 376 377 virtual void 378 do_resize(size_type); 379 380 void 381 resize_imp(entry_array, size_type); 382 383 inline void 384 resize_imp_reassign(entry_pointer, entry_array, false_type); 385 386 inline void 387 resize_imp_reassign(entry_pointer, entry_array, true_type); 388 389 inline size_type 390 find_ins_pos(const_key_reference, false_type); 391 392 inline comp_hash 393 find_ins_pos(const_key_reference, true_type); 394 395 inline std::pair<point_iterator, bool> 396 insert_imp(const_reference, false_type); 397 398 inline std::pair<point_iterator, bool> 399 insert_imp(const_reference, true_type); 400 401 inline pointer 402 insert_new_imp(const_reference r_val, size_type pos) 403 { 404 _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status); 405 406 if (do_resize_if_needed()) 407 pos = find_ins_pos(PB_DS_V2F(r_val), 408 traits_base::m_store_extra_indicator); 409 410 _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status); 411 412 entry* const p_e = m_entries + pos; 413 new (&p_e->m_value) value_type(r_val); 414 p_e->m_stat = valid_entry_status; 415 resize_base::notify_inserted(++m_num_used_e); 416 417 _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(p_e->m_value));) 418 419 _GLIBCXX_DEBUG_ONLY(assert_valid();) 420 return &p_e->m_value; 421 } 422 423 inline pointer 424 insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair) 425 { 426 _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat != 427 valid_entry_status); 428 429 if (do_resize_if_needed()) 430 r_pos_hash_pair = find_ins_pos(PB_DS_V2F(r_val), 431 traits_base::m_store_extra_indicator); 432 433 _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat != 434 valid_entry_status); 435 436 entry* const p_e = m_entries + r_pos_hash_pair.first; 437 new (&p_e->m_value) value_type(r_val); 438 p_e->m_hash = r_pos_hash_pair.second; 439 p_e->m_stat = valid_entry_status; 440 441 resize_base::notify_inserted(++m_num_used_e); 442 443 _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(p_e->m_value));) 444 445 _GLIBCXX_DEBUG_ONLY(assert_valid();) 446 return &p_e->m_value; 447 } 448 449#ifdef PB_DS_DATA_TRUE_INDICATOR 450 inline mapped_reference 451 subscript_imp(const_key_reference key, false_type) 452 { 453 _GLIBCXX_DEBUG_ONLY(assert_valid();) 454 455 const size_type pos = find_ins_pos(key, 456 traits_base::m_store_extra_indicator); 457 458 entry_pointer p_e = &m_entries[pos]; 459 if (p_e->m_stat != valid_entry_status) 460 return insert_new_imp(value_type(key, mapped_type()), pos)->second; 461 462 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(key);) 463 return p_e->m_value.second; 464 } 465 466 inline mapped_reference 467 subscript_imp(const_key_reference key, true_type) 468 { 469 _GLIBCXX_DEBUG_ONLY(assert_valid();) 470 471 comp_hash pos_hash_pair = 472 find_ins_pos(key, traits_base::m_store_extra_indicator); 473 474 if (m_entries[pos_hash_pair.first].m_stat != valid_entry_status) 475 return insert_new_imp(value_type(key, mapped_type()), 476 pos_hash_pair)->second; 477 478 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(key)); 479 return (m_entries + pos_hash_pair.first)->m_value.second; 480 } 481#endif 482 483 inline pointer 484 find_key_pointer(const_key_reference key, false_type) 485 { 486 const size_type hash = ranged_probe_fn_base::operator()(key); 487 size_type i; 488 resize_base::notify_find_search_start(); 489 490 // Loop until entry is found or until all possible entries accessed. 491 for (i = 0; i < m_num_e; ++i) 492 { 493 const size_type pos = ranged_probe_fn_base::operator()(key, hash, i); 494 495 entry* const p_e = m_entries + pos; 496 switch (p_e->m_stat) 497 { 498 case empty_entry_status: 499 { 500 resize_base::notify_find_search_end(); 501 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(key);) 502 503 return NULL; 504 } 505 break; 506 case valid_entry_status: 507 if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), key)) 508 { 509 resize_base::notify_find_search_end(); 510 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(key);) 511 512 return pointer(&p_e->m_value); 513 } 514 break; 515 case erased_entry_status: 516 break; 517 default: 518 _GLIBCXX_DEBUG_ASSERT(0); 519 }; 520 521 resize_base::notify_find_search_collision(); 522 } 523 524 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(key);) 525 resize_base::notify_find_search_end(); 526 return NULL; 527 } 528 529 inline pointer 530 find_key_pointer(const_key_reference key, true_type) 531 { 532 comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(key); 533 size_type i; 534 resize_base::notify_find_search_start(); 535 536 // Loop until entry is found or until all possible entries accessed. 537 for (i = 0; i < m_num_e; ++i) 538 { 539 const size_type pos = 540 ranged_probe_fn_base::operator()(key, pos_hash_pair.second, i); 541 542 entry* const p_e = m_entries + pos; 543 544 switch(p_e->m_stat) 545 { 546 case empty_entry_status: 547 { 548 resize_base::notify_find_search_end(); 549 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(key);) 550 551 return NULL; 552 } 553 break; 554 case valid_entry_status: 555 if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), 556 p_e->m_hash, 557 key, pos_hash_pair.second)) 558 { 559 resize_base::notify_find_search_end(); 560 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(key);) 561 return pointer(&p_e->m_value); 562 } 563 break; 564 case erased_entry_status: 565 break; 566 default: 567 _GLIBCXX_DEBUG_ASSERT(0); 568 }; 569 570 resize_base::notify_find_search_collision(); 571 } 572 573 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(key);) 574 resize_base::notify_find_search_end(); 575 return NULL; 576 } 577 578 inline bool 579 erase_imp(const_key_reference, true_type); 580 581 inline bool 582 erase_imp(const_key_reference, false_type); 583 584 inline void 585 erase_entry(entry_pointer p_e); 586 587#ifdef PB_DS_DATA_TRUE_INDICATOR 588 void 589 inc_it_state(pointer& r_p_value, size_type& r_pos) const 590 { inc_it_state((const_mapped_pointer& )r_p_value, r_pos); } 591#endif 592 593 void 594 inc_it_state(const_pointer& r_p_value, size_type& r_pos) const 595 { 596 _GLIBCXX_DEBUG_ASSERT(r_p_value != NULL); 597 for (++r_pos; r_pos < m_num_e; ++r_pos) 598 { 599 const_entry_pointer p_e =& m_entries[r_pos]; 600 if (p_e->m_stat == valid_entry_status) 601 { 602 r_p_value =& p_e->m_value; 603 return; 604 } 605 } 606 r_p_value = NULL; 607 } 608 609 void 610 get_start_it_state(const_pointer& r_p_value, size_type& r_pos) const 611 { 612 for (r_pos = 0; r_pos < m_num_e; ++r_pos) 613 { 614 const_entry_pointer p_e = &m_entries[r_pos]; 615 if (p_e->m_stat == valid_entry_status) 616 { 617 r_p_value = &p_e->m_value; 618 return; 619 } 620 } 621 r_p_value = NULL; 622 } 623 624 void 625 get_start_it_state(pointer& r_p_value, size_type& r_pos) 626 { 627 for (r_pos = 0; r_pos < m_num_e; ++r_pos) 628 { 629 entry_pointer p_e = &m_entries[r_pos]; 630 if (p_e->m_stat == valid_entry_status) 631 { 632 r_p_value = &p_e->m_value; 633 return; 634 } 635 } 636 r_p_value = NULL; 637 } 638 639#ifdef _GLIBCXX_DEBUG 640 void 641 assert_entry_array_valid(const entry_array, false_type) const; 642 643 void 644 assert_entry_array_valid(const entry_array, true_type) const; 645#endif 646 647 static entry_allocator s_entry_allocator; 648 static iterator s_end_it; 649 static const_iterator s_const_end_it; 650 651 size_type m_num_e; 652 size_type m_num_used_e; 653 entry_pointer m_entries; 654 655 enum 656 { 657 store_hash_ok = !Store_Hash 658 || !is_same<Hash_Fn, pb_ds::null_hash_fn>::value 659 }; 660 661 PB_DS_STATIC_ASSERT(sth, store_hash_ok); 662 }; 663 664#include <ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp> 665#include <ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp> 666#include <ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp> 667#include <ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp> 668#include <ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp> 669#include <ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp> 670#include <ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp> 671#include <ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp> 672#include <ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp> 673#include <ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp> 674 675#undef PB_DS_CLASS_T_DEC 676#undef PB_DS_CLASS_C_DEC 677#undef PB_DS_HASH_EQ_FN_C_DEC 678#undef PB_DS_RANGED_PROBE_FN_C_DEC 679#undef PB_DS_TYPES_TRAITS_C_DEC 680#undef PB_DS_MAP_DEBUG_BASE_C_DEC 681#undef PB_DS_CLASS_NAME 682#undef PB_DS_V2F 683#undef PB_DS_V2S 684#undef PB_DS_STATIC_ASSERT 685 686 } // namespace detail 687} // namespace pb_ds 688 689