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