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-2016
   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                 static unsigned char * alloc_space( unsigned int nHeight )
 174                 {
 175                     if ( nHeight > 1 ) {
 176                         unsigned char * pMem = tower_allocator_type().allocate( node_size(nHeight) );
 177
 178                         // check proper alignments
 179                         assert( (((uintptr_t) pMem) & (alignof(node_type) - 1)) == 0 );
 180                         assert( (((uintptr_t) (pMem + c_nNodeSize)) & (alignof(node_tower_item) - 1)) == 0 );
 181                         return pMem;
 182                     }
 183
 184                     return reinterpret_cast<unsigned char *>( node_allocator_type().allocate(1));
 185                 }
 186
 187                 static void free_space( unsigned char * p, unsigned int nHeight )
 188                 {
 189                     assert( p != nullptr );
 190                     if ( nHeight == 1 )
 191                         node_allocator_type().deallocate( reinterpret_cast<node_type *>(p), 1 );
 192                     else
 193                         tower_allocator_type().deallocate( p, node_size(nHeight));
 194                 }
 195
 196             public:
 197                 template <typename Q>
 198                 node_type * New( unsigned int nHeight, Q const& v )
 199                 {
 200                     unsigned char * pMem = alloc_space( nHeight );
 201                     node_type * p = new( pMem )
 202                         node_type( nHeight, nHeight > 1 ? reinterpret_cast<node_tower_item *>(pMem + c_nNodeSize) : nullptr, v );
 203                     return p;
 204                 }
 205
 206                 template <typename... Args>
 207                 node_type * New( unsigned int nHeight, Args&&... args )
 208                 {
 209                     unsigned char * pMem = alloc_space( nHeight );
 210                     node_type * p = new( pMem )
 211                         node_type( nHeight, nHeight > 1 ? reinterpret_cast<node_tower_item *>(pMem + c_nNodeSize) : nullptr,
 212                         std::forward<Args>(args)... );
 213                     return p;
 214                 }
 215
 216                 void Delete( node_type * p )
 217                 {
 218                     assert( p != nullptr );
 219
 220                     unsigned int nHeight = p->height();
 221                     node_allocator_type().destroy( p );
 222                     free_space( reinterpret_cast<unsigned char *>(p), nHeight );
 223                 }
 224             };
 225
 226             template <typename IntrusiveNode>
 227             struct dummy_node_builder {
 228                 typedef IntrusiveNode intrusive_node_type;
 229
 230                 template <typename RandomGen>
 231                 static intrusive_node_type * make_tower( intrusive_node_type * pNode, RandomGen& /*gen*/ ) { return pNode ; }
 232                 static intrusive_node_type * make_tower( intrusive_node_type * pNode, unsigned int /*nHeight*/ ) { return pNode ; }
 233                 static void dispose_tower( intrusive_node_type * pNode )
 234                 {
 235                     pNode->release_tower();
 236                 }
 237
 238                 struct node_disposer {
 239                     void operator()( intrusive_node_type * /*pNode*/ ) const {}
 240                 };
 241             };
 242
 243             template <typename ForwardIterator>
 244             class iterator
 245             {
 246                 typedef ForwardIterator intrusive_iterator;
 247                 typedef typename intrusive_iterator::value_type node_type;
 248                 typedef typename node_type::stored_value_type   value_type;
 249                 static bool const c_isConst = intrusive_iterator::c_isConst;
 250
 251                 typedef typename std::conditional< c_isConst, value_type const&, value_type&>::type   value_ref;
 252                 template <typename FwdIt> friend class iterator;
 253
 254                 intrusive_iterator      m_It;
 255
 256             public: // for internal use only!!!
 257                 iterator( intrusive_iterator const& it )
 258                     : m_It( it )
 259                 {}
 260
 261             public:
 262                 iterator()
 263                     : m_It()
 264                 {}
 265
 266                 iterator( iterator const& s)
 267                     : m_It( s.m_It )
 268                 {}
 269
 270                 value_type * operator ->() const
 271                 {
 272                     return &( m_It.operator->()->m_Value );
 273                 }
 274
 275                 value_ref operator *() const
 276                 {
 277                     return m_It.operator*().m_Value;
 278                 }
 279
 280                 /// Pre-increment
 281                 iterator& operator ++()
 282                 {
 283                     ++m_It;
 284                     return *this;
 285                 }
 286
 287                 iterator& operator = (iterator const& src)
 288                 {
 289                     m_It = src.m_It;
 290                     return *this;
 291                 }
 292
 293                 template <typename FwIt>
 294                 bool operator ==(iterator<FwIt> const& i ) const
 295                 {
 296                     return m_It == i.m_It;
 297                 }
 298                 template <typename FwIt>
 299                 bool operator !=(iterator<FwIt> const& i ) const
 300                 {
 301                     return !( *this == i );
 302                 }
 303             };
 304
 305         } // namespace details
 306         //@endcond
 307
 308     } // namespace skip_list
 309
 310     // Forward declaration
 311     template <class GC, typename T, typename Traits = skip_list::traits >
 312     class SkipListSet;
 313
 314     // Forward declaration
 315     template <class GC, typename K, typename T, typename Traits = skip_list::traits >
 316     class SkipListMap;
 317
 318 }} // namespace cds::container
 319
 320 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_SKIP_LIST_BASE_H