3 // Copyright (C) 2005-2013 Free Software Foundation, Inc.
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 3, or (at your option) any later
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.
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING3. If not see
18 // <http://www.gnu.org/licenses/>.
21 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
23 // Permission to use, copy, modify, sell, and distribute this software
24 // is hereby granted without fee, provided that the above copyright
25 // notice appears in all copies, and that both that copyright notice
26 // and this permission notice appear in supporting documentation. None
27 // of the above authors, nor IBM Haifa Research Laboratories, make any
28 // representation about the suitability of this software for any
29 // purpose. It is provided "as is" without express or implied
33 * @file common_type.hpp
34 * Contains common types.
37 #ifndef PB_DS_COMMON_TYPES_ASSOC_HPP
38 #define PB_DS_COMMON_TYPES_ASSOC_HPP
40 #include <ext/pb_ds/detail/type_utils.hpp>
41 #include <common_type/assoc/template_policy.hpp>
42 #include <ext/pb_ds/assoc_container.hpp>
48 template<typename Key
,
50 class Hash_Fn
= typename
__gnu_pbds::detail::default_hash_fn
<Key
>::type
,
51 class Eq_Fn
= std::equal_to
<Key
>,
52 typename _Alloc
= std::allocator
<std::pair
<const Key
, Data
> > >
53 struct hash_common_types
56 typedef typename
_Alloc::size_type size_type
;
59 __gnu_pbds::test::hash_load_check_resize_trigger_t_
<
64 no_access_half_load_check_resize_trigger_policy
;
67 __gnu_pbds::test::hash_load_check_resize_trigger_t_
<
72 access_half_load_check_resize_trigger_policy
;
75 __gnu_pbds::test::hash_load_check_resize_trigger_t_
<
80 no_access_one_load_check_resize_trigger_policy
;
83 __gnu_pbds::test::cc_hash_max_collision_check_resize_trigger_t_
<
87 no_access_half_max_col_check_check_resize_trigger_policy
;
90 __gnu_pbds::test::cc_hash_max_collision_check_resize_trigger_t_
<
94 access_half_max_col_check_check_resize_trigger_policy
;
96 typedef __gnu_pbds::test::linear_probe_fn_t_
<Key
, _Alloc
> lin_p_t
;
98 typedef __gnu_pbds::test::quadratic_probe_fn_t_
<Key
, _Alloc
> quad_p_t
;
101 typename
__gnu_cxx::typelist::create4
<
102 __gnu_pbds::detail::false_type
,
103 __gnu_pbds::test::direct_mask_range_hashing_t_
<_Alloc
>,
104 no_access_half_load_check_resize_trigger_policy
,
105 __gnu_pbds::test::hash_exponential_size_policy_t_
<_Alloc
> >::type
106 performance_cc_policy0
;
109 typename
__gnu_cxx::typelist::create4
<
110 __gnu_pbds::detail::false_type
,
111 __gnu_pbds::test::direct_mod_range_hashing_t_
<_Alloc
>,
112 no_access_half_load_check_resize_trigger_policy
,
113 __gnu_pbds::test::hash_prime_size_policy_t_
>::type
114 performance_cc_policy1
;
117 typename
__gnu_cxx::typelist::create4
<
118 __gnu_pbds::detail::false_type
,
119 __gnu_pbds::test::direct_mask_range_hashing_t_
<_Alloc
>,
120 no_access_one_load_check_resize_trigger_policy
,
121 __gnu_pbds::test::hash_exponential_size_policy_t_
<_Alloc
> >::type
122 performance_cc_policy2
;
125 typename
__gnu_cxx::typelist::create4
<
126 __gnu_pbds::detail::false_type
,
127 __gnu_pbds::test::direct_mod_range_hashing_t_
<_Alloc
>,
128 no_access_one_load_check_resize_trigger_policy
,
129 __gnu_pbds::test::hash_prime_size_policy_t_
>::type
130 performance_cc_policy3
;
133 typename
__gnu_cxx::typelist::create4
<
134 __gnu_pbds::detail::true_type
,
135 __gnu_pbds::test::direct_mask_range_hashing_t_
<_Alloc
>,
136 no_access_half_load_check_resize_trigger_policy
,
137 __gnu_pbds::test::hash_exponential_size_policy_t_
<_Alloc
> >::type
138 performance_cc_policy4
;
141 typename
__gnu_cxx::typelist::create4
<
142 __gnu_pbds::detail::false_type
,
143 __gnu_pbds::test::direct_mask_range_hashing_t_
<_Alloc
>,
144 no_access_half_max_col_check_check_resize_trigger_policy
,
145 __gnu_pbds::test::hash_exponential_size_policy_t_
<_Alloc
> >::type
146 performance_cc_policy5
;
149 typename
__gnu_cxx::typelist::create4
<
150 __gnu_pbds::detail::false_type
,
151 __gnu_pbds::test::direct_mask_range_hashing_t_
<_Alloc
>,
152 access_half_max_col_check_check_resize_trigger_policy
,
153 __gnu_pbds::test::hash_exponential_size_policy_t_
<_Alloc
> >::type
154 regression_cc_policy0
;
157 typename
__gnu_cxx::typelist::create4
<
158 __gnu_pbds::detail::false_type
,
159 __gnu_pbds::test::direct_mask_range_hashing_t_
<_Alloc
>,
160 access_half_load_check_resize_trigger_policy
,
161 __gnu_pbds::test::hash_exponential_size_policy_t_
<_Alloc
> >::type
162 regression_cc_policy1
;
165 typename
__gnu_cxx::typelist::create4
<
166 __gnu_pbds::detail::true_type
,
167 __gnu_pbds::test::direct_mod_range_hashing_t_
<_Alloc
>,
168 no_access_half_load_check_resize_trigger_policy
,
169 __gnu_pbds::test::hash_prime_size_policy_t_
>::type
170 regression_cc_policy2
;
173 typename
__gnu_cxx::typelist::create5
<
174 __gnu_pbds::detail::false_type
,
176 __gnu_pbds::test::direct_mask_range_hashing_t_
<_Alloc
>,
177 no_access_half_load_check_resize_trigger_policy
,
178 __gnu_pbds::test::hash_exponential_size_policy_t_
<_Alloc
> >::type
179 performance_gp_policy0
;
182 typename
__gnu_cxx::typelist::create5
<
183 __gnu_pbds::detail::false_type
,
185 __gnu_pbds::test::direct_mod_range_hashing_t_
<_Alloc
>,
186 no_access_half_load_check_resize_trigger_policy
,
187 __gnu_pbds::test::hash_prime_size_policy_t_
>::type
188 performance_gp_policy1
;
191 typename
__gnu_cxx::typelist::create5
<
192 __gnu_pbds::detail::false_type
,
194 __gnu_pbds::test::direct_mod_range_hashing_t_
<_Alloc
>,
195 access_half_load_check_resize_trigger_policy
,
196 __gnu_pbds::test::hash_prime_size_policy_t_
>::type
197 regression_gp_policy0
;
200 typename
__gnu_cxx::typelist::create5
<
201 __gnu_pbds::detail::true_type
,
203 __gnu_pbds::test::direct_mask_range_hashing_t_
<_Alloc
>,
204 access_half_load_check_resize_trigger_policy
,
205 __gnu_pbds::test::hash_exponential_size_policy_t_
<_Alloc
> >::type
206 regression_gp_policy1
;
209 typename
__gnu_cxx::typelist::create6
<
210 performance_cc_policy0
,
211 performance_cc_policy1
,
212 performance_cc_policy2
,
213 performance_cc_policy3
,
214 performance_cc_policy4
,
215 performance_cc_policy5
>::type
216 performance_cc_range_hashing_policies
;
219 typename
__gnu_cxx::typelist::create3
<
220 regression_cc_policy0
,
221 regression_cc_policy1
,
222 regression_cc_policy2
>::type
223 regression_cc_range_hashing_policies
;
226 typename
__gnu_cxx::typelist::create2
<
227 performance_gp_policy0
,
228 performance_gp_policy1
>::type
229 performance_gp_range_hashing_policies
;
232 typename
__gnu_cxx::typelist::create2
<
233 regression_gp_policy0
,
234 regression_gp_policy1
>::type
235 regression_gp_range_hashing_policies
;
237 template<typename Policy_Tl
>
238 struct no_access_generic_cc_hash_table_t
242 typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 0>::type
243 store_hash_indicator
;
247 store_hash
= store_hash_indicator::value
250 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 1>::type
253 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 2>::type
256 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 3>::type
261 __gnu_pbds::cc_hash_table
<
267 __gnu_pbds::hash_standard_resize_policy
<size_policy
, trigger_policy
,
274 template<typename Policy_Tl
>
275 struct access_generic_cc_hash_table_t
279 typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 0>::type
280 store_hash_indicator
;
284 store_hash
= store_hash_indicator::value
287 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 1>::type
290 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 2>::type
293 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 3>::type
298 __gnu_pbds::cc_hash_table
<
304 __gnu_pbds::hash_standard_resize_policy
<size_policy
, trigger_policy
,
311 template<typename Policy_Tl
>
312 struct no_access_generic_gp_hash_table_t
315 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 0>::type
316 store_hash_indicator
;
320 store_hash
= store_hash_indicator::value
323 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 1>::type
326 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 2>::type
329 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 3>::type
332 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 4>::type
337 __gnu_pbds::gp_hash_table
<
344 __gnu_pbds::hash_standard_resize_policy
<size_policy
, trigger_policy
,
351 template<typename Policy_Tl
>
352 struct access_generic_gp_hash_table_t
355 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 0>::type
356 store_hash_indicator
;
360 store_hash
= store_hash_indicator::value
363 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 1>::type
366 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 2>::type
369 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 3>::type
372 typedef typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 4>::type
377 __gnu_pbds::gp_hash_table
<
384 __gnu_pbds::hash_standard_resize_policy
<size_policy
, trigger_policy
,
392 typename
__gnu_cxx::typelist::transform
<
393 performance_cc_range_hashing_policies
,
394 no_access_generic_cc_hash_table_t
>::type
395 performance_cc_types
;
398 typename
__gnu_cxx::typelist::transform
<
399 regression_cc_range_hashing_policies
,
400 access_generic_cc_hash_table_t
>::type
404 typename
__gnu_cxx::typelist::at_index
<
405 performance_cc_types
,
407 performance_min_cc_type
;
410 typename
__gnu_cxx::typelist::transform
<
411 performance_gp_range_hashing_policies
,
412 no_access_generic_gp_hash_table_t
>::type
413 performance_gp_types
;
416 typename
__gnu_cxx::typelist::transform
<
417 regression_gp_range_hashing_policies
,
418 access_generic_gp_hash_table_t
>::type
422 typename
__gnu_cxx::typelist::at_index
<
423 performance_gp_types
,
425 performance_min_gp_type
;
429 typename
__gnu_cxx::typelist::append
<
430 performance_cc_types
,
431 performance_gp_types
>::type
435 typename
__gnu_cxx::typelist::append
<
437 regression_cc_types
>::type
441 typename
__gnu_cxx::typelist::create1
<
442 performance_min_cc_type
>::type
446 template<typename Key
,
448 class Comb_Hash_Fn_TL
,
449 class Comb_Probe_Fn_TL
,
452 typename _Alloc
= std::allocator
<std::pair
<const Key
, Data
> > >
453 struct ranged_hash_common_types
456 typedef typename
_Alloc::size_type size_type
;
459 __gnu_pbds::test::hash_load_check_resize_trigger_t_
<
464 no_access_half_load_check_resize_trigger_policy
;
467 __gnu_pbds::test::hash_load_check_resize_trigger_t_
<
472 no_access_one_load_check_resize_trigger_policy
;
475 __gnu_pbds::hash_standard_resize_policy
<
476 __gnu_pbds::test::hash_exponential_size_policy_t_
<
478 no_access_half_load_check_resize_trigger_policy
>
479 mask_half_resize_policy_t
;
482 __gnu_pbds::hash_standard_resize_policy
<
483 __gnu_pbds::test::hash_exponential_size_policy_t_
<
485 no_access_one_load_check_resize_trigger_policy
>
486 mask_one_resize_policy_t
;
489 __gnu_pbds::hash_standard_resize_policy
<
490 __gnu_pbds::test::hash_prime_size_policy_t_
,
491 no_access_half_load_check_resize_trigger_policy
>
492 mod_half_resize_policy_t
;
495 __gnu_pbds::hash_standard_resize_policy
<
496 __gnu_pbds::test::hash_prime_size_policy_t_
,
497 no_access_one_load_check_resize_trigger_policy
>
498 mod_one_resize_policy_t
;
500 template<typename Comb_Hash_Fn_
>
501 struct half_resize_policy_selector
;
503 template<typename _Alloc_
>
504 struct half_resize_policy_selector
<__gnu_pbds::test::direct_mask_range_hashing_t_
<_Alloc_
> >
506 typedef mask_half_resize_policy_t type
;
509 template<typename _Alloc_
>
510 struct half_resize_policy_selector
<__gnu_pbds::test::direct_mod_range_hashing_t_
<_Alloc_
> >
512 typedef mod_half_resize_policy_t type
;
515 template<typename Comb_Hash_Fn_
>
516 struct one_resize_policy_selector
;
518 template<typename _Alloc_
>
519 struct one_resize_policy_selector
<__gnu_pbds::test::direct_mask_range_hashing_t_
<_Alloc_
> >
521 typedef mask_one_resize_policy_t type
;
524 template<typename _Alloc_
>
525 struct one_resize_policy_selector
<__gnu_pbds::test::direct_mod_range_hashing_t_
<_Alloc_
> >
527 typedef mod_one_resize_policy_t type
;
530 template<typename Comb_Hash_Fn
>
531 struct generic_cc_hash_table_t
534 __gnu_pbds::cc_hash_table
<
537 __gnu_pbds::null_type
,
540 typename one_resize_policy_selector
<typename
Comb_Hash_Fn::comb_fn
>::type
,
546 typename
__gnu_cxx::typelist::transform
<
548 generic_cc_hash_table_t
>::type
549 performance_cc_types
;
551 template<typename Comb_Probe_Fn
>
552 struct no_access_generic_gp_hash_table_t
555 __gnu_pbds::gp_hash_table
<
558 __gnu_pbds::null_type
,
561 __gnu_pbds::null_type
,
562 typename half_resize_policy_selector
<typename
Comb_Probe_Fn::comb_fn
>::type
,
569 typename
__gnu_cxx::typelist::transform
<
571 no_access_generic_gp_hash_table_t
>::type
572 performance_gp_types
;
576 typename
__gnu_cxx::typelist::append
<
577 performance_cc_types
,
578 performance_gp_types
>::type
582 template<typename Key
, typename Data
, class Eq_Fn
= std::equal_to
<Key
>,
583 typename _Alloc
= std::allocator
<char> >
584 class lu_common_types
587 typedef typename
_Alloc::size_type size_type
;
589 typedef __gnu_pbds::test::lu_move_to_front_policy_t_ mtf_u
;
591 typedef __gnu_pbds::test::lu_counter_policy_t_
<_Alloc
, 5> cnt_5_u
;
593 typedef typename
__gnu_cxx::typelist::create1
<mtf_u
>::type lu_policy0
;
595 typedef typename
__gnu_cxx::typelist::create1
<cnt_5_u
>::type lu_policy1
;
598 typename
__gnu_cxx::typelist::create2
<lu_policy0
, lu_policy1
>::type
601 template<typename Policy_Tl
>
602 struct generic_list_update_t
606 typename
__gnu_cxx::typelist::at_index
<Policy_Tl
, 0>::type
611 __gnu_pbds::list_update
<Key
, Data
, Eq_Fn
, update_policy_t
, _Alloc
>
616 typename
__gnu_cxx::typelist::transform
<lu_policies
,
617 generic_list_update_t
>::type
621 typename
__gnu_cxx::typelist::at_index
<lu_types
, 0>::type
625 typedef lu_types performance_tl
;
626 typedef lu_types regression_tl
;
628 typedef typename
__gnu_cxx::typelist::create1
<min_lu_type
>::type performance_min_tl
;
631 template<typename Key
, typename Data
, class Cmp_Fn
= std::less
<Key
>,
632 template<typename Node_CItr
,
636 class Node_Update
= __gnu_pbds::null_node_update
,
637 typename _Alloc
= std::allocator
<std::pair
<const Key
, Data
> > >
638 struct tree_common_types
646 __gnu_pbds::ov_tree_tag
,
649 ov_tree_assoc_container_t
;
656 __gnu_pbds::rb_tree_tag
,
659 rb_tree_assoc_container_t
;
666 __gnu_pbds::splay_tree_tag
,
669 splay_tree_assoc_container_t
;
673 typename
__gnu_cxx::typelist::create3
<
674 splay_tree_assoc_container_t
,
675 rb_tree_assoc_container_t
,
676 ov_tree_assoc_container_t
>::type
680 typename
__gnu_cxx::typelist::create3
<
681 ov_tree_assoc_container_t
,
682 splay_tree_assoc_container_t
,
683 rb_tree_assoc_container_t
>::type
687 typename
__gnu_cxx::typelist::create1
<
688 rb_tree_assoc_container_t
>::type
692 template<typename Key
,
695 typename
__gnu_pbds::detail::default_trie_access_traits
<Key
>::type
,
696 class Tag
= __gnu_pbds::pat_trie_tag
,
697 template<typename Node_CItr
,
701 class Node_Update
= __gnu_pbds::null_node_update
,
702 typename _Alloc
= std::allocator
<char> >
703 class trie_common_types
706 typedef __gnu_pbds::trie
<Key
, Data
, _ATraits
, Tag
, Node_Update
, _Alloc
> type
;
709 typedef typename
__gnu_cxx::typelist::create1
<type
>::type performance_tl
;
710 typedef typename
__gnu_cxx::typelist::create1
<type
>::type regression_tl
;
711 typedef typename
__gnu_cxx::typelist::create1
<type
>::type performance_min_tl
;
715 } // namespace __gnu_pbds
717 #endif // #ifndef PB_DS_COMMON_TYPES_ASSOC_HPP