cds/container/skip_list_base.h

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