1*38fd1498Szrj // -*- C++ -*- 2*38fd1498Szrj 3*38fd1498Szrj // Copyright (C) 2005-2018 Free Software Foundation, Inc. 4*38fd1498Szrj // 5*38fd1498Szrj // This file is part of the GNU ISO C++ Library. This library is free 6*38fd1498Szrj // software; you can redistribute it and/or modify it under the terms 7*38fd1498Szrj // of the GNU General Public License as published by the Free Software 8*38fd1498Szrj // Foundation; either version 3, or (at your option) any later 9*38fd1498Szrj // version. 10*38fd1498Szrj 11*38fd1498Szrj // This library is distributed in the hope that it will be useful, but 12*38fd1498Szrj // WITHOUT ANY WARRANTY; without even the implied warranty of 13*38fd1498Szrj // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14*38fd1498Szrj // General Public License for more details. 15*38fd1498Szrj 16*38fd1498Szrj // Under Section 7 of GPL version 3, you are granted additional 17*38fd1498Szrj // permissions described in the GCC Runtime Library Exception, version 18*38fd1498Szrj // 3.1, as published by the Free Software Foundation. 19*38fd1498Szrj 20*38fd1498Szrj // You should have received a copy of the GNU General Public License and 21*38fd1498Szrj // a copy of the GCC Runtime Library Exception along with this program; 22*38fd1498Szrj // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23*38fd1498Szrj // <http://www.gnu.org/licenses/>. 24*38fd1498Szrj 25*38fd1498Szrj // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26*38fd1498Szrj 27*38fd1498Szrj // Permission to use, copy, modify, sell, and distribute this software 28*38fd1498Szrj // is hereby granted without fee, provided that the above copyright 29*38fd1498Szrj // notice appears in all copies, and that both that copyright notice 30*38fd1498Szrj // and this permission notice appear in supporting documentation. None 31*38fd1498Szrj // of the above authors, nor IBM Haifa Research Laboratories, make any 32*38fd1498Szrj // representation about the suitability of this software for any 33*38fd1498Szrj // purpose. It is provided "as is" without express or implied 34*38fd1498Szrj // warranty. 35*38fd1498Szrj 36*38fd1498Szrj /** 37*38fd1498Szrj * @file container_base_dispatch.hpp 38*38fd1498Szrj * Contains associative container dispatching. 39*38fd1498Szrj */ 40*38fd1498Szrj 41*38fd1498Szrj #ifndef PB_DS_ASSOC_CNTNR_BASE_DS_DISPATCHER_HPP 42*38fd1498Szrj #define PB_DS_ASSOC_CNTNR_BASE_DS_DISPATCHER_HPP 43*38fd1498Szrj 44*38fd1498Szrj #include <ext/typelist.h> 45*38fd1498Szrj 46*38fd1498Szrj #define PB_DS_ASSERT_VALID(X) \ 47*38fd1498Szrj _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);) 48*38fd1498Szrj 49*38fd1498Szrj #define PB_DS_DEBUG_VERIFY(_Cond) \ 50*38fd1498Szrj _GLIBCXX_DEBUG_VERIFY_AT(_Cond, \ 51*38fd1498Szrj _M_message(#_Cond" assertion from %1;:%2;") \ 52*38fd1498Szrj ._M_string(__FILE__)._M_integer(__LINE__) \ 53*38fd1498Szrj ,__file,__line) 54*38fd1498Szrj 55*38fd1498Szrj #define PB_DS_CHECK_KEY_EXISTS(_Key) \ 56*38fd1498Szrj _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(_Key, __FILE__, __LINE__);) 57*38fd1498Szrj 58*38fd1498Szrj #define PB_DS_CHECK_KEY_DOES_NOT_EXIST(_Key) \ 59*38fd1498Szrj _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(_Key, \ 60*38fd1498Szrj __FILE__, __LINE__);) 61*38fd1498Szrj 62*38fd1498Szrj #define PB_DS_DATA_TRUE_INDICATOR 63*38fd1498Szrj #define PB_DS_V2F(X) (X).first 64*38fd1498Szrj #define PB_DS_V2S(X) (X).second 65*38fd1498Szrj #define PB_DS_EP2VP(X)& ((X)->m_value) 66*38fd1498Szrj #include <ext/pb_ds/detail/list_update_map_/lu_map_.hpp> 67*38fd1498Szrj #include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp> 68*38fd1498Szrj #include <ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp> 69*38fd1498Szrj #include <ext/pb_ds/detail/splay_tree_/splay_tree_.hpp> 70*38fd1498Szrj #include <ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp> 71*38fd1498Szrj #include <ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp> 72*38fd1498Szrj #include <ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp> 73*38fd1498Szrj #include <ext/pb_ds/detail/pat_trie_/pat_trie_.hpp> 74*38fd1498Szrj #undef PB_DS_DATA_TRUE_INDICATOR 75*38fd1498Szrj #undef PB_DS_V2F 76*38fd1498Szrj #undef PB_DS_V2S 77*38fd1498Szrj #undef PB_DS_EP2VP 78*38fd1498Szrj 79*38fd1498Szrj #define PB_DS_DATA_FALSE_INDICATOR 80*38fd1498Szrj #define PB_DS_V2F(X) (X) 81*38fd1498Szrj #define PB_DS_V2S(X) Mapped_Data() 82*38fd1498Szrj #define PB_DS_EP2VP(X)& ((X)->m_value.first) 83*38fd1498Szrj #include <ext/pb_ds/detail/list_update_map_/lu_map_.hpp> 84*38fd1498Szrj #include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp> 85*38fd1498Szrj #include <ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp> 86*38fd1498Szrj #include <ext/pb_ds/detail/splay_tree_/splay_tree_.hpp> 87*38fd1498Szrj #include <ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp> 88*38fd1498Szrj #include <ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp> 89*38fd1498Szrj #include <ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp> 90*38fd1498Szrj #include <ext/pb_ds/detail/pat_trie_/pat_trie_.hpp> 91*38fd1498Szrj #undef PB_DS_DATA_FALSE_INDICATOR 92*38fd1498Szrj #undef PB_DS_V2F 93*38fd1498Szrj #undef PB_DS_V2S 94*38fd1498Szrj #undef PB_DS_EP2VP 95*38fd1498Szrj 96*38fd1498Szrj #undef PB_DS_CHECK_KEY_DOES_NOT_EXIST 97*38fd1498Szrj #undef PB_DS_CHECK_KEY_EXISTS 98*38fd1498Szrj #undef PB_DS_DEBUG_VERIFY 99*38fd1498Szrj #undef PB_DS_ASSERT_VALID 100*38fd1498Szrj 101*38fd1498Szrj namespace __gnu_pbds 102*38fd1498Szrj { 103*38fd1498Szrj namespace detail 104*38fd1498Szrj { 105*38fd1498Szrj /// Specialization for list-update map. 106*38fd1498Szrj template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 107*38fd1498Szrj struct container_base_dispatch<Key, Mapped, _Alloc, list_update_tag, 108*38fd1498Szrj Policy_Tl> 109*38fd1498Szrj { 110*38fd1498Szrj private: 111*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 112*38fd1498Szrj typedef typename at0::type at0t; 113*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 114*38fd1498Szrj typedef typename at1::type at1t; 115*38fd1498Szrj 116*38fd1498Szrj public: 117*38fd1498Szrj /// Dispatched type. 118*38fd1498Szrj typedef lu_map<Key, Mapped, at0t, _Alloc, at1t> type; 119*38fd1498Szrj }; 120*38fd1498Szrj 121*38fd1498Szrj /// Specialization for list-update set. 122*38fd1498Szrj template<typename Key, typename _Alloc, typename Policy_Tl> 123*38fd1498Szrj struct container_base_dispatch<Key, null_type, _Alloc, list_update_tag, 124*38fd1498Szrj Policy_Tl> 125*38fd1498Szrj { 126*38fd1498Szrj private: 127*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 128*38fd1498Szrj typedef typename at0::type at0t; 129*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 130*38fd1498Szrj typedef typename at1::type at1t; 131*38fd1498Szrj 132*38fd1498Szrj public: 133*38fd1498Szrj /// Dispatched type. 134*38fd1498Szrj typedef lu_set<Key, null_type, at0t, _Alloc, at1t> type; 135*38fd1498Szrj }; 136*38fd1498Szrj 137*38fd1498Szrj /// Specialization for PATRICIA trie map. 138*38fd1498Szrj template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 139*38fd1498Szrj struct container_base_dispatch<Key, Mapped, _Alloc, pat_trie_tag, Policy_Tl> 140*38fd1498Szrj { 141*38fd1498Szrj private: 142*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 143*38fd1498Szrj typedef typename at1::type at1t; 144*38fd1498Szrj 145*38fd1498Szrj public: 146*38fd1498Szrj typedef pat_trie_map<Key, Mapped, at1t, _Alloc> type; 147*38fd1498Szrj }; 148*38fd1498Szrj 149*38fd1498Szrj /// Specialization for PATRICIA trie set. 150*38fd1498Szrj template<typename Key, typename _Alloc, typename Policy_Tl> 151*38fd1498Szrj struct container_base_dispatch<Key, null_type, _Alloc, pat_trie_tag, 152*38fd1498Szrj Policy_Tl> 153*38fd1498Szrj { 154*38fd1498Szrj private: 155*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 156*38fd1498Szrj typedef typename at1::type at1t; 157*38fd1498Szrj 158*38fd1498Szrj public: 159*38fd1498Szrj /// Dispatched type. 160*38fd1498Szrj typedef pat_trie_set<Key, null_type, at1t, _Alloc> type; 161*38fd1498Szrj }; 162*38fd1498Szrj 163*38fd1498Szrj /// Specialization for R-B tree map. 164*38fd1498Szrj template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 165*38fd1498Szrj struct container_base_dispatch<Key, Mapped, _Alloc, rb_tree_tag, Policy_Tl> 166*38fd1498Szrj { 167*38fd1498Szrj private: 168*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 169*38fd1498Szrj typedef typename at0::type at0t; 170*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 171*38fd1498Szrj typedef typename at1::type at1t; 172*38fd1498Szrj 173*38fd1498Szrj public: 174*38fd1498Szrj /// Dispatched type. 175*38fd1498Szrj typedef rb_tree_map<Key, Mapped, at0t, at1t, _Alloc> type; 176*38fd1498Szrj }; 177*38fd1498Szrj 178*38fd1498Szrj /// Specialization for R-B tree set. 179*38fd1498Szrj template<typename Key, typename _Alloc, typename Policy_Tl> 180*38fd1498Szrj struct container_base_dispatch<Key, null_type, _Alloc, rb_tree_tag, 181*38fd1498Szrj Policy_Tl> 182*38fd1498Szrj { 183*38fd1498Szrj private: 184*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 185*38fd1498Szrj typedef typename at0::type at0t; 186*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 187*38fd1498Szrj typedef typename at1::type at1t; 188*38fd1498Szrj 189*38fd1498Szrj public: 190*38fd1498Szrj typedef rb_tree_set<Key, null_type, at0t, at1t, _Alloc> type; 191*38fd1498Szrj }; 192*38fd1498Szrj 193*38fd1498Szrj /// Specialization splay tree map. 194*38fd1498Szrj template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 195*38fd1498Szrj struct container_base_dispatch<Key, Mapped, _Alloc, splay_tree_tag, 196*38fd1498Szrj Policy_Tl> 197*38fd1498Szrj { 198*38fd1498Szrj private: 199*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 200*38fd1498Szrj typedef typename at0::type at0t; 201*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 202*38fd1498Szrj typedef typename at1::type at1t; 203*38fd1498Szrj 204*38fd1498Szrj public: 205*38fd1498Szrj /// Dispatched type. 206*38fd1498Szrj typedef splay_tree_map<Key, Mapped, at0t, at1t, _Alloc> type; 207*38fd1498Szrj }; 208*38fd1498Szrj 209*38fd1498Szrj /// Specialization splay tree set. 210*38fd1498Szrj template<typename Key, typename _Alloc, typename Policy_Tl> 211*38fd1498Szrj struct container_base_dispatch<Key, null_type, _Alloc, splay_tree_tag, 212*38fd1498Szrj Policy_Tl> 213*38fd1498Szrj { 214*38fd1498Szrj private: 215*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 216*38fd1498Szrj typedef typename at0::type at0t; 217*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 218*38fd1498Szrj typedef typename at1::type at1t; 219*38fd1498Szrj 220*38fd1498Szrj public: 221*38fd1498Szrj /// Dispatched type. 222*38fd1498Szrj typedef splay_tree_set<Key, null_type, at0t, at1t, _Alloc> type; 223*38fd1498Szrj }; 224*38fd1498Szrj 225*38fd1498Szrj /// Specialization ordered-vector tree map. 226*38fd1498Szrj template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 227*38fd1498Szrj struct container_base_dispatch<Key, Mapped, _Alloc, ov_tree_tag, Policy_Tl> 228*38fd1498Szrj { 229*38fd1498Szrj private: 230*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 231*38fd1498Szrj typedef typename at0::type at0t; 232*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 233*38fd1498Szrj typedef typename at1::type at1t; 234*38fd1498Szrj 235*38fd1498Szrj public: 236*38fd1498Szrj /// Dispatched type. 237*38fd1498Szrj typedef ov_tree_map<Key, Mapped, at0t, at1t, _Alloc> type; 238*38fd1498Szrj }; 239*38fd1498Szrj 240*38fd1498Szrj /// Specialization ordered-vector tree set. 241*38fd1498Szrj template<typename Key, typename _Alloc, typename Policy_Tl> 242*38fd1498Szrj struct container_base_dispatch<Key, null_type, _Alloc, ov_tree_tag, 243*38fd1498Szrj Policy_Tl> 244*38fd1498Szrj { 245*38fd1498Szrj private: 246*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 247*38fd1498Szrj typedef typename at0::type at0t; 248*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 249*38fd1498Szrj typedef typename at1::type at1t; 250*38fd1498Szrj 251*38fd1498Szrj public: 252*38fd1498Szrj /// Dispatched type. 253*38fd1498Szrj typedef ov_tree_set<Key, null_type, at0t, at1t, _Alloc> type; 254*38fd1498Szrj }; 255*38fd1498Szrj 256*38fd1498Szrj /// Specialization colision-chaining hash map. 257*38fd1498Szrj template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 258*38fd1498Szrj struct container_base_dispatch<Key, Mapped, _Alloc, cc_hash_tag, Policy_Tl> 259*38fd1498Szrj { 260*38fd1498Szrj private: 261*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 262*38fd1498Szrj typedef typename at0::type at0t; 263*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 264*38fd1498Szrj typedef typename at1::type at1t; 265*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2> at2; 266*38fd1498Szrj typedef typename at2::type at2t; 267*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3> at3; 268*38fd1498Szrj typedef typename at3::type at3t; 269*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> at4; 270*38fd1498Szrj typedef typename at4::type at4t; 271*38fd1498Szrj 272*38fd1498Szrj public: 273*38fd1498Szrj /// Dispatched type. 274*38fd1498Szrj typedef cc_ht_map<Key, Mapped, at0t, at1t, _Alloc, 275*38fd1498Szrj at3t::value, at4t, at2t> type; 276*38fd1498Szrj }; 277*38fd1498Szrj 278*38fd1498Szrj /// Specialization colision-chaining hash set. 279*38fd1498Szrj template<typename Key, typename _Alloc, typename Policy_Tl> 280*38fd1498Szrj struct container_base_dispatch<Key, null_type, _Alloc, cc_hash_tag, 281*38fd1498Szrj Policy_Tl> 282*38fd1498Szrj { 283*38fd1498Szrj private: 284*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 285*38fd1498Szrj typedef typename at0::type at0t; 286*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 287*38fd1498Szrj typedef typename at1::type at1t; 288*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2> at2; 289*38fd1498Szrj typedef typename at2::type at2t; 290*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3> at3; 291*38fd1498Szrj typedef typename at3::type at3t; 292*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> at4; 293*38fd1498Szrj typedef typename at4::type at4t; 294*38fd1498Szrj 295*38fd1498Szrj public: 296*38fd1498Szrj /// Dispatched type. 297*38fd1498Szrj typedef cc_ht_set<Key, null_type, at0t, at1t, _Alloc, 298*38fd1498Szrj at3t::value, at4t, at2t> type; 299*38fd1498Szrj }; 300*38fd1498Szrj 301*38fd1498Szrj /// Specialization general-probe hash map. 302*38fd1498Szrj template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl> 303*38fd1498Szrj struct container_base_dispatch<Key, Mapped, _Alloc, gp_hash_tag, Policy_Tl> 304*38fd1498Szrj { 305*38fd1498Szrj private: 306*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 307*38fd1498Szrj typedef typename at0::type at0t; 308*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 309*38fd1498Szrj typedef typename at1::type at1t; 310*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2> at2; 311*38fd1498Szrj typedef typename at2::type at2t; 312*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3> at3; 313*38fd1498Szrj typedef typename at3::type at3t; 314*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> at4; 315*38fd1498Szrj typedef typename at4::type at4t; 316*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 5> at5; 317*38fd1498Szrj typedef typename at5::type at5t; 318*38fd1498Szrj 319*38fd1498Szrj public: 320*38fd1498Szrj /// Dispatched type. 321*38fd1498Szrj typedef gp_ht_map<Key, Mapped, at0t, at1t, _Alloc, 322*38fd1498Szrj at3t::value, at4t, at5t, at2t> type; 323*38fd1498Szrj }; 324*38fd1498Szrj 325*38fd1498Szrj /// Specialization general-probe hash set. 326*38fd1498Szrj template<typename Key, typename _Alloc, typename Policy_Tl> 327*38fd1498Szrj struct container_base_dispatch<Key, null_type, _Alloc, gp_hash_tag, 328*38fd1498Szrj Policy_Tl> 329*38fd1498Szrj { 330*38fd1498Szrj private: 331*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0> at0; 332*38fd1498Szrj typedef typename at0::type at0t; 333*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> at1; 334*38fd1498Szrj typedef typename at1::type at1t; 335*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2> at2; 336*38fd1498Szrj typedef typename at2::type at2t; 337*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3> at3; 338*38fd1498Szrj typedef typename at3::type at3t; 339*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> at4; 340*38fd1498Szrj typedef typename at4::type at4t; 341*38fd1498Szrj typedef __gnu_cxx::typelist::at_index<Policy_Tl, 5> at5; 342*38fd1498Szrj typedef typename at5::type at5t; 343*38fd1498Szrj 344*38fd1498Szrj public: 345*38fd1498Szrj /// Dispatched type. 346*38fd1498Szrj typedef gp_ht_set<Key, null_type, at0t, at1t, _Alloc, 347*38fd1498Szrj at3t::value, at4t, at5t, at2t> type; 348*38fd1498Szrj }; 349*38fd1498Szrj } // namespace detail 350*38fd1498Szrj } // namespace __gnu_pbds 351*38fd1498Szrj 352*38fd1498Szrj #endif 353