libstdc++-v3/testsuite/util/common_type/assoc/common_type.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2020 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