cds/container/details/skip_list_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_DETAILS_SKIP_LIST_BASE_H
   4 #define __CDS_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
  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 <typename... Options>
 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, Options... >::type
 126                 ,Options...
 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                 template <typename... Args>
 186                 node_type * New( unsigned int nHeight, Args&&... args )
 187                 {
 188                     unsigned char * pMem = alloc_space( nHeight );
 189                     return new( pMem )
 190                         node_type( nHeight, nHeight > 1 ? reinterpret_cast<node_tower_item *>(pMem + c_nNodeSize) : nullptr,
 191                         std::forward<Args>(args)... );
 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                     free_space( reinterpret_cast<unsigned char *>(p), nHeight );
 201                 }
 202             };
 203
 204             template <typename IntrusiveNode>
 205             struct dummy_node_builder {
 206                 typedef IntrusiveNode intrusive_node_type;
 207
 208                 template <typename RandomGen>
 209                 static intrusive_node_type * make_tower( intrusive_node_type * pNode, RandomGen& /*gen*/ ) { return pNode ; }
 210                 static intrusive_node_type * make_tower( intrusive_node_type * pNode, unsigned int /*nHeight*/ ) { return pNode ; }
 211                 static void dispose_tower( intrusive_node_type * pNode )
 212                 {
 213                     pNode->release_tower();
 214                 }
 215
 216                 struct node_disposer {
 217                     void operator()( intrusive_node_type * pNode ) const {}
 218                 };
 219             };
 220
 221             template <typename ForwardIterator>
 222             class iterator
 223             {
 224                 typedef ForwardIterator intrusive_iterator;
 225                 typedef typename intrusive_iterator::value_type node_type;
 226                 typedef typename node_type::stored_value_type   value_type;
 227                 static bool const c_isConst = intrusive_iterator::c_isConst;
 228
 229                 typedef typename std::conditional< c_isConst, value_type const &, value_type &>::type   value_ref;
 230
 231                 intrusive_iterator      m_It;
 232
 233             public: // for internal use only!!!
 234                 iterator( intrusive_iterator const& it )
 235                     : m_It( it )
 236                 {}
 237
 238             public:
 239                 iterator()
 240                     : m_It()
 241                 {}
 242
 243                 iterator( iterator const& s)
 244                     : m_It( s.m_It )
 245                 {}
 246
 247                 value_type * operator ->() const
 248                 {
 249                     return &( m_It.operator->()->m_Value );
 250                 }
 251
 252                 value_ref operator *() const
 253                 {
 254                     return m_It.operator*().m_Value;
 255                 }
 256
 257                 /// Pre-increment
 258                 iterator& operator ++()
 259                 {
 260                     ++m_It;
 261                     return *this;
 262                 }
 263
 264                 iterator& operator = (iterator const& src)
 265                 {
 266                     m_It = src.m_It;
 267                     return *this;
 268                 }
 269
 270                 template <typename FwIt>
 271                 bool operator ==(iterator<FwIt> const& i ) const
 272                 {
 273                     return m_It == i.m_It;
 274                 }
 275                 template <typename FwIt>
 276                 bool operator !=(iterator<FwIt> const& i ) const
 277                 {
 278                     return !( *this == i );
 279                 }
 280             };
 281
 282         } // namespace details
 283         //@endcond
 284
 285     } // namespace skip_list
 286
 287     // Forward declaration
 288     template <class GC, typename T, typename Traits = skip_list::type_traits >
 289     class SkipListSet;
 290
 291     // Forward declaration
 292     template <class GC, typename K, typename T, typename Traits = skip_list::type_traits >
 293     class SkipListMap;
 294
 295 }} // namespace cds::container
 296
 297 #endif // #ifndef __CDS_CONTAINER_DETAILS_SKIP_LIST_BASE_H