1// -*- C++ -*- 2 3// Copyright (C) 2005 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 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 2, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 31 32// Permission to use, copy, modify, sell, and distribute this software 33// is hereby granted without fee, provided that the above copyright 34// notice appears in all copies, and that both that copyright notice and 35// this permission notice appear in supporting documentation. None of 36// the above authors, nor IBM Haifa Research Laboratories, make any 37// representation about the suitability of this software for any 38// purpose. It is provided "as is" without express or implied warranty. 39 40/** 41 * @file cc_ht_map_.hpp 42 * Contains an implementation class for cc_ht_map_. 43 */ 44 45#include <utility> 46#include <iterator> 47#include <ext/pb_assoc/detail/cond_dealtor.hpp> 48#include <ext/pb_assoc/trivial_iterator_def.hpp> 49#include <ext/pb_assoc/detail/hash_fn/ranged_hash_fn.hpp> 50#include <ext/pb_assoc/detail/hash_types_traits.hpp> 51#include <ext/pb_assoc/detail/types_traits.hpp> 52#include <ext/pb_assoc/exception.hpp> 53#include <ext/pb_assoc/detail/map_debug_base.hpp> 54#include <ext/pb_assoc/detail/eq_fn/hash_eq_fn.hpp> 55 56namespace pb_assoc 57{ 58 59 namespace detail 60 { 61 62#ifdef PB_ASSOC_CC_HT_MAP_DEBUG 63#define PB_ASSOC_DBG_ASSERT(X) assert(X) 64#define PB_ASSOC_DBG_VERIFY(X) assert(X) 65#define PB_ASSOC_DBG_ONLY(X) X 66#else // #ifdef PB_ASSOC_CC_HT_MAP_DEBUG 67#define PB_ASSOC_DBG_ASSERT(X) 68#define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);} 69#define PB_ASSOC_DBG_ONLY(X) ; 70#endif // #ifdef PB_ASSOC_CC_HT_MAP_DEBUG 71 72#define PB_ASSOC_CLASS_T_DEC \ 73 template< \ 74 typename Key, \ 75 typename Data, \ 76 class Hash_Fn, \ 77 class Eq_Fn, \ 78 class Allocator, \ 79 bool Store_Hash, \ 80 class Comb_Hash_Fn, \ 81 class Resize_Policy> 82 83#ifdef PB_ASSOC_DATA_TRUE_INDICATOR 84#define PB_ASSOC_CLASS_NAME \ 85 cc_ht_map_data_ 86#endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR 87 88#ifdef PB_ASSOC_DATA_FALSE_INDICATOR 89#define PB_ASSOC_CLASS_NAME \ 90 cc_ht_map_no_data_ 91#endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR 92 93#define PB_ASSOC_CLASS_C_DEC \ 94 PB_ASSOC_CLASS_NAME< \ 95 Key, \ 96 Data, \ 97 Hash_Fn, \ 98 Eq_Fn, \ 99 Allocator, \ 100 Store_Hash, \ 101 Comb_Hash_Fn, \ 102 Resize_Policy > 103 104#define PB_ASSOC_HASH_EQ_FN_C_DEC \ 105 pb_assoc::detail::hash_eq_fn< \ 106 Key, \ 107 Eq_Fn, \ 108 Allocator, \ 109 Store_Hash> 110 111#define PB_ASSOC_RANGED_HASH_FN_C_DEC \ 112 pb_assoc::detail::ranged_hash_fn< \ 113 Key, \ 114 Hash_Fn, \ 115 Allocator, \ 116 Comb_Hash_Fn, \ 117 Store_Hash> 118 119#define PB_ASSOC_TYPES_TRAITS_C_DEC \ 120 types_traits< \ 121 Key, \ 122 Data, \ 123 Allocator> 124 125#define PB_ASSOC_HASH_TYPES_TRAITS_C_DEC \ 126 hash_types_traits< \ 127 typename Allocator::size_type, \ 128 Store_Hash> 129 130#ifdef PB_ASSOC_USE_MAP_DEBUG_BASE 131#define PB_ASSOC_MAP_DEBUG_BASE_C_DEC \ 132 pb_assoc::detail::map_debug_base< \ 133 Key, \ 134 Eq_Fn> 135#endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE 136 137#ifdef PB_ASSOC_DATA_TRUE_INDICATOR 138#define PB_ASSOC_V2F(X) (X).first 139#define PB_ASSOC_V2S(X) (X).second 140#endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR 141 142#ifdef PB_ASSOC_DATA_FALSE_INDICATOR 143#define PB_ASSOC_V2F(X) (X) 144#define PB_ASSOC_V2S(X) Mapped_Data() 145#endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR 146 147#define PB_ASSOC_STATIC_ASSERT(UNIQUE, E) \ 148 typedef \ 149 pb_assoc::detail::static_assert_dummy_class< \ 150 sizeof(pb_assoc::detail::static_assert<(bool)(E)>)> \ 151 UNIQUE##static_assert_type 152 153 template<typename Key, 154 typename Data, 155 class Hash_Fn, 156 class Eq_Fn, 157 class Allocator, 158 bool Store_Hash, 159 class Comb_Hash_Fn, 160 class Resize_Policy > 161 class PB_ASSOC_CLASS_NAME: 162#ifdef PB_ASSOC_CC_HT_MAP_DEBUG 163 protected PB_ASSOC_MAP_DEBUG_BASE_C_DEC, 164#endif // #ifdef PB_ASSOC_CC_HT_MAP_DEBUG 165 public PB_ASSOC_HASH_EQ_FN_C_DEC, 166 public Resize_Policy, 167 public PB_ASSOC_RANGED_HASH_FN_C_DEC, 168 public PB_ASSOC_TYPES_TRAITS_C_DEC, 169 public PB_ASSOC_HASH_TYPES_TRAITS_C_DEC 170 { 171 172 public: 173 174 typedef typename Allocator::size_type size_type; 175 176 typedef 177 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_key_reference 178 const_key_reference; 179 180 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_type data_type; 181 182 typedef 183 typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_reference 184 data_reference; 185 186 typedef 187 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_data_reference 188 const_data_reference; 189 190 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type value_type; 191 192 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::pointer pointer; 193 194 typedef 195 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_pointer 196 const_pointer; 197 198 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::reference reference; 199 200 typedef 201 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_reference 202 const_reference; 203 204 protected: 205 206 typedef typename PB_ASSOC_HASH_TYPES_TRAITS_C_DEC::comp_hash comp_hash; 207 208 struct no_store_hash_entry 209 { 210 value_type m_value; 211 212 typename Allocator::template rebind< 213 no_store_hash_entry>::other::pointer m_p_next; 214 }; 215 216 struct store_hash_entry 217 { 218 value_type m_value; 219 220 size_type m_hash; 221 222 typename Allocator::template rebind< 223 store_hash_entry>::other::pointer m_p_next; 224 }; 225 226 typedef 227 typename cond_type< 228 Store_Hash, 229 store_hash_entry, 230 no_store_hash_entry>::type 231 entry; 232 233 typedef 234 typename Allocator::template rebind<entry>::other 235 entry_allocator; 236 237 typedef typename entry_allocator::pointer entry_pointer; 238 239 typedef typename entry_allocator::const_pointer const_entry_pointer; 240 241 typedef typename entry_allocator::reference entry_reference; 242 243 typedef 244 typename entry_allocator::const_reference 245 const_entry_reference; 246 247 typedef 248 typename Allocator::template rebind<entry_pointer>::other 249 entry_pointer_allocator; 250 251 typedef typename entry_pointer_allocator::pointer entry_pointer_array; 252 253 typedef value_type mapped_value_type; 254 255 typedef pointer mapped_pointer; 256 257 typedef const_pointer const_mapped_pointer; 258 259 typedef reference mapped_reference; 260 261 typedef const_reference const_mapped_reference; 262 263#define PB_ASSOC_GEN_POS std::pair<entry_pointer, size_type> 264 265#include <ext/pb_assoc/detail/unordered_iterator/const_find_iterator.hpp> 266#include <ext/pb_assoc/detail/unordered_iterator/find_iterator.hpp> 267#include <ext/pb_assoc/detail/unordered_iterator/const_iterator.hpp> 268#include <ext/pb_assoc/detail/unordered_iterator/iterator.hpp> 269 270#undef PB_ASSOC_GEN_POS 271 272 typedef find_iterator_ find_iterator; 273 274 typedef const_find_iterator_ const_find_iterator; 275 276 typedef iterator_ iterator; 277 278 typedef const_iterator_ const_iterator; 279 280 typedef Hash_Fn hash_fn; 281 282 typedef Eq_Fn eq_fn; 283 284 typedef Allocator allocator; 285 286 typedef Resize_Policy resize_policy; 287 288 protected: 289 290 PB_ASSOC_CLASS_NAME(); 291 292 PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn); 293 294 PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn); 295 296 PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Hash_Fn& r_comb_hash_fn); 297 298 PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Hash_Fn& r_comb_hash_fn, const Resize_Policy& r_resize_policy); 299 300 PB_ASSOC_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other); 301 302 virtual 303 ~PB_ASSOC_CLASS_NAME(); 304 305 void 306 swap(PB_ASSOC_CLASS_C_DEC& r_other); 307 308 template<class It> 309 void 310 copy_from_range(It first_it, It last_it); 311 312 inline size_type 313 size() const; 314 315 inline size_type 316 max_size() const; 317 318 inline bool 319 empty() const; 320 321 Hash_Fn& 322 get_hash_fn(); 323 324 const Hash_Fn& 325 get_hash_fn() const; 326 327 Eq_Fn& 328 get_eq_fn(); 329 330 const Eq_Fn& 331 get_eq_fn() const; 332 333 Comb_Hash_Fn& 334 get_comb_hash_fn(); 335 336 const Comb_Hash_Fn& 337 get_comb_hash_fn() const; 338 339 Resize_Policy& 340 get_resize_policy(); 341 342 const Resize_Policy& 343 get_resize_policy() const; 344 345 inline std::pair<find_iterator, bool> 346 insert(const_reference r_val); 347 348 inline data_reference 349 subscript_imp(const_key_reference r_key); 350 351 inline find_iterator 352 find(const_key_reference r_key); 353 354 inline const_find_iterator 355 find(const_key_reference r_key) const; 356 357 inline find_iterator 358 find_end(); 359 360 inline const_find_iterator 361 find_end() const; 362 363 template<class T> 364 inline size_type 365 erase(T r_t, bool erase_entry_if_last, pb_assoc::detail::int_to_type<false>); 366 367 template<class T> 368 inline size_type 369 erase(T r_t, bool erase_entry_if_last, pb_assoc::detail::int_to_type<true>); 370 371 template<class Pred> 372 inline size_type 373 erase_if(Pred& r_pred); 374 375 void 376 clear(); 377 378 inline iterator 379 begin(); 380 381 inline const_iterator 382 begin() const; 383 384 inline iterator 385 end(); 386 387 inline const_iterator 388 end() const; 389 390#ifdef PB_ASSOC_CC_HT_MAP_DEBUG 391 392 virtual void 393 assert_valid() const; 394 395#endif // #ifdef PB_ASSOC_CC_HT_MAP_DEBUG 396 397 virtual void 398 do_resize(size_type new_size); 399 400 private: 401 402 typedef PB_ASSOC_TYPES_TRAITS_C_DEC my_traits_base; 403 404 typedef PB_ASSOC_HASH_TYPES_TRAITS_C_DEC my_hash_traits_base; 405 406 typedef PB_ASSOC_RANGED_HASH_FN_C_DEC my_ranged_hash_fn_base; 407 408 typedef PB_ASSOC_HASH_EQ_FN_C_DEC my_hash_eq_fn_base; 409 410 typedef Resize_Policy my_resize_base; 411 412#ifdef PB_ASSOC_USE_MAP_DEBUG_BASE 413 typedef PB_ASSOC_MAP_DEBUG_BASE_C_DEC my_map_debug_base; 414#endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE 415 416 private: 417 418 inline bool 419 do_resize_if_needed(); 420 421 inline void 422 do_resize_if_needed_no_throw(); 423 424 void 425 resize_imp_no_exceptions(size_type new_size, entry_pointer_array a_p_entries_resized, size_type old_size); 426 427 inline entry_pointer 428 resize_imp_no_exceptions_reassign_pointer(entry_pointer p_e, entry_pointer_array a_p_entries_resized, int_to_type<false>); 429 430 inline entry_pointer 431 resize_imp_no_exceptions_reassign_pointer(entry_pointer p_e, entry_pointer_array a_p_entries_resized, int_to_type<true>); 432 433 template<class For_Each_Fn> 434 void 435 do_for_each(For_Each_Fn fn); 436 437 void 438 deallocate_links_in_list(entry_pointer p_e); 439 440 inline entry_pointer 441 get_entry(const_reference r_val, int_to_type<false>); 442 443 inline entry_pointer 444 get_entry(const_reference r_val, int_to_type<true>); 445 446 inline void 447 rels_entry(entry_pointer p_e); 448 449 void 450 constructor_insert_new_imp(const_reference r_val, size_type pos, int_to_type<false>); 451 452 void 453 constructor_insert_new_imp(const_reference r_val, size_type pos, int_to_type<true>); 454 455 void 456 deallocate_all(); 457 458 inline data_reference 459 subscript_imp(const_key_reference r_key, int_to_type<false>); 460 461 inline data_reference 462 subscript_imp(const_key_reference r_key, int_to_type<true>); 463 464 inline std::pair<find_iterator, bool> 465 insert_imp(const_reference r_val, int_to_type<false>); 466 467 inline std::pair<find_iterator, bool> 468 insert_imp(const_reference r_val, int_to_type<true>); 469 470 inline pointer 471 insert_new_imp(const_reference r_val, size_type pos); 472 473 inline pointer 474 insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair); 475 476 inline const_data_reference 477 const_subscript_imp(const_key_reference r_key, int_to_type<false>) const; 478 479 inline const_data_reference 480 const_subscript_imp(const_key_reference r_key, int_to_type<true>) const; 481 482 inline pointer 483 find_key_pointer(const_key_reference r_key, int_to_type<false>); 484 485 inline pointer 486 find_key_pointer(const_key_reference r_key, int_to_type<true>); 487 488 template<class T> 489 inline size_type 490 erase_in_pos_imp(T r_t, bool erase_entry_if_last, size_type pos); 491 492 template<class T> 493 inline size_type 494 erase_in_pos_imp(T r_t, bool erase_entry_if_last, const comp_hash& r_pos_hash_pair); 495 496 inline void 497 erase_entry_pointer(entry_pointer& r_p_e); 498 499#ifdef PB_ASSOC_DATA_TRUE_INDICATOR 500 void 501 inc_it_state(pointer& r_p_value, std::pair<entry_pointer, size_type>& r_pos) const; 502#endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR 503 504 void 505 inc_it_state(const_pointer& r_p_value, std::pair<entry_pointer, size_type>& r_pos) const; 506 507 void 508 get_start_it_state(pointer& r_p_value, std::pair<entry_pointer, size_type>& r_pos) const; 509 510#ifdef PB_ASSOC_CC_HT_MAP_DEBUG 511 512 void 513 assert_entry_pointer_array_valid(const entry_pointer_array a_p_entries) const; 514 515 void 516 assert_entry_pointer_valid(const entry_pointer p_e, store_hash_true_indicator) const; 517 518 void 519 assert_entry_pointer_valid(const entry_pointer p_e, store_hash_false_indicator) const; 520 521#endif // #ifdef PB_ASSOC_CC_HT_MAP_DEBUG 522 523 private: 524 static entry_allocator s_entry_allocator; 525 526 static entry_pointer_allocator s_entry_pointer_allocator; 527 528 typedef 529 pb_assoc::detail::cond_dealtor< 530 entry, 531 Allocator> 532 cond_dealtor_t; 533 534 entry_pointer_array m_a_p_entries; 535 536 size_type m_num_e_p; 537 538 size_type m_num_used_e; 539 540 friend class iterator_; 541 542 friend class const_iterator_; 543 544 static iterator s_end_it; 545 546 static const_iterator s_const_end_it; 547 548 static find_iterator s_find_end_it; 549 550 static const_find_iterator s_const_find_end_it; 551 552 enum 553 { 554 store_hash_ok = 555 !Store_Hash || 556 !pb_assoc::detail::is_same_type< 557 Hash_Fn, 558 pb_assoc::null_hash_fn>::value 559 }; 560 561 PB_ASSOC_STATIC_ASSERT(sth, store_hash_ok); 562 }; 563 564#include <ext/pb_assoc/detail/cc_ht_map_/constructor_destructor_fn_imps.hpp> 565#include <ext/pb_assoc/detail/cc_ht_map_/entry_list_fn_imps.hpp> 566#include <ext/pb_assoc/detail/cc_ht_map_/find_fn_imps.hpp> 567#include <ext/pb_assoc/detail/cc_ht_map_/resize_fn_imps.hpp> 568#include <ext/pb_assoc/detail/cc_ht_map_/debug_fn_imps.hpp> 569#include <ext/pb_assoc/detail/cc_ht_map_/size_fn_imps.hpp> 570#include <ext/pb_assoc/detail/cc_ht_map_/policy_access_fn_imps.hpp> 571#include <ext/pb_assoc/detail/cc_ht_map_/erase_fn_imps.hpp> 572#include <ext/pb_assoc/detail/cc_ht_map_/iterators_fn_imps.hpp> 573#include <ext/pb_assoc/detail/cc_ht_map_/insert_fn_imps.hpp> 574 575#undef PB_ASSOC_CLASS_T_DEC 576 577#undef PB_ASSOC_CLASS_C_DEC 578 579#undef PB_ASSOC_HASH_EQ_FN_C_DEC 580 581#undef PB_ASSOC_RANGED_HASH_FN_C_DEC 582 583#undef PB_ASSOC_TYPES_TRAITS_C_DEC 584 585#undef PB_ASSOC_HASH_TYPES_TRAITS_C_DEC 586 587#undef PB_ASSOC_MAP_DEBUG_BASE_C_DEC 588 589#undef PB_ASSOC_CLASS_NAME 590 591#undef PB_ASSOC_V2F 592#undef PB_ASSOC_V2S 593 594#undef PB_ASSOC_DBG_ASSERT 595#undef PB_ASSOC_DBG_VERIFY 596#undef PB_ASSOC_DBG_ONLY 597 598#undef PB_ASSOC_STATIC_ASSERT 599 600 } // namespace detail 601 602} // namespace pb_assoc 603