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-2017
   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     ///@name Forward iterators
 203     //@{
 204         /// Forward ordered iterator
 205         /**
 206             The forward iterator for a split-list has some features:
 207             - it has no post-increment operator
 208             - it depends on iterator of underlying \p OrderedList
 209         */
 210         typedef skip_list::details::iterator< typename base_class::iterator >  iterator;
 211
 212         /// Const iterator type
 213         typedef skip_list::details::iterator< typename base_class::const_iterator >   const_iterator;
 214
 215         /// Returns a forward iterator addressing the first element in a set
 216         iterator begin()
 217         {
 218             return iterator( base_class::begin());
 219         }
 220
 221         /// Returns a forward const iterator addressing the first element in a set
 222         const_iterator begin() const
 223         {
 224             return const_iterator( base_class::begin());
 225         }
 226
 227         /// Returns a forward const iterator addressing the first element in a set
 228         const_iterator cbegin() const
 229         {
 230             return const_iterator( base_class::cbegin());
 231         }
 232
 233         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
 234         iterator end()
 235         {
 236             return iterator( base_class::end());
 237         }
 238
 239         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 240         const_iterator end() const
 241         {
 242             return const_iterator( base_class::end());
 243         }
 244         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 245         const_iterator cend() const
 246         {
 247             return const_iterator( base_class::cend());
 248         }
 249     //@}
 250
 251     protected:
 252         //@cond
 253         static iterator node_to_iterator( node_type * pNode )
 254         {
 255             assert( pNode );
 256             return iterator( base_class::iterator::from_node( pNode ));
 257         }
 258         //@endcond
 259
 260     public:
 261         /// Default ctor
 262         SkipListSet()
 263             : base_class()
 264         {}
 265
 266         /// Destructor destroys the set object
 267         ~SkipListSet()
 268         {}
 269
 270         /// Inserts new node
 271         /**
 272             The function inserts \p val in the set if it does not contain
 273             an item with key equal to \p val.
 274
 275             Return an iterator pointing to inserted item if success, otherwise \ref end()
 276         */
 277         template <typename Q>
 278         iterator insert( const Q& val )
 279         {
 280             scoped_node_ptr sp( node_allocator().New( base_class::random_level(), val ));
 281             if ( base_class::insert( *sp.get())) {
 282                 return node_to_iterator( sp.release());
 283             }
 284             return end();
 285         }
 286
 287         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 288         /**
 289             Return an iterator pointing to inserted item if success \ref end() otherwise
 290         */
 291         template <typename... Args>
 292         iterator emplace( Args&&... args )
 293         {
 294             scoped_node_ptr sp( node_allocator().New( base_class::random_level(), std::forward<Args>(args)... ));
 295             if ( base_class::insert( *sp.get())) {
 296                 return node_to_iterator( sp.release());
 297             }
 298             return end();
 299         }
 300
 301         /// Updates the item
 302         /**
 303             The operation inserts new item if \p val is not found in the set and \p bInsert is \p true.
 304             Otherwise, if that key exists, the function returns an iterator that points to item found.
 305
 306             Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
 307             item found or inserted or \p end() if \p val is not found and \p bInsert is \p false,
 308             \p second is \p true if new item has been added or \p false if the item
 309             already is in the set.
 310         */
 311         template <typename Q>
 312         std::pair<iterator, bool> update( const Q& val, bool bInsert = true )
 313         {
 314             scoped_node_ptr sp( node_allocator().New( base_class::random_level(), val ));
 315             node_type * pNode;
 316             std::pair<bool, bool> bRes = base_class::update( *sp, [&pNode](bool, node_type& item, node_type&) { pNode = &item; }, bInsert );
 317             if ( bRes.first && bRes.second )
 318                 sp.release();
 319             else if ( !bRes.first )
 320                 return std::make_pair( end(), false );
 321             assert( pNode );
 322             return std::make_pair( node_to_iterator( pNode ), bRes.second );
 323         }
 324         //@cond
 325         template <typename Q>
 326         CDS_DEPRECATED("ensure() is deprecated, use update()")
 327         std::pair<iterator, bool> ensure( const Q& val )
 328         {
 329             return update( val, true );
 330         }
 331         //@endcond
 332
 333         /// Checks whether the set contains \p key
 334         /**
 335             The function searches the item with key equal to \p key
 336             and returns an iterator to item found or \p end() if the key is not fund
 337         */
 338         template <typename Q>
 339         iterator contains( Q const& key ) const
 340         {
 341             node_type * pNode = base_class::contains( key );
 342             if ( pNode )
 343                 return node_to_iterator( pNode );
 344             return base_class::nonconst_end();
 345         }
 346         //@cond
 347         template <typename Q>
 348         CDS_DEPRECATED("deprecated, use contains()")
 349         iterator find( Q const& key ) const
 350         {
 351             return contains( key );
 352         }
 353         //@edncond
 354
 355         /// Checks whether the set contains \p key using \p pred predicate for searching
 356         /**
 357             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 358             \p Less functor has the interface like \p std::less.
 359             \p Less must imply the same element order as the comparator used for building the set.
 360         */
 361         template <typename Q, typename Less>
 362         iterator contains( Q const& key, Less pred ) const
 363         {
 364             CDS_UNUSED( pred );
 365             node_type * pNode = base_class::contains( key, cds::details::predicate_wrapper< node_type, Less, key_accessor>());
 366             if ( pNode )
 367                 return node_to_iterator( pNode );
 368             return base_class::nonconst_end();
 369         }
 370         //@cond
 371         template <typename Q, typename Less>
 372         CDS_DEPRECATED("deprecated, use contains()")
 373         iterator find_with( Q const& key, Less pred ) const
 374         {
 375             return contains( key, pred );
 376         }
 377         //@endcond
 378
 379         /// Gets minimum key from the set
 380         /**
 381             If the set is empty the function returns \p nullptr
 382         */
 383         value_type * get_min() const
 384         {
 385             node_type * pNode = base_class::get_min();
 386             return pNode ? &pNode->m_Value : nullptr;
 387         }
 388
 389         /// Gets maximum key from the set
 390         /**
 391             The function returns \p nullptr if the set is empty
 392         */
 393         value_type * get_max() const
 394         {
 395             node_type * pNode = base_class::get_max();
 396             return pNode ? &pNode->m_Value : nullptr;
 397         }
 398
 399         /// Clears the set (non-atomic)
 400         /**
 401             The function is not atomic.
 402             Finding and/or inserting is prohibited while clearing.
 403             Otherwise an unpredictable result may be encountered.
 404             Thus, \p clear() may be used only for debugging purposes.
 405         */
 406         void clear()
 407         {
 408             base_class::clear();
 409         }
 410
 411         /// Checks if the set is empty
 412         bool empty() const
 413         {
 414             return base_class::empty();
 415         }
 416
 417         /// Returns item count in the set
 418         /**
 419             The value returned depends on item counter type provided by \p Traits template parameter.
 420             If it is atomicity::empty_item_counter this function always returns 0.
 421             The function is not suitable for checking the set emptiness, use \ref empty
 422             member function for this purpose.
 423         */
 424         size_t size() const
 425         {
 426             return base_class::size();
 427         }
 428
 429         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
 430         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
 431         {
 432             return base_class::max_height();
 433         }
 434
 435         /// Returns const reference to internal statistics
 436         stat const& statistics() const
 437         {
 438             return base_class::statistics();
 439         }
 440     };
 441
 442 }} // cds::container
 443
 444 #endif // ifndef CDSLIB_CONTAINER_SKIP_LIST_SET_NOGC_H