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