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