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