libstdc++-v3/include/ext/pb_ds/detail/container_base_dispatch.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2020 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