1// -*- C++ -*- 2 3// Copyright (C) 2005-2015 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 container_base_dispatch.hpp 38 * Contains associative container dispatching. 39 */ 40 41#ifndef PB_DS_ASSOC_CNTNR_BASE_DS_DISPATCHER_HPP 42#define PB_DS_ASSOC_CNTNR_BASE_DS_DISPATCHER_HPP 43 44#include <ext/typelist.h> 45 46#define PB_DS_ASSERT_VALID(X) \ 47 _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);) 48 49#define PB_DS_DEBUG_VERIFY(_Cond) \ 50 _GLIBCXX_DEBUG_VERIFY_AT(_Cond, \ 51 _M_message(#_Cond" assertion from %1;:%2;") \ 52 ._M_string(__FILE__)._M_integer(__LINE__) \ 53 ,__file,__line) 54 55#define PB_DS_CHECK_KEY_EXISTS(_Key) \ 56 _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(_Key, __FILE__, __LINE__);) 57 58#define PB_DS_CHECK_KEY_DOES_NOT_EXIST(_Key) \ 59 _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(_Key, \ 60 __FILE__, __LINE__);) 61 62#define PB_DS_DATA_TRUE_INDICATOR 63#define PB_DS_V2F(X) (X).first 64#define PB_DS_V2S(X) (X).second 65#define PB_DS_EP2VP(X)& ((X)->m_value) 66#include <ext/pb_ds/detail/list_update_map_/lu_map_.hpp> 67#include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp> 68#include <ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp> 69#include <ext/pb_ds/detail/splay_tree_/splay_tree_.hpp> 70#include <ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp> 71#include <ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp> 72#include <ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp> 73#include <ext/pb_ds/detail/pat_trie_/pat_trie_.hpp> 74#undef PB_DS_DATA_TRUE_INDICATOR 75#undef PB_DS_V2F 76#undef PB_DS_V2S 77#undef PB_DS_EP2VP 78 79#define PB_DS_DATA_FALSE_INDICATOR 80#define PB_DS_V2F(X) (X) 81#define PB_DS_V2S(X) Mapped_Data() 82#define PB_DS_EP2VP(X)& ((X)->m_value.first) 83#include <ext/pb_ds/detail/list_update_map_/lu_map_.hpp> 84#include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp> 85#include <ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp> 86#include <ext/pb_ds/detail/splay_tree_/splay_tree_.hpp> 87#include <ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp> 88#include <ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp> 89#include <ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp> 90#include <ext/pb_ds/detail/pat_trie_/pat_trie_.hpp> 91#undef PB_DS_DATA_FALSE_INDICATOR 92#undef PB_DS_V2F 93#undef PB_DS_V2S 94#undef PB_DS_EP2VP 95 96#undef PB_DS_CHECK_KEY_DOES_NOT_EXIST 97#undef PB_DS_CHECK_KEY_EXISTS 98#undef PB_DS_DEBUG_VERIFY 99#undef PB_DS_ASSERT_VALID 100 101namespace __gnu_pbds 102{ 103namespace detail 104{ 105 /// Specialization for list-update map. 106 template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 107 struct container_base_dispatch<Key, Mapped, _Alloc, list_update_tag, 108 Policy_Tl> 109 { 110 private: 111 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 112 typedef typename at0::type at0t; 113 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 114 typedef typename at1::type at1t; 115 116 public: 117 /// Dispatched type. 118 typedef lu_map<Key, Mapped, at0t, _Alloc, at1t> type; 119 }; 120 121 /// Specialization for list-update set. 122 template<typename Key, typename _Alloc, typename Policy_Tl> 123 struct container_base_dispatch<Key, null_type, _Alloc, list_update_tag, 124 Policy_Tl> 125 { 126 private: 127 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 128 typedef typename at0::type at0t; 129 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 130 typedef typename at1::type at1t; 131 132 public: 133 /// Dispatched type. 134 typedef lu_set<Key, null_type, at0t, _Alloc, at1t> type; 135 }; 136 137 /// Specialization for PATRICIA trie map. 138 template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 139 struct container_base_dispatch<Key, Mapped, _Alloc, pat_trie_tag, Policy_Tl> 140 { 141 private: 142 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 143 typedef typename at1::type at1t; 144 145 public: 146 typedef pat_trie_map<Key, Mapped, at1t, _Alloc> type; 147 }; 148 149 /// Specialization for PATRICIA trie set. 150 template<typename Key, typename _Alloc, typename Policy_Tl> 151 struct container_base_dispatch<Key, null_type, _Alloc, pat_trie_tag, 152 Policy_Tl> 153 { 154 private: 155 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 156 typedef typename at1::type at1t; 157 158 public: 159 /// Dispatched type. 160 typedef pat_trie_set<Key, null_type, at1t, _Alloc> type; 161 }; 162 163 /// Specialization for R-B tree map. 164 template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 165 struct container_base_dispatch<Key, Mapped, _Alloc, rb_tree_tag, Policy_Tl> 166 { 167 private: 168 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 169 typedef typename at0::type at0t; 170 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 171 typedef typename at1::type at1t; 172 173 public: 174 /// Dispatched type. 175 typedef rb_tree_map<Key, Mapped, at0t, at1t, _Alloc> type; 176 }; 177 178 /// Specialization for R-B tree set. 179 template<typename Key, typename _Alloc, typename Policy_Tl> 180 struct container_base_dispatch<Key, null_type, _Alloc, rb_tree_tag, 181 Policy_Tl> 182 { 183 private: 184 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 185 typedef typename at0::type at0t; 186 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 187 typedef typename at1::type at1t; 188 189 public: 190 typedef rb_tree_set<Key, null_type, at0t, at1t, _Alloc> type; 191 }; 192 193 /// Specialization splay tree map. 194 template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 195 struct container_base_dispatch<Key, Mapped, _Alloc, splay_tree_tag, 196 Policy_Tl> 197 { 198 private: 199 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 200 typedef typename at0::type at0t; 201 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 202 typedef typename at1::type at1t; 203 204 public: 205 /// Dispatched type. 206 typedef splay_tree_map<Key, Mapped, at0t, at1t, _Alloc> type; 207 }; 208 209 /// Specialization splay tree set. 210 template<typename Key, typename _Alloc, typename Policy_Tl> 211 struct container_base_dispatch<Key, null_type, _Alloc, splay_tree_tag, 212 Policy_Tl> 213 { 214 private: 215 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 216 typedef typename at0::type at0t; 217 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 218 typedef typename at1::type at1t; 219 220 public: 221 /// Dispatched type. 222 typedef splay_tree_set<Key, null_type, at0t, at1t, _Alloc> type; 223 }; 224 225 /// Specialization ordered-vector tree map. 226 template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 227 struct container_base_dispatch<Key, Mapped, _Alloc, ov_tree_tag, Policy_Tl> 228 { 229 private: 230 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 231 typedef typename at0::type at0t; 232 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 233 typedef typename at1::type at1t; 234 235 public: 236 /// Dispatched type. 237 typedef ov_tree_map<Key, Mapped, at0t, at1t, _Alloc> type; 238 }; 239 240 /// Specialization ordered-vector tree set. 241 template<typename Key, typename _Alloc, typename Policy_Tl> 242 struct container_base_dispatch<Key, null_type, _Alloc, ov_tree_tag, 243 Policy_Tl> 244 { 245 private: 246 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 247 typedef typename at0::type at0t; 248 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 249 typedef typename at1::type at1t; 250 251 public: 252 /// Dispatched type. 253 typedef ov_tree_set<Key, null_type, at0t, at1t, _Alloc> type; 254 }; 255 256 /// Specialization colision-chaining hash map. 257 template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 258 struct container_base_dispatch<Key, Mapped, _Alloc, cc_hash_tag, Policy_Tl> 259 { 260 private: 261 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 262 typedef typename at0::type at0t; 263 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 264 typedef typename at1::type at1t; 265 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2> at2; 266 typedef typename at2::type at2t; 267 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3> at3; 268 typedef typename at3::type at3t; 269 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> at4; 270 typedef typename at4::type at4t; 271 272 public: 273 /// Dispatched type. 274 typedef cc_ht_map<Key, Mapped, at0t, at1t, _Alloc, 275 at3t::value, at4t, at2t> type; 276 }; 277 278 /// Specialization colision-chaining hash set. 279 template<typename Key, typename _Alloc, typename Policy_Tl> 280 struct container_base_dispatch<Key, null_type, _Alloc, cc_hash_tag, 281 Policy_Tl> 282 { 283 private: 284 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 285 typedef typename at0::type at0t; 286 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 287 typedef typename at1::type at1t; 288 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2> at2; 289 typedef typename at2::type at2t; 290 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3> at3; 291 typedef typename at3::type at3t; 292 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> at4; 293 typedef typename at4::type at4t; 294 295 public: 296 /// Dispatched type. 297 typedef cc_ht_set<Key, null_type, at0t, at1t, _Alloc, 298 at3t::value, at4t, at2t> type; 299 }; 300 301 /// Specialization general-probe hash map. 302 template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 303 struct container_base_dispatch<Key, Mapped, _Alloc, gp_hash_tag, Policy_Tl> 304 { 305 private: 306 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 307 typedef typename at0::type at0t; 308 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 309 typedef typename at1::type at1t; 310 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2> at2; 311 typedef typename at2::type at2t; 312 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3> at3; 313 typedef typename at3::type at3t; 314 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> at4; 315 typedef typename at4::type at4t; 316 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 5> at5; 317 typedef typename at5::type at5t; 318 319 public: 320 /// Dispatched type. 321 typedef gp_ht_map<Key, Mapped, at0t, at1t, _Alloc, 322 at3t::value, at4t, at5t, at2t> type; 323 }; 324 325 /// Specialization general-probe hash set. 326 template<typename Key, typename _Alloc, typename Policy_Tl> 327 struct container_base_dispatch<Key, null_type, _Alloc, gp_hash_tag, 328 Policy_Tl> 329 { 330 private: 331 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 332 typedef typename at0::type at0t; 333 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 334 typedef typename at1::type at1t; 335 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2> at2; 336 typedef typename at2::type at2t; 337 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3> at3; 338 typedef typename at3::type at3t; 339 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> at4; 340 typedef typename at4::type at4t; 341 typedef __gnu_cxx::typelist::at_index<Policy_Tl, 5> at5; 342 typedef typename at5::type at5t; 343 344 public: 345 /// Dispatched type. 346 typedef gp_ht_set<Key, null_type, at0t, at1t, _Alloc, 347 at3t::value, at4t, at5t, at2t> type; 348 }; 349} // namespace detail 350} // namespace __gnu_pbds 351 352#endif 353