cds/container/details/skip_list_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_DETAILS_SKIP_LIST_BASE_H
   4 #define CDSLIB_CONTAINER_DETAILS_SKIP_LIST_BASE_H
   5
   6 #include <cds/intrusive/details/skip_list_base.h>
   7 #include <cds/container/details/base.h>
   8
   9 namespace cds { namespace container {
  10
  11     /// SkipListSet related definitions
  12     /** @ingroup cds_nonintrusive_helper
  13     */
  14     namespace skip_list {
  15         using cds::intrusive::skip_list::implementation_tag;
  16
  17         /// Option specifying random level generator
  18         template <typename Type>
  19         using random_level_generator = cds::intrusive::skip_list::random_level_generator<Type>;
  20
  21         /// Xor-shift random level generator
  22         typedef cds::intrusive::skip_list::xorshift xorshift;
  23
  24         /// Turbo-pascal random level generator
  25         typedef cds::intrusive::skip_list::turbo_pascal turbo_pascal;
  26
  27         /// Skip list internal statistics
  28         template <typename EventCounter = cds::atomicity::event_counter>
  29         using stat = cds::intrusive::skip_list::stat < EventCounter >;
  30
  31         /// Skip list empty internal statistics
  32         typedef cds::intrusive::skip_list::empty_stat empty_stat;
  33
  34         /// SkipListSet traits
  35         struct traits
  36         {
  37             /// Key comparison functor
  38             /**
  39                 No default functor is provided. If the option is not specified, the \p less is used.
  40             */
  41             typedef opt::none                       compare;
  42
  43             /// specifies binary predicate used for key compare.
  44             /**
  45                 Default is \p std::less<T>.
  46             */
  47             typedef opt::none                       less;
  48
  49             /// Item counter
  50             /**
  51                 The type for item counting feature,
  52                  by defaulr disabled (\p atomicity::empty_item_counter)
  53             */
  54             typedef atomicity::empty_item_counter     item_counter;
  55
  56             /// C++ memory ordering model
  57             /**
  58                 List of available memory ordering see \p opt::memory_model
  59             */
  60             typedef opt::v::relaxed_ordering        memory_model;
  61
  62             /// Random level generator
  63             /**
  64                 The random level generator is an important part of skip-list algorithm.
  65                 The node height in the skip-list have a probabilistic distribution
  66                 where half of the nodes that have level \p i also have level <tt>i+1</tt>
  67                 (i = 0..30). The height of a node is in range [0..31].
  68
  69                 See \p skip_list::random_level_generator option setter.
  70             */
  71             typedef turbo_pascal                    random_level_generator;
  72
  73             /// Allocator for skip-list nodes, \p std::allocator interface
  74             typedef CDS_DEFAULT_ALLOCATOR           allocator;
  75
  76             /// back-off strategy, default is \p cds::backoff::Default
  77             typedef cds::backoff::Default           back_off;
  78
  79             /// Internal statistics, by default disabled. To enable, use \p split_list::stat
  80             typedef empty_stat                      stat;
  81
  82             /// RCU deadlock checking policy (for \ref cds_nonintrusive_SkipListSet_rcu "RCU-based SkipListSet")
  83             /**
  84                 List of available options see opt::rcu_check_deadlock
  85             */
  86             typedef opt::v::rcu_throw_deadlock      rcu_check_deadlock;
  87
  88             //@cond
  89             // For internal use only
  90             typedef opt::none                       key_accessor;
  91             //@endcond
  92         };
  93
  94         /// Metafunction converting option list to SkipListSet traits
  95         /**
  96             \p Options are:
  97             - \p opt::compare - key comparison functor. No default functor is provided.
  98                 If the option is not specified, the \p opt::less is used.
  99             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 100             - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::empty_item_counter that is no item counting.
 101             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 102                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 103             - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xorshift, \p skip_list::turbo_pascal or
 104                 user-provided one.
 105                 Default is \p %skip_list::turbo_pascal.
 106             - \p opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
 107             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 108             - \p opt::stat - internal statistics. Available types: \p skip_list::stat, \p skip_list::empty_stat (the default)
 109             - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based skip-list.
 110                 Default is \p opt::v::rcu_throw_deadlock
 111
 112         */
 113         template <typename... Options>
 114         struct make_traits {
 115 #   ifdef CDS_DOXYGEN_INVOKED
 116             typedef implementation_defined type ;   ///< Metafunction result
 117 #   else
 118             typedef typename cds::opt::make_options<
 119                 typename cds::opt::find_type_traits< traits, Options... >::type
 120                 ,Options...
 121             >::type   type;
 122 #   endif
 123         };
 124
 125         //@cond
 126         namespace details {
 127
 128             template <typename Node, typename Traits>
 129             class node_allocator
 130             {
 131             protected:
 132                 typedef Node node_type;
 133                 typedef Traits traits;
 134
 135                 typedef typename node_type::tower_item_type node_tower_item;
 136                 typedef typename traits::allocator::template rebind<unsigned char>::other  tower_allocator_type;
 137                 typedef typename traits::allocator::template rebind<node_type>::other      node_allocator_type;
 138
 139                 static size_t const c_nTowerItemSize = sizeof(node_tower_item);
 140                 static size_t const c_nNodePadding = sizeof(node_type) % c_nTowerItemSize;
 141                 static size_t const c_nNodeSize = sizeof(node_type) + (c_nNodePadding ? (c_nTowerItemSize - c_nNodePadding) : 0);
 142
 143                 static CDS_CONSTEXPR size_t node_size( unsigned int nHeight ) CDS_NOEXCEPT
 144                 {
 145                     return c_nNodeSize + (nHeight - 1) * c_nTowerItemSize;
 146                 }
 147                 static unsigned char * alloc_space( unsigned int nHeight )
 148                 {
 149                     if ( nHeight > 1 ) {
 150                         unsigned char * pMem = tower_allocator_type().allocate( node_size(nHeight) );
 151
 152                         // check proper alignments
 153                         assert( (((uintptr_t) pMem) & (alignof(node_type) - 1)) == 0 );
 154                         assert( (((uintptr_t) (pMem + c_nNodeSize)) & (alignof(node_tower_item) - 1)) == 0 );
 155                         return pMem;
 156                     }
 157
 158                     return reinterpret_cast<unsigned char *>( node_allocator_type().allocate(1));
 159                 }
 160
 161                 static void free_space( unsigned char * p, unsigned int nHeight )
 162                 {
 163                     assert( p != nullptr );
 164                     if ( nHeight == 1 )
 165                         node_allocator_type().deallocate( reinterpret_cast<node_type *>(p), 1 );
 166                     else
 167                         tower_allocator_type().deallocate( p, node_size(nHeight));
 168                 }
 169
 170             public:
 171                 template <typename Q>
 172                 node_type * New( unsigned int nHeight, Q const& v )
 173                 {
 174                     CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
 175                     unsigned char * pMem = alloc_space( nHeight );
 176                     node_type * p = new( pMem )
 177                         node_type( nHeight, nHeight > 1 ? reinterpret_cast<node_tower_item *>(pMem + c_nNodeSize) : nullptr, v );
 178                     CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
 179                     return p;
 180                 }
 181
 182                 template <typename... Args>
 183                 node_type * New( unsigned int nHeight, Args&&... args )
 184                 {
 185                     CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
 186                     unsigned char * pMem = alloc_space( nHeight );
 187                     node_type * p = new( pMem )
 188                         node_type( nHeight, nHeight > 1 ? reinterpret_cast<node_tower_item *>(pMem + c_nNodeSize) : nullptr,
 189                         std::forward<Args>(args)... );
 190                     CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
 191                     return p;
 192                 }
 193
 194                 void Delete( node_type * p )
 195                 {
 196                     assert( p != nullptr );
 197
 198                     unsigned int nHeight = p->height();
 199                     node_allocator_type().destroy( p );
 200                     CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
 201                     free_space( reinterpret_cast<unsigned char *>(p), nHeight );
 202                     CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
 203                 }
 204             };
 205
 206             template <typename IntrusiveNode>
 207             struct dummy_node_builder {
 208                 typedef IntrusiveNode intrusive_node_type;
 209
 210                 template <typename RandomGen>
 211                 static intrusive_node_type * make_tower( intrusive_node_type * pNode, RandomGen& /*gen*/ ) { return pNode ; }
 212                 static intrusive_node_type * make_tower( intrusive_node_type * pNode, unsigned int /*nHeight*/ ) { return pNode ; }
 213                 static void dispose_tower( intrusive_node_type * pNode )
 214                 {
 215                     pNode->release_tower();
 216                 }
 217
 218                 struct node_disposer {
 219                     void operator()( intrusive_node_type * /*pNode*/ ) const {}
 220                 };
 221             };
 222
 223             template <typename ForwardIterator>
 224             class iterator
 225             {
 226                 typedef ForwardIterator intrusive_iterator;
 227                 typedef typename intrusive_iterator::value_type node_type;
 228                 typedef typename node_type::stored_value_type   value_type;
 229                 static bool const c_isConst = intrusive_iterator::c_isConst;
 230
 231                 typedef typename std::conditional< c_isConst, value_type const&, value_type&>::type   value_ref;
 232                 template <typename FwdIt> friend class iterator;
 233
 234                 intrusive_iterator      m_It;
 235
 236             public: // for internal use only!!!
 237                 iterator( intrusive_iterator const& it )
 238                     : m_It( it )
 239                 {}
 240
 241             public:
 242                 iterator()
 243                     : m_It()
 244                 {}
 245
 246                 iterator( iterator const& s)
 247                     : m_It( s.m_It )
 248                 {}
 249
 250                 value_type * operator ->() const
 251                 {
 252                     return &( m_It.operator->()->m_Value );
 253                 }
 254
 255                 value_ref operator *() const
 256                 {
 257                     return m_It.operator*().m_Value;
 258                 }
 259
 260                 /// Pre-increment
 261                 iterator& operator ++()
 262                 {
 263                     ++m_It;
 264                     return *this;
 265                 }
 266
 267                 iterator& operator = (iterator const& src)
 268                 {
 269                     m_It = src.m_It;
 270                     return *this;
 271                 }
 272
 273                 template <typename FwIt>
 274                 bool operator ==(iterator<FwIt> const& i ) const
 275                 {
 276                     return m_It == i.m_It;
 277                 }
 278                 template <typename FwIt>
 279                 bool operator !=(iterator<FwIt> const& i ) const
 280                 {
 281                     return !( *this == i );
 282                 }
 283             };
 284
 285         } // namespace details
 286         //@endcond
 287
 288     } // namespace skip_list
 289
 290     // Forward declaration
 291     template <class GC, typename T, typename Traits = skip_list::traits >
 292     class SkipListSet;
 293
 294     // Forward declaration
 295     template <class GC, typename K, typename T, typename Traits = skip_list::traits >
 296     class SkipListMap;
 297
 298 }} // namespace cds::container
 299
 300 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_SKIP_LIST_BASE_H