cds/container/split_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_SPLIT_LIST_SET_NOGC_H
  32 #define CDSLIB_CONTAINER_SPLIT_LIST_SET_NOGC_H
  33
  34 #include <cds/intrusive/split_list_nogc.h>
  35 #include <cds/container/details/split_list_base.h>
  36 #include <cds/gc/nogc.h>
  37 #include <cds/container/details/make_split_list_set.h>
  38
  39 namespace cds { namespace container {
  40
  41     /// Split-ordered list set (template specialization for \p gc::nogc)
  42     /** @ingroup cds_nonintrusive_set
  43         \anchor cds_nonintrusive_SplitListSet_nogc
  44
  45         This specialization is so-called append-only container when no item
  46         reclamation may be performed. The class does not support deleting of list item.
  47
  48         See \ref cds_nonintrusive_SplitListSet_hp "SplitListSet" for description of template parameters.
  49
  50         @warning Many member functions return an iterator pointing to an item.
  51         The iterator can be used to set up field of the item,
  52         but you should provide an exclusive access to it,
  53         see \ref cds_intrusive_item_creating "insert item troubleshooting".
  54     */
  55     template <
  56         class T,
  57 #ifdef CDS_DOXYGEN_INVOKED
  58         class Traits = split_list::traits
  59 #else
  60         class Traits
  61 #endif
  62     >
  63     class SplitListSet< cds::gc::nogc, T, Traits>
  64 #ifdef CDS_DOXYGEN_INVOKED
  65         :protected intrusive::SplitListSet<cds::gc::nogc, typename Traits::ordered_list, Traits>
  66 #else
  67         :protected details::make_split_list_set< cds::gc::nogc, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> >::type
  68 #endif
  69     {
  70     protected:
  71         //@cond
  72         typedef details::make_split_list_set< cds::gc::nogc, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> > maker;
  73         typedef typename maker::type  base_class;
  74         //@endcond
  75
  76     public:
  77         typedef cds::gc::nogc  gc;         ///< Garbage collector
  78         typedef T              value_type; ///< type of value to be stored in the list
  79         typedef Traits         traits;     ///< List traits
  80
  81         typedef typename maker::ordered_list      ordered_list;     ///< Underlying ordered list class
  82         typedef typename base_class::key_comparator key_comparator; ///< key comparison functor
  83
  84         /// Hash functor for \ref value_type and all its derivatives that you use
  85         typedef typename base_class::hash           hash;
  86         typedef typename base_class::item_counter   item_counter; ///< Item counter type
  87         typedef typename base_class::stat           stat; ///< Internal statistics
  88
  89     protected:
  90         //@cond
  91         typedef typename maker::cxx_node_allocator    cxx_node_allocator;
  92         typedef typename maker::node_type             node_type;
  93
  94         template <typename Q>
  95         static node_type * alloc_node(Q const& v )
  96         {
  97             return cxx_node_allocator().New( v );
  98         }
  99
 100         template <typename... Args>
 101         static node_type * alloc_node( Args&&... args )
 102         {
 103             return cxx_node_allocator().MoveNew( std::forward<Args>(args)...);
 104         }
 105
 106         static void free_node( node_type * pNode )
 107         {
 108             cxx_node_allocator().Delete( pNode );
 109         }
 110
 111         struct node_disposer {
 112             void operator()( node_type * pNode )
 113             {
 114                 free_node( pNode );
 115             }
 116         };
 117         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 118         //@endcond
 119
 120     public:
 121         /// Initialize split-ordered list of default capacity
 122         /**
 123             The default capacity is defined in bucket table constructor.
 124             See \p intrusive::split_list::expandable_bucket_table, \p intrusive::split_list::static_bucket_table
 125             which selects by \p split_list::dynamic_bucket_table option.
 126         */
 127         SplitListSet()
 128             : base_class()
 129         {}
 130
 131         /// Initialize split-ordered list
 132         SplitListSet(
 133             size_t nItemCount           ///< estimated average of item count
 134             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
 135             )
 136             : base_class( nItemCount, nLoadFactor )
 137         {}
 138
 139     protected:
 140         //@cond
 141         template <bool IsConst>
 142         class iterator_type: protected base_class::template iterator_type<IsConst>
 143         {
 144             typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
 145             friend class SplitListSet;
 146
 147         public:
 148             /// Value pointer type (const for const iterator)
 149             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 150             /// Value reference type (const for const iterator)
 151             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 152
 153         public:
 154             /// Default ctor
 155             iterator_type()
 156             {}
 157
 158             /// Copy ctor
 159             iterator_type( iterator_type const& src )
 160                 : iterator_base_class( src )
 161             {}
 162
 163         protected:
 164             explicit iterator_type( iterator_base_class const& src )
 165                 : iterator_base_class( src )
 166             {}
 167
 168         public:
 169             /// Dereference operator
 170             value_ptr operator ->() const
 171             {
 172                 return &(iterator_base_class::operator->()->m_Value);
 173             }
 174
 175             /// Dereference operator
 176             value_ref operator *() const
 177             {
 178                 return iterator_base_class::operator*().m_Value;
 179             }
 180
 181             /// Pre-increment
 182             iterator_type& operator ++()
 183             {
 184                 iterator_base_class::operator++();
 185                 return *this;
 186             }
 187
 188             /// Assignment operator
 189             iterator_type& operator = (iterator_type const& src)
 190             {
 191                 iterator_base_class::operator=(src);
 192                 return *this;
 193             }
 194
 195             /// Equality operator
 196             template <bool C>
 197             bool operator ==(iterator_type<C> const& i ) const
 198             {
 199                 return iterator_base_class::operator==(i);
 200             }
 201
 202             /// Equality operator
 203             template <bool C>
 204             bool operator !=(iterator_type<C> const& i ) const
 205             {
 206                 return iterator_base_class::operator!=(i);
 207             }
 208         };
 209         //@endcond
 210
 211     public:
 212     ///@name Forward iterators
 213     //@{
 214         /// Forward iterator
 215         /**
 216             The forward iterator for split-list is based on \p OrderedList forward iterator and has some features:
 217             - it has no post-increment operator
 218             - it iterates items in unordered fashion
 219
 220             The iterator interface:
 221             \code
 222             class iterator {
 223             public:
 224                 // Default constructor
 225                 iterator();
 226
 227                 // Copy construtor
 228                 iterator( iterator const& src );
 229
 230                 // Dereference operator
 231                 value_type * operator ->() const;
 232
 233                 // Dereference operator
 234                 value_type& operator *() const;
 235
 236                 // Preincrement operator
 237                 iterator& operator ++();
 238
 239                 // Assignment operator
 240                 iterator& operator = (iterator const& src);
 241
 242                 // Equality operators
 243                 bool operator ==(iterator const& i ) const;
 244                 bool operator !=(iterator const& i ) const;
 245             };
 246             \endcode
 247         */
 248         typedef iterator_type<false>  iterator;
 249
 250         /// Const forward iterator
 251         typedef iterator_type<true>    const_iterator;
 252
 253         /// Returns a forward iterator addressing the first element in a set
 254         /**
 255             For empty set \code begin() == end() \endcode
 256         */
 257         iterator begin()
 258         {
 259             return iterator( base_class::begin());
 260         }
 261
 262         /// Returns an iterator that addresses the location succeeding the last element in a set
 263         /**
 264             Do not use the value returned by <tt>end</tt> function to access any item.
 265             The returned value can be used only to control reaching the end of the set.
 266             For empty set \code begin() == end() \endcode
 267         */
 268         iterator end()
 269         {
 270             return iterator( base_class::end());
 271         }
 272
 273         /// Returns a forward const iterator addressing the first element in a set
 274         const_iterator begin() const
 275         {
 276             return cbegin();
 277         }
 278         /// Returns a forward const iterator addressing the first element in a set
 279         const_iterator cbegin() const
 280         {
 281             return const_iterator( base_class::cbegin());
 282         }
 283
 284         /// Returns an const iterator that addresses the location succeeding the last element in a set
 285         const_iterator end() const
 286         {
 287             return cend();
 288         }
 289         /// Returns an const iterator that addresses the location succeeding the last element in a set
 290         const_iterator cend() const
 291         {
 292             return const_iterator( base_class::cend());
 293         }
 294     //@}
 295
 296     protected:
 297         //@cond
 298         iterator insert_node( node_type * pNode )
 299         {
 300             assert( pNode != nullptr );
 301             scoped_node_ptr p(pNode);
 302
 303             iterator it( base_class::insert_( *pNode ));
 304             if ( it != end()) {
 305                 p.release();
 306                 return it;
 307             }
 308
 309             return end();
 310         }
 311         //@endcond
 312
 313     public:
 314         /// Inserts new node
 315         /**
 316             The function inserts \p val in the set if it does not contain
 317             an item with key equal to \p val.
 318             The \p value_type should be constructible from a value of type \p Q.
 319
 320             Return an iterator pointing to inserted item if success \p end() otherwise
 321         */
 322         template <typename Q>
 323         iterator insert( const Q& val )
 324         {
 325             return insert_node( alloc_node( val ));
 326         }
 327
 328         /// Inserts data of type \p value_type created from \p args
 329         /**
 330             Return an iterator pointing to inserted item if success \p end() otherwise
 331         */
 332         template <typename... Args>
 333         iterator emplace( Args&&... args )
 334         {
 335             return insert_node( alloc_node( std::forward<Args>(args)... ));
 336         }
 337
 338         /// Updates the item
 339         /**
 340             If \p key is not in the set and \p bAllowInsert is \p true, the function inserts a new item.
 341             Otherwise, the function returns an iterator pointing to the item found.
 342
 343             Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
 344             item found or inserted (if inserting is not allowed and \p key is not found, the iterator will be \p end()),
 345
 346             \p second is true if new item has been added or \p false if the item
 347             already is in the set.
 348
 349             @warning If the set is based on \ref cds_nonintrusive_MichaelList_nogc "MichaelList",
 350
 351             see \ref cds_intrusive_item_creating "insert item troubleshooting".
 352             \ref cds_nonintrusive_LazyList_nogc "LazyList" as the base provides exclusive access to inserted item
 353
 354             and does not require any node-level synchronization.
 355         */
 356         template <typename Q>
 357         std::pair<iterator, bool> update( Q const& key, bool bAllowInsert = true )
 358         {
 359             scoped_node_ptr pNode( alloc_node( key ));
 360
 361             std::pair<typename base_class::iterator, bool> ret = base_class::update_( *pNode,
 362
 363                 [](bool /*bNew*/, node_type& /*item*/, node_type& /*val*/){},
 364                 bAllowInsert );
 365             if ( ret.first != base_class::end() && ret.second ) {
 366                 pNode.release();
 367                 return std::make_pair( iterator(ret.first), ret.second );
 368             }
 369
 370             return std::make_pair( iterator(ret.first), ret.second );
 371         }
 372         //@cond
 373         template <typename Q>
 374         CDS_DEPRECATED("ensure() is deprecated, use update()")
 375         std::pair<iterator, bool> ensure( const Q& val )
 376         {
 377             return update( val, true );
 378         }
 379         //@endcond
 380
 381         /// Checks whether the set contains \p key
 382         /**
 383             The function searches the item with key equal to \p key
 384             and returns an iterator pointed to item found and \ref end() otherwise
 385         */
 386         template <typename Q>
 387         iterator contains( Q const& key )
 388         {
 389             return iterator( base_class::find_( key ));
 390         }
 391         //@cond
 392         template <typename Q>
 393         CDS_DEPRECATED("deprecated, use contains()")
 394         iterator find( Q const& key )
 395         {
 396             return contains( key );
 397         }
 398         //@endcond
 399
 400         /// Checks whether the set contains \p key using \p pred predicate for searching
 401         /**
 402             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 403             \p Less functor has the interface like \p std::less.
 404             \p pred must imply the same element order as the comparator used for building the set.
 405         */
 406         template <typename Q, typename Less>
 407         iterator contains( Q const& key, Less pred )
 408         {
 409             CDS_UNUSED( pred );
 410             return iterator( base_class::find_with_( key, typename maker::template predicate_wrapper<Less>::type()));
 411         }
 412         //@cond
 413         // eprecated, use contains()
 414         template <typename Q, typename Less>
 415         iterator find_with( Q const& key, Less pred )
 416         {
 417             return contains( key, pred );
 418         }
 419         //@endcond
 420
 421         /// Clears the set (not atomic, for debugging purposes only)
 422         void clear()
 423         {
 424             base_class::clear();
 425         }
 426
 427         /// Checks if the set is empty
 428         /**
 429             Emptiness is checked by item counting: if item count is zero then the set is empty.
 430             Thus, the correct item counting feature is an important part of split-list set implementation.
 431         */
 432         bool empty() const
 433         {
 434             return base_class::empty();
 435         }
 436
 437         /// Returns item count in the set
 438         size_t size() const
 439         {
 440             return base_class::size();
 441         }
 442
 443         /// Returns internal statistics
 444         stat const& statistics() const
 445         {
 446             return base_class::statistics();
 447         }
 448
 449         /// Returns internal statistics for \p ordered_list
 450         typename ordered_list::stat const& list_statistics() const
 451         {
 452             return base_class::list_statistics();
 453         }
 454     };
 455
 456 }}  // namespace cds::container
 457
 458 #endif // #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_NOGC_H