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