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