1// -*- C++ -*- 2 3// Copyright (C) 2005-2013 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 <utility> 49 50namespace __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> 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> 101 struct stored_data<_Tv, null_type> 102 : public stored_value<_Tv> 103 { }; 104 105 /// Primary template. 106 template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash> 107 struct type_base; 108 109 /** 110 * Specialization of type_base for the case where the hash value 111 * is not stored alongside each value. 112 */ 113 template<typename Key, typename Mapped, typename _Alloc> 114 struct type_base<Key, Mapped, _Alloc, false> 115 { 116 public: 117 typedef typename _Alloc::size_type size_type; 118 119 private: 120 typedef typename _Alloc::template rebind<Mapped> __rebind_m; 121 typedef typename __rebind_m::other __rebind_ma; 122 typedef std::pair<const Key, Mapped> __value_type; 123 typedef typename _Alloc::template rebind<__value_type> __rebind_v; 124 typedef typename __rebind_v::other __rebind_va; 125 126 public: 127 typedef typename __rebind_ma::value_type mapped_type; 128 typedef typename __rebind_ma::pointer mapped_pointer; 129 typedef typename __rebind_ma::const_pointer mapped_const_pointer; 130 typedef typename __rebind_ma::reference mapped_reference; 131 typedef typename __rebind_ma::const_reference mapped_const_reference; 132 133 typedef typename __rebind_va::value_type value_type; 134 typedef typename __rebind_va::pointer pointer; 135 typedef typename __rebind_va::const_pointer const_pointer; 136 typedef typename __rebind_va::reference reference; 137 typedef typename __rebind_va::const_reference const_reference; 138 139 typedef stored_data<value_type, null_type> stored_data_type; 140 }; 141 142 /** 143 * Specialization of type_base for the case where the hash value 144 * is stored alongside each value. 145 */ 146 template<typename Key, typename Mapped, typename _Alloc> 147 struct type_base<Key, Mapped, _Alloc, true> 148 { 149 public: 150 typedef typename _Alloc::size_type size_type; 151 152 private: 153 typedef typename _Alloc::template rebind<Mapped> __rebind_m; 154 typedef typename __rebind_m::other __rebind_ma; 155 typedef std::pair<const Key, Mapped> __value_type; 156 typedef typename _Alloc::template rebind<__value_type> __rebind_v; 157 typedef typename __rebind_v::other __rebind_va; 158 159 public: 160 typedef typename __rebind_ma::value_type mapped_type; 161 typedef typename __rebind_ma::pointer mapped_pointer; 162 typedef typename __rebind_ma::const_pointer mapped_const_pointer; 163 typedef typename __rebind_ma::reference mapped_reference; 164 typedef typename __rebind_ma::const_reference mapped_const_reference; 165 166 typedef typename __rebind_va::value_type value_type; 167 typedef typename __rebind_va::pointer pointer; 168 typedef typename __rebind_va::const_pointer const_pointer; 169 typedef typename __rebind_va::reference reference; 170 typedef typename __rebind_va::const_reference const_reference; 171 172 typedef stored_data<value_type, size_type> stored_data_type; 173 }; 174 175 176 /** 177 * Specialization of type_base for the case where the hash value 178 * is not stored alongside each value. 179 */ 180 template<typename Key, typename _Alloc> 181 struct type_base<Key, null_type, _Alloc, false> 182 { 183 public: 184 typedef typename _Alloc::size_type size_type; 185 typedef Key value_type; 186 187 private: 188 typedef typename _Alloc::template rebind<null_type> __rebind_m; 189 typedef typename __rebind_m::other __rebind_ma; 190 typedef typename _Alloc::template rebind<value_type> __rebind_v; 191 typedef typename __rebind_v::other __rebind_va; 192 193 public: 194 typedef typename __rebind_ma::value_type mapped_type; 195 typedef typename __rebind_ma::pointer mapped_pointer; 196 typedef typename __rebind_ma::const_pointer mapped_const_pointer; 197 typedef typename __rebind_ma::reference mapped_reference; 198 typedef typename __rebind_ma::const_reference mapped_const_reference; 199 200 typedef typename __rebind_va::pointer pointer; 201 typedef typename __rebind_va::const_pointer const_pointer; 202 typedef typename __rebind_va::reference reference; 203 typedef typename __rebind_va::const_reference const_reference; 204 205 typedef stored_data<value_type, null_type> stored_data_type; 206 207 static null_type s_null_type; 208 }; 209 210 template<typename Key, typename _Alloc> 211 null_type 212 type_base<Key, null_type, _Alloc, false>::s_null_type; 213 214 215 /** 216 * Specialization of type_base for the case where the hash value 217 * is stored alongside each value. 218 */ 219 template<typename Key, typename _Alloc> 220 struct type_base<Key, null_type, _Alloc, true> 221 { 222 public: 223 typedef typename _Alloc::size_type size_type; 224 typedef Key value_type; 225 226 private: 227 typedef typename _Alloc::template rebind<null_type> __rebind_m; 228 typedef typename __rebind_m::other __rebind_ma; 229 typedef typename _Alloc::template rebind<value_type> __rebind_v; 230 typedef typename __rebind_v::other __rebind_va; 231 232 public: 233 typedef typename __rebind_ma::value_type mapped_type; 234 typedef typename __rebind_ma::pointer mapped_pointer; 235 typedef typename __rebind_ma::const_pointer mapped_const_pointer; 236 typedef typename __rebind_ma::reference mapped_reference; 237 typedef typename __rebind_ma::const_reference mapped_const_reference; 238 239 typedef typename __rebind_va::pointer pointer; 240 typedef typename __rebind_va::const_pointer const_pointer; 241 typedef typename __rebind_va::reference reference; 242 typedef typename __rebind_va::const_reference const_reference; 243 244 typedef stored_data<value_type, size_type> stored_data_type; 245 246 static null_type s_null_type; 247 }; 248 249 template<typename Key, typename _Alloc> 250 null_type 251 type_base<Key, null_type, _Alloc, true>::s_null_type; 252 253 254 /// Type base dispatch. 255 template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash> 256 struct type_dispatch 257 { 258 typedef type_base<Key, Mapped, _Alloc, Store_Hash> type; 259 }; 260 261 /// Traits for abstract types. 262 template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash> 263 struct types_traits 264 : public type_dispatch<Key, Mapped, _Alloc, Store_Hash>::type 265 { 266 private: 267 typedef no_throw_copies<Key, Mapped> __nothrowcopy; 268 typedef typename _Alloc::template rebind<Key>::other __rebind_a; 269 270 public: 271 typedef typename _Alloc::size_type size_type; 272 typedef typename __rebind_a::value_type key_type; 273 typedef typename __rebind_a::pointer key_pointer; 274 typedef typename __rebind_a::const_pointer key_const_pointer; 275 typedef typename __rebind_a::reference key_reference; 276 typedef typename __rebind_a::const_reference key_const_reference; 277 typedef std::pair<size_type, size_type> comp_hash; 278 typedef integral_constant<int, Store_Hash> store_extra; 279 typedef typename __nothrowcopy::indicator no_throw_indicator; 280 281 store_extra m_store_extra_indicator; 282 no_throw_indicator m_no_throw_copies_indicator; 283 }; 284 //@} 285 } // namespace detail 286} // namespace __gnu_pbds 287 288#endif 289