3 // Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
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
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.
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.
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/>.
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
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
37 * @file container_base_dispatch.hpp
38 * Contains an associative container dispatching base.
41 #ifndef PB_DS_ASSOC_CNTNR_BASE_DS_DISPATCHER_HPP
42 #define PB_DS_ASSOC_CNTNR_BASE_DS_DISPATCHER_HPP
44 #include <ext/typelist.h>
46 #define PB_DS_ASSERT_VALID(X) \
47 _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
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__) \
55 #define PB_DS_CHECK_KEY_EXISTS(_Key) \
56 _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(_Key, __FILE__, __LINE__);)
58 #define PB_DS_CHECK_KEY_DOES_NOT_EXIST(_Key) \
59 _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(_Key, \
62 #define PB_DS_DATA_TRUE_INDICATOR
63 #include <ext/pb_ds/detail/list_update_map_/lu_map_.hpp>
64 #undef PB_DS_DATA_TRUE_INDICATOR
66 #define PB_DS_DATA_FALSE_INDICATOR
67 #include <ext/pb_ds/detail/list_update_map_/lu_map_.hpp>
68 #undef PB_DS_DATA_FALSE_INDICATOR
70 #define PB_DS_DATA_TRUE_INDICATOR
71 #include <ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp>
72 #undef PB_DS_DATA_TRUE_INDICATOR
74 #define PB_DS_DATA_FALSE_INDICATOR
75 #include <ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp>
76 #undef PB_DS_DATA_FALSE_INDICATOR
78 #define PB_DS_DATA_TRUE_INDICATOR
79 #include <ext/pb_ds/detail/splay_tree_/splay_tree_.hpp>
80 #undef PB_DS_DATA_TRUE_INDICATOR
82 #define PB_DS_DATA_FALSE_INDICATOR
83 #include <ext/pb_ds/detail/splay_tree_/splay_tree_.hpp>
84 #undef PB_DS_DATA_FALSE_INDICATOR
86 #define PB_DS_DATA_TRUE_INDICATOR
87 #include <ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp>
88 #undef PB_DS_DATA_TRUE_INDICATOR
90 #define PB_DS_DATA_FALSE_INDICATOR
91 #include <ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp>
92 #undef PB_DS_DATA_FALSE_INDICATOR
94 #define PB_DS_DATA_TRUE_INDICATOR
95 #include <ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp>
96 #undef PB_DS_DATA_TRUE_INDICATOR
98 #define PB_DS_DATA_FALSE_INDICATOR
99 #include <ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp>
100 #undef PB_DS_DATA_FALSE_INDICATOR
102 #define PB_DS_DATA_TRUE_INDICATOR
103 #include <ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp>
104 #undef PB_DS_DATA_TRUE_INDICATOR
106 #define PB_DS_DATA_FALSE_INDICATOR
107 #include <ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp>
108 #undef PB_DS_DATA_FALSE_INDICATOR
110 #define PB_DS_DATA_TRUE_INDICATOR
111 #include <ext/pb_ds/detail/pat_trie_/pat_trie_.hpp>
112 #undef PB_DS_DATA_TRUE_INDICATOR
114 #define PB_DS_DATA_FALSE_INDICATOR
115 #include <ext/pb_ds/detail/pat_trie_/pat_trie_.hpp>
116 #undef PB_DS_DATA_FALSE_INDICATOR
118 #undef PB_DS_CHECK_KEY_DOES_NOT_EXIST
119 #undef PB_DS_CHECK_KEY_EXISTS
120 #undef PB_DS_DEBUG_VERIFY
121 #undef PB_DS_ASSERT_VALID
128 template<typename Key
, typename Mapped
, typename Data_Structure_Taq
,
129 typename Policy_Tl
, typename Alloc
>
130 struct container_base_dispatch
;
132 template<typename Key
, typename Mapped
, typename Policy_Tl
, typename Alloc
>
133 struct container_base_dispatch
<Key
, Mapped
, list_update_tag
,
137 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 0> at0
;
138 typedef typename
at0::type at0t
;
139 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 1> at1
;
140 typedef typename
at1::type at1t
;
143 typedef lu_map_data_
<Key
, Mapped
, at0t
, Alloc
, at1t
> type
;
146 template<typename Key
, typename Policy_Tl
, typename Alloc
>
147 struct container_base_dispatch
<Key
, null_mapped_type
, list_update_tag
,
151 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 0> at0
;
152 typedef typename
at0::type at0t
;
153 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 1> at1
;
154 typedef typename
at1::type at1t
;
157 typedef lu_map_no_data_
<Key
, null_mapped_type
, at0t
, Alloc
, at1t
> type
;
160 template<typename Key
, typename Mapped
, typename Policy_Tl
, typename Alloc
>
161 struct container_base_dispatch
<Key
, Mapped
, pat_trie_tag
, Policy_Tl
, Alloc
>
164 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 1> at1
;
165 typedef typename
at1::type at1t
;
168 typedef pat_trie_data_
<Key
, Mapped
, at1t
, Alloc
> type
;
171 template<typename Key
, typename Policy_Tl
, typename Alloc
>
172 struct container_base_dispatch
<Key
, null_mapped_type
, pat_trie_tag
,
176 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 1> at1
;
177 typedef typename
at1::type at1t
;
180 typedef pat_trie_no_data_
<Key
, null_mapped_type
, at1t
, Alloc
> type
;
183 template<typename Key
, typename Mapped
, typename Policy_Tl
, typename Alloc
>
184 struct container_base_dispatch
<Key
, Mapped
, rb_tree_tag
, Policy_Tl
, Alloc
>
187 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 0> at0
;
188 typedef typename
at0::type at0t
;
189 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 1> at1
;
190 typedef typename
at1::type at1t
;
193 typedef rb_tree_data_
<Key
, Mapped
, at0t
, at1t
, Alloc
> type
;
196 template<typename Key
, typename Policy_Tl
, typename Alloc
>
197 struct container_base_dispatch
<Key
, null_mapped_type
, rb_tree_tag
,
201 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 0> at0
;
202 typedef typename
at0::type at0t
;
203 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 1> at1
;
204 typedef typename
at1::type at1t
;
207 typedef rb_tree_no_data_
<Key
, null_mapped_type
, at0t
, at1t
, Alloc
> type
;
210 template<typename Key
, typename Mapped
, typename Policy_Tl
, typename Alloc
>
211 struct container_base_dispatch
<Key
, Mapped
, splay_tree_tag
,
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
;
221 typedef splay_tree_data_
<Key
, Mapped
, at0t
, at1t
, Alloc
> type
;
224 template<typename Key
, typename Policy_Tl
, typename Alloc
>
225 struct container_base_dispatch
<Key
, null_mapped_type
, splay_tree_tag
,
229 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 0> at0
;
230 typedef typename
at0::type at0t
;
231 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 1> at1
;
232 typedef typename
at1::type at1t
;
235 typedef splay_tree_no_data_
<Key
, null_mapped_type
, at0t
, at1t
, Alloc
> type
;
238 template<typename Key
, typename Mapped
, typename Policy_Tl
, typename Alloc
>
239 struct container_base_dispatch
<Key
, Mapped
, ov_tree_tag
, Policy_Tl
, Alloc
>
242 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 0> at0
;
243 typedef typename
at0::type at0t
;
244 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 1> at1
;
245 typedef typename
at1::type at1t
;
248 typedef ov_tree_data_
<Key
, Mapped
, at0t
, at1t
, Alloc
> type
;
251 template<typename Key
, typename Policy_Tl
, typename Alloc
>
252 struct container_base_dispatch
<Key
, null_mapped_type
, ov_tree_tag
,
256 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 0> at0
;
257 typedef typename
at0::type at0t
;
258 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 1> at1
;
259 typedef typename
at1::type at1t
;
262 typedef ov_tree_no_data_
<Key
, null_mapped_type
, at0t
, at1t
, Alloc
> type
;
265 template<typename Key
, typename Mapped
, typename Policy_Tl
, typename Alloc
>
266 struct container_base_dispatch
<Key
, Mapped
, cc_hash_tag
, Policy_Tl
, Alloc
>
269 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 0> at0
;
270 typedef typename
at0::type at0t
;
271 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 1> at1
;
272 typedef typename
at1::type at1t
;
273 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 2> at2
;
274 typedef typename
at2::type at2t
;
275 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 3> at3
;
276 typedef typename
at3::type at3t
;
277 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 4> at4
;
278 typedef typename
at4::type at4t
;
281 typedef cc_ht_map_data_
<Key
, Mapped
, at0t
, at1t
, Alloc
, at3t::value
,
285 template<typename Key
, typename Policy_Tl
, typename Alloc
>
286 struct container_base_dispatch
<Key
, null_mapped_type
, cc_hash_tag
,
290 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 0> at0
;
291 typedef typename
at0::type at0t
;
292 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 1> at1
;
293 typedef typename
at1::type at1t
;
294 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 2> at2
;
295 typedef typename
at2::type at2t
;
296 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 3> at3
;
297 typedef typename
at3::type at3t
;
298 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 4> at4
;
299 typedef typename
at4::type at4t
;
302 typedef cc_ht_map_no_data_
<Key
, null_mapped_type
, at0t
, at1t
, Alloc
,
303 at3t::value
, at4t
, at2t
> type
;
306 template<typename Key
, typename Mapped
, typename Policy_Tl
, typename Alloc
>
307 struct container_base_dispatch
<Key
, Mapped
, gp_hash_tag
, Policy_Tl
, Alloc
>
310 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 0> at0
;
311 typedef typename
at0::type at0t
;
312 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 1> at1
;
313 typedef typename
at1::type at1t
;
314 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 2> at2
;
315 typedef typename
at2::type at2t
;
316 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 3> at3
;
317 typedef typename
at3::type at3t
;
318 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 4> at4
;
319 typedef typename
at4::type at4t
;
320 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 5> at5
;
321 typedef typename
at5::type at5t
;
324 typedef gp_ht_map_data_
<Key
, Mapped
, at0t
, at1t
, Alloc
, at3t::value
,
325 at4t
, at5t
, at2t
> type
;
328 template<typename Key
, typename Policy_Tl
, typename Alloc
>
329 struct container_base_dispatch
<Key
, null_mapped_type
, gp_hash_tag
,
333 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 0> at0
;
334 typedef typename
at0::type at0t
;
335 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 1> at1
;
336 typedef typename
at1::type at1t
;
337 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 2> at2
;
338 typedef typename
at2::type at2t
;
339 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 3> at3
;
340 typedef typename
at3::type at3t
;
341 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 4> at4
;
342 typedef typename
at4::type at4t
;
343 typedef __gnu_cxx::typelist::at_index
<Policy_Tl
, 5> at5
;
344 typedef typename
at5::type at5t
;
347 typedef gp_ht_map_no_data_
<Key
, null_mapped_type
, at0t
, at1t
, Alloc
,
348 at3t::value
, at4t
, at5t
, at2t
> type
;
350 } // namespace detail
351 } // namespace __gnu_pbds