cds/container/skip_list_set_nogc.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_SKIP_LIST_SET_NOGC_H
   4 #define __CDS_CONTAINER_SKIP_LIST_SET_NOGC_H
   5
   6 #include <cds/intrusive/skip_list_nogc.h>
   7 #include <cds/container/skip_list_base.h>
   8 #include <cds/details/binary_functor_wrapper.h>
   9 #include <cds/gc/nogc.h>
  10 #include <cds/details/allocator.h>
  11
  12 namespace cds { namespace container {
  13     //@cond
  14     namespace skip_list { namespace details {
  15         struct set_key_accessor
  16         {
  17             template <typename NodeType>
  18             typename NodeType::stored_value_type const& operator()( NodeType const& node ) const
  19             {
  20                 return node.m_Value;
  21             }
  22         };
  23     }} // namespace skip_list::details
  24
  25     namespace details {
  26         template <typename T, typename Traits >
  27         struct make_skip_list_set_nogc
  28         {
  29             typedef cds::gc::nogc   gc;
  30             typedef T               value_type;
  31             typedef Traits          type_traits;
  32
  33             typedef cds::intrusive::skip_list::node< gc >   intrusive_node_type;
  34             struct node_type: public intrusive_node_type
  35             {
  36                 typedef intrusive_node_type             base_class;
  37                 typedef typename base_class::atomic_ptr atomic_ptr;
  38                 typedef atomic_ptr                      tower_item_type;
  39                 typedef value_type                      stored_value_type;
  40
  41                 value_type m_Value;
  42                 //atomic_ptr m_arrTower[] ;  // allocated together with node_type in single memory block
  43
  44                 template <typename Q>
  45                 node_type( unsigned int nHeight, atomic_ptr * pTower, Q const& v )
  46                     : m_Value(v)
  47                 {
  48                     if ( nHeight > 1 ) {
  49                         new (pTower) atomic_ptr[ nHeight - 1 ];
  50                         base_class::make_tower( nHeight, pTower );
  51                     }
  52                 }
  53
  54                 template <typename Q, typename... Args>
  55                 node_type( unsigned int nHeight, atomic_ptr * pTower, Q&& q, Args&&... args )
  56                     : m_Value( std::forward<Q>(q), std::forward<Args>(args)... )
  57                 {
  58                     if ( nHeight > 1 ) {
  59                         new (pTower) atomic_ptr[ nHeight - 1 ];
  60                         base_class::make_tower( nHeight, pTower );
  61                     }
  62                 }
  63
  64                 node_type() = delete;   // no default ctor
  65             };
  66
  67             typedef skip_list::details::node_allocator< node_type, type_traits> node_allocator;
  68
  69             struct node_deallocator {
  70                 void operator ()( node_type * pNode )
  71                 {
  72                     node_allocator().Delete( pNode );
  73                 }
  74             };
  75
  76             typedef skip_list::details::dummy_node_builder<intrusive_node_type> dummy_node_builder;
  77
  78             typedef typename type_traits::key_accessor key_accessor;
  79             typedef typename opt::details::make_comparator< value_type, type_traits >::type key_comparator;
  80
  81             /*
  82             template <typename Less>
  83             struct less_wrapper {
  84                 typedef compare_wrapper< node_type, cds::opt::details::make_comparator_from_less<Less>, key_accessor >    type;
  85             };
  86             */
  87
  88             typedef typename cds::intrusive::skip_list::make_traits<
  89                 cds::opt::type_traits< type_traits >
  90                 ,cds::intrusive::opt::hook< intrusive::skip_list::base_hook< cds::opt::gc< gc > > >
  91                 ,cds::intrusive::opt::disposer< node_deallocator >
  92                 ,cds::intrusive::skip_list::internal_node_builder< dummy_node_builder >
  93                 ,cds::opt::compare< cds::details::compare_wrapper< node_type, key_comparator, key_accessor > >
  94             >::type intrusive_type_traits;
  95
  96             typedef cds::intrusive::SkipListSet< gc, node_type, intrusive_type_traits>   type;
  97         };
  98     } // namespace details
  99     //@endcond
 100
 101     /// Lock-free skip-list set (template specialization for gc::nogc)
 102     /** @ingroup cds_nonintrusive_set
 103         \anchor cds_nonintrusive_SkipListSet_nogc
 104
 105         This specialization is intended for so-called persistent usage when no item
 106         reclamation may be performed. The class does not support deleting of list item.
 107         See \ref cds_nonintrusive_SkipListSet_hp "SkipListSet" for detailed description.
 108
 109         Template arguments:
 110         - \p T - type to be stored in the list.
 111         - \p Traits - type traits. See skip_list::type_traits for explanation.
 112
 113         It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of \p Traits template
 114         argument. \p Options template arguments of cds::container::skip_list::make_traits metafunction are:
 115         - opt::compare - key comparison functor. No default functor is provided.
 116             If the option is not specified, the opt::less is used.
 117         - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 118         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
 119         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
 120             or opt::v::sequential_consistent (sequentially consisnent memory model).
 121         - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
 122             user-provided one. See skip_list::random_level_generator option description for explanation.
 123             Default is \p %skip_list::turbo_pascal.
 124         - opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
 125         - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
 126         - opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
 127     */
 128     template <
 129         typename T,
 130 #ifdef CDS_DOXYGEN_INVOKED
 131         class Traits = skip_list::type_traits
 132 #else
 133         class Traits
 134 #endif
 135     >
 136     class SkipListSet< gc::nogc, T, Traits >:
 137 #ifdef CDS_DOXYGEN_INVOKED
 138         protected intrusive::SkipListSet< cds::gc::nogc, T, Traits >
 139 #else
 140         protected details::make_skip_list_set_nogc< T, typename cds::opt::replace_key_accessor< Traits, skip_list::details::set_key_accessor >::type >::type
 141 #endif
 142     {
 143         //@cond
 144         typedef details::make_skip_list_set_nogc< T, typename cds::opt::replace_key_accessor< Traits, skip_list::details::set_key_accessor >::type >    maker;
 145         typedef typename maker::type base_class;
 146         //@endcond
 147     public:
 148         typedef typename base_class::gc gc  ; ///< Garbage collector used
 149         typedef T       value_type  ;   ///< Value type stored in the set
 150         typedef Traits  options     ;   ///< Options specified
 151
 152         typedef typename base_class::back_off       back_off        ;   ///< Back-off strategy used
 153         typedef typename options::allocator         allocator_type  ;   ///< Allocator type used for allocate/deallocate the skip-list nodes
 154         typedef typename base_class::item_counter   item_counter    ;   ///< Item counting policy used
 155         typedef typename maker::key_comparator      key_comparator  ;   ///< key compare functor
 156         typedef typename base_class::memory_model   memory_model    ;   ///< Memory ordering. See cds::opt::memory_model option
 157         typedef typename options::stat              stat            ;   ///< internal statistics type
 158         typedef typename base_class::random_level_generator random_level_generator  ;   ///< random level generator
 159
 160     protected:
 161         //@cond
 162         typedef typename maker::node_type           node_type;
 163         typedef typename maker::node_allocator      node_allocator;
 164         typedef typename std::conditional<
 165             std::is_same< typename options::key_accessor, opt::none >::value,
 166             skip_list::details::set_key_accessor,
 167             typename options::key_accessor
 168         >::type     key_accessor;
 169
 170         typedef std::unique_ptr< node_type, typename maker::node_deallocator >    scoped_node_ptr;
 171
 172 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 173         struct ensure_functor
 174         {
 175             node_type * pNode;
 176             void operator ()( bool bNew, node_type& node, node_type& )
 177             {
 178                 pNode = &node;
 179             }
 180         };
 181
 182         struct find_functor
 183         {
 184             node_type * pNode;
 185
 186             template <typename Q>
 187             void operator ()( node_type& node, Q& )
 188             {
 189                 pNode = &node;
 190             }
 191         };
 192 #   endif
 193         //@endcond
 194
 195     public:
 196         /// Iterator type
 197         typedef skip_list::details::iterator< typename base_class::iterator >  iterator;
 198
 199         /// Const iterator type
 200         typedef skip_list::details::iterator< typename base_class::const_iterator >   const_iterator;
 201
 202         /// Returns a forward iterator addressing the first element in a set
 203         iterator begin()
 204         {
 205             return iterator( base_class::begin() );
 206         }
 207
 208         /// Returns a forward const iterator addressing the first element in a set
 209         //@{
 210         const_iterator begin() const
 211         {
 212             return const_iterator( base_class::begin() );
 213         }
 214         const_iterator cbegin()
 215         {
 216             return const_iterator( base_class::cbegin() );
 217         }
 218         //@}
 219
 220         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
 221         iterator end()
 222         {
 223             return iterator( base_class::end() );
 224         }
 225
 226         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 227         //@{
 228         const_iterator end() const
 229         {
 230             return const_iterator( base_class::end() );
 231         }
 232         const_iterator cend()
 233         {
 234             return const_iterator( base_class::cend() );
 235         }
 236         //@}
 237
 238     protected:
 239         //@cond
 240         static iterator node_to_iterator( node_type * pNode )
 241         {
 242             assert( pNode );
 243             return iterator( base_class::iterator::from_node( pNode ));
 244         }
 245         //@endcond
 246
 247     public:
 248         /// Default ctor
 249         SkipListSet()
 250             : base_class()
 251         {}
 252
 253         /// Destructor destroys the set object
 254         ~SkipListSet()
 255         {}
 256
 257         /// Inserts new node
 258         /**
 259             The function inserts \p val in the set if it does not contain
 260             an item with key equal to \p val.
 261
 262             Return an iterator pointing to inserted item if success, otherwise \ref end()
 263         */
 264         template <typename Q>
 265         iterator insert( const Q& val )
 266         {
 267             scoped_node_ptr sp( node_allocator().New( base_class::random_level(), val ));
 268             if ( base_class::insert( *sp.get() )) {
 269                 return node_to_iterator( sp.release() );
 270             }
 271             return end();
 272         }
 273
 274         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 275         /**
 276             Return an iterator pointing to inserted item if success \ref end() otherwise
 277         */
 278         template <typename... Args>
 279         iterator emplace( Args&&... args )
 280         {
 281             scoped_node_ptr sp( node_allocator().New( base_class::random_level(), std::forward<Args>(args)... ));
 282             if ( base_class::insert( *sp.get() )) {
 283                 return node_to_iterator( sp.release() );
 284             }
 285             return end();
 286         }
 287
 288         /// Ensures that the item \p val exists in the set
 289         /**
 290             The operation inserts new item if the key \p val is not found in the set.
 291             Otherwise, the function returns an iterator that points to item found.
 292
 293             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 294             item found or inserted, \p second is true if new item has been added or \p false if the item
 295             already is in the set.
 296         */
 297         template <typename Q>
 298         std::pair<iterator, bool> ensure( const Q& val )
 299         {
 300             scoped_node_ptr sp( node_allocator().New( base_class::random_level(), val ));
 301 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 302             node_type * pNode;
 303             std::pair<bool, bool> bRes = base_class::ensure( *sp, [&pNode](bool, node_type& item, node_type&) { pNode = &item; } );
 304             if ( bRes.first && bRes.second )
 305                 sp.release();
 306             assert( pNode );
 307             return std::make_pair( node_to_iterator( pNode ), bRes.second );
 308 #       else
 309             ensure_functor f;
 310             std::pair<bool, bool> bRes = base_class::ensure( *sp, cds::ref(f) );
 311             if ( bRes.first && bRes.second )
 312                 sp.release();
 313             assert( f.pNode );
 314             return std::make_pair( node_to_iterator( f.pNode ), bRes.second );
 315 #       endif
 316         }
 317
 318         /// Searches \p key
 319         /** \anchor cds_nonintrusive_SkipListSet_nogc_find_val
 320
 321             The function searches the item with key equal to \p key
 322             and returns an iterator pointed to item found if the key is found,
 323             and \ref end() otherwise
 324         */
 325         template <typename Q>
 326         iterator find( Q const& key ) const
 327         {
 328             node_type * pNode = base_class::find( key );
 329             if ( pNode )
 330                 return node_to_iterator( pNode );
 331             return base_class::nonconst_end();
 332         }
 333
 334         /// Finds the key \p val using \p pred predicate for searching
 335         /**
 336             The function is an analog of \ref cds_nonintrusive_SkipListSet_nogc_find_val "find(Q const&)"
 337             but \p pred is used for key comparing.
 338             \p Less functor has the interface like \p std::less.
 339             \p Less must imply the same element order as the comparator used for building the set.
 340         */
 341         template <typename Q, typename Less>
 342         iterator find_with( Q const& key, Less pred ) const
 343         {
 344             node_type * pNode = base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, key_accessor>() );
 345             if ( pNode )
 346                 return node_to_iterator( pNode );
 347             return base_class::nonconst_end();
 348         }
 349
 350         /// Gets minimum key from the set
 351         /**
 352             If the set is empty the function returns \p nullptr
 353         */
 354         value_type * get_min() const
 355         {
 356             node_type * pNode = base_class::get_min();
 357             return pNode ? &pNode->m_Value : nullptr;
 358         }
 359
 360         /// Gets maximum key from the set
 361         /**
 362             The function returns \p nullptr if the set is empty
 363         */
 364         value_type * get_max() const
 365         {
 366             node_type * pNode = base_class::get_max();
 367             return pNode ? &pNode->m_Value : nullptr;
 368         }
 369
 370         /// Clears the set (non-atomic)
 371         /**
 372             The function is not atomic.
 373             Finding and/or inserting is prohibited while clearing.
 374             Otherwise an unpredictable result may be encountered.
 375             Thus, \p clear() may be used only for debugging purposes.
 376         */
 377         void clear()
 378         {
 379             base_class::clear();
 380         }
 381
 382         /// Checks if the set is empty
 383         bool empty() const
 384         {
 385             return base_class::empty();
 386         }
 387
 388         /// Returns item count in the set
 389         /**
 390             The value returned depends on item counter type provided by \p Traits template parameter.
 391             If it is atomicity::empty_item_counter this function always returns 0.
 392             The function is not suitable for checking the set emptiness, use \ref empty
 393             member function for this purpose.
 394         */
 395         size_t size() const
 396         {
 397             return base_class::size();
 398         }
 399
 400         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
 401         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
 402         {
 403             return base_class::max_height();
 404         }
 405
 406         /// Returns const reference to internal statistics
 407         stat const& statistics() const
 408         {
 409             return base_class::statistics();
 410         }
 411     };
 412
 413 }} // cds::container
 414
 415 #endif // ifndef __CDS_CONTAINER_SKIP_LIST_SET_NOGC_H