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-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_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         /// Forward iterator
 141         /**
 142             \p IsConst - constness boolean flag
 143
 144             The forward iterator has the following features:
 145             - it has no post-increment operator
 146             - it depends on underlying ordered list iterator
 147         */
 148         template <bool IsConst>
 149         class iterator_type: protected base_class::template iterator_type<IsConst>
 150         {
 151             //@cond
 152             typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
 153             friend class SplitListSet;
 154             //@endcond
 155         public:
 156             /// Value pointer type (const for const iterator)
 157             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 158             /// Value reference type (const for const iterator)
 159             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 160
 161         public:
 162             /// Default ctor
 163             iterator_type()
 164             {}
 165
 166             /// Copy ctor
 167             iterator_type( iterator_type const& src )
 168                 : iterator_base_class( src )
 169             {}
 170
 171         protected:
 172             //@cond
 173             explicit iterator_type( iterator_base_class const& src )
 174                 : iterator_base_class( src )
 175             {}
 176             //@endcond
 177
 178         public:
 179             /// Dereference operator
 180             value_ptr operator ->() const
 181             {
 182                 return &(iterator_base_class::operator->()->m_Value);
 183             }
 184
 185             /// Dereference operator
 186             value_ref operator *() const
 187             {
 188                 return iterator_base_class::operator*().m_Value;
 189             }
 190
 191             /// Pre-increment
 192             iterator_type& operator ++()
 193             {
 194                 iterator_base_class::operator++();
 195                 return *this;
 196             }
 197
 198             /// Assignment operator
 199             iterator_type& operator = (iterator_type const& src)
 200             {
 201                 iterator_base_class::operator=(src);
 202                 return *this;
 203             }
 204
 205             /// Equality operator
 206             template <bool C>
 207             bool operator ==(iterator_type<C> const& i ) const
 208             {
 209                 return iterator_base_class::operator==(i);
 210             }
 211
 212             /// Equality operator
 213             template <bool C>
 214             bool operator !=(iterator_type<C> const& i ) const
 215             {
 216                 return iterator_base_class::operator!=(i);
 217             }
 218         };
 219
 220     public:
 221         /// Forward iterator
 222         typedef iterator_type<false>  iterator;
 223
 224         /// Const forward iterator
 225         typedef iterator_type<true>    const_iterator;
 226
 227         /// Returns a forward iterator addressing the first element in a set
 228         /**
 229             For empty set \code begin() == end() \endcode
 230         */
 231         iterator begin()
 232         {
 233             return iterator( base_class::begin() );
 234         }
 235
 236         /// Returns an iterator that addresses the location succeeding the last element in a set
 237         /**
 238             Do not use the value returned by <tt>end</tt> function to access any item.
 239             The returned value can be used only to control reaching the end of the set.
 240             For empty set \code begin() == end() \endcode
 241         */
 242         iterator end()
 243         {
 244             return iterator( base_class::end() );
 245         }
 246
 247         /// Returns a forward const iterator addressing the first element in a set
 248         const_iterator begin() const
 249         {
 250             return cbegin();
 251         }
 252         /// Returns a forward const iterator addressing the first element in a set
 253         const_iterator cbegin() const
 254         {
 255             return const_iterator( base_class::cbegin() );
 256         }
 257
 258         /// Returns an const iterator that addresses the location succeeding the last element in a set
 259         const_iterator end() const
 260         {
 261             return cend();
 262         }
 263         /// Returns an const iterator that addresses the location succeeding the last element in a set
 264         const_iterator cend() const
 265         {
 266             return const_iterator( base_class::cend() );
 267         }
 268
 269     protected:
 270         //@cond
 271         iterator insert_node( node_type * pNode )
 272         {
 273             assert( pNode != nullptr );
 274             scoped_node_ptr p(pNode);
 275
 276             iterator it( base_class::insert_( *pNode ));
 277             if ( it != end() ) {
 278                 p.release();
 279                 return it;
 280             }
 281
 282             return end();
 283         }
 284         //@endcond
 285
 286     public:
 287         /// Inserts new node
 288         /**
 289             The function inserts \p val in the set if it does not contain
 290             an item with key equal to \p val.
 291             The \p value_type should be constructible from a value of type \p Q.
 292
 293             Return an iterator pointing to inserted item if success \p end() otherwise
 294         */
 295         template <typename Q>
 296         iterator insert( const Q& val )
 297         {
 298             return insert_node( alloc_node( val ) );
 299         }
 300
 301         /// Inserts data of type \p value_type created from \p args
 302         /**
 303             Return an iterator pointing to inserted item if success \p end() otherwise
 304         */
 305         template <typename... Args>
 306         iterator emplace( Args&&... args )
 307         {
 308             return insert_node( alloc_node( std::forward<Args>(args)... ) );
 309         }
 310
 311         /// Updates the item
 312         /**
 313             If \p key is not in the set and \p bAllowInsert is \p true, the function inserts a new item.
 314             Otherwise, the function returns an iterator pointing to the item found.
 315
 316             Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
 317             item found or inserted (if inserting is not allowed and \p key is not found, the iterator will be \p end()),
 318
 319             \p second is true if new item has been added or \p false if the item
 320             already is in the set.
 321
 322             @warning If the set is based on \ref cds_nonintrusive_MichaelList_nogc "MichaelList",
 323
 324             see \ref cds_intrusive_item_creating "insert item troubleshooting".
 325             \ref cds_nonintrusive_LazyList_nogc "LazyList" as the base provides exclusive access to inserted item
 326
 327             and does not require any node-level synchronization.
 328         */
 329         template <typename Q>
 330         std::pair<iterator, bool> update( Q const& key, bool bAllowInsert = true )
 331         {
 332             scoped_node_ptr pNode( alloc_node( key ));
 333
 334             std::pair<typename base_class::iterator, bool> ret = base_class::update_( *pNode,
 335
 336                 [](bool /*bNew*/, node_type& /*item*/, node_type& /*val*/){},
 337                 bAllowInsert );
 338             if ( ret.first != base_class::end() && ret.second ) {
 339                 pNode.release();
 340                 return std::make_pair( iterator(ret.first), ret.second );
 341             }
 342
 343             return std::make_pair( iterator(ret.first), ret.second );
 344         }
 345         //@cond
 346         template <typename Q>
 347         CDS_DEPRECATED("ensure() is deprecated, use update()")
 348         std::pair<iterator, bool> ensure( const Q& val )
 349         {
 350             return update( val, true );
 351         }
 352         //@endcond
 353
 354         /// Checks whether the set contains \p key
 355         /**
 356             The function searches the item with key equal to \p key
 357             and returns an iterator pointed to item found and \ref end() otherwise
 358         */
 359         template <typename Q>
 360         iterator contains( Q const& key )
 361         {
 362             return iterator( base_class::find_( key ));
 363         }
 364         //@cond
 365         template <typename Q>
 366         CDS_DEPRECATED("deprecated, use contains()")
 367         iterator find( Q const& key )
 368         {
 369             return contains( key );
 370         }
 371         //@endcond
 372
 373         /// Checks whether the set contains \p key using \p pred predicate for searching
 374         /**
 375             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 376             \p Less functor has the interface like \p std::less.
 377             \p pred must imply the same element order as the comparator used for building the set.
 378         */
 379         template <typename Q, typename Less>
 380         iterator contains( Q const& key, Less pred )
 381         {
 382             CDS_UNUSED( pred );
 383             return iterator( base_class::find_with_( key, typename maker::template predicate_wrapper<Less>::type() ));
 384         }
 385         //@cond
 386         // eprecated, use contains()
 387         template <typename Q, typename Less>
 388         iterator find_with( Q const& key, Less pred )
 389         {
 390             return contains( key, pred );
 391         }
 392         //@endcond
 393
 394         /// Checks if the set is empty
 395         /**
 396             Emptiness is checked by item counting: if item count is zero then the set is empty.
 397             Thus, the correct item counting feature is an important part of split-list set implementation.
 398         */
 399         bool empty() const
 400         {
 401             return base_class::empty();
 402         }
 403
 404         /// Returns item count in the set
 405         size_t size() const
 406         {
 407             return base_class::size();
 408         }
 409
 410         /// Returns internal statistics
 411         stat const& statistics() const
 412         {
 413             return base_class::statistics();
 414         }
 415     };
 416
 417 }}  // namespace cds::container
 418
 419 #endif // #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_NOGC_H