cds/container/split_list_set_nogc.h

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