cds/container/details/skip_list_base.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_CONTAINER_DETAILS_SKIP_LIST_BASE_H
  32 #define CDSLIB_CONTAINER_DETAILS_SKIP_LIST_BASE_H
  33
  34 #include <cds/intrusive/details/skip_list_base.h>
  35 #include <cds/container/details/base.h>
  36
  37 namespace cds { namespace container {
  38
  39     /// SkipListSet related definitions
  40     /** @ingroup cds_nonintrusive_helper
  41     */
  42     namespace skip_list {
  43         /// Option specifying random level generator
  44         template <typename Type>
  45         using random_level_generator = cds::intrusive::skip_list::random_level_generator<Type>;
  46
  47         /// Xor-shift random level generator
  48         typedef cds::intrusive::skip_list::xorshift xorshift;
  49
  50         /// Turbo-pascal random level generator
  51         typedef cds::intrusive::skip_list::turbo_pascal turbo_pascal;
  52
  53         /// Skip list internal statistics
  54         template <typename EventCounter = cds::atomicity::event_counter>
  55         using stat = cds::intrusive::skip_list::stat < EventCounter >;
  56
  57         /// Skip list empty internal statistics
  58         typedef cds::intrusive::skip_list::empty_stat empty_stat;
  59
  60         /// SkipListSet traits
  61         struct traits
  62         {
  63             /// Key comparison functor
  64             /**
  65                 No default functor is provided. If the option is not specified, the \p less is used.
  66             */
  67             typedef opt::none                       compare;
  68
  69             /// specifies binary predicate used for key compare.
  70             /**
  71                 Default is \p std::less<T>.
  72             */
  73             typedef opt::none                       less;
  74
  75             /// Item counter
  76             /**
  77                 The type for item counting feature,
  78                  by defaulr disabled (\p atomicity::empty_item_counter)
  79             */
  80             typedef atomicity::empty_item_counter     item_counter;
  81
  82             /// C++ memory ordering model
  83             /**
  84                 List of available memory ordering see \p opt::memory_model
  85             */
  86             typedef opt::v::relaxed_ordering        memory_model;
  87
  88             /// Random level generator
  89             /**
  90                 The random level generator is an important part of skip-list algorithm.
  91                 The node height in the skip-list have a probabilistic distribution
  92                 where half of the nodes that have level \p i also have level <tt>i+1</tt>
  93                 (i = 0..30). The height of a node is in range [0..31].
  94
  95                 See \p skip_list::random_level_generator option setter.
  96             */
  97             typedef turbo_pascal                    random_level_generator;
  98
  99             /// Allocator for skip-list nodes, \p std::allocator interface
 100             typedef CDS_DEFAULT_ALLOCATOR           allocator;
 101
 102             /// back-off strategy, default is \p cds::backoff::Default
 103             typedef cds::backoff::Default           back_off;
 104
 105             /// Internal statistics, by default disabled. To enable, use \p split_list::stat
 106             typedef empty_stat                      stat;
 107
 108             /// RCU deadlock checking policy (for \ref cds_nonintrusive_SkipListSet_rcu "RCU-based SkipListSet")
 109             /**
 110                 List of available options see opt::rcu_check_deadlock
 111             */
 112             typedef opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 113
 114             //@cond
 115             // For internal use only
 116             typedef opt::none                       key_accessor;
 117             //@endcond
 118         };
 119
 120         /// Metafunction converting option list to SkipListSet traits
 121         /**
 122             \p Options are:
 123             - \p opt::compare - key comparison functor. No default functor is provided.
 124                 If the option is not specified, the \p opt::less is used.
 125             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 126             - \p opt::item_counter - the type of item counting feature. Default is \p atomicity::empty_item_counter that is no item counting.
 127             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 128                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 129             - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xorshift, \p skip_list::turbo_pascal or
 130                 user-provided one.
 131                 Default is \p %skip_list::turbo_pascal.
 132             - \p opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
 133             - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
 134             - \p opt::stat - internal statistics. Available types: \p skip_list::stat, \p skip_list::empty_stat (the default)
 135             - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based skip-list.
 136                 Default is \p opt::v::rcu_throw_deadlock
 137
 138         */
 139         template <typename... Options>
 140         struct make_traits {
 141 #   ifdef CDS_DOXYGEN_INVOKED
 142             typedef implementation_defined type ;   ///< Metafunction result
 143 #   else
 144             typedef typename cds::opt::make_options<
 145                 typename cds::opt::find_type_traits< traits, Options... >::type
 146                 ,Options...
 147             >::type   type;
 148 #   endif
 149         };
 150
 151         //@cond
 152         namespace details {
 153
 154             template <typename Node, typename Traits>
 155             class node_allocator
 156             {
 157             protected:
 158                 typedef Node node_type;
 159                 typedef Traits traits;
 160
 161                 typedef typename node_type::tower_item_type node_tower_item;
 162                 typedef typename traits::allocator::template rebind<unsigned char>::other  tower_allocator_type;
 163                 typedef typename traits::allocator::template rebind<node_type>::other      node_allocator_type;
 164
 165                 static size_t const c_nTowerItemSize = sizeof(node_tower_item);
 166                 static size_t const c_nNodePadding = sizeof(node_type) % c_nTowerItemSize;
 167                 static size_t const c_nNodeSize = sizeof(node_type) + (c_nNodePadding ? (c_nTowerItemSize - c_nNodePadding) : 0);
 168
 169                 static CDS_CONSTEXPR size_t node_size( unsigned int nHeight ) CDS_NOEXCEPT
 170                 {
 171                     return c_nNodeSize + (nHeight - 1) * c_nTowerItemSize;
 172                 }
 173
 174                 static unsigned char * alloc_space( unsigned int nHeight )
 175                 {
 176                     unsigned char * pMem;
 177                     size_t const sz = node_size( nHeight );
 178
 179                     if ( nHeight > 1 ) {
 180                         pMem = tower_allocator_type().allocate( sz );
 181
 182                         // check proper alignments
 183                         assert( (((uintptr_t) pMem) & (alignof(node_type) - 1)) == 0 );
 184                         assert( (((uintptr_t) (pMem + c_nNodeSize)) & (alignof(node_tower_item) - 1)) == 0 );
 185                         return pMem;
 186                     }
 187                     else
 188                         pMem = reinterpret_cast<unsigned char *>( node_allocator_type().allocate( 1 ) );
 189
 190                     return pMem;
 191                 }
 192
 193                 static void free_space( unsigned char * p, unsigned int nHeight )
 194                 {
 195                     assert( p != nullptr );
 196
 197                     if ( nHeight == 1 )
 198                         node_allocator_type().deallocate( reinterpret_cast<node_type *>(p), 1 );
 199                     else
 200                         tower_allocator_type().deallocate( p, node_size(nHeight));
 201                 }
 202
 203             public:
 204                 template <typename Q>
 205                 node_type * New( unsigned int nHeight, Q const& v )
 206                 {
 207                     unsigned char * pMem = alloc_space( nHeight );
 208                     node_type * p = new( pMem )
 209                         node_type( nHeight, nHeight > 1 ? reinterpret_cast<node_tower_item *>(pMem + c_nNodeSize) : nullptr, v );
 210                     return p;
 211                 }
 212
 213                 template <typename... Args>
 214                 node_type * New( unsigned int nHeight, Args&&... args )
 215                 {
 216                     unsigned char * pMem = alloc_space( nHeight );
 217                     node_type * p = new( pMem )
 218                         node_type( nHeight, nHeight > 1 ? reinterpret_cast<node_tower_item *>(pMem + c_nNodeSize) : nullptr,
 219                         std::forward<Args>(args)... );
 220                     return p;
 221                 }
 222
 223                 void Delete( node_type * p )
 224                 {
 225                     assert( p != nullptr );
 226
 227                     unsigned int nHeight = p->height();
 228                     node_allocator_type().destroy( p );
 229                     free_space( reinterpret_cast<unsigned char *>(p), nHeight );
 230                 }
 231             };
 232
 233             template <typename IntrusiveNode>
 234             struct dummy_node_builder {
 235                 typedef IntrusiveNode intrusive_node_type;
 236
 237                 template <typename RandomGen>
 238                 static intrusive_node_type * make_tower( intrusive_node_type * pNode, RandomGen& /*gen*/ ) { return pNode ; }
 239                 static intrusive_node_type * make_tower( intrusive_node_type * pNode, unsigned int /*nHeight*/ ) { return pNode ; }
 240                 static void dispose_tower( intrusive_node_type * pNode )
 241                 {
 242                     pNode->release_tower();
 243                 }
 244
 245                 struct node_disposer {
 246                     void operator()( intrusive_node_type * /*pNode*/ ) const {}
 247                 };
 248             };
 249
 250             template <typename ForwardIterator>
 251             class iterator
 252             {
 253                 typedef ForwardIterator intrusive_iterator;
 254                 typedef typename intrusive_iterator::value_type node_type;
 255                 typedef typename node_type::stored_value_type   value_type;
 256                 static bool const c_isConst = intrusive_iterator::c_isConst;
 257
 258                 typedef typename std::conditional< c_isConst, value_type const&, value_type&>::type   value_ref;
 259                 template <typename FwdIt> friend class iterator;
 260
 261                 intrusive_iterator      m_It;
 262
 263             public: // for internal use only!!!
 264                 iterator( intrusive_iterator const& it )
 265                     : m_It( it )
 266                 {}
 267
 268             public:
 269                 iterator()
 270                     : m_It()
 271                 {}
 272
 273                 iterator( iterator const& s)
 274                     : m_It( s.m_It )
 275                 {}
 276
 277                 value_type * operator ->() const
 278                 {
 279                     return &( m_It.operator->()->m_Value );
 280                 }
 281
 282                 value_ref operator *() const
 283                 {
 284                     return m_It.operator*().m_Value;
 285                 }
 286
 287                 /// Pre-increment
 288                 iterator& operator ++()
 289                 {
 290                     ++m_It;
 291                     return *this;
 292                 }
 293
 294                 iterator& operator = (iterator const& src)
 295                 {
 296                     m_It = src.m_It;
 297                     return *this;
 298                 }
 299
 300                 template <typename FwIt>
 301                 bool operator ==(iterator<FwIt> const& i ) const
 302                 {
 303                     return m_It == i.m_It;
 304                 }
 305                 template <typename FwIt>
 306                 bool operator !=(iterator<FwIt> const& i ) const
 307                 {
 308                     return !( *this == i );
 309                 }
 310             };
 311
 312         } // namespace details
 313         //@endcond
 314
 315     } // namespace skip_list
 316
 317     // Forward declaration
 318     template <class GC, typename T, typename Traits = skip_list::traits >
 319     class SkipListSet;
 320
 321     // Forward declaration
 322     template <class GC, typename K, typename T, typename Traits = skip_list::traits >
 323     class SkipListMap;
 324
 325 }} // namespace cds::container
 326
 327 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_SKIP_LIST_BASE_H