cds/container/skip_list_set_nogc.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_SKIP_LIST_SET_NOGC_H
   4 #define CDSLIB_CONTAINER_SKIP_LIST_SET_NOGC_H
   5
   6 #include <cds/intrusive/skip_list_nogc.h>
   7 #include <cds/container/details/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          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, 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 traits::key_accessor key_accessor;
  79             typedef typename opt::details::make_comparator< value_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< 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::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::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         //@cond
 161         typedef cds::container::skip_list::implementation_tag implementation_tag;
 162         //@endcond
 163
 164     protected:
 165         //@cond
 166         typedef typename maker::node_type           node_type;
 167         typedef typename maker::node_allocator      node_allocator;
 168         typedef typename std::conditional<
 169             std::is_same< typename options::key_accessor, opt::none >::value,
 170             skip_list::details::set_key_accessor,
 171             typename options::key_accessor
 172         >::type     key_accessor;
 173
 174         typedef std::unique_ptr< node_type, typename maker::node_deallocator >    scoped_node_ptr;
 175         //@endcond
 176
 177     public:
 178         /// Iterator type
 179         typedef skip_list::details::iterator< typename base_class::iterator >  iterator;
 180
 181         /// Const iterator type
 182         typedef skip_list::details::iterator< typename base_class::const_iterator >   const_iterator;
 183
 184         /// Returns a forward iterator addressing the first element in a set
 185         iterator begin()
 186         {
 187             return iterator( base_class::begin() );
 188         }
 189
 190         /// Returns a forward const iterator addressing the first element in a set
 191         //@{
 192         const_iterator begin() const
 193         {
 194             return const_iterator( base_class::begin() );
 195         }
 196         const_iterator cbegin() const
 197         {
 198             return const_iterator( base_class::cbegin() );
 199         }
 200         //@}
 201
 202         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
 203         iterator end()
 204         {
 205             return iterator( base_class::end() );
 206         }
 207
 208         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 209         //@{
 210         const_iterator end() const
 211         {
 212             return const_iterator( base_class::end() );
 213         }
 214         const_iterator cend() const
 215         {
 216             return const_iterator( base_class::cend() );
 217         }
 218         //@}
 219
 220     protected:
 221         //@cond
 222         static iterator node_to_iterator( node_type * pNode )
 223         {
 224             assert( pNode );
 225             return iterator( base_class::iterator::from_node( pNode ));
 226         }
 227         //@endcond
 228
 229     public:
 230         /// Default ctor
 231         SkipListSet()
 232             : base_class()
 233         {}
 234
 235         /// Destructor destroys the set object
 236         ~SkipListSet()
 237         {}
 238
 239         /// Inserts new node
 240         /**
 241             The function inserts \p val in the set if it does not contain
 242             an item with key equal to \p val.
 243
 244             Return an iterator pointing to inserted item if success, otherwise \ref end()
 245         */
 246         template <typename Q>
 247         iterator insert( const Q& val )
 248         {
 249             scoped_node_ptr sp( node_allocator().New( base_class::random_level(), val ));
 250             if ( base_class::insert( *sp.get() )) {
 251                 return node_to_iterator( sp.release() );
 252             }
 253             return end();
 254         }
 255
 256         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 257         /**
 258             Return an iterator pointing to inserted item if success \ref end() otherwise
 259         */
 260         template <typename... Args>
 261         iterator emplace( Args&&... args )
 262         {
 263             scoped_node_ptr sp( node_allocator().New( base_class::random_level(), std::forward<Args>(args)... ));
 264             if ( base_class::insert( *sp.get() )) {
 265                 return node_to_iterator( sp.release() );
 266             }
 267             return end();
 268         }
 269
 270         /// Updates the item
 271         /**
 272             The operation inserts new item if \p val is not found in the set and \p bInsert is \p true.
 273             Otherwise, if that key exists, the function returns an iterator that points to item found.
 274
 275             Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
 276             item found or inserted or \p end() if \p val is not found and \p bInsert is \p false,
 277             \p second is \p true if new item has been added or \p false if the item
 278             already is in the set.
 279         */
 280         template <typename Q>
 281         std::pair<iterator, bool> update( const Q& val, bool bInsert = true )
 282         {
 283             scoped_node_ptr sp( node_allocator().New( base_class::random_level(), val ));
 284             node_type * pNode;
 285             std::pair<bool, bool> bRes = base_class::update( *sp, [&pNode](bool, node_type& item, node_type&) { pNode = &item; }, bInsert );
 286             if ( bRes.first && bRes.second )
 287                 sp.release();
 288             else if ( !bRes.first )
 289                 return std::make_pair( end(), false );
 290             assert( pNode );
 291             return std::make_pair( node_to_iterator( pNode ), bRes.second );
 292         }
 293         //@cond
 294         // Deprecated, use update()
 295         template <typename Q>
 296         std::pair<iterator, bool> ensure( const Q& val )
 297         {
 298             return update( val, true );
 299         }
 300         //@endcond
 301
 302         /// Checks whether the set contains \p key
 303         /**
 304             The function searches the item with key equal to \p key
 305             and returns an iterator to item found or \p end() if the key is not fund
 306         */
 307         template <typename Q>
 308         iterator contains( Q const& key ) const
 309         {
 310             node_type * pNode = base_class::contains( key );
 311             if ( pNode )
 312                 return node_to_iterator( pNode );
 313             return base_class::nonconst_end();
 314         }
 315         //@cond
 316         // Deprecated, use contains()
 317         template <typename Q>
 318         iterator find( Q const& key ) const
 319         {
 320             return contains( key );
 321         }
 322         //@edncond
 323
 324         /// Checks whether the set contains \p key using \p pred predicate for searching
 325         /**
 326             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 327             \p Less functor has the interface like \p std::less.
 328             \p Less must imply the same element order as the comparator used for building the set.
 329         */
 330         template <typename Q, typename Less>
 331         iterator contains( Q const& key, Less pred ) const
 332         {
 333             CDS_UNUSED( pred );
 334             node_type * pNode = base_class::contains( key, cds::details::predicate_wrapper< node_type, Less, key_accessor>() );
 335             if ( pNode )
 336                 return node_to_iterator( pNode );
 337             return base_class::nonconst_end();
 338         }
 339         //@cond
 340         // Deprecated, use contains()
 341         template <typename Q, typename Less>
 342         iterator find_with( Q const& key, Less pred ) const
 343         {
 344             return contains( key, pred );
 345         }
 346         //@endcond
 347
 348         /// Gets minimum key from the set
 349         /**
 350             If the set is empty the function returns \p nullptr
 351         */
 352         value_type * get_min() const
 353         {
 354             node_type * pNode = base_class::get_min();
 355             return pNode ? &pNode->m_Value : nullptr;
 356         }
 357
 358         /// Gets maximum key from the set
 359         /**
 360             The function returns \p nullptr if the set is empty
 361         */
 362         value_type * get_max() const
 363         {
 364             node_type * pNode = base_class::get_max();
 365             return pNode ? &pNode->m_Value : nullptr;
 366         }
 367
 368         /// Clears the set (non-atomic)
 369         /**
 370             The function is not atomic.
 371             Finding and/or inserting is prohibited while clearing.
 372             Otherwise an unpredictable result may be encountered.
 373             Thus, \p clear() may be used only for debugging purposes.
 374         */
 375         void clear()
 376         {
 377             base_class::clear();
 378         }
 379
 380         /// Checks if the set is empty
 381         bool empty() const
 382         {
 383             return base_class::empty();
 384         }
 385
 386         /// Returns item count in the set
 387         /**
 388             The value returned depends on item counter type provided by \p Traits template parameter.
 389             If it is atomicity::empty_item_counter this function always returns 0.
 390             The function is not suitable for checking the set emptiness, use \ref empty
 391             member function for this purpose.
 392         */
 393         size_t size() const
 394         {
 395             return base_class::size();
 396         }
 397
 398         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
 399         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
 400         {
 401             return base_class::max_height();
 402         }
 403
 404         /// Returns const reference to internal statistics
 405         stat const& statistics() const
 406         {
 407             return base_class::statistics();
 408         }
 409     };
 410
 411 }} // cds::container
 412
 413 #endif // ifndef CDSLIB_CONTAINER_SKIP_LIST_SET_NOGC_H