1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2013 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 101 namespace __gnu_pbds 102 { 103 namespace 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
