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