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 63namespace 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> 283 insert(const_reference r_val) 284 { return insert_imp(r_val, traits_base::m_store_extra_indicator); } 285 286 inline mapped_reference 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 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 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 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 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 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 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 536 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 544 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 566 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