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/types_traits.hpp 38 * Contains a traits class of types used by containers. 39 */ 40 41 #ifndef PB_DS_TYPES_TRAITS_HPP 42 #define PB_DS_TYPES_TRAITS_HPP 43 44 #include <algorithm> 45 #include <utility> 46 #include <ext/pb_ds/tag_and_trait.hpp> 47 #include <ext/pb_ds/detail/type_utils.hpp> 48 #include <memory> 49 50 namespace __gnu_pbds 51 { 52 namespace detail 53 { 54 /** 55 * @addtogroup traits Traits 56 * @{ 57 */ 58 59 /// Primary template. 60 template<typename Key, typename Mapped> 61 struct no_throw_copies 62 { 63 static const bool __simple = is_simple<Key>::value 64 && is_simple<Mapped>::value; 65 typedef integral_constant<int, __simple> indicator; 66 }; 67 68 /// Specialization. 69 template<typename Key> 70 struct no_throw_copies<Key, null_type> 71 { 72 typedef integral_constant<int, is_simple<Key>::value> indicator; 73 }; 74 75 76 /// Stored value. 77 template<typename _Tv> 78 struct stored_value 79 { 80 typedef _Tv value_type; 81 value_type m_value; 82 }; 83 84 /// Stored hash. 85 template<typename _Th> 86 struct stored_hash 87 { 88 typedef _Th hash_type; 89 hash_type m_hash; 90 }; 91 92 /// Primary template for representation of stored data. 93 /// Two types of data can be stored: value and hash. 94 template<typename _Tv, typename _Th, bool Store_Hash> 95 struct stored_data 96 : public stored_value<_Tv>, public stored_hash<_Th> 97 { }; 98 99 /// Specialization for representation of stored data of just value type. 100 template<typename _Tv, typename _Th> 101 struct stored_data<_Tv, _Th, false> 102 : public stored_value<_Tv> 103 { }; 104 105 /// Choose value_type to be a key/value pair or just a key. 106 template<typename Key, typename Mapped> 107 struct select_value_type 108 { 109 typedef std::pair<const Key, Mapped> type; 110 }; 111 112 /// Specialization for sets where the key is the value_type. 113 template<typename Key> 114 struct select_value_type<Key, null_type> 115 { 116 typedef Key type; 117 }; 118 119 /// Base class for conditionally defining a static data member. 120 template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash> 121 struct maybe_null_type 122 { }; 123 124 /// Specialization that defines a static data member of type null_type. 125 template<typename Key,typename _Alloc, bool Store_Hash> 126 struct maybe_null_type<Key, null_type, _Alloc, Store_Hash> 127 { 128 static null_type s_null_type; 129 }; 130 131 template<typename Key,typename _Alloc, bool Store_Hash> 132 null_type 133 maybe_null_type<Key, null_type, _Alloc, Store_Hash>::s_null_type; 134 135 /// Consistent API for accessing allocator-related types. 136 template<typename _Alloc, typename T> 137 struct rebind_traits 138 #if __cplusplus >= 201103L 139 : std::allocator_traits<_Alloc>::template rebind_traits<T> 140 { 141 using reference = T&; 142 using const_reference = const T&; 143 }; 144 #else 145 : _Alloc::template rebind<T>::other 146 { 147 typedef typename _Alloc::template rebind<T>::other allocator_type; 148 }; 149 #endif 150 151 152 /// Traits for abstract types. 153 template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash> 154 struct types_traits 155 : public maybe_null_type<Key, Mapped, _Alloc, Store_Hash> 156 { 157 public: 158 typedef typename _Alloc::size_type size_type; 159 typedef typename select_value_type<Key, Mapped>::type value_type; 160 typedef Key key_type; 161 typedef Mapped mapped_type; 162 163 private: 164 typedef rebind_traits<_Alloc, value_type> __rebind_va; 165 typedef rebind_traits<_Alloc, key_type> __rebind_ka; 166 typedef rebind_traits<_Alloc, mapped_type> __rebind_ma; 167 168 typedef no_throw_copies<Key, Mapped> __nothrowcopy; 169 170 public: 171 typedef typename __rebind_ma::pointer mapped_pointer; 172 typedef typename __rebind_ma::const_pointer mapped_const_pointer; 173 typedef typename __rebind_ma::reference mapped_reference; 174 typedef typename __rebind_ma::const_reference mapped_const_reference; 175 176 typedef typename __rebind_va::pointer pointer; 177 typedef typename __rebind_va::const_pointer const_pointer; 178 typedef typename __rebind_va::reference reference; 179 typedef typename __rebind_va::const_reference const_reference; 180 181 typedef stored_data<value_type, size_type, Store_Hash> stored_data_type; 182 183 typedef typename __rebind_ka::pointer key_pointer; 184 typedef typename __rebind_ka::const_pointer key_const_pointer; 185 typedef typename __rebind_ka::reference key_reference; 186 typedef typename __rebind_ka::const_reference key_const_reference; 187 typedef std::pair<size_type, size_type> comp_hash; 188 typedef integral_constant<int, Store_Hash> store_extra; 189 typedef typename __nothrowcopy::indicator no_throw_indicator; 190 191 store_extra m_store_extra_indicator; 192 no_throw_indicator m_no_throw_copies_indicator; 193 }; 194 ///@} 195 } // namespace detail 196 } // namespace __gnu_pbds 197 198 #endif 199