2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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 #include "test_intrusive_tree_hp.h"
33 #include <cds/intrusive/ellen_bintree_dhp.h>
34 #include <cds/memory/vyukov_queue_pool.h>
35 #include <cds/memory/pool_allocator.h>
38 namespace ci = cds::intrusive;
39 typedef cds::gc::DHP gc_type;
41 class IntrusiveEllenBinTree_DHP : public cds_test::intrusive_tree_hp
44 typedef cds_test::intrusive_tree_hp base_class;
47 typedef base_class::key_type key_type;
49 typedef typename base_class::base_int_item< ci::ellen_bintree::node<gc_type>> base_item_type;
50 typedef ci::ellen_bintree::internal_node< key_type, base_item_type > internal_base_node;
51 typedef ci::ellen_bintree::update_desc< base_item_type, internal_base_node > update_base_desc;
53 typedef typename base_class::member_int_item< ci::ellen_bintree::node<gc_type>> member_item_type;
54 typedef ci::ellen_bintree::internal_node< key_type, member_item_type > internal_member_node;
55 typedef ci::ellen_bintree::update_desc< member_item_type, internal_member_node > update_member_desc;
58 struct pool_traits: public cds::memory::vyukov_queue_pool_traits
60 typedef cds::opt::v::static_buffer< update_base_desc, 256 > buffer;
62 typedef cds::memory::vyukov_queue_pool< update_base_desc, pool_traits > pool_type;
63 typedef cds::memory::lazy_vyukov_queue_pool< update_base_desc, pool_traits > lazy_pool_type;
65 static pool_type * s_Pool;
66 static lazy_pool_type * s_LazyPool;
70 typedef pool_type::value_type value_type;
72 pool_type& operator()() const
78 struct lazy_pool_accessor
80 typedef lazy_pool_type::value_type value_type;
82 lazy_pool_type& operator()() const
88 static void SetUpTestCase()
90 ASSERT_TRUE( s_Pool == nullptr );
91 ASSERT_TRUE( s_LazyPool == nullptr );
92 s_Pool = new pool_type;
93 s_LazyPool = new lazy_pool_type;
96 static void TearDownTestCase()
98 ASSERT_TRUE( s_Pool != nullptr );
99 ASSERT_TRUE( s_LazyPool != nullptr );
103 s_LazyPool = nullptr;
109 struct list_traits : public ci::ellen_bintree::traits
111 typedef ci::ellen_bintree::base_hook< ci::opt::gc<gc_type>> hook;
113 typedef ci::EllenBinTree< gc_type, key_type, base_item_type > tree_type;
115 cds::gc::dhp::GarbageCollector::Construct( 16, tree_type::c_nHazardPtrCount );
116 cds::threading::Manager::attachThread();
121 cds::threading::Manager::detachThread();
122 cds::gc::dhp::GarbageCollector::Destruct();
125 struct generic_traits: public ci::ellen_bintree::traits
127 typedef base_class::key_extractor key_extractor;
128 typedef mock_disposer disposer;
132 /*static*/ IntrusiveEllenBinTree_DHP::pool_type * IntrusiveEllenBinTree_DHP::s_Pool = nullptr;
133 /*static*/ IntrusiveEllenBinTree_DHP::lazy_pool_type * IntrusiveEllenBinTree_DHP::s_LazyPool = nullptr;
135 TEST_F( IntrusiveEllenBinTree_DHP, base_cmp )
137 typedef ci::EllenBinTree< gc_type, key_type, base_item_type,
138 ci::ellen_bintree::make_traits<
139 ci::opt::type_traits< generic_traits >
140 ,ci::opt::hook< ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >>>
141 ,ci::opt::compare< cmp<base_item_type>>
149 TEST_F( IntrusiveEllenBinTree_DHP, base_less )
151 typedef ci::EllenBinTree< gc_type, key_type, base_item_type,
152 ci::ellen_bintree::make_traits<
153 ci::opt::type_traits< generic_traits >
154 ,ci::opt::hook< ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >>>
155 ,ci::opt::less< less<base_item_type>>
163 TEST_F( IntrusiveEllenBinTree_DHP, base_item_counter )
165 typedef ci::EllenBinTree< gc_type, key_type, base_item_type,
166 ci::ellen_bintree::make_traits<
167 ci::opt::type_traits< generic_traits >
168 ,ci::opt::hook< ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >>>
169 ,ci::opt::compare< cmp<base_item_type>>
170 ,ci::opt::item_counter< simple_item_counter >
178 TEST_F( IntrusiveEllenBinTree_DHP, base_backoff )
180 struct tree_traits: public generic_traits
182 typedef ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >> hook;
183 typedef cmp<base_item_type> compare;
184 typedef base_class::less<base_item_type> less;
185 typedef cds::atomicity::item_counter item_counter;
186 typedef cds::backoff::yield back_off;
189 typedef ci::EllenBinTree< gc_type, key_type, base_item_type, tree_traits > tree_type;
195 TEST_F( IntrusiveEllenBinTree_DHP, base_seq_cst )
197 struct tree_traits: public generic_traits
199 typedef ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >> hook;
200 typedef cmp<base_item_type> compare;
201 typedef base_class::less<base_item_type> less;
202 typedef cds::atomicity::item_counter item_counter;
203 typedef cds::backoff::pause back_off;
204 typedef ci::opt::v::sequential_consistent memory_model;
207 typedef ci::EllenBinTree< gc_type, key_type, base_item_type, tree_traits > tree_type;
213 TEST_F( IntrusiveEllenBinTree_DHP, base_update_desc_pool )
215 struct tree_traits: public generic_traits
217 typedef ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >> hook;
218 typedef base_class::less<base_item_type> less;
219 typedef cds::atomicity::item_counter item_counter;
220 typedef cds::memory::pool_allocator<update_base_desc, pool_accessor> update_desc_allocator;
223 typedef ci::EllenBinTree< gc_type, key_type, base_item_type, tree_traits > tree_type;
229 TEST_F( IntrusiveEllenBinTree_DHP, base_update_desc_lazy_pool )
231 struct tree_traits: public generic_traits
233 typedef ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >> hook;
234 typedef base_class::less<base_item_type> less;
235 typedef cds::atomicity::item_counter item_counter;
236 typedef cds::memory::pool_allocator<update_base_desc, lazy_pool_accessor> update_desc_allocator;
239 typedef ci::EllenBinTree< gc_type, key_type, base_item_type, tree_traits > tree_type;
246 TEST_F( IntrusiveEllenBinTree_DHP, member_cmp )
248 typedef ci::EllenBinTree< gc_type, key_type, member_item_type,
249 ci::ellen_bintree::make_traits<
250 ci::opt::type_traits< generic_traits >
251 ,ci::opt::hook< ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember), ci::opt::gc< gc_type >>>
252 ,ci::opt::compare< cmp<member_item_type>>
260 TEST_F( IntrusiveEllenBinTree_DHP, member_less )
262 typedef ci::EllenBinTree< gc_type, key_type, member_item_type,
263 ci::ellen_bintree::make_traits<
264 ci::opt::type_traits< generic_traits >
265 ,ci::opt::hook< ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >>>
266 ,ci::opt::less< less<member_item_type>>
274 TEST_F( IntrusiveEllenBinTree_DHP, member_item_counter )
276 typedef ci::EllenBinTree< gc_type, key_type, member_item_type,
277 ci::ellen_bintree::make_traits<
278 ci::opt::type_traits< generic_traits >
279 ,ci::opt::hook< ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >>>
280 ,ci::opt::compare< cmp<member_item_type>>
281 ,ci::opt::item_counter< simple_item_counter >
289 TEST_F( IntrusiveEllenBinTree_DHP, member_backoff )
291 struct tree_traits: public generic_traits
293 typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >> hook;
294 typedef cmp<member_item_type> compare;
295 typedef base_class::less<member_item_type> less;
296 typedef cds::atomicity::item_counter item_counter;
297 typedef cds::backoff::yield back_off;
300 typedef ci::EllenBinTree< gc_type, key_type, member_item_type, tree_traits > tree_type;
306 TEST_F( IntrusiveEllenBinTree_DHP, member_seq_cst )
308 struct tree_traits: public generic_traits
310 typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >> hook;
311 typedef cmp<member_item_type> compare;
312 typedef base_class::less<member_item_type> less;
313 typedef cds::atomicity::item_counter item_counter;
314 typedef cds::backoff::pause back_off;
315 typedef ci::opt::v::sequential_consistent memory_model;
318 typedef ci::EllenBinTree< gc_type, key_type, member_item_type, tree_traits > tree_type;
324 TEST_F( IntrusiveEllenBinTree_DHP, member_update_desc_pool )
326 struct tree_traits: public generic_traits
328 typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >> hook;
329 typedef base_class::less<member_item_type> less;
330 typedef cds::atomicity::item_counter item_counter;
331 typedef cds::memory::pool_allocator<update_member_desc, pool_accessor> update_desc_allocator;
334 typedef ci::EllenBinTree< gc_type, key_type, member_item_type, tree_traits > tree_type;
340 TEST_F( IntrusiveEllenBinTree_DHP, member_update_desc_lazy_pool )
342 struct tree_traits: public generic_traits
344 typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >> hook;
345 typedef base_class::less<member_item_type> less;
346 typedef cds::atomicity::item_counter item_counter;
347 typedef cds::memory::pool_allocator<update_member_desc, lazy_pool_accessor> update_desc_allocator;
350 typedef ci::EllenBinTree< gc_type, key_type, member_item_type, tree_traits > tree_type;