1// -*- C++ -*-
2
3// Copyright (C) 2005-2022 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 3, 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// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.
24
25// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26
27// Permission to use, copy, modify, sell, and distribute this software
28// is hereby granted without fee, provided that the above copyright
29// notice appears in all copies, and that both that copyright notice
30// and this permission notice appear in supporting documentation. None
31// of the above authors, nor IBM Haifa Research Laboratories, make any
32// representation about the suitability of this software for any
33// purpose. It is provided "as is" without express or implied
34// warranty.
35
36/**
37 * @file detail/standard_policies.hpp
38 * Contains standard policies for containers.
39 */
40
41#ifndef PB_DS_STANDARD_POLICIES_HPP
42#define PB_DS_STANDARD_POLICIES_HPP
43
44#include <memory>
45#include <ext/pb_ds/hash_policy.hpp>
46#include <ext/pb_ds/list_update_policy.hpp>
47#include <ext/pb_ds/detail/branch_policy/null_node_metadata.hpp>
48#include <ext/pb_ds/tree_policy.hpp>
49#include <ext/pb_ds/trie_policy.hpp>
50#include <ext/pb_ds/tag_and_trait.hpp>
51#include <tr1/functional>
52
53namespace __gnu_pbds
54{
55  namespace detail
56  {
57    /// Primary template, default_hash_fn.
58    template<typename Key>
59    struct default_hash_fn
60    {
61	/// Dispatched type.
62      typedef std::tr1::hash<Key> 				type;
63    };
64
65    /// Primary template, default_eq_fn.
66    template<typename Key>
67    struct default_eq_fn
68    {
69	/// Dispatched type.
70      typedef std::equal_to<Key> 				type;
71    };
72
73    /// Enumeration for default behavior of stored hash data.
74    enum
75      {
76	default_store_hash = false
77      };
78
79    /// Primary template, default_comb_hash_fn.
80    struct default_comb_hash_fn
81    {
82	/// Dispatched type.
83      typedef direct_mask_range_hashing<> 			type;
84    };
85
86    /// Primary template, default_resize_policy.
87    template<typename Comb_Hash_Fn>
88    struct default_resize_policy
89    {
90    private:
91      typedef typename Comb_Hash_Fn::size_type 			size_type;
92
93      typedef direct_mask_range_hashing<size_type> 		default_fn;
94      typedef is_same<default_fn, Comb_Hash_Fn> 		same_type;
95      typedef hash_exponential_size_policy<size_type> 		iftrue;
96      typedef hash_prime_size_policy 				iffalse;
97      typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type;
98      typedef typename cond_type::__type 		       size_policy_type;
99
100      typedef hash_load_check_resize_trigger<false, size_type> 	trigger;
101
102    public:
103	/// Dispatched type.
104      typedef hash_standard_resize_policy<size_policy_type, trigger,
105					  false, size_type> 	type;
106    };
107
108    /// Default update policy.
109    struct default_update_policy
110    {
111	/// Dispatched type.
112      typedef lu_move_to_front_policy<> 			type;
113    };
114
115    /// Primary template, default_probe_fn.
116    template<typename Comb_Probe_Fn>
117    struct default_probe_fn
118    {
119    private:
120      typedef typename Comb_Probe_Fn::size_type 		size_type;
121      typedef direct_mask_range_hashing<size_type> 		default_fn;
122      typedef is_same<default_fn, Comb_Probe_Fn> 		same_type;
123      typedef linear_probe_fn<size_type> 			iftrue;
124      typedef quadratic_probe_fn<size_type> 			iffalse;
125      typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type;
126
127    public:
128	/// Dispatched type.
129      typedef typename cond_type::__type 			type;
130    };
131
132
133    /// Primary template, default_trie_access_traits.
134    template<typename Key>
135      struct default_trie_access_traits;
136
137#define __dtrie_alloc std::allocator<char>
138#define __dtrie_string std::basic_string<Char, Char_Traits, __dtrie_alloc>
139
140    /// Partial specialization, default_trie_access_traits.
141    template<typename Char, typename Char_Traits>
142      struct default_trie_access_traits<__dtrie_string>
143      {
144      private:
145	typedef __dtrie_string					string_type;
146
147      public:
148	/// Dispatched type.
149	typedef trie_string_access_traits<string_type> 		type;
150      };
151
152#undef __dtrie_alloc
153#undef __dtrie_string
154
155  } // namespace detail
156} // namespace __gnu_pbds
157
158#endif // #ifndef PB_DS_STANDARD_POLICIES_HPP
159