cds/container/split_list_set_nogc.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_SPLIT_LIST_SET_NOGC_H
   4 #define __CDS_CONTAINER_SPLIT_LIST_SET_NOGC_H
   5
   6 #include <cds/intrusive/split_list_nogc.h>
   7 #include <cds/container/details/split_list_base.h>
   8 #include <cds/gc/nogc.h>
   9 #include <cds/container/details/make_split_list_set.h>
  10
  11 namespace cds { namespace container {
  12
  13     /// Split-ordered list set (template specialization for \p gc::nogc)
  14     /** @ingroup cds_nonintrusive_set
  15         \anchor cds_nonintrusive_SplitListSet_nogc
  16
  17         This specialization is so-called append-only container when no item
  18         reclamation may be performed. The class does not support deleting of list item.
  19
  20         See \ref cds_nonintrusive_SplitListSet_hp "SplitListSet" for description of template parameters.
  21
  22         @warning Many member functions return an iterator pointing to an item.
  23         The iterator can be used to set up field of the item,
  24         but you should provide an exclusive access to it,
  25         see \ref cds_intrusive_item_creating "insert item troubleshooting".
  26     */
  27     template <
  28         class T,
  29 #ifdef CDS_DOXYGEN_INVOKED
  30         class Traits = split_list::traits
  31 #else
  32         class Traits
  33 #endif
  34     >
  35     class SplitListSet< cds::gc::nogc, T, Traits>
  36 #ifdef CDS_DOXYGEN_INVOKED
  37         :protected intrusive::SplitListSet<cds::gc::nogc, typename Traits::ordered_list, Traits>
  38 #else
  39         :protected details::make_split_list_set< cds::gc::nogc, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> >::type
  40 #endif
  41     {
  42     protected:
  43         //@cond
  44         typedef details::make_split_list_set< cds::gc::nogc, T, typename Traits::ordered_list, split_list::details::wrap_set_traits<T, Traits> > maker;
  45         typedef typename maker::type  base_class;
  46         //@endcond
  47
  48     public:
  49         typedef cds::gc::nogc  gc;         ///< Garbage collector
  50         typedef T              value_type; ///< type of value to be stored in the list
  51         typedef Traits         traits;     ///< List traits
  52
  53         typedef typename maker::ordered_list      ordered_list;     ///< Underlying ordered list class
  54         typedef typename base_class::key_comparator key_comparator; ///< key comparison functor
  55
  56         /// Hash functor for \ref value_type and all its derivatives that you use
  57         typedef typename base_class::hash           hash;
  58         typedef typename base_class::item_counter   item_counter; ///< Item counter type
  59
  60     protected:
  61         //@cond
  62         typedef typename maker::cxx_node_allocator    cxx_node_allocator;
  63         typedef typename maker::node_type             node_type;
  64
  65         template <typename Q>
  66         static node_type * alloc_node(Q const& v )
  67         {
  68             return cxx_node_allocator().New( v );
  69         }
  70
  71         template <typename... Args>
  72         static node_type * alloc_node( Args&&... args )
  73         {
  74             return cxx_node_allocator().MoveNew( std::forward<Args>(args)...);
  75         }
  76
  77         static void free_node( node_type * pNode )
  78         {
  79             cxx_node_allocator().Delete( pNode );
  80         }
  81
  82         struct node_disposer {
  83             void operator()( node_type * pNode )
  84             {
  85                 free_node( pNode );
  86             }
  87         };
  88         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
  89         //@endcond
  90
  91     public:
  92         /// Initialize split-ordered list of default capacity
  93         /**
  94             The default capacity is defined in bucket table constructor.
  95             See \p intrusive::split_list::expandable_bucket_table, \p intrusive::split_list::static_bucket_table
  96             which selects by \p split_list::dynamic_bucket_table option.
  97         */
  98         SplitListSet()
  99             : base_class()
 100         {}
 101
 102         /// Initialize split-ordered list
 103         SplitListSet(
 104             size_t nItemCount           ///< estimated average of item count
 105             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
 106             )
 107             : base_class( nItemCount, nLoadFactor )
 108         {}
 109
 110     protected:
 111         /// Forward iterator
 112         /**
 113             \p IsConst - constness boolean flag
 114
 115             The forward iterator has the following features:
 116             - it has no post-increment operator
 117             - it depends on underlying ordered list iterator
 118         */
 119         template <bool IsConst>
 120         class iterator_type: protected base_class::template iterator_type<IsConst>
 121         {
 122             //@cond
 123             typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
 124             friend class SplitListSet;
 125             //@endcond
 126         public:
 127             /// Value pointer type (const for const iterator)
 128             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 129             /// Value reference type (const for const iterator)
 130             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 131
 132         public:
 133             /// Default ctor
 134             iterator_type()
 135             {}
 136
 137             /// Copy ctor
 138             iterator_type( iterator_type const& src )
 139                 : iterator_base_class( src )
 140             {}
 141
 142         protected:
 143             //@cond
 144             explicit iterator_type( iterator_base_class const& src )
 145                 : iterator_base_class( src )
 146             {}
 147             //@endcond
 148
 149         public:
 150             /// Dereference operator
 151             value_ptr operator ->() const
 152             {
 153                 return &(iterator_base_class::operator->()->m_Value);
 154             }
 155
 156             /// Dereference operator
 157             value_ref operator *() const
 158             {
 159                 return iterator_base_class::operator*().m_Value;
 160             }
 161
 162             /// Pre-increment
 163             iterator_type& operator ++()
 164             {
 165                 iterator_base_class::operator++();
 166                 return *this;
 167             }
 168
 169             /// Assignment operator
 170             iterator_type& operator = (iterator_type const& src)
 171             {
 172                 iterator_base_class::operator=(src);
 173                 return *this;
 174             }
 175
 176             /// Equality operator
 177             template <bool C>
 178             bool operator ==(iterator_type<C> const& i ) const
 179             {
 180                 return iterator_base_class::operator==(i);
 181             }
 182
 183             /// Equality operator
 184             template <bool C>
 185             bool operator !=(iterator_type<C> const& i ) const
 186             {
 187                 return iterator_base_class::operator!=(i);
 188             }
 189         };
 190
 191     public:
 192         /// Forward iterator
 193         typedef iterator_type<false>  iterator;
 194
 195         /// Const forward iterator
 196         typedef iterator_type<true>    const_iterator;
 197
 198         /// Returns a forward iterator addressing the first element in a set
 199         /**
 200             For empty set \code begin() == end() \endcode
 201         */
 202         iterator begin()
 203         {
 204             return iterator( base_class::begin() );
 205         }
 206
 207         /// Returns an iterator that addresses the location succeeding the last element in a set
 208         /**
 209             Do not use the value returned by <tt>end</tt> function to access any item.
 210             The returned value can be used only to control reaching the end of the set.
 211             For empty set \code begin() == end() \endcode
 212         */
 213         iterator end()
 214         {
 215             return iterator( base_class::end() );
 216         }
 217
 218         /// Returns a forward const iterator addressing the first element in a set
 219         const_iterator begin() const
 220         {
 221             return const_iterator( base_class::begin() );
 222         }
 223
 224         /// Returns an const iterator that addresses the location succeeding the last element in a set
 225         const_iterator end() const
 226         {
 227             return const_iterator( base_class::end() );
 228         }
 229
 230     protected:
 231         //@cond
 232         iterator insert_node( node_type * pNode )
 233         {
 234             assert( pNode != nullptr );
 235             scoped_node_ptr p(pNode);
 236
 237             iterator it( base_class::insert_( *pNode ));
 238             if ( it != end() ) {
 239                 p.release();
 240                 return it;
 241             }
 242
 243             return end();
 244         }
 245         //@endcond
 246
 247     public:
 248         /// Inserts new node
 249         /**
 250             The function inserts \p val in the set if it does not contain
 251             an item with key equal to \p val.
 252             The \p value_type should be constructible from a value of type \p Q.
 253
 254             Return an iterator pointing to inserted item if success \p end() otherwise
 255         */
 256         template <typename Q>
 257         iterator insert( const Q& val )
 258         {
 259             return insert_node( alloc_node( val ) );
 260         }
 261
 262         /// Inserts data of type \p value_type created from \p args
 263         /**
 264             Return an iterator pointing to inserted item if success \p end() otherwise
 265         */
 266         template <typename... Args>
 267         iterator emplace( Args&&... args )
 268         {
 269             return insert_node( alloc_node( std::forward<Args>(args)... ) );
 270         }
 271
 272         /// Ensures that the item \p val exists in the set
 273         /**
 274             The operation inserts new item created from \p val if the key \p val is not found in the set.
 275             Otherwise, the function returns an iterator that points to item found.
 276             The \p value_type should be constructible from a value of type \p Q.
 277
 278             Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
 279             item found or inserted, \p second is true if new item has been added or \p false if the item
 280             already is in the set.
 281         */
 282         template <typename Q>
 283         std::pair<iterator, bool> ensure( const Q& val )
 284         {
 285             scoped_node_ptr pNode( alloc_node( val ));
 286
 287             std::pair<typename base_class::iterator, bool> ret = base_class::ensure_( *pNode, [](bool /*bNew*/, node_type& /*item*/, node_type& /*val*/){} );
 288             if ( ret.first != base_class::end() && ret.second ) {
 289                 pNode.release();
 290                 return std::make_pair( iterator(ret.first), ret.second );
 291             }
 292
 293             return std::make_pair( iterator(ret.first), ret.second );
 294         }
 295
 296         /// Find the key \p key
 297         /** \anchor cds_nonintrusive_SplitListSet_nogc_find
 298
 299             The function searches the item with key equal to \p key
 300             and returns an iterator pointed to item found if the key is found,
 301             and \ref end() otherwise.
 302         */
 303         template <typename Q>
 304         iterator find( Q const& key )
 305         {
 306             return iterator( base_class::find_( key ));
 307         }
 308
 309         /// Finds the key \p key using \p pred predicate for searching
 310         /**
 311             The function is an analog of \ref cds_nonintrusive_SplitListSet_nogc_find "find(Q const&)"
 312             but \p pred is used for key comparing.
 313             \p Less functor has the interface like \p std::less.
 314             \p Less must imply the same element order as the comparator used for building the set.
 315         */
 316         template <typename Q, typename Less>
 317         iterator find_with( Q const& key, Less pred )
 318         {
 319             return iterator( base_class::find_with_( key, typename maker::template predicate_wrapper<Less>::type() ));
 320         }
 321
 322         /// Checks if the set is empty
 323         /**
 324             Emptiness is checked by item counting: if item count is zero then the set is empty.
 325             Thus, the correct item counting feature is an important part of split-list set implementation.
 326         */
 327         bool empty() const
 328         {
 329             return base_class::empty();
 330         }
 331
 332         /// Returns item count in the set
 333         size_t size() const
 334         {
 335             return base_class::size();
 336         }
 337     };
 338
 339 }}  // namespace cds::container
 340
 341 #endif // #ifndef __CDS_CONTAINER_SPLIT_LIST_SET_NOGC_H