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