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 55namespace pb_ds 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 pb_ds 215 216#endif 217 218