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