1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2018 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 // You should have received a copy of the GNU General Public License 17 // along with this library; see the file COPYING3. If not see 18 // <http://www.gnu.org/licenses/>. 19 20 21 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 22 23 // Permission to use, copy, modify, sell, and distribute this software 24 // is hereby granted without fee, provided that the above copyright 25 // notice appears in all copies, and that both that copyright notice 26 // and this permission notice appear in supporting documentation. None 27 // of the above authors, nor IBM Haifa Research Laboratories, make any 28 // representation about the suitability of this software for any 29 // purpose. It is provided "as is" without express or implied 30 // warranty. 31 32 /** 33 * @file common_type.hpp 34 * Contains common types. 35 */ 36 37 #ifndef PB_DS_COMMON_TYPES_ASSOC_HPP 38 #define PB_DS_COMMON_TYPES_ASSOC_HPP 39 40 #include <ext/pb_ds/detail/type_utils.hpp> 41 #include <common_type/assoc/template_policy.hpp> 42 #include <ext/pb_ds/assoc_container.hpp> 43 44 namespace __gnu_pbds 45 { 46 namespace test 47 { 48 template<typename Key, 49 typename Data, 50 class Hash_Fn = typename __gnu_pbds::detail::default_hash_fn<Key>::type, 51 class Eq_Fn = std::equal_to<Key>, 52 typename _Alloc = std::allocator<std::pair<const Key, Data> > > 53 struct hash_common_types 54 { 55 private: 56 typedef typename _Alloc::size_type size_type; 57 58 typedef 59 __gnu_pbds::test::hash_load_check_resize_trigger_t_< 60 _Alloc, 61 1, 8, 62 1, 2, 63 false> 64 no_access_half_load_check_resize_trigger_policy; 65 66 typedef 67 __gnu_pbds::test::hash_load_check_resize_trigger_t_< 68 _Alloc, 69 1, 8, 70 1, 2, 71 true> 72 access_half_load_check_resize_trigger_policy; 73 74 typedef 75 __gnu_pbds::test::hash_load_check_resize_trigger_t_< 76 _Alloc, 77 1, 8, 78 1, 1, 79 false> 80 no_access_one_load_check_resize_trigger_policy; 81 82 typedef 83 __gnu_pbds::test::cc_hash_max_collision_check_resize_trigger_t_< 84 _Alloc, 85 1, 2, 86 false> 87 no_access_half_max_col_check_check_resize_trigger_policy; 88 89 typedef 90 __gnu_pbds::test::cc_hash_max_collision_check_resize_trigger_t_< 91 _Alloc, 92 1, 2, 93 true> 94 access_half_max_col_check_check_resize_trigger_policy; 95 96 typedef __gnu_pbds::test::linear_probe_fn_t_<Key, _Alloc> lin_p_t; 97 98 typedef __gnu_pbds::test::quadratic_probe_fn_t_<Key, _Alloc> quad_p_t; 99 100 typedef 101 typename __gnu_cxx::typelist::create4< 102 __gnu_pbds::detail::false_type, 103 __gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc>, 104 no_access_half_load_check_resize_trigger_policy, 105 __gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::type 106 performance_cc_policy0; 107 108 typedef 109 typename __gnu_cxx::typelist::create4< 110 __gnu_pbds::detail::false_type, 111 __gnu_pbds::test::direct_mod_range_hashing_t_<_Alloc>, 112 no_access_half_load_check_resize_trigger_policy, 113 __gnu_pbds::test::hash_prime_size_policy_t_>::type 114 performance_cc_policy1; 115 116 typedef 117 typename __gnu_cxx::typelist::create4< 118 __gnu_pbds::detail::false_type, 119 __gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc>, 120 no_access_one_load_check_resize_trigger_policy, 121 __gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::type 122 performance_cc_policy2; 123 124 typedef 125 typename __gnu_cxx::typelist::create4< 126 __gnu_pbds::detail::false_type, 127 __gnu_pbds::test::direct_mod_range_hashing_t_<_Alloc>, 128 no_access_one_load_check_resize_trigger_policy, 129 __gnu_pbds::test::hash_prime_size_policy_t_ >::type 130 performance_cc_policy3; 131 132 typedef 133 typename __gnu_cxx::typelist::create4< 134 __gnu_pbds::detail::true_type, 135 __gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc>, 136 no_access_half_load_check_resize_trigger_policy, 137 __gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::type 138 performance_cc_policy4; 139 140 typedef 141 typename __gnu_cxx::typelist::create4< 142 __gnu_pbds::detail::false_type, 143 __gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc>, 144 no_access_half_max_col_check_check_resize_trigger_policy, 145 __gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::type 146 performance_cc_policy5; 147 148 typedef 149 typename __gnu_cxx::typelist::create4< 150 __gnu_pbds::detail::false_type, 151 __gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc>, 152 access_half_max_col_check_check_resize_trigger_policy, 153 __gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::type 154 regression_cc_policy0; 155 156 typedef 157 typename __gnu_cxx::typelist::create4< 158 __gnu_pbds::detail::false_type, 159 __gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc>, 160 access_half_load_check_resize_trigger_policy, 161 __gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::type 162 regression_cc_policy1; 163 164 typedef 165 typename __gnu_cxx::typelist::create4< 166 __gnu_pbds::detail::true_type, 167 __gnu_pbds::test::direct_mod_range_hashing_t_<_Alloc>, 168 no_access_half_load_check_resize_trigger_policy, 169 __gnu_pbds::test::hash_prime_size_policy_t_>::type 170 regression_cc_policy2; 171 172 typedef 173 typename __gnu_cxx::typelist::create5< 174 __gnu_pbds::detail::false_type, 175 lin_p_t, 176 __gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc>, 177 no_access_half_load_check_resize_trigger_policy, 178 __gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::type 179 performance_gp_policy0; 180 181 typedef 182 typename __gnu_cxx::typelist::create5< 183 __gnu_pbds::detail::false_type, 184 quad_p_t, 185 __gnu_pbds::test::direct_mod_range_hashing_t_<_Alloc>, 186 no_access_half_load_check_resize_trigger_policy, 187 __gnu_pbds::test::hash_prime_size_policy_t_ >::type 188 performance_gp_policy1; 189 190 typedef 191 typename __gnu_cxx::typelist::create5< 192 __gnu_pbds::detail::false_type, 193 quad_p_t, 194 __gnu_pbds::test::direct_mod_range_hashing_t_<_Alloc>, 195 access_half_load_check_resize_trigger_policy, 196 __gnu_pbds::test::hash_prime_size_policy_t_>::type 197 regression_gp_policy0; 198 199 typedef 200 typename __gnu_cxx::typelist::create5< 201 __gnu_pbds::detail::true_type, 202 lin_p_t, 203 __gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc>, 204 access_half_load_check_resize_trigger_policy, 205 __gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::type 206 regression_gp_policy1; 207 208 typedef 209 typename __gnu_cxx::typelist::create6< 210 performance_cc_policy0, 211 performance_cc_policy1, 212 performance_cc_policy2, 213 performance_cc_policy3, 214 performance_cc_policy4, 215 performance_cc_policy5>::type 216 performance_cc_range_hashing_policies; 217 218 typedef 219 typename __gnu_cxx::typelist::create3< 220 regression_cc_policy0, 221 regression_cc_policy1, 222 regression_cc_policy2>::type 223 regression_cc_range_hashing_policies; 224 225 typedef 226 typename __gnu_cxx::typelist::create2< 227 performance_gp_policy0, 228 performance_gp_policy1>::type 229 performance_gp_range_hashing_policies; 230 231 typedef 232 typename __gnu_cxx::typelist::create2< 233 regression_gp_policy0, 234 regression_gp_policy1>::type 235 regression_gp_range_hashing_policies; 236 237 template<typename Policy_Tl> 238 struct no_access_generic_cc_hash_table_t 239 { 240 private: 241 typedef 242 typename __gnu_cxx::typelist::at_index<Policy_Tl, 0>::type 243 store_hash_indicator; 244 245 enum 246 { 247 store_hash = store_hash_indicator::value 248 }; 249 250 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 1>::type 251 comb_hash_fn; 252 253 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 2>::type 254 trigger_policy; 255 256 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 3>::type 257 size_policy; 258 259 public: 260 typedef 261 __gnu_pbds::cc_hash_table< 262 Key, 263 Data, 264 Hash_Fn, 265 Eq_Fn, 266 comb_hash_fn, 267 __gnu_pbds::hash_standard_resize_policy<size_policy, trigger_policy, 268 false>, 269 store_hash, 270 _Alloc> 271 type; 272 }; 273 274 template<typename Policy_Tl> 275 struct access_generic_cc_hash_table_t 276 { 277 private: 278 typedef 279 typename __gnu_cxx::typelist::at_index<Policy_Tl, 0>::type 280 store_hash_indicator; 281 282 enum 283 { 284 store_hash = store_hash_indicator::value 285 }; 286 287 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 1>::type 288 comb_hash_fn; 289 290 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 2>::type 291 trigger_policy; 292 293 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 3>::type 294 size_policy; 295 296 public: 297 typedef 298 __gnu_pbds::cc_hash_table< 299 Key, 300 Data, 301 Hash_Fn, 302 Eq_Fn, 303 comb_hash_fn, 304 __gnu_pbds::hash_standard_resize_policy<size_policy, trigger_policy, 305 true>, 306 store_hash, 307 _Alloc> 308 type; 309 }; 310 311 template<typename Policy_Tl> 312 struct no_access_generic_gp_hash_table_t 313 { 314 private: 315 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 0>::type 316 store_hash_indicator; 317 318 enum 319 { 320 store_hash = store_hash_indicator::value 321 }; 322 323 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 1>::type 324 probe_fn; 325 326 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 2>::type 327 comb_probe_fn; 328 329 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 3>::type 330 trigger_policy; 331 332 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 4>::type 333 size_policy; 334 335 public: 336 typedef 337 __gnu_pbds::gp_hash_table< 338 Key, 339 Data, 340 Hash_Fn, 341 Eq_Fn, 342 comb_probe_fn, 343 probe_fn, 344 __gnu_pbds::hash_standard_resize_policy<size_policy, trigger_policy, 345 false>, 346 store_hash, 347 _Alloc> 348 type; 349 }; 350 351 template<typename Policy_Tl> 352 struct access_generic_gp_hash_table_t 353 { 354 private: 355 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 0>::type 356 store_hash_indicator; 357 358 enum 359 { 360 store_hash = store_hash_indicator::value 361 }; 362 363 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 1>::type 364 probe_fn; 365 366 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 2>::type 367 comb_probe_fn; 368 369 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 3>::type 370 trigger_policy; 371 372 typedef typename __gnu_cxx::typelist::at_index<Policy_Tl, 4>::type 373 size_policy; 374 375 public: 376 typedef 377 __gnu_pbds::gp_hash_table< 378 Key, 379 Data, 380 Hash_Fn, 381 Eq_Fn, 382 comb_probe_fn, 383 probe_fn, 384 __gnu_pbds::hash_standard_resize_policy<size_policy, trigger_policy, 385 true>, 386 store_hash, 387 _Alloc> 388 type; 389 }; 390 391 typedef 392 typename __gnu_cxx::typelist::transform< 393 performance_cc_range_hashing_policies, 394 no_access_generic_cc_hash_table_t>::type 395 performance_cc_types; 396 397 typedef 398 typename __gnu_cxx::typelist::transform< 399 regression_cc_range_hashing_policies, 400 access_generic_cc_hash_table_t>::type 401 regression_cc_types; 402 403 typedef 404 typename __gnu_cxx::typelist::at_index< 405 performance_cc_types, 406 0>::type 407 performance_min_cc_type; 408 409 typedef 410 typename __gnu_cxx::typelist::transform< 411 performance_gp_range_hashing_policies, 412 no_access_generic_gp_hash_table_t>::type 413 performance_gp_types; 414 415 typedef 416 typename __gnu_cxx::typelist::transform< 417 regression_gp_range_hashing_policies, 418 access_generic_gp_hash_table_t>::type 419 regression_gp_types; 420 421 typedef 422 typename __gnu_cxx::typelist::at_index< 423 performance_gp_types, 424 0>::type 425 performance_min_gp_type; 426 427 public: 428 typedef 429 typename __gnu_cxx::typelist::append< 430 performance_cc_types, 431 performance_gp_types>::type 432 performance_tl; 433 434 typedef 435 typename __gnu_cxx::typelist::append< 436 regression_gp_types, 437 regression_cc_types>::type 438 regression_tl; 439 440 typedef 441 typename __gnu_cxx::typelist::create1< 442 performance_min_cc_type>::type 443 performance_min_tl; 444 }; 445 446 template<typename Key, 447 typename Data, 448 class Comb_Hash_Fn_TL, 449 class Comb_Probe_Fn_TL, 450 class Eq_Fn = 451 std::equal_to<Key>, 452 typename _Alloc = std::allocator<std::pair<const Key, Data> > > 453 struct ranged_hash_common_types 454 { 455 private: 456 typedef typename _Alloc::size_type size_type; 457 458 typedef 459 __gnu_pbds::test::hash_load_check_resize_trigger_t_< 460 _Alloc, 461 1, 8, 462 1, 2, 463 false> 464 no_access_half_load_check_resize_trigger_policy; 465 466 typedef 467 __gnu_pbds::test::hash_load_check_resize_trigger_t_< 468 _Alloc, 469 1, 8, 470 1, 1, 471 false> 472 no_access_one_load_check_resize_trigger_policy; 473 474 typedef 475 __gnu_pbds::hash_standard_resize_policy< 476 __gnu_pbds::test::hash_exponential_size_policy_t_< 477 _Alloc>, 478 no_access_half_load_check_resize_trigger_policy> 479 mask_half_resize_policy_t; 480 481 typedef 482 __gnu_pbds::hash_standard_resize_policy< 483 __gnu_pbds::test::hash_exponential_size_policy_t_< 484 _Alloc>, 485 no_access_one_load_check_resize_trigger_policy> 486 mask_one_resize_policy_t; 487 488 typedef 489 __gnu_pbds::hash_standard_resize_policy< 490 __gnu_pbds::test::hash_prime_size_policy_t_, 491 no_access_half_load_check_resize_trigger_policy> 492 mod_half_resize_policy_t; 493 494 typedef 495 __gnu_pbds::hash_standard_resize_policy< 496 __gnu_pbds::test::hash_prime_size_policy_t_, 497 no_access_one_load_check_resize_trigger_policy> 498 mod_one_resize_policy_t; 499 500 template<typename Comb_Hash_Fn_> 501 struct half_resize_policy_selector; 502 503 template<typename _Alloc_> 504 struct half_resize_policy_selector<__gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc_> > 505 { 506 typedef mask_half_resize_policy_t type; 507 }; 508 509 template<typename _Alloc_> 510 struct half_resize_policy_selector<__gnu_pbds::test::direct_mod_range_hashing_t_<_Alloc_> > 511 { 512 typedef mod_half_resize_policy_t type; 513 }; 514 515 template<typename Comb_Hash_Fn_> 516 struct one_resize_policy_selector; 517 518 template<typename _Alloc_> 519 struct one_resize_policy_selector<__gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc_> > 520 { 521 typedef mask_one_resize_policy_t type; 522 }; 523 524 template<typename _Alloc_> 525 struct one_resize_policy_selector<__gnu_pbds::test::direct_mod_range_hashing_t_<_Alloc_> > 526 { 527 typedef mod_one_resize_policy_t type; 528 }; 529 530 template<typename Comb_Hash_Fn> 531 struct generic_cc_hash_table_t 532 { 533 typedef 534 __gnu_pbds::cc_hash_table< 535 Key, 536 Data, 537 __gnu_pbds::null_type, 538 Eq_Fn, 539 Comb_Hash_Fn, 540 typename one_resize_policy_selector<typename Comb_Hash_Fn::comb_fn>::type, 541 false, _Alloc> 542 type; 543 }; 544 545 typedef 546 typename __gnu_cxx::typelist::transform< 547 Comb_Hash_Fn_TL, 548 generic_cc_hash_table_t>::type 549 performance_cc_types; 550 551 template<typename Comb_Probe_Fn> 552 struct no_access_generic_gp_hash_table_t 553 { 554 typedef 555 __gnu_pbds::gp_hash_table< 556 Key, 557 Data, 558 __gnu_pbds::null_type, 559 Eq_Fn, 560 Comb_Probe_Fn, 561 __gnu_pbds::null_type, 562 typename half_resize_policy_selector<typename Comb_Probe_Fn::comb_fn>::type, 563 false, 564 _Alloc> 565 type; 566 }; 567 568 typedef 569 typename __gnu_cxx::typelist::transform< 570 Comb_Probe_Fn_TL, 571 no_access_generic_gp_hash_table_t>::type 572 performance_gp_types; 573 574 public: 575 typedef 576 typename __gnu_cxx::typelist::append< 577 performance_cc_types, 578 performance_gp_types>::type 579 performance_tl; 580 }; 581 582 template<typename Key, typename Data, class Eq_Fn = std::equal_to<Key>, 583 typename _Alloc = std::allocator<char> > 584 class lu_common_types 585 { 586 private: 587 typedef typename _Alloc::size_type size_type; 588 589 typedef __gnu_pbds::test::lu_move_to_front_policy_t_ mtf_u; 590 591 typedef __gnu_pbds::test::lu_counter_policy_t_<_Alloc, 5> cnt_5_u; 592 593 typedef typename __gnu_cxx::typelist::create1<mtf_u>::type lu_policy0; 594 595 typedef typename __gnu_cxx::typelist::create1<cnt_5_u>::type lu_policy1; 596 597 typedef 598 typename __gnu_cxx::typelist::create2<lu_policy0, lu_policy1>::type 599 lu_policies; 600 601 template<typename Policy_Tl> 602 struct generic_list_update_t 603 { 604 private: 605 typedef 606 typename __gnu_cxx::typelist::at_index<Policy_Tl, 0>::type 607 update_policy_t; 608 609 public: 610 typedef 611 __gnu_pbds::list_update<Key, Data, Eq_Fn, update_policy_t, _Alloc> 612 type; 613 }; 614 615 typedef 616 typename __gnu_cxx::typelist::transform<lu_policies, 617 generic_list_update_t>::type 618 lu_types; 619 620 typedef 621 typename __gnu_cxx::typelist::at_index<lu_types, 0>::type 622 min_lu_type; 623 624 public: 625 typedef lu_types performance_tl; 626 typedef lu_types regression_tl; 627 628 typedef typename __gnu_cxx::typelist::create1<min_lu_type>::type performance_min_tl; 629 }; 630 631 template<typename Key, typename Data, class Cmp_Fn = std::less<Key>, 632 template<typename Node_CItr, 633 class Node_Itr, 634 class Cmp_Fn_, 635 typename _Alloc_> 636 class Node_Update = __gnu_pbds::null_node_update, 637 typename _Alloc = std::allocator<std::pair<const Key, Data> > > 638 struct tree_common_types 639 { 640 private: 641 typedef 642 __gnu_pbds::tree< 643 Key, 644 Data, 645 Cmp_Fn, 646 __gnu_pbds::ov_tree_tag, 647 Node_Update, 648 _Alloc> 649 ov_tree_assoc_container_t; 650 651 typedef 652 __gnu_pbds::tree< 653 Key, 654 Data, 655 Cmp_Fn, 656 __gnu_pbds::rb_tree_tag, 657 Node_Update, 658 _Alloc> 659 rb_tree_assoc_container_t; 660 661 typedef 662 __gnu_pbds::tree< 663 Key, 664 Data, 665 Cmp_Fn, 666 __gnu_pbds::splay_tree_tag, 667 Node_Update, 668 _Alloc> 669 splay_tree_assoc_container_t; 670 671 public: 672 typedef 673 typename __gnu_cxx::typelist::create3< 674 splay_tree_assoc_container_t, 675 rb_tree_assoc_container_t, 676 ov_tree_assoc_container_t>::type 677 performance_tl; 678 679 typedef 680 typename __gnu_cxx::typelist::create3< 681 ov_tree_assoc_container_t, 682 splay_tree_assoc_container_t, 683 rb_tree_assoc_container_t>::type 684 regression_tl; 685 686 typedef 687 typename __gnu_cxx::typelist::create1< 688 rb_tree_assoc_container_t>::type 689 performance_min_tl; 690 }; 691 692 template<typename Key, 693 typename Data, 694 class _ATraits = 695 typename __gnu_pbds::detail::default_trie_access_traits<Key>::type, 696 class Tag = __gnu_pbds::pat_trie_tag, 697 template<typename Node_CItr, 698 typename Node_Itr, 699 class _ATraits_, 700 typename _Alloc_> 701 class Node_Update = __gnu_pbds::null_node_update, 702 typename _Alloc = std::allocator<char> > 703 class trie_common_types 704 { 705 private: 706 typedef __gnu_pbds::trie<Key, Data, _ATraits, Tag, Node_Update, _Alloc> type; 707 708 public: 709 typedef typename __gnu_cxx::typelist::create1<type>::type performance_tl; 710 typedef typename __gnu_cxx::typelist::create1<type>::type regression_tl; 711 typedef typename __gnu_cxx::typelist::create1<type>::type performance_min_tl; 712 }; 713 714 } // namespace test 715 } // namespace __gnu_pbds 716 717 #endif // #ifndef PB_DS_COMMON_TYPES_ASSOC_HPP 718