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 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