libstdc++-v3/include/ext/pb_ds/detail/types_traits.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009, 2011 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
  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>
  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