--- /dev/null
+// -*- 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
+// <http://www.gnu.org/licenses/>.
+
+
+// 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 <ext/pb_ds/detail/type_utils.hpp>
+#include <common_type/assoc/template_policy.hpp>
+#include <ext/pb_ds/assoc_container.hpp>
+
+namespace __gnu_pbds
+{
+ namespace test
+ {
+ template<typename Key,
+ typename Data,
+ class Hash_Fn = typename __gnu_pbds::detail::default_hash_fn<Key>::type,
+ class Eq_Fn = std::equal_to<Key>,
+ class Allocator = std::allocator<std::pair<const Key, Data> > >
+ 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_<Key, Allocator> lin_p_t;
+
+ typedef __gnu_pbds::test::quadratic_probe_fn_t_<Key, Allocator> 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<typename Policy_Tl>
+ 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<typename Policy_Tl>
+ 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<typename Policy_Tl>
+ 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<typename Policy_Tl>
+ 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<typename Key,
+ typename Data,
+ class Comb_Hash_Fn_TL,
+ class Comb_Probe_Fn_TL,
+ class Eq_Fn =
+ std::equal_to<Key>,
+ 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<typename Comb_Hash_Fn_>
+ struct half_resize_policy_selector;
+
+ template<typename Allocator_>
+ struct half_resize_policy_selector<
+ __gnu_pbds::test::direct_mask_range_hashing_t_<
+ Allocator_> >
+ {
+ typedef mask_half_resize_policy_t type;
+ };
+
+ template<typename Allocator_>
+ struct half_resize_policy_selector<
+ __gnu_pbds::test::direct_mod_range_hashing_t_<
+ Allocator_> >
+ {
+ typedef mod_half_resize_policy_t type;
+ };
+
+ template<typename Comb_Hash_Fn_>
+ struct one_resize_policy_selector;
+
+ template<typename Allocator_>
+ struct one_resize_policy_selector<
+ __gnu_pbds::test::direct_mask_range_hashing_t_<
+ Allocator_> >
+ {
+ typedef mask_one_resize_policy_t type;
+ };
+
+ template<typename Allocator_>
+ struct one_resize_policy_selector<
+ __gnu_pbds::test::direct_mod_range_hashing_t_<
+ Allocator_> >
+ {
+ typedef mod_one_resize_policy_t type;
+ };
+
+ template<typename Comb_Hash_Fn>
+ 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<typename Comb_Probe_Fn>
+ 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<typename Key, typename Data, class Eq_Fn = std::equal_to<Key>,
+ class Allocator =
+ std::allocator<char> >
+ 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_<Allocator, 5> cnt_5_u;
+
+ typedef typename __gnu_cxx::typelist::create1<mtf_u>::type lu_policy0;
+
+ typedef typename __gnu_cxx::typelist::create1<cnt_5_u>::type lu_policy1;
+
+ typedef
+ typename __gnu_cxx::typelist::create2<
+ lu_policy0,
+ lu_policy1>::type
+ lu_policies;
+
+ template<typename Policy_Tl>
+ 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<min_lu_type>::type performance_min_tl;
+ };
+
+ template<typename Key, typename Data, class Cmp_Fn = std::less<Key>,
+ template<typename Const_Node_Iterator,
+ class Node_Iterator,
+ class Cmp_Fn_,
+ class Allocator_>
+ class Node_Update = __gnu_pbds::null_tree_node_update,
+ class Allocator = std::allocator<std::pair<const Key, Data> > >
+ 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<typename Key,
+ typename Data,
+ class E_Access_Traits =
+ typename __gnu_pbds::detail::default_trie_e_access_traits<Key>::type,
+ class Tag = __gnu_pbds::pat_trie_tag,
+ template<typename Const_Node_Iterator,
+ typename Node_Iterator,
+ class E_Access_Traits_,
+ typename Allocator_>
+ class Node_Update = __gnu_pbds::null_trie_node_update,
+ class Allocator = std::allocator<char> >
+ class trie_common_types
+ {
+ private:
+ typedef __gnu_pbds::trie<Key, Data, E_Access_Traits, Tag, Node_Update, Allocator> type;
+
+ public:
+ typedef typename __gnu_cxx::typelist::create1<type>::type performance_tl;
+ typedef typename __gnu_cxx::typelist::create1<type>::type regression_tl;
+ typedef typename __gnu_cxx::typelist::create1<type>::type performance_min_tl;
+ };
+
+ } // namespace test
+} // namespace __gnu_pbds
+
+#endif // #ifndef PB_DS_COMMON_TYPES_ASSOC_HPP
projects / msp430-gcc.git / blobdiff