Update copyright years.

[thirdparty/gcc.git] / libstdc++-v3 / testsuite / util / common_type / assoc / common_type.hpp

// -*- C++ -*-

// Copyright (C) 2005-2022 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>,
	     typename _Alloc = std::allocator<std::pair<const Key, Data> > >
    struct hash_common_types
    {
    private:
      typedef typename _Alloc::size_type size_type;

      typedef
      __gnu_pbds::test::hash_load_check_resize_trigger_t_<
	_Alloc,
	1, 8,
	1, 2,
	false>
      no_access_half_load_check_resize_trigger_policy;

      typedef
      __gnu_pbds::test::hash_load_check_resize_trigger_t_<
	_Alloc,
	1, 8,
	1, 2,
	true>
      access_half_load_check_resize_trigger_policy;

      typedef
      __gnu_pbds::test::hash_load_check_resize_trigger_t_<
	_Alloc,
	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_<
	_Alloc,
	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_<
	_Alloc,
	1, 2,
	true>
      access_half_max_col_check_check_resize_trigger_policy;

      typedef __gnu_pbds::test::linear_probe_fn_t_<Key, _Alloc> lin_p_t;

      typedef __gnu_pbds::test::quadratic_probe_fn_t_<Key, _Alloc> quad_p_t;

      typedef
      typename __gnu_cxx::typelist::create4<
	__gnu_pbds::detail::false_type,
	__gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc>,
	no_access_half_load_check_resize_trigger_policy,
	__gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::type
      performance_cc_policy0;

      typedef
      typename __gnu_cxx::typelist::create4<
	__gnu_pbds::detail::false_type,
	__gnu_pbds::test::direct_mod_range_hashing_t_<_Alloc>,
	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_<_Alloc>,
	no_access_one_load_check_resize_trigger_policy,
	__gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::type
      performance_cc_policy2;

      typedef
      typename __gnu_cxx::typelist::create4<
	__gnu_pbds::detail::false_type,
	__gnu_pbds::test::direct_mod_range_hashing_t_<_Alloc>,
	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_<_Alloc>,
	no_access_half_load_check_resize_trigger_policy,
	__gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::type
      performance_cc_policy4;

      typedef
      typename __gnu_cxx::typelist::create4<
	__gnu_pbds::detail::false_type,
	__gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc>,
	no_access_half_max_col_check_check_resize_trigger_policy,
	__gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::type
      performance_cc_policy5;

      typedef
      typename __gnu_cxx::typelist::create4<
	__gnu_pbds::detail::false_type,
	__gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc>,
	access_half_max_col_check_check_resize_trigger_policy,
	__gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::type
      regression_cc_policy0;

      typedef
      typename __gnu_cxx::typelist::create4<
	__gnu_pbds::detail::false_type,
	__gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc>,
	access_half_load_check_resize_trigger_policy,
	__gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::type
      regression_cc_policy1;

      typedef
      typename __gnu_cxx::typelist::create4<
	__gnu_pbds::detail::true_type,
	__gnu_pbds::test::direct_mod_range_hashing_t_<_Alloc>,
	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_<_Alloc>,
	no_access_half_load_check_resize_trigger_policy,
	__gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::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_<_Alloc>,
	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_<_Alloc>,
	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_<_Alloc>,
	access_half_load_check_resize_trigger_policy,
	__gnu_pbds::test::hash_exponential_size_policy_t_<_Alloc> >::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,
	_Alloc>
	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,
	_Alloc>
	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,
	_Alloc>
	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,
	_Alloc>
	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>,
	     typename _Alloc = std::allocator<std::pair<const Key, Data> > >
    struct ranged_hash_common_types
    {
    private:
      typedef typename _Alloc::size_type size_type;

      typedef
      __gnu_pbds::test::hash_load_check_resize_trigger_t_<
	_Alloc,
	1, 8,
	1, 2,
	false>
      no_access_half_load_check_resize_trigger_policy;

      typedef
      __gnu_pbds::test::hash_load_check_resize_trigger_t_<
	_Alloc,
	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_<
	_Alloc>,
	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_<
	_Alloc>,
	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 _Alloc_>
      struct half_resize_policy_selector<__gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc_> >
      {
        typedef mask_half_resize_policy_t type;
      };

      template<typename _Alloc_>
      struct half_resize_policy_selector<__gnu_pbds::test::direct_mod_range_hashing_t_<_Alloc_> >
      {
        typedef mod_half_resize_policy_t type;
      };

      template<typename Comb_Hash_Fn_>
      struct one_resize_policy_selector;

      template<typename _Alloc_>
      struct one_resize_policy_selector<__gnu_pbds::test::direct_mask_range_hashing_t_<_Alloc_> >
      {
        typedef mask_one_resize_policy_t type;
      };

      template<typename _Alloc_>
      struct one_resize_policy_selector<__gnu_pbds::test::direct_mod_range_hashing_t_<_Alloc_> >
      {
        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_type,
	  Eq_Fn,
	  Comb_Hash_Fn,
	  typename one_resize_policy_selector<typename Comb_Hash_Fn::comb_fn>::type,
	  false, _Alloc>
	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_type,
	  Eq_Fn,
	  Comb_Probe_Fn,
	  __gnu_pbds::null_type,
	  typename half_resize_policy_selector<typename Comb_Probe_Fn::comb_fn>::type,
	  false,
	  _Alloc>
	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>,
	     typename _Alloc = std::allocator<char> >
    class lu_common_types
    {
    private:
      typedef typename _Alloc::size_type size_type;

      typedef __gnu_pbds::test::lu_move_to_front_policy_t_ mtf_u;

      typedef __gnu_pbds::test::lu_counter_policy_t_<_Alloc, 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, _Alloc>
	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 Node_CItr,
		      class Node_Itr,
		      class Cmp_Fn_,
		      typename _Alloc_>
    class Node_Update = __gnu_pbds::null_node_update,
	     typename _Alloc = 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,
      _Alloc>
      ov_tree_assoc_container_t;

      typedef
      __gnu_pbds::tree<
	Key,
	Data,
	Cmp_Fn,
	__gnu_pbds::rb_tree_tag,
	Node_Update,
	_Alloc>
      rb_tree_assoc_container_t;

      typedef
      __gnu_pbds::tree<
	Key,
	Data,
	Cmp_Fn,
	__gnu_pbds::splay_tree_tag,
	Node_Update,
	_Alloc>
      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 _ATraits =
	     typename __gnu_pbds::detail::default_trie_access_traits<Key>::type,
	     class Tag = __gnu_pbds::pat_trie_tag,
	     template<typename Node_CItr,
		      typename Node_Itr,
		      class _ATraits_,
		      typename _Alloc_>
    class Node_Update = __gnu_pbds::null_node_update,
	     typename _Alloc = std::allocator<char> >
    class trie_common_types
    {
    private:
      typedef __gnu_pbds::trie<Key, Data, _ATraits, Tag, Node_Update, _Alloc> 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