2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSUNIT_MAP_TYPE_SKIP_LIST_H
32 #define CDSUNIT_MAP_TYPE_SKIP_LIST_H
36 #include <cds/container/skip_list_map_hp.h>
37 #include <cds/container/skip_list_map_dhp.h>
38 #include <cds/container/skip_list_map_rcu.h>
39 #include <cds/container/skip_list_map_nogc.h>
41 #include <cds_test/stat_skiplist_out.h>
45 template <class GC, typename Key, typename T, typename Traits = cc::skip_list::traits >
46 class SkipListMap : public cc::SkipListMap< GC, Key, T, Traits >
48 typedef cc::SkipListMap< GC, Key, T, Traits > base_class;
50 template <typename Config>
51 SkipListMap( Config const& /*cfg*/)
55 std::pair<Key, bool> extract_min_key()
57 auto xp = base_class::extract_min();
59 return std::make_pair( xp->first, true );
60 return std::make_pair( Key(), false );
63 std::pair<Key, bool> extract_max_key()
65 auto xp = base_class::extract_max();
67 return std::make_pair( xp->first, true );
68 return std::make_pair( Key(), false );
72 static constexpr bool const c_bExtractSupported = true;
73 static constexpr bool const c_bLoadFactorDepended = false;
74 static constexpr bool const c_bEraseExactKey = false;
77 struct tag_SkipListMap;
79 template <typename Key, typename Value>
80 struct map_type< tag_SkipListMap, Key, Value >: public map_type_base< Key, Value >
82 typedef map_type_base< Key, Value > base_class;
83 typedef typename base_class::key_compare compare;
84 typedef typename base_class::key_less less;
86 class traits_SkipListMap_less_turbo32: public cc::skip_list::make_traits <
88 ,cc::skip_list::random_level_generator< cc::skip_list::turbo32 >
89 ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
92 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_turbo32 > SkipListMap_hp_less_turbo32;
93 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_less_turbo32 > SkipListMap_dhp_less_turbo32;
94 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_less_turbo32 > SkipListMap_nogc_less_turbo32;
95 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_less_turbo32 > SkipListMap_rcu_gpi_less_turbo32;
96 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_less_turbo32 > SkipListMap_rcu_gpb_less_turbo32;
97 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_less_turbo32 > SkipListMap_rcu_gpt_less_turbo32;
98 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
99 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_less_turbo32 > SkipListMap_rcu_shb_less_turbo32;
102 class traits_SkipListMap_less_turbo24: public cc::skip_list::make_traits <
104 , cc::skip_list::random_level_generator< cc::skip_list::turbo24 >
105 , co::item_counter< cds::atomicity::cache_friendly_item_counter >
108 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_turbo24 > SkipListMap_hp_less_turbo24;
109 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_less_turbo24 > SkipListMap_dhp_less_turbo24;
110 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_less_turbo24 > SkipListMap_nogc_less_turbo24;
111 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_less_turbo24 > SkipListMap_rcu_gpi_less_turbo24;
112 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_less_turbo24 > SkipListMap_rcu_gpb_less_turbo24;
113 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_less_turbo24 > SkipListMap_rcu_gpt_less_turbo24;
114 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
115 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_less_turbo24 > SkipListMap_rcu_shb_less_turbo24;
118 class traits_SkipListMap_less_turbo16: public cc::skip_list::make_traits <
120 , cc::skip_list::random_level_generator< cc::skip_list::turbo16 >
121 , co::item_counter< cds::atomicity::cache_friendly_item_counter >
124 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_turbo16 > SkipListMap_hp_less_turbo16;
125 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_less_turbo16 > SkipListMap_dhp_less_turbo16;
126 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_less_turbo16 > SkipListMap_nogc_less_turbo16;
127 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_less_turbo16 > SkipListMap_rcu_gpi_less_turbo16;
128 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_less_turbo16 > SkipListMap_rcu_gpb_less_turbo16;
129 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_less_turbo16 > SkipListMap_rcu_gpt_less_turbo16;
130 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
131 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_less_turbo16 > SkipListMap_rcu_shb_less_turbo16;
134 class traits_SkipListMap_less_turbo32_seqcst: public cc::skip_list::make_traits <
136 ,cc::skip_list::random_level_generator< cc::skip_list::turbo32 >
137 ,co::memory_model< co::v::sequential_consistent >
138 ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
141 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_turbo32_seqcst > SkipListMap_hp_less_turbo32_seqcst;
142 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_less_turbo32_seqcst > SkipListMap_dhp_less_turbo32_seqcst;
143 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_less_turbo32_seqcst > SkipListMap_nogc_less_turbo32_seqcst;
144 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_less_turbo32_seqcst > SkipListMap_rcu_gpi_less_turbo32_seqcst;
145 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_less_turbo32_seqcst > SkipListMap_rcu_gpb_less_turbo32_seqcst;
146 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_less_turbo32_seqcst > SkipListMap_rcu_gpt_less_turbo32_seqcst;
147 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
148 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_less_turbo32_seqcst > SkipListMap_rcu_shb_less_turbo32_seqcst;
151 class traits_SkipListMap_less_turbo32_stat: public cc::skip_list::make_traits <
153 ,cc::skip_list::random_level_generator< cc::skip_list::turbo32 >
154 ,co::stat< cc::skip_list::stat<> >
155 ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
158 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_turbo32_stat > SkipListMap_hp_less_turbo32_stat;
159 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_less_turbo32_stat > SkipListMap_dhp_less_turbo32_stat;
160 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_less_turbo32_stat > SkipListMap_nogc_less_turbo32_stat;
161 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_less_turbo32_stat > SkipListMap_rcu_gpi_less_turbo32_stat;
162 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_less_turbo32_stat > SkipListMap_rcu_gpb_less_turbo32_stat;
163 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_less_turbo32_stat > SkipListMap_rcu_gpt_less_turbo32_stat;
164 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
165 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_less_turbo32_stat > SkipListMap_rcu_shb_less_turbo32_stat;
168 class traits_SkipListMap_less_turbo24_stat: public cc::skip_list::make_traits <
170 , cc::skip_list::random_level_generator< cc::skip_list::turbo24 >
171 , co::stat< cc::skip_list::stat<> >
172 , co::item_counter< cds::atomicity::cache_friendly_item_counter >
175 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_turbo24_stat > SkipListMap_hp_less_turbo24_stat;
176 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_less_turbo24_stat > SkipListMap_dhp_less_turbo24_stat;
177 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_less_turbo24_stat > SkipListMap_nogc_less_turbo24_stat;
178 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_less_turbo24_stat > SkipListMap_rcu_gpi_less_turbo24_stat;
179 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_less_turbo24_stat > SkipListMap_rcu_gpb_less_turbo24_stat;
180 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_less_turbo24_stat > SkipListMap_rcu_gpt_less_turbo24_stat;
181 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
182 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_less_turbo24_stat > SkipListMap_rcu_shb_less_turbo24_stat;
185 class traits_SkipListMap_less_turbo16_stat: public cc::skip_list::make_traits <
187 , cc::skip_list::random_level_generator< cc::skip_list::turbo16 >
188 , co::stat< cc::skip_list::stat<> >
189 , co::item_counter< cds::atomicity::cache_friendly_item_counter >
192 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_turbo16_stat > SkipListMap_hp_less_turbo16_stat;
193 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_less_turbo16_stat > SkipListMap_dhp_less_turbo16_stat;
194 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_less_turbo16_stat > SkipListMap_nogc_less_turbo16_stat;
195 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_less_turbo16_stat > SkipListMap_rcu_gpi_less_turbo16_stat;
196 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_less_turbo16_stat > SkipListMap_rcu_gpb_less_turbo16_stat;
197 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_less_turbo16_stat > SkipListMap_rcu_gpt_less_turbo16_stat;
198 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
199 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_less_turbo16_stat > SkipListMap_rcu_shb_less_turbo16_stat;
202 class traits_SkipListMap_cmp_turbo32: public cc::skip_list::make_traits <
203 co::compare< compare >
204 ,cc::skip_list::random_level_generator< cc::skip_list::turbo32 >
205 ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
208 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_cmp_turbo32 > SkipListMap_hp_cmp_turbo32;
209 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_cmp_turbo32 > SkipListMap_dhp_cmp_turbo32;
210 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_cmp_turbo32 > SkipListMap_nogc_cmp_turbo32;
211 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_cmp_turbo32 > SkipListMap_rcu_gpi_cmp_turbo32;
212 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_cmp_turbo32 > SkipListMap_rcu_gpb_cmp_turbo32;
213 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_cmp_turbo32 > SkipListMap_rcu_gpt_cmp_turbo32;
214 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
215 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_cmp_turbo32 > SkipListMap_rcu_shb_cmp_turbo32;
218 class traits_SkipListMap_cmp_turbo32_stat: public cc::skip_list::make_traits <
219 co::compare< compare >
220 ,cc::skip_list::random_level_generator< cc::skip_list::turbo32 >
221 ,co::stat< cc::skip_list::stat<> >
222 ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
225 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_cmp_turbo32_stat > SkipListMap_hp_cmp_turbo32_stat;
226 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_cmp_turbo32_stat > SkipListMap_dhp_cmp_turbo32_stat;
227 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_cmp_turbo32_stat > SkipListMap_nogc_cmp_turbo32_stat;
228 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_cmp_turbo32_stat > SkipListMap_rcu_gpi_cmp_turbo32_stat;
229 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_cmp_turbo32_stat > SkipListMap_rcu_gpb_cmp_turbo32_stat;
230 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_cmp_turbo32_stat > SkipListMap_rcu_gpt_cmp_turbo32_stat;
231 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
232 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_cmp_turbo32_stat > SkipListMap_rcu_shb_cmp_turbo32_stat;
235 class traits_SkipListMap_less_xorshift32: public cc::skip_list::make_traits <
237 ,cc::skip_list::random_level_generator< cc::skip_list::xorshift32 >
238 ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
241 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_xorshift32 > SkipListMap_hp_less_xorshift32;
242 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_less_xorshift32 > SkipListMap_dhp_less_xorshift32;
243 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_less_xorshift32 > SkipListMap_nogc_less_xorshift32;
244 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_less_xorshift32 > SkipListMap_rcu_gpi_less_xorshift32;
245 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_less_xorshift32 > SkipListMap_rcu_gpb_less_xorshift32;
246 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_less_xorshift32 > SkipListMap_rcu_gpt_less_xorshift32;
247 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
248 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_less_xorshift32 > SkipListMap_rcu_shb_less_xorshift32;
251 class traits_SkipListMap_less_xorshift24: public cc::skip_list::make_traits <
253 , cc::skip_list::random_level_generator< cc::skip_list::xorshift24 >
254 , co::item_counter< cds::atomicity::cache_friendly_item_counter >
257 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_xorshift24 > SkipListMap_hp_less_xorshift24;
258 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_less_xorshift24 > SkipListMap_dhp_less_xorshift24;
259 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_less_xorshift24 > SkipListMap_nogc_less_xorshift24;
260 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_less_xorshift24 > SkipListMap_rcu_gpi_less_xorshift24;
261 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_less_xorshift24 > SkipListMap_rcu_gpb_less_xorshift24;
262 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_less_xorshift24 > SkipListMap_rcu_gpt_less_xorshift24;
263 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
264 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_less_xorshift24 > SkipListMap_rcu_shb_less_xorshift24;
267 class traits_SkipListMap_less_xorshift16: public cc::skip_list::make_traits <
269 , cc::skip_list::random_level_generator< cc::skip_list::xorshift16 >
270 , co::item_counter< cds::atomicity::cache_friendly_item_counter >
273 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_xorshift16 > SkipListMap_hp_less_xorshift16;
274 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_less_xorshift16 > SkipListMap_dhp_less_xorshift16;
275 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_less_xorshift16 > SkipListMap_nogc_less_xorshift16;
276 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_less_xorshift16 > SkipListMap_rcu_gpi_less_xorshift16;
277 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_less_xorshift16 > SkipListMap_rcu_gpb_less_xorshift16;
278 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_less_xorshift16 > SkipListMap_rcu_gpt_less_xorshift16;
279 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
280 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_less_xorshift16 > SkipListMap_rcu_shb_less_xorshift16;
283 class traits_SkipListMap_less_xorshift32_stat: public cc::skip_list::make_traits <
285 ,cc::skip_list::random_level_generator< cc::skip_list::xorshift32 >
286 ,co::stat< cc::skip_list::stat<> >
287 ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
290 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_xorshift32_stat > SkipListMap_hp_less_xorshift32_stat;
291 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_less_xorshift32_stat > SkipListMap_dhp_less_xorshift32_stat;
292 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_less_xorshift32_stat > SkipListMap_nogc_less_xorshift32_stat;
293 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_less_xorshift32_stat > SkipListMap_rcu_gpi_less_xorshift32_stat;
294 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_less_xorshift32_stat > SkipListMap_rcu_gpb_less_xorshift32_stat;
295 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_less_xorshift32_stat > SkipListMap_rcu_gpt_less_xorshift32_stat;
296 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
297 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_less_xorshift32_stat > SkipListMap_rcu_shb_less_xorshift32_stat;
300 class traits_SkipListMap_less_xorshift24_stat: public cc::skip_list::make_traits <
302 , cc::skip_list::random_level_generator< cc::skip_list::xorshift24 >
303 , co::stat< cc::skip_list::stat<> >
304 , co::item_counter< cds::atomicity::cache_friendly_item_counter >
307 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_xorshift24_stat > SkipListMap_hp_less_xorshift24_stat;
308 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_less_xorshift24_stat > SkipListMap_dhp_less_xorshift24_stat;
309 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_less_xorshift24_stat > SkipListMap_nogc_less_xorshift24_stat;
310 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_less_xorshift24_stat > SkipListMap_rcu_gpi_less_xorshift24_stat;
311 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_less_xorshift24_stat > SkipListMap_rcu_gpb_less_xorshift24_stat;
312 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_less_xorshift24_stat > SkipListMap_rcu_gpt_less_xorshift24_stat;
313 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
314 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_less_xorshift24_stat > SkipListMap_rcu_shb_less_xorshift24_stat;
317 class traits_SkipListMap_less_xorshift16_stat: public cc::skip_list::make_traits <
319 , cc::skip_list::random_level_generator< cc::skip_list::xorshift16 >
320 , co::stat< cc::skip_list::stat<> >
321 , co::item_counter< cds::atomicity::cache_friendly_item_counter >
324 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_less_xorshift16_stat > SkipListMap_hp_less_xorshift16_stat;
325 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_less_xorshift16_stat > SkipListMap_dhp_less_xorshift16_stat;
326 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_less_xorshift16_stat > SkipListMap_nogc_less_xorshift16_stat;
327 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_less_xorshift16_stat > SkipListMap_rcu_gpi_less_xorshift16_stat;
328 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_less_xorshift16_stat > SkipListMap_rcu_gpb_less_xorshift16_stat;
329 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_less_xorshift16_stat > SkipListMap_rcu_gpt_less_xorshift16_stat;
330 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
331 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_less_xorshift16_stat > SkipListMap_rcu_shb_less_xorshift16_stat;
334 class traits_SkipListMap_cmp_xorshift32: public cc::skip_list::make_traits <
335 co::compare< compare >
336 ,cc::skip_list::random_level_generator< cc::skip_list::xorshift32 >
337 ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
340 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_cmp_xorshift32 > SkipListMap_hp_cmp_xorshift32;
341 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_cmp_xorshift32 > SkipListMap_dhp_cmp_xorshift32;
342 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_cmp_xorshift32 > SkipListMap_nogc_cmp_xorshift32;
343 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_cmp_xorshift32 > SkipListMap_rcu_gpi_cmp_xorshift32;
344 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_cmp_xorshift32 > SkipListMap_rcu_gpb_cmp_xorshift32;
345 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_cmp_xorshift32 > SkipListMap_rcu_gpt_cmp_xorshift32;
346 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
347 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_cmp_xorshift32 > SkipListMap_rcu_shb_cmp_xorshift32;
350 class traits_SkipListMap_cmp_xorshift32_stat: public cc::skip_list::make_traits <
351 co::compare< compare >
352 ,cc::skip_list::random_level_generator< cc::skip_list::xorshift32 >
353 ,co::stat< cc::skip_list::stat<> >
354 ,co::item_counter< cds::atomicity::cache_friendly_item_counter >
357 typedef SkipListMap< cds::gc::HP, Key, Value, traits_SkipListMap_cmp_xorshift32_stat > SkipListMap_hp_cmp_xorshift32_stat;
358 typedef SkipListMap< cds::gc::DHP, Key, Value, traits_SkipListMap_cmp_xorshift32_stat > SkipListMap_dhp_cmp_xorshift32_stat;
359 typedef SkipListMap< cds::gc::nogc, Key, Value, traits_SkipListMap_cmp_xorshift32_stat > SkipListMap_nogc_cmp_xorshift32_stat;
360 typedef SkipListMap< rcu_gpi, Key, Value, traits_SkipListMap_cmp_xorshift32_stat > SkipListMap_rcu_gpi_cmp_xorshift32_stat;
361 typedef SkipListMap< rcu_gpb, Key, Value, traits_SkipListMap_cmp_xorshift32_stat > SkipListMap_rcu_gpb_cmp_xorshift32_stat;
362 typedef SkipListMap< rcu_gpt, Key, Value, traits_SkipListMap_cmp_xorshift32_stat > SkipListMap_rcu_gpt_cmp_xorshift32_stat;
363 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
364 typedef SkipListMap< rcu_shb, Key, Value, traits_SkipListMap_cmp_xorshift32_stat > SkipListMap_rcu_shb_cmp_xorshift32_stat;
369 template <typename GC, typename K, typename T, typename Traits >
370 static inline void print_stat( cds_test::property_stream& o, SkipListMap< GC, K, T, Traits > const& m )
377 #define CDSSTRESS_SkipListMap_case( fixture, test_case, skiplist_map_type, key_type, value_type ) \
378 TEST_F( fixture, skiplist_map_type ) \
380 typedef map::map_type< tag_SkipListMap, key_type, value_type >::skiplist_map_type map_type; \
381 test_case<map_type>(); \
384 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
386 #if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL > 1
387 # define CDSSTRESS_SkipListMap_SHRCU_2( fixture, test_case, key_type, value_type ) \
388 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_shb_less_turbo32_seqcst, key_type, value_type ) \
391 # define CDSSTRESS_SkipListMap_SHRCU_2( fixture, test_case, key_type, value_type )
394 #if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL == 1
395 # define CDSSTRESS_SkipListMap_SHRCU_1( fixture, test_case, key_type, value_type ) \
396 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_shb_less_turbo32_stat, key_type, value_type ) \
397 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_shb_cmp_turbo32, key_type, value_type ) \
398 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_shb_cmp_turbo32_stat, key_type, value_type ) \
399 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_shb_less_xorshift32_stat, key_type, value_type ) \
400 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_shb_cmp_xorshift32, key_type, value_type ) \
403 # define CDSSTRESS_SkipListMap_SHRCU_1( fixture, test_case, key_type, value_type )
407 # define CDSSTRESS_SkipListMap_SHRCU( fixture, test_case, key_type, value_type ) \
408 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_shb_less_turbo32, key_type, value_type ) \
409 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_shb_less_xorshift32, key_type, value_type ) \
410 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_shb_cmp_xorshift32_stat, key_type, value_type ) \
411 CDSSTRESS_SkipListMap_SHRCU_1( fixture, test_case, key_type, value_type ) \
412 CDSSTRESS_SkipListMap_SHRCU_2( fixture, test_case, key_type, value_type ) \
415 # define CDSSTRESS_SkipListMap_SHRCU( fixture, test_case, key_type, value_type )
418 #if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL > 1
419 # define CDSSTRESS_SkipListMap_HP_2( fixture, test_case, key_type, value_type ) \
420 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_hp_less_turbo32_seqcst, key_type, value_type ) \
421 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_dhp_less_turbo32_seqcst, key_type, value_type ) \
423 # define CDSSTRESS_SkipListMap_RCU_2( fixture, test_case, key_type, value_type ) \
424 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpi_less_turbo32_seqcst, key_type, value_type ) \
425 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpb_less_turbo32_seqcst, key_type, value_type ) \
426 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpt_less_turbo32_seqcst, key_type, value_type ) \
428 # define CDSSTRESS_SkipListMap_2( fixture, test_case, key_type, value_type ) \
429 CDSSTRESS_SkipListMap_HP_2( fixture, test_case, key_type, value_type ) \
430 CDSSTRESS_SkipListMap_RCU_2( fixture, test_case, key_type, value_type ) \
433 # define CDSSTRESS_SkipListMap_HP_2( fixture, test_case, key_type, value_type )
434 # define CDSSTRESS_SkipListMap_RCU_2( fixture, test_case, key_type, value_type )
435 # define CDSSTRESS_SkipListMap_2( fixture, test_case, key_type, value_type )
438 #if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL == 1
439 # define CDSSTRESS_SkipListMap_HP_1( fixture, test_case, key_type, value_type ) \
440 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_dhp_less_turbo32, key_type, value_type ) \
441 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_hp_less_turbo32_stat, key_type, value_type ) \
442 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_hp_cmp_turbo32, key_type, value_type ) \
443 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_dhp_cmp_turbo32_stat, key_type, value_type ) \
444 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_dhp_less_xorshift32, key_type, value_type ) \
445 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_hp_less_xorshift32_stat, key_type, value_type ) \
446 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_hp_cmp_xorshift32, key_type, value_type ) \
447 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_dhp_cmp_xorshift32_stat, key_type, value_type ) \
449 # define CDSSTRESS_SkipListMap_RCU_1( fixture, test_case, key_type, value_type ) \
450 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpb_less_turbo32, key_type, value_type ) \
451 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpi_less_turbo32_stat, key_type, value_type ) \
452 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpt_less_turbo32_stat, key_type, value_type ) \
453 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpi_cmp_turbo32, key_type, value_type ) \
454 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpt_cmp_turbo32, key_type, value_type ) \
455 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpb_cmp_turbo32_stat, key_type, value_type ) \
456 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpb_less_xorshift32, key_type, value_type ) \
457 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpi_less_xorshift32_stat, key_type, value_type ) \
458 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpt_less_xorshift32_stat, key_type, value_type ) \
459 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpi_cmp_xorshift32, key_type, value_type ) \
460 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpt_cmp_xorshift32, key_type, value_type ) \
461 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpb_cmp_xorshift32_stat, key_type, value_type ) \
462 CDSSTRESS_SkipListMap_SHRCU( fixture, test_case, key_type, value_type )
464 # define CDSSTRESS_SkipListMap_1( fixture, test_case, key_type, value_type ) \
465 CDSSTRESS_SkipListMap_HP_1( fixture, test_case, key_type, value_type ) \
466 CDSSTRESS_SkipListMap_RCU_1( fixture, test_case, key_type, value_type ) \
469 # define CDSSTRESS_SkipListMap_HP_1( fixture, test_case, key_type, value_type )
470 # define CDSSTRESS_SkipListMap_RCU_1( fixture, test_case, key_type, value_type )
471 # define CDSSTRESS_SkipListMap_1( fixture, test_case, key_type, value_type )
475 #define CDSSTRESS_SkipListMap_HP( fixture, test_case, key_type, value_type ) \
476 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_hp_less_turbo32, key_type, value_type ) \
477 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_hp_less_turbo24, key_type, value_type ) \
478 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_hp_less_turbo16, key_type, value_type ) \
479 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_dhp_less_turbo32_stat, key_type, value_type ) \
480 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_dhp_less_turbo24_stat, key_type, value_type ) \
481 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_dhp_less_turbo16_stat, key_type, value_type ) \
482 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_dhp_cmp_turbo32, key_type, value_type ) \
483 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_hp_cmp_turbo32_stat, key_type, value_type ) \
484 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_hp_less_xorshift32, key_type, value_type ) \
485 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_hp_less_xorshift24, key_type, value_type ) \
486 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_hp_less_xorshift16, key_type, value_type ) \
487 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_dhp_less_xorshift32_stat, key_type, value_type ) \
488 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_dhp_less_xorshift24_stat, key_type, value_type ) \
489 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_dhp_less_xorshift16_stat, key_type, value_type ) \
490 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_dhp_cmp_xorshift32, key_type, value_type ) \
491 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_hp_cmp_xorshift32_stat, key_type, value_type ) \
492 CDSSTRESS_SkipListMap_HP_1( fixture, test_case, key_type, value_type ) \
493 CDSSTRESS_SkipListMap_HP_2( fixture, test_case, key_type, value_type ) \
495 #define CDSSTRESS_SkipListMap_RCU( fixture, test_case, key_type, value_type ) \
496 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpi_less_turbo32, key_type, value_type ) \
497 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpt_less_turbo32, key_type, value_type ) \
498 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpb_less_turbo32_stat, key_type, value_type ) \
499 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpb_less_turbo24_stat, key_type, value_type ) \
500 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpb_less_turbo16_stat, key_type, value_type ) \
501 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpb_cmp_turbo32, key_type, value_type ) \
502 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpi_cmp_turbo32_stat, key_type, value_type ) \
503 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpt_cmp_turbo32_stat, key_type, value_type ) \
504 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpi_less_xorshift32, key_type, value_type ) \
505 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpt_less_xorshift32, key_type, value_type ) \
506 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpb_less_xorshift32_stat, key_type, value_type ) \
507 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpb_less_xorshift24_stat, key_type, value_type ) \
508 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpb_less_xorshift16_stat, key_type, value_type ) \
509 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpb_cmp_xorshift32, key_type, value_type ) \
510 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpi_cmp_xorshift32_stat, key_type, value_type ) \
511 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_rcu_gpt_cmp_xorshift32_stat, key_type, value_type ) \
512 CDSSTRESS_SkipListMap_RCU_1( fixture, test_case, key_type, value_type ) \
513 CDSSTRESS_SkipListMap_RCU_2( fixture, test_case, key_type, value_type ) \
515 #define CDSSTRESS_SkipListMap( fixture, test_case, key_type, value_type ) \
516 CDSSTRESS_SkipListMap_HP( fixture, test_case, key_type, value_type ) \
517 CDSSTRESS_SkipListMap_RCU( fixture, test_case, key_type, value_type ) \
519 #define CDSSTRESS_SkipListMap_nogc( fixture, test_case, key_type, value_type ) \
520 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_less_turbo32, key_type, value_type ) \
521 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_less_turbo24, key_type, value_type ) \
522 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_less_turbo16, key_type, value_type ) \
523 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_less_turbo32_seqcst, key_type, value_type ) \
524 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_less_turbo32_stat, key_type, value_type ) \
525 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_less_turbo24_stat, key_type, value_type ) \
526 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_less_turbo16_stat, key_type, value_type ) \
527 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_cmp_turbo32, key_type, value_type ) \
528 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_cmp_turbo32_stat, key_type, value_type ) \
529 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_less_xorshift32, key_type, value_type ) \
530 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_less_xorshift24, key_type, value_type ) \
531 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_less_xorshift16, key_type, value_type ) \
532 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_less_xorshift32_stat, key_type, value_type ) \
533 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_less_xorshift24_stat, key_type, value_type ) \
534 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_less_xorshift16_stat, key_type, value_type ) \
535 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_cmp_xorshift32, key_type, value_type ) \
536 CDSSTRESS_SkipListMap_case( fixture, test_case, SkipListMap_nogc_cmp_xorshift32_stat, key_type, value_type ) \
538 #endif // ifndef CDSUNIT_MAP_TYPE_SKIP_LIST_H