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

   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 common_type.hpp
  44  * Contains common types.
  45  */
  46
  47 #ifndef PB_DS_COMMON_TYPES_HPP
  48 #define PB_DS_COMMON_TYPES_HPP
  49
  50 #include <ext/pb_ds/detail/type_utils.hpp>
  51 #include <common_type/assoc/template_policy.hpp>
  52 #include <ext/pb_ds/assoc_container.hpp>
  53
  54 namespace pb_ds
  55 {
  56
  57   namespace test
  58   {
  59
  60     template<typename Key,
  61              typename Data,
  62              class Hash_Fn =
  63              typename pb_ds::detail::default_hash_fn<
  64       Key>::type,
  65              class Eq_Fn =
  66              std::equal_to<Key>,
  67              class Allocator =
  68              std::allocator<std::pair<const Key, Data> > >
  69     struct hash_common_types
  70     {
  71     private:
  72       typedef typename Allocator::size_type size_type;
  73
  74       typedef
  75       pb_ds::test::hash_load_check_resize_trigger_t_<
  76         Allocator,
  77         1, 8,
  78         1, 2,
  79         false>
  80       no_access_half_load_check_resize_trigger_policy;
  81
  82       typedef
  83       pb_ds::test::hash_load_check_resize_trigger_t_<
  84         Allocator,
  85         1, 8,
  86         1, 2,
  87         true>
  88       access_half_load_check_resize_trigger_policy;
  89
  90       typedef
  91       pb_ds::test::hash_load_check_resize_trigger_t_<
  92         Allocator,
  93         1, 8,
  94         1, 1,
  95         false>
  96       no_access_one_load_check_resize_trigger_policy;
  97
  98       typedef
  99       pb_ds::test::cc_hash_max_collision_check_resize_trigger_t_<
 100         Allocator,
 101         1, 2,
 102         false>
 103       no_access_half_max_col_check_check_resize_trigger_policy;
 104
 105       typedef
 106       pb_ds::test::cc_hash_max_collision_check_resize_trigger_t_<
 107         Allocator,
 108         1, 2,
 109         true>
 110       access_half_max_col_check_check_resize_trigger_policy;
 111
 112       typedef pb_ds::test::linear_probe_fn_t_<Key, Allocator> lin_p_t;
 113
 114       typedef pb_ds::test::quadratic_probe_fn_t_<Key, Allocator> quad_p_t;
 115
 116       typedef
 117       typename __gnu_cxx::typelist::create4<
 118         pb_ds::detail::false_type,
 119         pb_ds::test::direct_mask_range_hashing_t_<
 120         Allocator>,
 121         no_access_half_load_check_resize_trigger_policy,
 122         pb_ds::test::hash_exponential_size_policy_t_<
 123         Allocator> >::type
 124       performance_cc_policy0;
 125
 126       typedef
 127       typename __gnu_cxx::typelist::create4<
 128         pb_ds::detail::false_type,
 129         pb_ds::test::direct_mod_range_hashing_t_<
 130         Allocator>,
 131         no_access_half_load_check_resize_trigger_policy,
 132         pb_ds::test::hash_prime_size_policy_t_>::type
 133       performance_cc_policy1;
 134
 135       typedef
 136       typename __gnu_cxx::typelist::create4<
 137         pb_ds::detail::false_type,
 138         pb_ds::test::direct_mask_range_hashing_t_<
 139         Allocator>,
 140         no_access_one_load_check_resize_trigger_policy,
 141         pb_ds::test::hash_exponential_size_policy_t_<
 142         Allocator> >::type
 143       performance_cc_policy2;
 144
 145       typedef
 146       typename __gnu_cxx::typelist::create4<
 147         pb_ds::detail::false_type,
 148         pb_ds::test::direct_mod_range_hashing_t_<
 149         Allocator>,
 150         no_access_one_load_check_resize_trigger_policy,
 151         pb_ds::test::hash_prime_size_policy_t_ >::type
 152       performance_cc_policy3;
 153
 154       typedef
 155       typename __gnu_cxx::typelist::create4<
 156         pb_ds::detail::true_type,
 157         pb_ds::test::direct_mask_range_hashing_t_<
 158         Allocator>,
 159         no_access_half_load_check_resize_trigger_policy,
 160         pb_ds::test::hash_exponential_size_policy_t_<
 161         Allocator> >::type
 162       performance_cc_policy4;
 163
 164       typedef
 165       typename __gnu_cxx::typelist::create4<
 166         pb_ds::detail::false_type,
 167         pb_ds::test::direct_mask_range_hashing_t_<
 168         Allocator>,
 169         no_access_half_max_col_check_check_resize_trigger_policy,
 170         pb_ds::test::hash_exponential_size_policy_t_<
 171         Allocator> >::type
 172       performance_cc_policy5;
 173
 174       typedef
 175       typename __gnu_cxx::typelist::create4<
 176         pb_ds::detail::false_type,
 177         pb_ds::test::direct_mask_range_hashing_t_<
 178         Allocator>,
 179         access_half_max_col_check_check_resize_trigger_policy,
 180         pb_ds::test::hash_exponential_size_policy_t_<
 181         Allocator> >::type
 182       regression_cc_policy0;
 183
 184       typedef
 185       typename __gnu_cxx::typelist::create4<
 186         pb_ds::detail::false_type,
 187         pb_ds::test::direct_mask_range_hashing_t_<
 188         Allocator>,
 189         access_half_load_check_resize_trigger_policy,
 190         pb_ds::test::hash_exponential_size_policy_t_<
 191         Allocator> >::type
 192       regression_cc_policy1;
 193
 194       typedef
 195       typename __gnu_cxx::typelist::create4<
 196         pb_ds::detail::true_type,
 197         pb_ds::test::direct_mod_range_hashing_t_<
 198         Allocator>,
 199         no_access_half_load_check_resize_trigger_policy,
 200         pb_ds::test::hash_prime_size_policy_t_ >::type
 201       regression_cc_policy2;
 202
 203       typedef
 204       typename __gnu_cxx::typelist::create5<
 205         pb_ds::detail::false_type,
 206         lin_p_t,
 207         pb_ds::test::direct_mask_range_hashing_t_<
 208         Allocator>,
 209         no_access_half_load_check_resize_trigger_policy,
 210         pb_ds::test::hash_exponential_size_policy_t_<
 211         Allocator> >::type
 212       performance_gp_policy0;
 213
 214       typedef
 215       typename __gnu_cxx::typelist::create5<
 216         pb_ds::detail::false_type,
 217         quad_p_t,
 218         pb_ds::test::direct_mod_range_hashing_t_<
 219         Allocator>,
 220         no_access_half_load_check_resize_trigger_policy,
 221         pb_ds::test::hash_prime_size_policy_t_ >::type
 222       performance_gp_policy1;
 223
 224       typedef
 225       typename __gnu_cxx::typelist::create5<
 226         pb_ds::detail::false_type,
 227         quad_p_t,
 228         pb_ds::test::direct_mod_range_hashing_t_<
 229         Allocator>,
 230         access_half_load_check_resize_trigger_policy,
 231         pb_ds::test::hash_prime_size_policy_t_>::type
 232       regression_gp_policy0;
 233
 234       typedef
 235       typename __gnu_cxx::typelist::create5<
 236         pb_ds::detail::true_type,
 237         lin_p_t,
 238         pb_ds::test::direct_mask_range_hashing_t_<
 239         Allocator>,
 240         access_half_load_check_resize_trigger_policy,
 241         pb_ds::test::hash_exponential_size_policy_t_<
 242         Allocator> >::type
 243       regression_gp_policy1;
 244
 245       typedef
 246       typename __gnu_cxx::typelist::create6<
 247         performance_cc_policy0,
 248         performance_cc_policy1,
 249         performance_cc_policy2,
 250         performance_cc_policy3,
 251         performance_cc_policy4,
 252         performance_cc_policy5>::type
 253       performance_cc_range_hashing_policies;
 254
 255       typedef
 256       typename __gnu_cxx::typelist::create3<
 257         regression_cc_policy0,
 258         regression_cc_policy1,
 259         regression_cc_policy2>::type
 260       regression_cc_range_hashing_policies;
 261
 262       typedef
 263       typename __gnu_cxx::typelist::create2<
 264         performance_gp_policy0,
 265         performance_gp_policy1>::type
 266       performance_gp_range_hashing_policies;
 267
 268       typedef
 269       typename __gnu_cxx::typelist::create2<
 270         regression_gp_policy0,
 271         regression_gp_policy1>::type
 272       regression_gp_range_hashing_policies;
 273
 274       template<typename Policy_Tl>
 275       struct no_access_generic_cc_hash_table_t
 276       {
 277       private:
 278         typedef
 279         typename __gnu_cxx::typelist::at_index<
 280         Policy_Tl, 0>::type
 281         store_hash_indicator;
 282
 283         enum
 284           {
 285             store_hash = store_hash_indicator::value
 286           };
 287
 288         typedef
 289         typename __gnu_cxx::typelist::at_index<
 290           Policy_Tl, 1>::type
 291         comb_hash_fn;
 292
 293         typedef
 294         typename __gnu_cxx::typelist::at_index<
 295           Policy_Tl, 2>::type
 296         trigger_policy;
 297
 298         typedef
 299         typename __gnu_cxx::typelist::at_index<
 300           Policy_Tl, 3>::type
 301         size_policy;
 302
 303       public:
 304         typedef
 305         pb_ds::cc_hash_table<
 306         Key,
 307         Data,
 308         Hash_Fn,
 309         Eq_Fn,
 310         comb_hash_fn,
 311         pb_ds::hash_standard_resize_policy<
 312         size_policy,
 313         trigger_policy,
 314         false>,
 315         store_hash,
 316         Allocator>
 317         type;
 318       };
 319
 320       template<typename Policy_Tl>
 321       struct access_generic_cc_hash_table_t
 322       {
 323       private:
 324         typedef
 325         typename __gnu_cxx::typelist::at_index<
 326         Policy_Tl, 0>::type
 327         store_hash_indicator;
 328
 329         enum
 330           {
 331             store_hash = store_hash_indicator::value
 332           };
 333
 334         typedef
 335         typename __gnu_cxx::typelist::at_index<
 336           Policy_Tl, 1>::type
 337         comb_hash_fn;
 338
 339         typedef
 340         typename __gnu_cxx::typelist::at_index<
 341           Policy_Tl, 2>::type
 342         trigger_policy;
 343
 344         typedef
 345         typename __gnu_cxx::typelist::at_index<
 346           Policy_Tl, 3>::type
 347         size_policy;
 348
 349       public:
 350         typedef
 351         pb_ds::cc_hash_table<
 352         Key,
 353         Data,
 354         Hash_Fn,
 355         Eq_Fn,
 356         comb_hash_fn,
 357         pb_ds::hash_standard_resize_policy<
 358         size_policy,
 359         trigger_policy,
 360         true>,
 361         store_hash,
 362         Allocator>
 363         type;
 364       };
 365
 366       template<typename Policy_Tl>
 367       struct no_access_generic_gp_hash_table_t
 368       {
 369       private:
 370         typedef
 371         typename __gnu_cxx::typelist::at_index<
 372         Policy_Tl, 0>::type
 373         store_hash_indicator;
 374
 375         enum
 376           {
 377             store_hash = store_hash_indicator::value
 378           };
 379
 380         typedef
 381         typename __gnu_cxx::typelist::at_index<
 382           Policy_Tl, 1>::type
 383         probe_fn;
 384
 385         typedef
 386         typename __gnu_cxx::typelist::at_index<
 387           Policy_Tl, 2>::type
 388         comb_probe_fn;
 389
 390         typedef
 391         typename __gnu_cxx::typelist::at_index<
 392           Policy_Tl, 3>::type
 393         trigger_policy;
 394
 395         typedef
 396         typename __gnu_cxx::typelist::at_index<
 397           Policy_Tl, 4>::type
 398         size_policy;
 399
 400       public:
 401         typedef
 402         pb_ds::gp_hash_table<
 403         Key,
 404         Data,
 405         Hash_Fn,
 406         Eq_Fn,
 407         comb_probe_fn,
 408         probe_fn,
 409         pb_ds::hash_standard_resize_policy<
 410         size_policy,
 411         trigger_policy,
 412         false>,
 413         store_hash,
 414         Allocator>
 415         type;
 416       };
 417
 418       template<typename Policy_Tl>
 419       struct access_generic_gp_hash_table_t
 420       {
 421       private:
 422         typedef
 423         typename __gnu_cxx::typelist::at_index<
 424         Policy_Tl, 0>::type
 425         store_hash_indicator;
 426
 427         enum
 428           {
 429             store_hash = store_hash_indicator::value
 430           };
 431
 432         typedef
 433         typename __gnu_cxx::typelist::at_index<
 434           Policy_Tl, 1>::type
 435         probe_fn;
 436
 437         typedef
 438         typename __gnu_cxx::typelist::at_index<
 439           Policy_Tl, 2>::type
 440         comb_probe_fn;
 441
 442         typedef
 443         typename __gnu_cxx::typelist::at_index<
 444           Policy_Tl, 3>::type
 445         trigger_policy;
 446
 447         typedef
 448         typename __gnu_cxx::typelist::at_index<
 449           Policy_Tl, 4>::type
 450         size_policy;
 451
 452       public:
 453         typedef
 454         pb_ds::gp_hash_table<
 455         Key,
 456         Data,
 457         Hash_Fn,
 458         Eq_Fn,
 459         comb_probe_fn,
 460         probe_fn,
 461         pb_ds::hash_standard_resize_policy<
 462         size_policy,
 463         trigger_policy,
 464         true>,
 465         store_hash,
 466         Allocator>
 467         type;
 468       };
 469
 470       typedef
 471       typename __gnu_cxx::typelist::transform<
 472         performance_cc_range_hashing_policies,
 473         no_access_generic_cc_hash_table_t>::type
 474       performance_cc_types;
 475
 476       typedef
 477       typename __gnu_cxx::typelist::transform<
 478         regression_cc_range_hashing_policies,
 479         access_generic_cc_hash_table_t>::type
 480       regression_cc_types;
 481
 482       typedef
 483       typename __gnu_cxx::typelist::at_index<
 484         performance_cc_types,
 485         0>::type
 486       performance_min_cc_type;
 487
 488       typedef
 489       typename __gnu_cxx::typelist::transform<
 490         performance_gp_range_hashing_policies,
 491         no_access_generic_gp_hash_table_t>::type
 492       performance_gp_types;
 493
 494       typedef
 495       typename __gnu_cxx::typelist::transform<
 496         regression_gp_range_hashing_policies,
 497         access_generic_gp_hash_table_t>::type
 498       regression_gp_types;
 499
 500       typedef
 501       typename __gnu_cxx::typelist::at_index<
 502         performance_gp_types,
 503         0>::type
 504       performance_min_gp_type;
 505
 506     public:
 507       typedef
 508       typename __gnu_cxx::typelist::append<
 509       performance_cc_types,
 510       performance_gp_types>::type
 511       performance_tl;
 512
 513       typedef
 514       typename __gnu_cxx::typelist::append<
 515         regression_gp_types,
 516         regression_cc_types>::type
 517       regression_tl;
 518
 519       typedef
 520       typename __gnu_cxx::typelist::create1<
 521         performance_min_cc_type>::type
 522       performance_min_tl;
 523     };
 524
 525     template<typename Key,
 526              typename Data,
 527              class Comb_Hash_Fn_TL,
 528              class Comb_Probe_Fn_TL,
 529              class Eq_Fn =
 530              std::equal_to<Key>,
 531              class Allocator =
 532              std::allocator<
 533       std::pair<
 534       const Key,
 535       Data> > >
 536     struct ranged_hash_common_types
 537     {
 538     private:
 539       typedef typename Allocator::size_type size_type;
 540
 541       typedef
 542       pb_ds::test::hash_load_check_resize_trigger_t_<
 543         Allocator,
 544         1, 8,
 545         1, 2,
 546         false>
 547       no_access_half_load_check_resize_trigger_policy;
 548
 549       typedef
 550       pb_ds::test::hash_load_check_resize_trigger_t_<
 551         Allocator,
 552         1, 8,
 553         1, 1,
 554         false>
 555       no_access_one_load_check_resize_trigger_policy;
 556
 557       typedef
 558       pb_ds::hash_standard_resize_policy<
 559         pb_ds::test::hash_exponential_size_policy_t_<
 560         Allocator>,
 561         no_access_half_load_check_resize_trigger_policy>
 562       mask_half_resize_policy_t;
 563
 564       typedef
 565       pb_ds::hash_standard_resize_policy<
 566         pb_ds::test::hash_exponential_size_policy_t_<
 567         Allocator>,
 568         no_access_one_load_check_resize_trigger_policy>
 569       mask_one_resize_policy_t;
 570
 571       typedef
 572       pb_ds::hash_standard_resize_policy<
 573         pb_ds::test::hash_prime_size_policy_t_,
 574         no_access_half_load_check_resize_trigger_policy>
 575       mod_half_resize_policy_t;
 576
 577       typedef
 578       pb_ds::hash_standard_resize_policy<
 579         pb_ds::test::hash_prime_size_policy_t_,
 580         no_access_one_load_check_resize_trigger_policy>
 581       mod_one_resize_policy_t;
 582
 583       template<typename Comb_Hash_Fn_>
 584       struct half_resize_policy_selector;
 585
 586       template<typename Allocator_>
 587       struct half_resize_policy_selector<
 588         pb_ds::test::direct_mask_range_hashing_t_<
 589         Allocator_> >
 590       {
 591         typedef mask_half_resize_policy_t type;
 592       };
 593
 594       template<typename Allocator_>
 595       struct half_resize_policy_selector<
 596         pb_ds::test::direct_mod_range_hashing_t_<
 597         Allocator_> >
 598       {
 599         typedef mod_half_resize_policy_t type;
 600       };
 601
 602       template<typename Comb_Hash_Fn_>
 603       struct one_resize_policy_selector;
 604
 605       template<typename Allocator_>
 606       struct one_resize_policy_selector<
 607         pb_ds::test::direct_mask_range_hashing_t_<
 608         Allocator_> >
 609       {
 610         typedef mask_one_resize_policy_t type;
 611       };
 612
 613       template<typename Allocator_>
 614       struct one_resize_policy_selector<
 615         pb_ds::test::direct_mod_range_hashing_t_<
 616         Allocator_> >
 617       {
 618         typedef mod_one_resize_policy_t type;
 619       };
 620
 621       template<typename Comb_Hash_Fn>
 622       struct generic_cc_hash_table_t
 623       {
 624         typedef
 625         pb_ds::cc_hash_table<
 626           Key,
 627           Data,
 628           pb_ds::null_hash_fn,
 629           Eq_Fn,
 630           Comb_Hash_Fn,
 631           typename one_resize_policy_selector<
 632           typename Comb_Hash_Fn::comb_fn>::type,
 633           false,
 634           Allocator>
 635         type;
 636       };
 637
 638       typedef
 639       typename __gnu_cxx::typelist::transform<
 640         Comb_Hash_Fn_TL,
 641         generic_cc_hash_table_t>::type
 642       performance_cc_types;
 643
 644       template<typename Comb_Probe_Fn>
 645       struct no_access_generic_gp_hash_table_t
 646       {
 647         typedef
 648         pb_ds::gp_hash_table<
 649           Key,
 650           Data,
 651           pb_ds::null_hash_fn,
 652           Eq_Fn,
 653           Comb_Probe_Fn,
 654           pb_ds::null_probe_fn,
 655           typename half_resize_policy_selector<
 656           typename Comb_Probe_Fn::comb_fn>::type,
 657           false,
 658           Allocator>
 659         type;
 660       };
 661
 662       typedef
 663       typename __gnu_cxx::typelist::transform<
 664         Comb_Probe_Fn_TL,
 665         no_access_generic_gp_hash_table_t>::type
 666       performance_gp_types;
 667
 668     public:
 669       typedef
 670       typename __gnu_cxx::typelist::append<
 671       performance_cc_types,
 672       performance_gp_types>::type
 673       performance_tl;
 674     };
 675
 676     template<typename Key, typename Data, class Eq_Fn = std::equal_to<Key>,
 677              class Allocator =
 678              std::allocator<char> >
 679     class lu_common_types
 680     {
 681     private:
 682       typedef typename Allocator::size_type size_type;
 683
 684       typedef pb_ds::test::move_to_front_lu_policy_t_ mtf_u;
 685
 686       typedef pb_ds::test::counter_lu_policy_t_<Allocator, 5> cnt_5_u;
 687
 688       typedef typename __gnu_cxx::typelist::create1<mtf_u>::type lu_policy0;
 689
 690       typedef typename __gnu_cxx::typelist::create1<cnt_5_u>::type lu_policy1;
 691
 692       typedef
 693       typename __gnu_cxx::typelist::create2<
 694         lu_policy0,
 695         lu_policy1>::type
 696       lu_policies;
 697
 698       template<typename Policy_Tl>
 699       struct generic_list_update_t
 700       {
 701       private:
 702         typedef
 703         typename __gnu_cxx::typelist::at_index<
 704         Policy_Tl, 0>::type
 705         update_policy_t;
 706
 707       public:
 708         typedef
 709         pb_ds::list_update<
 710         Key,
 711         Data,
 712         Eq_Fn,
 713         update_policy_t,
 714         Allocator>
 715         type;
 716       };
 717
 718       typedef
 719       typename __gnu_cxx::typelist::transform<
 720         lu_policies,
 721         generic_list_update_t>::type
 722       lu_types;
 723
 724       typedef
 725       typename __gnu_cxx::typelist::at_index<
 726         lu_types,
 727         0>::type
 728       min_lu_type;
 729
 730     public:
 731       typedef lu_types performance_tl;
 732       typedef lu_types regression_tl;
 733
 734       typedef typename __gnu_cxx::typelist::create1<min_lu_type>::type performance_min_tl;
 735     };
 736
 737     template<typename Key, typename Data, class Cmp_Fn = std::less<Key>,
 738              template<typename Const_Node_Iterator,
 739                       class Node_Iterator,
 740                       class Cmp_Fn_,
 741                       class Allocator_>
 742     class Node_Update = pb_ds::null_tree_node_update,
 743              class Allocator = std::allocator<std::pair<const Key, Data> > >
 744     struct tree_common_types
 745     {
 746     private:
 747       typedef
 748       pb_ds::tree<
 749       Key,
 750       Data,
 751       Cmp_Fn,
 752       pb_ds::ov_tree_tag,
 753       Node_Update,
 754       Allocator>
 755       ov_tree_assoc_container_t;
 756
 757       typedef
 758       pb_ds::tree<
 759         Key,
 760         Data,
 761         Cmp_Fn,
 762         pb_ds::rb_tree_tag,
 763         Node_Update,
 764         Allocator>
 765       rb_tree_assoc_container_t;
 766
 767       typedef
 768       pb_ds::tree<
 769         Key,
 770         Data,
 771         Cmp_Fn,
 772         pb_ds::splay_tree_tag,
 773         Node_Update,
 774         Allocator>
 775       splay_tree_assoc_container_t;
 776
 777     public:
 778       typedef
 779       typename __gnu_cxx::typelist::create3<
 780       splay_tree_assoc_container_t,
 781       rb_tree_assoc_container_t,
 782       ov_tree_assoc_container_t>::type
 783       performance_tl;
 784
 785       typedef
 786       typename __gnu_cxx::typelist::create3<
 787         ov_tree_assoc_container_t,
 788         splay_tree_assoc_container_t,
 789         rb_tree_assoc_container_t>::type
 790       regression_tl;
 791
 792       typedef
 793       typename __gnu_cxx::typelist::create1<
 794         rb_tree_assoc_container_t>::type
 795       performance_min_tl;
 796     };
 797
 798     template<typename Key,
 799              typename Data,
 800              class E_Access_Traits =
 801              typename pb_ds::detail::default_trie_e_access_traits<Key>::type,
 802              class Tag = pb_ds::pat_trie_tag,
 803              template<typename Const_Node_Iterator,
 804                       typename Node_Iterator,
 805                       class E_Access_Traits_,
 806                       typename Allocator_>
 807     class Node_Update = pb_ds::null_trie_node_update,
 808              class Allocator = std::allocator<char> >
 809     class trie_common_types
 810     {
 811     private:
 812       typedef pb_ds::trie<Key, Data, E_Access_Traits, Tag, Node_Update, Allocator> type;
 813
 814     public:
 815       typedef typename __gnu_cxx::typelist::create1<type>::type performance_tl;
 816       typedef typename __gnu_cxx::typelist::create1<type>::type regression_tl;
 817       typedef typename __gnu_cxx::typelist::create1<type>::type performance_min_tl;
 818     };
 819
 820   } // namespace test
 821
 822 } // namespace pb_ds
 823
 824 #endif // #ifndef PB_DS_COMMON_TYPES_HPP