-//$$CDS-header$$
-
-#ifndef __CDS_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
-#define __CDS_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+ Source code repo: http://github.com/khizmax/libcds/
+ Download: http://sourceforge.net/projects/libcds/files/
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
+#define CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
#include <cds/intrusive/details/base.h>
#include <cds/details/marked_ptr.h>
/** @ingroup cds_intrusive_helper
*/
namespace skip_list {
-
/// The maximum possible height of any skip-list
static unsigned int const c_nHeightLimit = 32;
- \p Tag - a \ref cds_intrusive_hook_tag "tag"
*/
template <class GC, typename Tag = opt::none>
- class node
+ class node
{
public:
typedef GC gc; ///< Garbage collector
assert( nLevel < height() );
assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr) );
+# ifdef CDS_THREAD_SANITIZER_ENABLED
+ // TSan false positive: m_arrNext is read-only array
+ CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN;
+ atomic_marked_ptr& r = nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
+ CDS_TSAN_ANNOTATE_IGNORE_READS_END;
+ return r;
+# else
return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
+# endif
}
/// Access to element of next pointer array (const version)
assert( nLevel < height() );
assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
+# ifdef CDS_THREAD_SANITIZER_ENABLED
+ // TSan false positive: m_arrNext is read-only array
+ CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN;
+ atomic_marked_ptr const& r = nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
+ CDS_TSAN_ANNOTATE_IGNORE_READS_END;
+ return r;
+# else
return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
+# endif
}
/// Access to element of next pointer array (same as \ref next function)
event_counter m_nInsertSuccess ; ///< Count of success insertion
event_counter m_nInsertFailed ; ///< Count of failed insertion
event_counter m_nInsertRetries ; ///< Count of unsuccessful retries of insertion
- event_counter m_nEnsureExist ; ///< Count of \p ensure call for existed node
- event_counter m_nEnsureNew ; ///< Count of \p ensure call for new node
+ event_counter m_nUpdateExist ; ///< Count of \p update() call for existed node
+ event_counter m_nUpdateNew ; ///< Count of \p update() call for new node
event_counter m_nUnlinkSuccess ; ///< Count of successful call of \p unlink
event_counter m_nUnlinkFailed ; ///< Count of failed call of \p unlink
event_counter m_nEraseSuccess ; ///< Count of successful call of \p erase
event_counter m_nEraseFailed ; ///< Count of failed call of \p erase
+ event_counter m_nEraseRetry ; ///< Count of retries while erasing node
event_counter m_nFindFastSuccess ; ///< Count of successful call of \p find and all derivatives (via fast-path)
event_counter m_nFindFastFailed ; ///< Count of failed call of \p find and all derivatives (via fast-path)
event_counter m_nFindSlowSuccess ; ///< Count of successful call of \p find and all derivatives (via slow-path)
void onInsertSuccess() { ++m_nInsertSuccess ; }
void onInsertFailed() { ++m_nInsertFailed ; }
void onInsertRetry() { ++m_nInsertRetries ; }
- void onEnsureExist() { ++m_nEnsureExist ; }
- void onEnsureNew() { ++m_nEnsureNew ; }
+ void onUpdateExist() { ++m_nUpdateExist ; }
+ void onUpdateNew() { ++m_nUpdateNew ; }
void onUnlinkSuccess() { ++m_nUnlinkSuccess ; }
void onUnlinkFailed() { ++m_nUnlinkFailed ; }
void onEraseSuccess() { ++m_nEraseSuccess ; }
void onEraseFailed() { ++m_nEraseFailed ; }
+ void onEraseRetry() { ++m_nEraseRetry; }
void onFindFastSuccess() { ++m_nFindFastSuccess ; }
void onFindFastFailed() { ++m_nFindFastFailed ; }
void onFindSlowSuccess() { ++m_nFindSlowSuccess ; }
/// \p SkipListSet empty internal statistics
struct empty_stat {
//@cond
- void onAddNode( unsigned int nHeight ) const {}
- void onRemoveNode( unsigned int nHeight ) const {}
+ void onAddNode( unsigned int /*nHeight*/ ) const {}
+ void onRemoveNode( unsigned int /*nHeight*/ ) const {}
void onInsertSuccess() const {}
void onInsertFailed() const {}
void onInsertRetry() const {}
- void onEnsureExist() const {}
- void onEnsureNew() const {}
+ void onUpdateExist() const {}
+ void onUpdateNew() const {}
void onUnlinkSuccess() const {}
void onUnlinkFailed() const {}
void onEraseSuccess() const {}
void onEraseFailed() const {}
+ void onEraseRetry() const {}
void onFindFastSuccess() const {}
void onFindFastFailed() const {}
void onFindSlowSuccess() const {}
/// Item counter
/**
The type for item counting feature.
- By default, item counting is disabled (\p atomicity::empty_item_counter)
+ By default, item counting is disabled (\p atomicity::empty_item_counter),
\p atomicity::item_counter enables it.
*/
typedef atomicity::empty_item_counter item_counter;
To enable it use \p atomicity::item_counter
- \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
or \p opt::v::sequential_consistent (sequentially consisnent memory model).
- - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xorshift,
+ - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xorshift,
\p skip_list::turbo_pascal (the default) or
user-provided one. See \p skip_list::random_level_generator option description for explanation.
- \p opt::allocator - although the skip-list is an intrusive container,
an allocator should be provided to maintain variable randomly-calculated height of the node
since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
for nodes which height is more than 1. Default is \ref CDS_DEFAULT_ALLOCATOR.
- - \p opt::back_off - back-off strategy, default is \รง cds::backoff::Default.
+ - \p opt::back_off - back-off strategy, default is \p cds::backoff::Default.
- \p opt::stat - internal statistics. By default, it is disabled (\p skip_list::empty_stat).
To enable it use \p skip_list::stat
*/
}} // namespace cds::intrusive
-#endif // #ifndef __CDS_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
+#endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H
projects / libcds.git / blobdiff