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 #ifndef CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
32 #define CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
34 #include <cds/intrusive/details/base.h>
35 #include <cds/details/marked_ptr.h>
36 #include <cds/algo/bitop.h>
37 #include <cds/os/timer.h>
38 #include <cds/urcu/options.h>
40 namespace cds { namespace intrusive {
41 /// SkipListSet related definitions
42 /** @ingroup cds_intrusive_helper
45 /// The maximum possible height of any skip-list
46 static unsigned int const c_nHeightLimit = 32;
51 - \p GC - garbage collector
52 - \p Tag - a \ref cds_intrusive_hook_tag "tag"
54 template <class GC, typename Tag = opt::none>
58 typedef GC gc; ///< Garbage collector
59 typedef Tag tag; ///< tag
61 typedef cds::details::marked_ptr<node, 1> marked_ptr; ///< marked pointer
62 typedef typename gc::template atomic_marked_ptr< marked_ptr> atomic_marked_ptr; ///< atomic marked pointer specific for GC
64 typedef atomic_marked_ptr tower_item_type;
70 atomic_marked_ptr m_pNext; ///< Next item in bottom-list (list at level 0)
71 unsigned int m_nHeight; ///< Node height (size of \p m_arrNext array). For node at level 0 the height is 1.
72 atomic_marked_ptr * m_arrNext; ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
79 , m_arrNext( nullptr )
83 /// Constructs a node's tower of height \p nHeight
84 void make_tower( unsigned int nHeight, atomic_marked_ptr * nextTower )
86 assert( nHeight > 0 );
87 assert( (nHeight == 1 && nextTower == nullptr) // bottom-list node
88 || (nHeight > 1 && nextTower != nullptr) // node at level of more than 0
91 m_arrNext = nextTower;
93 atomics::atomic_thread_fence( atomics::memory_order_release );
97 atomic_marked_ptr * release_tower()
99 atomic_marked_ptr * pTower = m_arrNext;
105 atomic_marked_ptr * get_tower() const
110 bool has_tower() const
112 return m_nHeight > 1;
116 /// Access to element of next pointer array
117 atomic_marked_ptr& next( unsigned int nLevel )
119 assert( nLevel < height());
120 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr));
122 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
125 /// Access to element of next pointer array (const version)
126 atomic_marked_ptr const& next( unsigned int nLevel ) const
128 assert( nLevel < height());
129 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
131 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
134 /// Access to element of next pointer array (synonym for \p next() function)
135 atomic_marked_ptr& operator[]( unsigned int nLevel )
137 return next( nLevel );
140 /// Access to element of next pointer array (synonym for \p next() function)
141 atomic_marked_ptr const& operator[]( unsigned int nLevel ) const
143 return next( nLevel );
146 /// Height of the node
147 unsigned int height() const
152 /// Clears internal links
155 assert( m_arrNext == nullptr );
156 m_pNext.store( marked_ptr(), atomics::memory_order_release );
160 bool is_cleared() const
162 return m_pNext == atomic_marked_ptr()
163 && m_arrNext == nullptr
171 struct default_hook {
172 typedef undefined_gc gc;
173 typedef opt::none tag;
178 template < typename HookType, typename... Options>
181 typedef typename opt::make_options< default_hook, Options...>::type options;
182 typedef typename options::gc gc;
183 typedef typename options::tag tag;
184 typedef node<gc, tag> node_type;
185 typedef HookType hook_type;
192 - \p opt::gc - garbage collector
193 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
195 template < typename... Options >
196 struct base_hook: public hook< opt::base_hook_tag, Options... >
201 \p MemberOffset defines offset in bytes of \ref node member into your structure.
202 Use \p offsetof macro to define \p MemberOffset
205 - \p opt::gc - garbage collector
206 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
208 template < size_t MemberOffset, typename... Options >
209 struct member_hook: public hook< opt::member_hook_tag, Options... >
212 static const size_t c_nMemberOffset = MemberOffset;
218 \p NodeTraits defines type traits for node.
219 See \ref node_traits for \p NodeTraits interface description
222 - \p opt::gc - garbage collector
223 - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
225 template <typename NodeTraits, typename... Options >
226 struct traits_hook: public hook< opt::traits_hook_tag, Options... >
229 typedef NodeTraits node_traits;
233 /// Option specifying random level generator
235 The random level generator is an important part of skip-list algorithm.
236 The node height in the skip-list have a probabilistic distribution
237 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
239 The random level generator should provide such distribution.
241 The \p Type functor interface is:
243 struct random_generator {
244 static unsigned int const c_nUpperBound = 32;
246 unsigned int operator()();
251 - \p c_nUpperBound - constant that specifies the upper bound of random number generated.
252 The generator produces a number from range <tt>[0 .. c_nUpperBound)</tt> (upper bound excluded).
253 \p c_nUpperBound must be no more than 32.
254 - <tt>random_generator()</tt> - the constructor of generator object initialises the generator instance (its internal state).
255 - <tt>unsigned int operator()()</tt> - the main generating function. Returns random level from range 0..31.
257 Stateful generators are supported.
259 Available \p Type implementations:
260 - \p skip_list::xorshift
261 - \p skip_list::turbo_pascal
263 template <typename Type>
264 struct random_level_generator {
266 template <typename Base>
267 struct pack: public Base
269 typedef Type random_level_generator;
274 /// Xor-shift random level generator
276 The simplest of the generators described in George
277 Marsaglia's "Xorshift RNGs" paper. This is not a high-quality
278 generator but is acceptable for skip-list.
280 The random generator should return numbers from range [0..31].
282 From Doug Lea's ConcurrentSkipListMap.java.
286 atomics::atomic<unsigned int> m_nSeed;
289 /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
290 static unsigned int const c_nUpperBound = c_nHeightLimit;
292 /// Initializes the generator instance
295 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
298 /// Main generator function
299 unsigned int operator()()
301 /* ConcurrentSkipListMap.java
302 private int randomLevel() {
306 randomSeed = x ^= x << 5;
307 if ((x & 0x80000001) != 0) // test highest and lowest bits
310 while (((x >>>= 1) & 1) != 0) ++level;
314 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed );
318 m_nSeed.store( x, atomics::memory_order_relaxed );
319 unsigned int nLevel = ((x & 0x00000001) != 0) ? 0 : cds::bitop::LSB( (~(x >> 1)) & 0x7FFFFFFF );
320 assert( nLevel < c_nUpperBound );
325 /// Turbo-pascal random level generator
327 This uses a cheap pseudo-random function that was used in Turbo Pascal.
329 The random generator should return numbers from range [0..31].
331 From Doug Lea's ConcurrentSkipListMap.java.
336 atomics::atomic<unsigned int> m_nSeed;
339 /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
340 static unsigned int const c_nUpperBound = c_nHeightLimit;
342 /// Initializes the generator instance
345 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
348 /// Main generator function
349 unsigned int operator()()
352 private int randomLevel() {
355 randomSeed = r * 134775813 + 1;
357 while ((r <<= 1) > 0)
364 The low bits are apparently not very random (the original used only
365 upper 16 bits) so we traverse from highest bit down (i.e., test
366 sign), thus hardly ever use lower bits.
368 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed ) * 134775813 + 1;
369 m_nSeed.store( x, atomics::memory_order_relaxed );
370 unsigned int nLevel = ( x & 0x80000000 ) ? (31 - cds::bitop::MSBnz( (x & 0x7FFFFFFF) | 1 )) : 0;
371 assert( nLevel < c_nUpperBound );
376 /// \p SkipListSet internal statistics
377 template <typename EventCounter = cds::atomicity::event_counter>
379 typedef EventCounter event_counter ; ///< Event counter type
381 event_counter m_nNodeHeightAdd[c_nHeightLimit] ; ///< Count of added node of each height
382 event_counter m_nNodeHeightDel[c_nHeightLimit] ; ///< Count of deleted node of each height
383 event_counter m_nInsertSuccess ; ///< Count of success insertion
384 event_counter m_nInsertFailed ; ///< Count of failed insertion
385 event_counter m_nInsertRetries ; ///< Count of unsuccessful retries of insertion
386 event_counter m_nUpdateExist ; ///< Count of \p update() call for existed node
387 event_counter m_nUpdateNew ; ///< Count of \p update() call for new node
388 event_counter m_nUnlinkSuccess ; ///< Count of successful call of \p unlink
389 event_counter m_nUnlinkFailed ; ///< Count of failed call of \p unlink
390 event_counter m_nEraseSuccess ; ///< Count of successful call of \p erase
391 event_counter m_nEraseFailed ; ///< Count of failed call of \p erase
392 event_counter m_nEraseRetry ; ///< Count of retries while erasing node
393 event_counter m_nFindFastSuccess ; ///< Count of successful call of \p find and all derivatives (via fast-path)
394 event_counter m_nFindFastFailed ; ///< Count of failed call of \p find and all derivatives (via fast-path)
395 event_counter m_nFindSlowSuccess ; ///< Count of successful call of \p find and all derivatives (via slow-path)
396 event_counter m_nFindSlowFailed ; ///< Count of failed call of \p find and all derivatives (via slow-path)
397 event_counter m_nRenewInsertPosition ; ///< Count of renewing position events while inserting
398 event_counter m_nLogicDeleteWhileInsert ; ///< Count of events "The node has been logically deleted while inserting"
399 event_counter m_nNotFoundWhileInsert ; ///< Count of events "Inserting node is not found"
400 event_counter m_nFastErase ; ///< Fast erase event counter
401 event_counter m_nFastExtract ; ///< Fast extract event counter
402 event_counter m_nSlowErase ; ///< Slow erase event counter
403 event_counter m_nSlowExtract ; ///< Slow extract event counter
404 event_counter m_nExtractSuccess ; ///< Count of successful call of \p extract
405 event_counter m_nExtractFailed ; ///< Count of failed call of \p extract
406 event_counter m_nExtractRetries ; ///< Count of retries of \p extract call
407 event_counter m_nExtractMinSuccess ; ///< Count of successful call of \p extract_min
408 event_counter m_nExtractMinFailed ; ///< Count of failed call of \p extract_min
409 event_counter m_nExtractMinRetries ; ///< Count of retries of \p extract_min call
410 event_counter m_nExtractMaxSuccess ; ///< Count of successful call of \p extract_max
411 event_counter m_nExtractMaxFailed ; ///< Count of failed call of \p extract_max
412 event_counter m_nExtractMaxRetries ; ///< Count of retries of \p extract_max call
413 event_counter m_nEraseWhileFind ; ///< Count of erased item while searching
414 event_counter m_nExtractWhileFind ; ///< Count of extracted item while searching (RCU only)
417 void onAddNode( unsigned int nHeight )
419 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightAdd) / sizeof(m_nNodeHeightAdd[0]));
420 ++m_nNodeHeightAdd[nHeight - 1];
422 void onRemoveNode( unsigned int nHeight )
424 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightDel) / sizeof(m_nNodeHeightDel[0]));
425 ++m_nNodeHeightDel[nHeight - 1];
428 void onInsertSuccess() { ++m_nInsertSuccess ; }
429 void onInsertFailed() { ++m_nInsertFailed ; }
430 void onInsertRetry() { ++m_nInsertRetries ; }
431 void onUpdateExist() { ++m_nUpdateExist ; }
432 void onUpdateNew() { ++m_nUpdateNew ; }
433 void onUnlinkSuccess() { ++m_nUnlinkSuccess ; }
434 void onUnlinkFailed() { ++m_nUnlinkFailed ; }
435 void onEraseSuccess() { ++m_nEraseSuccess ; }
436 void onEraseFailed() { ++m_nEraseFailed ; }
437 void onEraseRetry() { ++m_nEraseRetry; }
438 void onFindFastSuccess() { ++m_nFindFastSuccess ; }
439 void onFindFastFailed() { ++m_nFindFastFailed ; }
440 void onFindSlowSuccess() { ++m_nFindSlowSuccess ; }
441 void onFindSlowFailed() { ++m_nFindSlowFailed ; }
442 void onEraseWhileFind() { ++m_nEraseWhileFind ; }
443 void onExtractWhileFind() { ++m_nExtractWhileFind ; }
444 void onRenewInsertPosition() { ++m_nRenewInsertPosition; }
445 void onLogicDeleteWhileInsert() { ++m_nLogicDeleteWhileInsert; }
446 void onNotFoundWhileInsert() { ++m_nNotFoundWhileInsert; }
447 void onFastErase() { ++m_nFastErase; }
448 void onFastExtract() { ++m_nFastExtract; }
449 void onSlowErase() { ++m_nSlowErase; }
450 void onSlowExtract() { ++m_nSlowExtract; }
451 void onExtractSuccess() { ++m_nExtractSuccess; }
452 void onExtractFailed() { ++m_nExtractFailed; }
453 void onExtractRetry() { ++m_nExtractRetries; }
454 void onExtractMinSuccess() { ++m_nExtractMinSuccess; }
455 void onExtractMinFailed() { ++m_nExtractMinFailed; }
456 void onExtractMinRetry() { ++m_nExtractMinRetries; }
457 void onExtractMaxSuccess() { ++m_nExtractMaxSuccess; }
458 void onExtractMaxFailed() { ++m_nExtractMaxFailed; }
459 void onExtractMaxRetry() { ++m_nExtractMaxRetries; }
463 /// \p SkipListSet empty internal statistics
466 void onAddNode( unsigned int /*nHeight*/ ) const {}
467 void onRemoveNode( unsigned int /*nHeight*/ ) const {}
468 void onInsertSuccess() const {}
469 void onInsertFailed() const {}
470 void onInsertRetry() const {}
471 void onUpdateExist() const {}
472 void onUpdateNew() const {}
473 void onUnlinkSuccess() const {}
474 void onUnlinkFailed() const {}
475 void onEraseSuccess() const {}
476 void onEraseFailed() const {}
477 void onEraseRetry() const {}
478 void onFindFastSuccess() const {}
479 void onFindFastFailed() const {}
480 void onFindSlowSuccess() const {}
481 void onFindSlowFailed() const {}
482 void onEraseWhileFind() const {}
483 void onExtractWhileFind() const {}
484 void onRenewInsertPosition() const {}
485 void onLogicDeleteWhileInsert() const {}
486 void onNotFoundWhileInsert() const {}
487 void onFastErase() const {}
488 void onFastExtract() const {}
489 void onSlowErase() const {}
490 void onSlowExtract() const {}
491 void onExtractSuccess() const {}
492 void onExtractFailed() const {}
493 void onExtractRetry() const {}
494 void onExtractMinSuccess() const {}
495 void onExtractMinFailed() const {}
496 void onExtractMinRetry() const {}
497 void onExtractMaxSuccess() const {}
498 void onExtractMaxFailed() const {}
499 void onExtractMaxRetry() const {}
504 // For internal use only!!!
505 template <typename Type>
506 struct internal_node_builder {
507 template <typename Base>
508 struct pack: public Base
510 typedef Type internal_node_builder;
515 /// \p SkipListSet traits
520 Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
522 typedef base_hook<> hook;
524 /// Key comparison functor
526 No default functor is provided. If the option is not specified, the \p less is used.
528 typedef opt::none compare;
530 /// specifies binary predicate used for key compare.
532 Default is \p std::less<T>.
534 typedef opt::none less;
538 The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
540 typedef opt::v::empty_disposer disposer;
544 The type for item counting feature.
545 By default, item counting is disabled (\p atomicity::empty_item_counter),
546 \p atomicity::item_counter enables it.
548 typedef atomicity::empty_item_counter item_counter;
550 /// C++ memory ordering model
552 List of available memory ordering see \p opt::memory_model
554 typedef opt::v::relaxed_ordering memory_model;
556 /// Random level generator
558 The random level generator is an important part of skip-list algorithm.
559 The node height in the skip-list have a probabilistic distribution
560 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
561 (i = 0..30). So, the height of a node is in range [0..31].
563 See \p skip_list::random_level_generator option setter.
565 typedef turbo_pascal random_level_generator;
569 Although the skip-list is an intrusive container,
570 an allocator should be provided to maintain variable randomly-calculated height of the node
571 since the node can contain up to 32 next pointers.
572 The allocator specified is used to allocate an array of next pointers
573 for nodes which height is more than 1.
575 typedef CDS_DEFAULT_ALLOCATOR allocator;
577 /// back-off strategy
579 If the option is not specified, the \p cds::backoff::Default is used.
581 typedef cds::backoff::Default back_off;
583 /// Internal statistics
585 By default, internal statistics is disabled (\p skip_list::empty_stat).
586 Use \p skip_list::stat to enable it.
588 typedef empty_stat stat;
590 /// RCU deadlock checking policy (only for \ref cds_intrusive_SkipListSet_rcu "RCU-based SkipListSet")
592 List of available options see \p opt::rcu_check_deadlock
594 typedef opt::v::rcu_throw_deadlock rcu_check_deadlock;
597 // For internal use only!!!
598 typedef opt::none internal_node_builder;
602 /// Metafunction converting option list to \p SkipListSet traits
605 - \p opt::hook - hook used. Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
606 If the option is not specified, <tt>skip_list::base_hook<></tt> and \p gc::HP is used.
607 - \p opt::compare - key comparison functor. No default functor is provided.
608 If the option is not specified, the \p opt::less is used.
609 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
610 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
611 of GC schema the disposer may be called asynchronously.
612 - \p opt::item_counter - the type of item counting feature. Default is disabled, i.e. \p atomicity::empty_item_counter.
613 To enable it use \p atomicity::item_counter
614 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
615 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
616 - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xorshift,
617 \p skip_list::turbo_pascal (the default) or
618 user-provided one. See \p skip_list::random_level_generator option description for explanation.
619 - \p opt::allocator - although the skip-list is an intrusive container,
620 an allocator should be provided to maintain variable randomly-calculated height of the node
621 since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
622 for nodes which height is more than 1. Default is \ref CDS_DEFAULT_ALLOCATOR.
623 - \p opt::back_off - back-off strategy, default is \p cds::backoff::Default.
624 - \p opt::stat - internal statistics. By default, it is disabled (\p skip_list::empty_stat).
625 To enable it use \p skip_list::stat
627 template <typename... Options>
629 # ifdef CDS_DOXYGEN_INVOKED
630 typedef implementation_defined type ; ///< Metafunction result
632 typedef typename cds::opt::make_options<
633 typename cds::opt::find_type_traits< traits, Options... >::type
641 template <typename Node>
642 class head_node: public Node
644 typedef Node node_type;
645 typename node_type::atomic_marked_ptr m_Tower[skip_list::c_nHeightLimit];
648 head_node( unsigned int nHeight )
650 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
651 m_Tower[i].store( typename node_type::marked_ptr(), atomics::memory_order_relaxed );
653 node_type::make_tower( nHeight, m_Tower );
656 node_type * head() const
658 return const_cast<node_type *>( static_cast<node_type const *>(this));
662 template <typename NodeType, typename AtomicNodePtr, typename Alloc>
663 struct intrusive_node_builder
665 typedef NodeType node_type;
666 typedef AtomicNodePtr atomic_node_ptr;
667 typedef Alloc allocator_type;
669 typedef cds::details::Allocator< atomic_node_ptr, allocator_type > tower_allocator;
671 template <typename RandomGen>
672 static node_type * make_tower( node_type * pNode, RandomGen& gen )
674 return make_tower( pNode, gen() + 1 );
677 static node_type * make_tower( node_type * pNode, unsigned int nHeight )
680 pNode->make_tower( nHeight, tower_allocator().NewArray( nHeight - 1, nullptr ));
684 static void dispose_tower( node_type * pNode )
686 unsigned int nHeight = pNode->height();
688 tower_allocator().Delete( pNode->release_tower(), nHeight );
691 struct node_disposer {
692 void operator()( node_type * pNode )
694 dispose_tower( pNode );
699 // Forward declaration
700 template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
703 } // namespace details
706 } // namespace skip_list
708 // Forward declaration
709 template <class GC, typename T, typename Traits = skip_list::traits >
712 }} // namespace cds::intrusive
714 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H