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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file basic_types.hpp
  44  * Contains basic types used by containers.
  45  */
  46
  47 #ifndef PB_DS_BASIC_TYPES_HPP
  48 #define PB_DS_BASIC_TYPES_HPP
  49
  50 #include <algorithm>
  51 #include <utility>
  52 #include <ext/pb_ds/tag_and_trait.hpp>
  53 #include <ext/pb_ds/detail/type_utils.hpp>
  54
  55 namespace __gnu_pbds
  56 {
  57   namespace detail
  58   {
  59     template<typename Key, typename Mapped, typename Allocator, bool Store_Hash>
  60     struct value_type_base;
  61
  62     /**
  63      * Specialization of value_type_base for the case where the hash value
  64      * is not stored alongside each value.
  65      **/
  66     template<typename Key, typename Mapped, typename Allocator>
  67     struct value_type_base<Key, Mapped, Allocator, false>
  68     {
  69       typedef typename Allocator::template rebind<Mapped>::other mapped_type_allocator;
  70       typedef typename mapped_type_allocator::value_type mapped_type;
  71       typedef typename mapped_type_allocator::pointer mapped_pointer;
  72       typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
  73       typedef typename mapped_type_allocator::reference mapped_reference;
  74       typedef typename mapped_type_allocator::const_reference const_mapped_reference;
  75
  76       typedef typename Allocator::template rebind<std::pair<const Key, Mapped> >::other value_type_allocator;
  77       typedef typename value_type_allocator::value_type value_type;
  78       typedef typename value_type_allocator::pointer pointer;
  79       typedef typename value_type_allocator::const_pointer const_pointer;
  80       typedef typename value_type_allocator::reference reference;
  81       typedef typename value_type_allocator::const_reference const_reference;
  82
  83       struct stored_value_type
  84       {
  85         value_type m_value;
  86       };
  87     };
  88
  89     /**
  90      * Specialization of value_type_base for the case where the hash value
  91      * is stored alongside each value.
  92      **/
  93     template<typename Key, typename Mapped, typename Allocator>
  94     struct value_type_base<Key, Mapped, Allocator, true>
  95     {
  96       typedef typename Allocator::template rebind<Mapped>::other mapped_type_allocator;
  97       typedef typename mapped_type_allocator::value_type mapped_type;
  98       typedef typename mapped_type_allocator::pointer mapped_pointer;
  99       typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
 100       typedef typename mapped_type_allocator::reference mapped_reference;
 101       typedef typename mapped_type_allocator::const_reference const_mapped_reference;
 102
 103       typedef typename Allocator::template rebind<std::pair<const Key, Mapped> >::other value_type_allocator;
 104       typedef typename value_type_allocator::value_type value_type;
 105       typedef typename value_type_allocator::pointer pointer;
 106       typedef typename value_type_allocator::const_pointer const_pointer;
 107       typedef typename value_type_allocator::reference reference;
 108       typedef typename value_type_allocator::const_reference const_reference;
 109
 110       struct stored_value_type
 111       {
 112         value_type m_value;
 113         typename Allocator::size_type m_hash;
 114       };
 115     };
 116
 117 #define PB_DS_CLASS_T_DEC \
 118     template<typename Key, typename Allocator>
 119
 120 #define PB_DS_CLASS_C_DEC \
 121     value_type_base<Key, null_mapped_type, Allocator, false>
 122
 123     /**
 124      * Specialization of value_type_base for the case where the hash value
 125      * is not stored alongside each value.
 126      **/
 127     template<typename Key, typename Allocator>
 128     struct value_type_base<Key, null_mapped_type, Allocator, false>
 129     {
 130       typedef typename Allocator::template rebind<null_mapped_type>::other mapped_type_allocator;
 131       typedef typename mapped_type_allocator::value_type mapped_type;
 132       typedef typename mapped_type_allocator::pointer mapped_pointer;
 133       typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
 134       typedef typename mapped_type_allocator::reference mapped_reference;
 135       typedef typename mapped_type_allocator::const_reference const_mapped_reference;
 136
 137       typedef Key value_type;
 138
 139       typedef typename Allocator::template rebind<value_type>::other value_type_allocator;
 140       typedef typename value_type_allocator::pointer pointer;
 141       typedef typename value_type_allocator::const_pointer const_pointer;
 142       typedef typename value_type_allocator::reference reference;
 143       typedef typename value_type_allocator::const_reference const_reference;
 144
 145       struct stored_value_type
 146       {
 147         value_type m_value;
 148       };
 149
 150       static null_mapped_type s_null_mapped;
 151     };
 152
 153     PB_DS_CLASS_T_DEC
 154     null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped;
 155
 156 #undef PB_DS_CLASS_T_DEC
 157 #undef PB_DS_CLASS_C_DEC
 158
 159 #define PB_DS_CLASS_T_DEC \
 160     template<typename Key, typename Allocator>
 161
 162 #define PB_DS_CLASS_C_DEC \
 163     value_type_base<Key, null_mapped_type, Allocator, true>
 164
 165     /**
 166      * Specialization of value_type_base for the case where the hash value
 167      * is stored alongside each value.
 168      **/
 169     template<typename Key, typename Allocator>
 170     struct value_type_base<Key, null_mapped_type, Allocator, true>
 171     {
 172       typedef typename Allocator::template rebind<null_mapped_type>::other mapped_type_allocator;
 173       typedef typename mapped_type_allocator::value_type mapped_type;
 174       typedef typename mapped_type_allocator::pointer mapped_pointer;
 175       typedef typename mapped_type_allocator::const_pointer const_mapped_pointer;
 176       typedef typename mapped_type_allocator::reference mapped_reference;
 177       typedef typename mapped_type_allocator::const_reference const_mapped_reference;
 178
 179       typedef Key value_type;
 180
 181       typedef typename Allocator::template rebind<value_type>::other value_type_allocator;
 182       typedef typename value_type_allocator::pointer pointer;
 183       typedef typename value_type_allocator::const_pointer const_pointer;
 184       typedef typename value_type_allocator::reference reference;
 185       typedef typename value_type_allocator::const_reference const_reference;
 186
 187       struct stored_value_type
 188       {
 189         value_type m_value;
 190         typename Allocator::size_type m_hash;
 191       };
 192
 193       static null_mapped_type s_null_mapped;
 194     };
 195
 196     PB_DS_CLASS_T_DEC
 197     null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped;
 198
 199 #undef PB_DS_CLASS_T_DEC
 200 #undef PB_DS_CLASS_C_DEC
 201
 202     template<typename Key, typename Mapped>
 203     struct no_throw_copies
 204     {
 205       typedef integral_constant<int, is_simple<Key>::value && is_simple<Mapped>::value> indicator;
 206     };
 207
 208     template<typename Key>
 209     struct no_throw_copies<Key, null_mapped_type>
 210     {
 211       typedef integral_constant<int, is_simple<Key>::value> indicator;
 212     };
 213   } // namespace detail
 214 } // namespace __gnu_pbds
 215
 216 #endif
 217