1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2009 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 basic_types.hpp 38 * Contains basic types used by containers. 39 */ 40 41#ifndef PB_DS_BASIC_TYPES_HPP 42#define PB_DS_BASIC_TYPES_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 49namespace __gnu_pbds 50{ 51 namespace detail 52 { 53 template<typename Key, typename Mapped, typename Allocator, bool Store_Hash> 54 struct value_type_base; 55 56 /** 57 * Specialization of value_type_base for the case where the hash value 58 * is not stored alongside each value. 59 **/ 60 template<typename Key, typename Mapped, typename Allocator> 61 struct value_type_base<Key, Mapped, Allocator, false> 62 { 63 typedef typename Allocator::template rebind<Mapped>::other mapped_type_allocator; 64 typedef typename mapped_type_allocator::value_type mapped_type; 65 typedef typename mapped_type_allocator::pointer mapped_pointer; 66 typedef typename mapped_type_allocator::const_pointer const_mapped_pointer; 67 typedef typename mapped_type_allocator::reference mapped_reference; 68 typedef typename mapped_type_allocator::const_reference const_mapped_reference; 69 70 typedef typename Allocator::template rebind<std::pair<const Key, Mapped> >::other value_type_allocator; 71 typedef typename value_type_allocator::value_type value_type; 72 typedef typename value_type_allocator::pointer pointer; 73 typedef typename value_type_allocator::const_pointer const_pointer; 74 typedef typename value_type_allocator::reference reference; 75 typedef typename value_type_allocator::const_reference const_reference; 76 77 struct stored_value_type 78 { 79 value_type m_value; 80 }; 81 }; 82 83 /** 84 * Specialization of value_type_base for the case where the hash value 85 * is stored alongside each value. 86 **/ 87 template<typename Key, typename Mapped, typename Allocator> 88 struct value_type_base<Key, Mapped, Allocator, true> 89 { 90 typedef typename Allocator::template rebind<Mapped>::other mapped_type_allocator; 91 typedef typename mapped_type_allocator::value_type mapped_type; 92 typedef typename mapped_type_allocator::pointer mapped_pointer; 93 typedef typename mapped_type_allocator::const_pointer const_mapped_pointer; 94 typedef typename mapped_type_allocator::reference mapped_reference; 95 typedef typename mapped_type_allocator::const_reference const_mapped_reference; 96 97 typedef typename Allocator::template rebind<std::pair<const Key, Mapped> >::other value_type_allocator; 98 typedef typename value_type_allocator::value_type value_type; 99 typedef typename value_type_allocator::pointer pointer; 100 typedef typename value_type_allocator::const_pointer const_pointer; 101 typedef typename value_type_allocator::reference reference; 102 typedef typename value_type_allocator::const_reference const_reference; 103 104 struct stored_value_type 105 { 106 value_type m_value; 107 typename Allocator::size_type m_hash; 108 }; 109 }; 110 111#define PB_DS_CLASS_T_DEC \ 112 template<typename Key, typename Allocator> 113 114#define PB_DS_CLASS_C_DEC \ 115 value_type_base<Key, null_mapped_type, Allocator, false> 116 117 /** 118 * Specialization of value_type_base for the case where the hash value 119 * is not stored alongside each value. 120 **/ 121 template<typename Key, typename Allocator> 122 struct value_type_base<Key, null_mapped_type, Allocator, false> 123 { 124 typedef typename Allocator::template rebind<null_mapped_type>::other mapped_type_allocator; 125 typedef typename mapped_type_allocator::value_type mapped_type; 126 typedef typename mapped_type_allocator::pointer mapped_pointer; 127 typedef typename mapped_type_allocator::const_pointer const_mapped_pointer; 128 typedef typename mapped_type_allocator::reference mapped_reference; 129 typedef typename mapped_type_allocator::const_reference const_mapped_reference; 130 131 typedef Key value_type; 132 133 typedef typename Allocator::template rebind<value_type>::other value_type_allocator; 134 typedef typename value_type_allocator::pointer pointer; 135 typedef typename value_type_allocator::const_pointer const_pointer; 136 typedef typename value_type_allocator::reference reference; 137 typedef typename value_type_allocator::const_reference const_reference; 138 139 struct stored_value_type 140 { 141 value_type m_value; 142 }; 143 144 static null_mapped_type s_null_mapped; 145 }; 146 147 PB_DS_CLASS_T_DEC 148 null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped; 149 150#undef PB_DS_CLASS_T_DEC 151#undef PB_DS_CLASS_C_DEC 152 153#define PB_DS_CLASS_T_DEC \ 154 template<typename Key, typename Allocator> 155 156#define PB_DS_CLASS_C_DEC \ 157 value_type_base<Key, null_mapped_type, Allocator, true> 158 159 /** 160 * Specialization of value_type_base for the case where the hash value 161 * is stored alongside each value. 162 **/ 163 template<typename Key, typename Allocator> 164 struct value_type_base<Key, null_mapped_type, Allocator, true> 165 { 166 typedef typename Allocator::template rebind<null_mapped_type>::other mapped_type_allocator; 167 typedef typename mapped_type_allocator::value_type mapped_type; 168 typedef typename mapped_type_allocator::pointer mapped_pointer; 169 typedef typename mapped_type_allocator::const_pointer const_mapped_pointer; 170 typedef typename mapped_type_allocator::reference mapped_reference; 171 typedef typename mapped_type_allocator::const_reference const_mapped_reference; 172 173 typedef Key value_type; 174 175 typedef typename Allocator::template rebind<value_type>::other value_type_allocator; 176 typedef typename value_type_allocator::pointer pointer; 177 typedef typename value_type_allocator::const_pointer const_pointer; 178 typedef typename value_type_allocator::reference reference; 179 typedef typename value_type_allocator::const_reference const_reference; 180 181 struct stored_value_type 182 { 183 value_type m_value; 184 typename Allocator::size_type m_hash; 185 }; 186 187 static null_mapped_type s_null_mapped; 188 }; 189 190 PB_DS_CLASS_T_DEC 191 null_mapped_type PB_DS_CLASS_C_DEC::s_null_mapped; 192 193#undef PB_DS_CLASS_T_DEC 194#undef PB_DS_CLASS_C_DEC 195 196 template<typename Key, typename Mapped> 197 struct no_throw_copies 198 { 199 typedef integral_constant<int, is_simple<Key>::value && is_simple<Mapped>::value> indicator; 200 }; 201 202 template<typename Key> 203 struct no_throw_copies<Key, null_mapped_type> 204 { 205 typedef integral_constant<int, is_simple<Key>::value> indicator; 206 }; 207 } // namespace detail 208} // namespace __gnu_pbds 209 210#endif 211 212