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_hp.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::HP gc_type;
41 class IntrusiveEllenBinTree_HP : 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 // +1 - for guarded_ptr
116 cds::gc::hp::GarbageCollector::Construct( tree_type::c_nHazardPtrCount + 1, 1, 16 );
117 cds::threading::Manager::attachThread();
122 cds::threading::Manager::detachThread();
123 cds::gc::hp::GarbageCollector::Destruct( true );
126 struct generic_traits: public ci::ellen_bintree::traits
128 typedef base_class::key_extractor key_extractor;
129 typedef mock_disposer disposer;
133 /*static*/ IntrusiveEllenBinTree_HP::pool_type * IntrusiveEllenBinTree_HP::s_Pool = nullptr;
134 /*static*/ IntrusiveEllenBinTree_HP::lazy_pool_type * IntrusiveEllenBinTree_HP::s_LazyPool = nullptr;
137 TEST_F( IntrusiveEllenBinTree_HP, base_cmp )
139 typedef ci::EllenBinTree< gc_type, key_type, base_item_type,
140 ci::ellen_bintree::make_traits<
141 ci::opt::type_traits< generic_traits >
142 ,ci::opt::hook< ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >>>
143 ,ci::opt::compare< cmp<base_item_type>>
151 TEST_F( IntrusiveEllenBinTree_HP, base_less )
153 typedef ci::EllenBinTree< gc_type, key_type, base_item_type,
154 ci::ellen_bintree::make_traits<
155 ci::opt::type_traits< generic_traits >
156 ,ci::opt::hook< ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >>>
157 ,ci::opt::less< less<base_item_type>>
165 TEST_F( IntrusiveEllenBinTree_HP, base_item_counter )
167 typedef ci::EllenBinTree< gc_type, key_type, base_item_type,
168 ci::ellen_bintree::make_traits<
169 ci::opt::type_traits< generic_traits >
170 ,ci::opt::hook< ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >>>
171 ,ci::opt::compare< cmp<base_item_type>>
172 ,ci::opt::item_counter< simple_item_counter >
180 TEST_F( IntrusiveEllenBinTree_HP, base_backoff )
182 struct tree_traits: public generic_traits
184 typedef ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >> hook;
185 typedef cmp<base_item_type> compare;
186 typedef base_class::less<base_item_type> less;
187 typedef cds::atomicity::item_counter item_counter;
188 typedef cds::backoff::yield back_off;
191 typedef ci::EllenBinTree< gc_type, key_type, base_item_type, tree_traits > tree_type;
197 TEST_F( IntrusiveEllenBinTree_HP, base_seq_cst )
199 struct tree_traits: public generic_traits
201 typedef ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >> hook;
202 typedef cmp<base_item_type> compare;
203 typedef base_class::less<base_item_type> less;
204 typedef cds::atomicity::item_counter item_counter;
205 typedef cds::backoff::pause back_off;
206 typedef ci::opt::v::sequential_consistent memory_model;
209 typedef ci::EllenBinTree< gc_type, key_type, base_item_type, tree_traits > tree_type;
215 TEST_F( IntrusiveEllenBinTree_HP, base_update_desc_pool )
217 struct tree_traits: public generic_traits
219 typedef ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >> hook;
220 typedef base_class::less<base_item_type> less;
221 typedef cds::atomicity::item_counter item_counter;
222 typedef cds::memory::pool_allocator<update_base_desc, pool_accessor> update_desc_allocator;
225 typedef ci::EllenBinTree< gc_type, key_type, base_item_type, tree_traits > tree_type;
231 TEST_F( IntrusiveEllenBinTree_HP, base_update_desc_lazy_pool )
233 struct tree_traits: public generic_traits
235 typedef ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >> hook;
236 typedef base_class::less<base_item_type> less;
237 typedef cds::atomicity::item_counter item_counter;
238 typedef cds::memory::pool_allocator<update_base_desc, lazy_pool_accessor> update_desc_allocator;
241 typedef ci::EllenBinTree< gc_type, key_type, base_item_type, tree_traits > tree_type;
248 TEST_F( IntrusiveEllenBinTree_HP, member_cmp )
250 typedef ci::EllenBinTree< gc_type, key_type, member_item_type,
251 ci::ellen_bintree::make_traits<
252 ci::opt::type_traits< generic_traits >
253 ,ci::opt::hook< ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember), ci::opt::gc< gc_type >>>
254 ,ci::opt::compare< cmp<member_item_type>>
262 TEST_F( IntrusiveEllenBinTree_HP, member_less )
264 typedef ci::EllenBinTree< gc_type, key_type, member_item_type,
265 ci::ellen_bintree::make_traits<
266 ci::opt::type_traits< generic_traits >
267 ,ci::opt::hook< ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >>>
268 ,ci::opt::less< less<member_item_type>>
276 TEST_F( IntrusiveEllenBinTree_HP, member_item_counter )
278 typedef ci::EllenBinTree< gc_type, key_type, member_item_type,
279 ci::ellen_bintree::make_traits<
280 ci::opt::type_traits< generic_traits >
281 ,ci::opt::hook< ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >>>
282 ,ci::opt::compare< cmp<member_item_type>>
283 ,ci::opt::item_counter< simple_item_counter >
291 TEST_F( IntrusiveEllenBinTree_HP, member_backoff )
293 struct tree_traits: public generic_traits
295 typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >> hook;
296 typedef cmp<member_item_type> compare;
297 typedef base_class::less<member_item_type> less;
298 typedef cds::atomicity::item_counter item_counter;
299 typedef cds::backoff::yield back_off;
302 typedef ci::EllenBinTree< gc_type, key_type, member_item_type, tree_traits > tree_type;
308 TEST_F( IntrusiveEllenBinTree_HP, member_seq_cst )
310 struct tree_traits: public generic_traits
312 typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >> hook;
313 typedef cmp<member_item_type> compare;
314 typedef base_class::less<member_item_type> less;
315 typedef cds::atomicity::item_counter item_counter;
316 typedef cds::backoff::pause back_off;
317 typedef ci::opt::v::sequential_consistent memory_model;
320 typedef ci::EllenBinTree< gc_type, key_type, member_item_type, tree_traits > tree_type;
326 TEST_F( IntrusiveEllenBinTree_HP, member_update_desc_pool )
328 struct tree_traits: public generic_traits
330 typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >> hook;
331 typedef base_class::less<member_item_type> less;
332 typedef cds::atomicity::item_counter item_counter;
333 typedef cds::memory::pool_allocator<update_member_desc, pool_accessor> update_desc_allocator;
336 typedef ci::EllenBinTree< gc_type, key_type, member_item_type, tree_traits > tree_type;
342 TEST_F( IntrusiveEllenBinTree_HP, member_update_desc_lazy_pool )
344 struct tree_traits: public generic_traits
346 typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >> hook;
347 typedef base_class::less<member_item_type> less;
348 typedef cds::atomicity::item_counter item_counter;
349 typedef cds::memory::pool_allocator<update_member_desc, lazy_pool_accessor> update_desc_allocator;
352 typedef ci::EllenBinTree< gc_type, key_type, member_item_type, tree_traits > tree_type;