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         typedef typename base_class::stat           stat; ///< Internal statistics
  60
  61     protected:
  62         //@cond
  63         typedef typename maker::cxx_node_allocator    cxx_node_allocator;
  64         typedef typename maker::node_type             node_type;
  65
  66         template <typename Q>
  67         static node_type * alloc_node(Q const& v )
  68         {
  69             return cxx_node_allocator().New( v );
  70         }
  71
  72         template <typename... Args>
  73         static node_type * alloc_node( Args&&... args )
  74         {
  75             return cxx_node_allocator().MoveNew( std::forward<Args>(args)...);
  76         }
  77
  78         static void free_node( node_type * pNode )
  79         {
  80             cxx_node_allocator().Delete( pNode );
  81         }
  82
  83         struct node_disposer {
  84             void operator()( node_type * pNode )
  85             {
  86                 free_node( pNode );
  87             }
  88         };
  89         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
  90         //@endcond
  91
  92     public:
  93         /// Initialize split-ordered list of default capacity
  94         /**
  95             The default capacity is defined in bucket table constructor.
  96             See \p intrusive::split_list::expandable_bucket_table, \p intrusive::split_list::static_bucket_table
  97             which selects by \p split_list::dynamic_bucket_table option.
  98         */
  99         SplitListSet()
 100             : base_class()
 101         {}
 102
 103         /// Initialize split-ordered list
 104         SplitListSet(
 105             size_t nItemCount           ///< estimated average of item count
 106             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
 107             )
 108             : base_class( nItemCount, nLoadFactor )
 109         {}
 110
 111     protected:
 112         /// Forward iterator
 113         /**
 114             \p IsConst - constness boolean flag
 115
 116             The forward iterator has the following features:
 117             - it has no post-increment operator
 118             - it depends on underlying ordered list iterator
 119         */
 120         template <bool IsConst>
 121         class iterator_type: protected base_class::template iterator_type<IsConst>
 122         {
 123             //@cond
 124             typedef typename base_class::template iterator_type<IsConst> iterator_base_class;
 125             friend class SplitListSet;
 126             //@endcond
 127         public:
 128             /// Value pointer type (const for const iterator)
 129             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 130             /// Value reference type (const for const iterator)
 131             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 132
 133         public:
 134             /// Default ctor
 135             iterator_type()
 136             {}
 137
 138             /// Copy ctor
 139             iterator_type( iterator_type const& src )
 140                 : iterator_base_class( src )
 141             {}
 142
 143         protected:
 144             //@cond
 145             explicit iterator_type( iterator_base_class const& src )
 146                 : iterator_base_class( src )
 147             {}
 148             //@endcond
 149
 150         public:
 151             /// Dereference operator
 152             value_ptr operator ->() const
 153             {
 154                 return &(iterator_base_class::operator->()->m_Value);
 155             }
 156
 157             /// Dereference operator
 158             value_ref operator *() const
 159             {
 160                 return iterator_base_class::operator*().m_Value;
 161             }
 162
 163             /// Pre-increment
 164             iterator_type& operator ++()
 165             {
 166                 iterator_base_class::operator++();
 167                 return *this;
 168             }
 169
 170             /// Assignment operator
 171             iterator_type& operator = (iterator_type const& src)
 172             {
 173                 iterator_base_class::operator=(src);
 174                 return *this;
 175             }
 176
 177             /// Equality operator
 178             template <bool C>
 179             bool operator ==(iterator_type<C> const& i ) const
 180             {
 181                 return iterator_base_class::operator==(i);
 182             }
 183
 184             /// Equality operator
 185             template <bool C>
 186             bool operator !=(iterator_type<C> const& i ) const
 187             {
 188                 return iterator_base_class::operator!=(i);
 189             }
 190         };
 191
 192     public:
 193         /// Forward iterator
 194         typedef iterator_type<false>  iterator;
 195
 196         /// Const forward iterator
 197         typedef iterator_type<true>    const_iterator;
 198
 199         /// Returns a forward iterator addressing the first element in a set
 200         /**
 201             For empty set \code begin() == end() \endcode
 202         */
 203         iterator begin()
 204         {
 205             return iterator( base_class::begin() );
 206         }
 207
 208         /// Returns an iterator that addresses the location succeeding the last element in a set
 209         /**
 210             Do not use the value returned by <tt>end</tt> function to access any item.
 211             The returned value can be used only to control reaching the end of the set.
 212             For empty set \code begin() == end() \endcode
 213         */
 214         iterator end()
 215         {
 216             return iterator( base_class::end() );
 217         }
 218
 219         /// Returns a forward const iterator addressing the first element in a set
 220         const_iterator begin() const
 221         {
 222             return cbegin();
 223         }
 224         /// Returns a forward const iterator addressing the first element in a set
 225         const_iterator cbegin() const
 226         {
 227             return const_iterator( base_class::cbegin() );
 228         }
 229
 230         /// Returns an const iterator that addresses the location succeeding the last element in a set
 231         const_iterator end() const
 232         {
 233             return cend();
 234         }
 235         /// Returns an const iterator that addresses the location succeeding the last element in a set
 236         const_iterator cend() const
 237         {
 238             return const_iterator( base_class::cend() );
 239         }
 240
 241     protected:
 242         //@cond
 243         iterator insert_node( node_type * pNode )
 244         {
 245             assert( pNode != nullptr );
 246             scoped_node_ptr p(pNode);
 247
 248             iterator it( base_class::insert_( *pNode ));
 249             if ( it != end() ) {
 250                 p.release();
 251                 return it;
 252             }
 253
 254             return end();
 255         }
 256         //@endcond
 257
 258     public:
 259         /// Inserts new node
 260         /**
 261             The function inserts \p val in the set if it does not contain
 262             an item with key equal to \p val.
 263             The \p value_type should be constructible from a value of type \p Q.
 264
 265             Return an iterator pointing to inserted item if success \p end() otherwise
 266         */
 267         template <typename Q>
 268         iterator insert( const Q& val )
 269         {
 270             return insert_node( alloc_node( val ) );
 271         }
 272
 273         /// Inserts data of type \p value_type created from \p args
 274         /**
 275             Return an iterator pointing to inserted item if success \p end() otherwise
 276         */
 277         template <typename... Args>
 278         iterator emplace( Args&&... args )
 279         {
 280             return insert_node( alloc_node( std::forward<Args>(args)... ) );
 281         }
 282
 283         /// Ensures that the item \p val exists in the set
 284         /**
 285             The operation inserts new item created from \p val if the key \p val is not found in the set.
 286             Otherwise, the function returns an iterator that points to item found.
 287             The \p value_type should be constructible from a value of type \p Q.
 288
 289             Returns <tt> std::pair<iterator, bool> </tt> where \p first is an iterator pointing to
 290             item found or inserted, \p second is true if new item has been added or \p false if the item
 291             already is in the set.
 292         */
 293         template <typename Q>
 294         std::pair<iterator, bool> ensure( const Q& val )
 295         {
 296             scoped_node_ptr pNode( alloc_node( val ));
 297
 298             std::pair<typename base_class::iterator, bool> ret = base_class::ensure_( *pNode, [](bool /*bNew*/, node_type& /*item*/, node_type& /*val*/){} );
 299             if ( ret.first != base_class::end() && ret.second ) {
 300                 pNode.release();
 301                 return std::make_pair( iterator(ret.first), ret.second );
 302             }
 303
 304             return std::make_pair( iterator(ret.first), ret.second );
 305         }
 306
 307         /// Find the key \p key
 308         /** \anchor cds_nonintrusive_SplitListSet_nogc_find
 309
 310             The function searches the item with key equal to \p key
 311             and returns an iterator pointed to item found if the key is found,
 312             and \ref end() otherwise.
 313         */
 314         template <typename Q>
 315         iterator find( Q const& key )
 316         {
 317             return iterator( base_class::find_( key ));
 318         }
 319
 320         /// Finds the key \p key using \p pred predicate for searching
 321         /**
 322             The function is an analog of \ref cds_nonintrusive_SplitListSet_nogc_find "find(Q const&)"
 323             but \p pred is used for key comparing.
 324             \p Less functor has the interface like \p std::less.
 325             \p Less must imply the same element order as the comparator used for building the set.
 326         */
 327         template <typename Q, typename Less>
 328         iterator find_with( Q const& key, Less pred )
 329         {
 330             CDS_UNUSED( pred );
 331             return iterator( base_class::find_with_( key, typename maker::template predicate_wrapper<Less>::type() ));
 332         }
 333
 334         /// Checks if the set is empty
 335         /**
 336             Emptiness is checked by item counting: if item count is zero then the set is empty.
 337             Thus, the correct item counting feature is an important part of split-list set implementation.
 338         */
 339         bool empty() const
 340         {
 341             return base_class::empty();
 342         }
 343
 344         /// Returns item count in the set
 345         size_t size() const
 346         {
 347             return base_class::size();
 348         }
 349
 350         /// Returns internal statistics
 351         stat const& statistics() const
 352         {
 353             return base_class::statistics();
 354         }
 355     };
 356
 357 }}  // namespace cds::container
 358
 359 #endif // #ifndef __CDS_CONTAINER_SPLIT_LIST_SET_NOGC_H