// -*- C++ -*- // Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 3, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING3. If not see // . // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file common_type.hpp * Contains common types. */ #ifndef PB_DS_COMMON_TYPES_ASSOC_HPP #define PB_DS_COMMON_TYPES_ASSOC_HPP #include #include #include namespace __gnu_pbds { namespace test { template::type, class Eq_Fn = std::equal_to, class Allocator = std::allocator > > struct hash_common_types { private: typedef typename Allocator::size_type size_type; typedef __gnu_pbds::test::hash_load_check_resize_trigger_t_< Allocator, 1, 8, 1, 2, false> no_access_half_load_check_resize_trigger_policy; typedef __gnu_pbds::test::hash_load_check_resize_trigger_t_< Allocator, 1, 8, 1, 2, true> access_half_load_check_resize_trigger_policy; typedef __gnu_pbds::test::hash_load_check_resize_trigger_t_< Allocator, 1, 8, 1, 1, false> no_access_one_load_check_resize_trigger_policy; typedef __gnu_pbds::test::cc_hash_max_collision_check_resize_trigger_t_< Allocator, 1, 2, false> no_access_half_max_col_check_check_resize_trigger_policy; typedef __gnu_pbds::test::cc_hash_max_collision_check_resize_trigger_t_< Allocator, 1, 2, true> access_half_max_col_check_check_resize_trigger_policy; typedef __gnu_pbds::test::linear_probe_fn_t_ lin_p_t; typedef __gnu_pbds::test::quadratic_probe_fn_t_ quad_p_t; typedef typename __gnu_cxx::typelist::create4< __gnu_pbds::detail::false_type, __gnu_pbds::test::direct_mask_range_hashing_t_< Allocator>, no_access_half_load_check_resize_trigger_policy, __gnu_pbds::test::hash_exponential_size_policy_t_< Allocator> >::type performance_cc_policy0; typedef typename __gnu_cxx::typelist::create4< __gnu_pbds::detail::false_type, __gnu_pbds::test::direct_mod_range_hashing_t_< Allocator>, no_access_half_load_check_resize_trigger_policy, __gnu_pbds::test::hash_prime_size_policy_t_>::type performance_cc_policy1; typedef typename __gnu_cxx::typelist::create4< __gnu_pbds::detail::false_type, __gnu_pbds::test::direct_mask_range_hashing_t_< Allocator>, no_access_one_load_check_resize_trigger_policy, __gnu_pbds::test::hash_exponential_size_policy_t_< Allocator> >::type performance_cc_policy2; typedef typename __gnu_cxx::typelist::create4< __gnu_pbds::detail::false_type, __gnu_pbds::test::direct_mod_range_hashing_t_< Allocator>, no_access_one_load_check_resize_trigger_policy, __gnu_pbds::test::hash_prime_size_policy_t_ >::type performance_cc_policy3; typedef typename __gnu_cxx::typelist::create4< __gnu_pbds::detail::true_type, __gnu_pbds::test::direct_mask_range_hashing_t_< Allocator>, no_access_half_load_check_resize_trigger_policy, __gnu_pbds::test::hash_exponential_size_policy_t_< Allocator> >::type performance_cc_policy4; typedef typename __gnu_cxx::typelist::create4< __gnu_pbds::detail::false_type, __gnu_pbds::test::direct_mask_range_hashing_t_< Allocator>, no_access_half_max_col_check_check_resize_trigger_policy, __gnu_pbds::test::hash_exponential_size_policy_t_< Allocator> >::type performance_cc_policy5; typedef typename __gnu_cxx::typelist::create4< __gnu_pbds::detail::false_type, __gnu_pbds::test::direct_mask_range_hashing_t_< Allocator>, access_half_max_col_check_check_resize_trigger_policy, __gnu_pbds::test::hash_exponential_size_policy_t_< Allocator> >::type regression_cc_policy0; typedef typename __gnu_cxx::typelist::create4< __gnu_pbds::detail::false_type, __gnu_pbds::test::direct_mask_range_hashing_t_< Allocator>, access_half_load_check_resize_trigger_policy, __gnu_pbds::test::hash_exponential_size_policy_t_< Allocator> >::type regression_cc_policy1; typedef typename __gnu_cxx::typelist::create4< __gnu_pbds::detail::true_type, __gnu_pbds::test::direct_mod_range_hashing_t_< Allocator>, no_access_half_load_check_resize_trigger_policy, __gnu_pbds::test::hash_prime_size_policy_t_ >::type regression_cc_policy2; typedef typename __gnu_cxx::typelist::create5< __gnu_pbds::detail::false_type, lin_p_t, __gnu_pbds::test::direct_mask_range_hashing_t_< Allocator>, no_access_half_load_check_resize_trigger_policy, __gnu_pbds::test::hash_exponential_size_policy_t_< Allocator> >::type performance_gp_policy0; typedef typename __gnu_cxx::typelist::create5< __gnu_pbds::detail::false_type, quad_p_t, __gnu_pbds::test::direct_mod_range_hashing_t_< Allocator>, no_access_half_load_check_resize_trigger_policy, __gnu_pbds::test::hash_prime_size_policy_t_ >::type performance_gp_policy1; typedef typename __gnu_cxx::typelist::create5< __gnu_pbds::detail::false_type, quad_p_t, __gnu_pbds::test::direct_mod_range_hashing_t_< Allocator>, access_half_load_check_resize_trigger_policy, __gnu_pbds::test::hash_prime_size_policy_t_>::type regression_gp_policy0; typedef typename __gnu_cxx::typelist::create5< __gnu_pbds::detail::true_type, lin_p_t, __gnu_pbds::test::direct_mask_range_hashing_t_< Allocator>, access_half_load_check_resize_trigger_policy, __gnu_pbds::test::hash_exponential_size_policy_t_< Allocator> >::type regression_gp_policy1; typedef typename __gnu_cxx::typelist::create6< performance_cc_policy0, performance_cc_policy1, performance_cc_policy2, performance_cc_policy3, performance_cc_policy4, performance_cc_policy5>::type performance_cc_range_hashing_policies; typedef typename __gnu_cxx::typelist::create3< regression_cc_policy0, regression_cc_policy1, regression_cc_policy2>::type regression_cc_range_hashing_policies; typedef typename __gnu_cxx::typelist::create2< performance_gp_policy0, performance_gp_policy1>::type performance_gp_range_hashing_policies; typedef typename __gnu_cxx::typelist::create2< regression_gp_policy0, regression_gp_policy1>::type regression_gp_range_hashing_policies; template struct no_access_generic_cc_hash_table_t { private: typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 0>::type store_hash_indicator; enum { store_hash = store_hash_indicator::value }; typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 1>::type comb_hash_fn; typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 2>::type trigger_policy; typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 3>::type size_policy; public: typedef __gnu_pbds::cc_hash_table< Key, Data, Hash_Fn, Eq_Fn, comb_hash_fn, __gnu_pbds::hash_standard_resize_policy< size_policy, trigger_policy, false>, store_hash, Allocator> type; }; template struct access_generic_cc_hash_table_t { private: typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 0>::type store_hash_indicator; enum { store_hash = store_hash_indicator::value }; typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 1>::type comb_hash_fn; typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 2>::type trigger_policy; typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 3>::type size_policy; public: typedef __gnu_pbds::cc_hash_table< Key, Data, Hash_Fn, Eq_Fn, comb_hash_fn, __gnu_pbds::hash_standard_resize_policy< size_policy, trigger_policy, true>, store_hash, Allocator> type; }; template struct no_access_generic_gp_hash_table_t { private: typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 0>::type store_hash_indicator; enum { store_hash = store_hash_indicator::value }; typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 1>::type probe_fn; typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 2>::type comb_probe_fn; typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 3>::type trigger_policy; typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 4>::type size_policy; public: typedef __gnu_pbds::gp_hash_table< Key, Data, Hash_Fn, Eq_Fn, comb_probe_fn, probe_fn, __gnu_pbds::hash_standard_resize_policy< size_policy, trigger_policy, false>, store_hash, Allocator> type; }; template struct access_generic_gp_hash_table_t { private: typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 0>::type store_hash_indicator; enum { store_hash = store_hash_indicator::value }; typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 1>::type probe_fn; typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 2>::type comb_probe_fn; typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 3>::type trigger_policy; typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 4>::type size_policy; public: typedef __gnu_pbds::gp_hash_table< Key, Data, Hash_Fn, Eq_Fn, comb_probe_fn, probe_fn, __gnu_pbds::hash_standard_resize_policy< size_policy, trigger_policy, true>, store_hash, Allocator> type; }; typedef typename __gnu_cxx::typelist::transform< performance_cc_range_hashing_policies, no_access_generic_cc_hash_table_t>::type performance_cc_types; typedef typename __gnu_cxx::typelist::transform< regression_cc_range_hashing_policies, access_generic_cc_hash_table_t>::type regression_cc_types; typedef typename __gnu_cxx::typelist::at_index< performance_cc_types, 0>::type performance_min_cc_type; typedef typename __gnu_cxx::typelist::transform< performance_gp_range_hashing_policies, no_access_generic_gp_hash_table_t>::type performance_gp_types; typedef typename __gnu_cxx::typelist::transform< regression_gp_range_hashing_policies, access_generic_gp_hash_table_t>::type regression_gp_types; typedef typename __gnu_cxx::typelist::at_index< performance_gp_types, 0>::type performance_min_gp_type; public: typedef typename __gnu_cxx::typelist::append< performance_cc_types, performance_gp_types>::type performance_tl; typedef typename __gnu_cxx::typelist::append< regression_gp_types, regression_cc_types>::type regression_tl; typedef typename __gnu_cxx::typelist::create1< performance_min_cc_type>::type performance_min_tl; }; template, class Allocator = std::allocator< std::pair< const Key, Data> > > struct ranged_hash_common_types { private: typedef typename Allocator::size_type size_type; typedef __gnu_pbds::test::hash_load_check_resize_trigger_t_< Allocator, 1, 8, 1, 2, false> no_access_half_load_check_resize_trigger_policy; typedef __gnu_pbds::test::hash_load_check_resize_trigger_t_< Allocator, 1, 8, 1, 1, false> no_access_one_load_check_resize_trigger_policy; typedef __gnu_pbds::hash_standard_resize_policy< __gnu_pbds::test::hash_exponential_size_policy_t_< Allocator>, no_access_half_load_check_resize_trigger_policy> mask_half_resize_policy_t; typedef __gnu_pbds::hash_standard_resize_policy< __gnu_pbds::test::hash_exponential_size_policy_t_< Allocator>, no_access_one_load_check_resize_trigger_policy> mask_one_resize_policy_t; typedef __gnu_pbds::hash_standard_resize_policy< __gnu_pbds::test::hash_prime_size_policy_t_, no_access_half_load_check_resize_trigger_policy> mod_half_resize_policy_t; typedef __gnu_pbds::hash_standard_resize_policy< __gnu_pbds::test::hash_prime_size_policy_t_, no_access_one_load_check_resize_trigger_policy> mod_one_resize_policy_t; template struct half_resize_policy_selector; template struct half_resize_policy_selector< __gnu_pbds::test::direct_mask_range_hashing_t_< Allocator_> > { typedef mask_half_resize_policy_t type; }; template struct half_resize_policy_selector< __gnu_pbds::test::direct_mod_range_hashing_t_< Allocator_> > { typedef mod_half_resize_policy_t type; }; template struct one_resize_policy_selector; template struct one_resize_policy_selector< __gnu_pbds::test::direct_mask_range_hashing_t_< Allocator_> > { typedef mask_one_resize_policy_t type; }; template struct one_resize_policy_selector< __gnu_pbds::test::direct_mod_range_hashing_t_< Allocator_> > { typedef mod_one_resize_policy_t type; }; template struct generic_cc_hash_table_t { typedef __gnu_pbds::cc_hash_table< Key, Data, __gnu_pbds::null_hash_fn, Eq_Fn, Comb_Hash_Fn, typename one_resize_policy_selector< typename Comb_Hash_Fn::comb_fn>::type, false, Allocator> type; }; typedef typename __gnu_cxx::typelist::transform< Comb_Hash_Fn_TL, generic_cc_hash_table_t>::type performance_cc_types; template struct no_access_generic_gp_hash_table_t { typedef __gnu_pbds::gp_hash_table< Key, Data, __gnu_pbds::null_hash_fn, Eq_Fn, Comb_Probe_Fn, __gnu_pbds::null_probe_fn, typename half_resize_policy_selector< typename Comb_Probe_Fn::comb_fn>::type, false, Allocator> type; }; typedef typename __gnu_cxx::typelist::transform< Comb_Probe_Fn_TL, no_access_generic_gp_hash_table_t>::type performance_gp_types; public: typedef typename __gnu_cxx::typelist::append< performance_cc_types, performance_gp_types>::type performance_tl; }; template, class Allocator = std::allocator > class lu_common_types { private: typedef typename Allocator::size_type size_type; typedef __gnu_pbds::test::move_to_front_lu_policy_t_ mtf_u; typedef __gnu_pbds::test::counter_lu_policy_t_ cnt_5_u; typedef typename __gnu_cxx::typelist::create1::type lu_policy0; typedef typename __gnu_cxx::typelist::create1::type lu_policy1; typedef typename __gnu_cxx::typelist::create2< lu_policy0, lu_policy1>::type lu_policies; template struct generic_list_update_t { private: typedef typename __gnu_cxx::typelist::at_index< Policy_Tl, 0>::type update_policy_t; public: typedef __gnu_pbds::list_update< Key, Data, Eq_Fn, update_policy_t, Allocator> type; }; typedef typename __gnu_cxx::typelist::transform< lu_policies, generic_list_update_t>::type lu_types; typedef typename __gnu_cxx::typelist::at_index< lu_types, 0>::type min_lu_type; public: typedef lu_types performance_tl; typedef lu_types regression_tl; typedef typename __gnu_cxx::typelist::create1::type performance_min_tl; }; template, template class Node_Update = __gnu_pbds::null_tree_node_update, class Allocator = std::allocator > > struct tree_common_types { private: typedef __gnu_pbds::tree< Key, Data, Cmp_Fn, __gnu_pbds::ov_tree_tag, Node_Update, Allocator> ov_tree_assoc_container_t; typedef __gnu_pbds::tree< Key, Data, Cmp_Fn, __gnu_pbds::rb_tree_tag, Node_Update, Allocator> rb_tree_assoc_container_t; typedef __gnu_pbds::tree< Key, Data, Cmp_Fn, __gnu_pbds::splay_tree_tag, Node_Update, Allocator> splay_tree_assoc_container_t; public: typedef typename __gnu_cxx::typelist::create3< splay_tree_assoc_container_t, rb_tree_assoc_container_t, ov_tree_assoc_container_t>::type performance_tl; typedef typename __gnu_cxx::typelist::create3< ov_tree_assoc_container_t, splay_tree_assoc_container_t, rb_tree_assoc_container_t>::type regression_tl; typedef typename __gnu_cxx::typelist::create1< rb_tree_assoc_container_t>::type performance_min_tl; }; template::type, class Tag = __gnu_pbds::pat_trie_tag, template class Node_Update = __gnu_pbds::null_trie_node_update, class Allocator = std::allocator > class trie_common_types { private: typedef __gnu_pbds::trie type; public: typedef typename __gnu_cxx::typelist::create1::type performance_tl; typedef typename __gnu_cxx::typelist::create1::type regression_tl; typedef typename __gnu_cxx::typelist::create1::type performance_min_tl; }; } // namespace test } // namespace __gnu_pbds #endif // #ifndef PB_DS_COMMON_TYPES_ASSOC_HPP