cds/intrusive/striped_set.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_STRIPED_SET_H
   4 #define __CDS_INTRUSIVE_STRIPED_SET_H
   5
   6 #include <cds/intrusive/base.h>
   7 #include <cds/intrusive/striped_set/adapter.h>
   8 #include <cds/intrusive/striped_set/striping_policy.h>
   9
  10 namespace cds { namespace intrusive {
  11     /// StripedSet related definitions
  12     namespace striped_set {
  13     }   // namespace striped_set
  14
  15     /// Striped hash set
  16     /** @ingroup cds_intrusive_map
  17
  18         Source
  19             - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
  20
  21         Lock striping is very simple technique.
  22         The set consists of the bucket table and the array of locks.
  23         Initially, the capacity of lock array and bucket table is the same.
  24         When set is resized, bucket table capacity will be doubled but lock array will not.
  25         The lock \p i protects each bucket \p j, where <tt> j = i mod L </tt>,
  26         where \p L - the size of lock array.
  27
  28         Template arguments:
  29             - \p Container - the container class that is used as bucket table entry. The \p Container class should support
  30                 an uniform interface described below.
  31             - \p Options - options
  32
  33         The \p %StripedSet class does not exactly dictate the type of container that should be used as a \p Container bucket.
  34         Instead, the class supports different intrusive container type for the bucket, for exampe, \p boost::intrusive::list, \p boost::intrusive::set and others.
  35
  36         Remember that \p %StripedSet class algorithm ensures sequential blocking access to its bucket through the mutex type you specify
  37         among \p Options template arguments.
  38
  39         The \p Options are:
  40         - opt::mutex_policy - concurrent access policy.
  41             Available policies: striped_set::striping, striped_set::refinable.
  42             Default is striped_set::striping.
  43         - cds::opt::hash - hash functor. Default option value see <tt>opt::v::hash_selector <opt::none></tt> which selects default hash functor for
  44             your compiler.
  45         - cds::opt::compare - key comparison functor. No default functor is provided.
  46             If the option is not specified, the opt::less is used.
  47         - cds::opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
  48         - cds::opt::item_counter - item counter type. Default is \p atomicity::item_counter since some operation on the counter is performed
  49             without locks. Note that item counting is an essential part of the set algorithm, so dummy type like atomicity::empty_item_counter
  50             is not suitable.
  51         - cds::opt::allocator - the allocator type using for memory allocation of bucket table and lock array. Default is CDS_DEFAULT_ALLOCATOR.
  52         - cds::opt::resizing_policy - the resizing policy that is a functor that decides when to resize the hash set.
  53             Default option value depends on bucket container type:
  54                 for sequential containers like \p boost::intrusive::list the resizing policy is <tt>cds::container::striped_set::load_factor_resizing <4></tt>;
  55                 for other type of containers like \p boost::intrusive::set  the resizing policy is cds::container::striped_set::no_resizing.
  56             See cds::container::striped_set namespace for list of all possible types of the option.
  57             Note that the choose of resizing policy depends of \p Container type:
  58             for sequential containers like \p boost::intrusive::list right choosing of the policy can significantly improve performance.
  59             For other, non-sequential types of \p Container (like a \p boost::intrusive::set) the resizing policy is not so important.
  60         - cds::opt::buffer - a buffer type used only for boost::intrusive::unordered_set.
  61             Default is cds::opt::v::static_buffer< cds::any_type, 256 >.
  62
  63             opt::compare or opt::less options are used in some \p Container class for ordering.
  64             opt::compare option has the highest priority: if opt::compare is specified, opt::less is not used.
  65
  66             You can pass other option that would be passed to <tt>adapt</tt> metafunction, see below.
  67
  68         <b>Internal details</b>
  69
  70             The \p %StripedSet class cannot utilize the \p Container container specified directly, but only its adapted variant which
  71             supports an unified interface. Internally, the adaptation is made via intrusive::striped_set::adapt metafunction that wraps bucket container
  72             and provides the unified bucket interface suitable for \p %StripedSet. Such adaptation is completely transparent for you -
  73             you don't need to call \p adapt metafunction directly, \p %StripedSet class's internal machinery itself invokes appropriate
  74             \p adapt metafunction specialization to adjust your \p Container container class to \p %StripedSet bucket's internal interface.
  75             All you need is to include a right header before <tt>striped_set.h</tt>.
  76
  77             By default, <tt>intrusive::striped_set::adapt<AnyContainer, OptionPack> </tt> metafunction does not make any wrapping to \p AnyContainer,
  78             so, the result <tt>intrusive::striped_set::adapt<AnyContainer, OptionPack>::type </tt> is the same as \p AnyContainer.
  79             However, there are a lot of specializations of \p %intrusive::striped_set::adapt for \p boost::intrusive containers, see table below.
  80             Any of this specialization wraps corresponding container making it suitable for the set's bucket.
  81             Remember, you should include the proper header file for \p adapt <b>before</b> including <tt>striped_set.h</tt>.
  82
  83             \note It is important to specify <tt>boost::intrusive::constant_time_size<true></tt> option
  84             for all \p boost::intrusive container that supports this option. Fast item counting feature is essential part of
  85             \p %StripedSet resizing algorithm.
  86
  87             <table>
  88                 <tr>
  89                     <th>Container</th>
  90                     <th>.h-file for \p adapt</th>
  91                     <th>Example</th>
  92                     <th>Notes</th>
  93                 </tr>
  94                 <tr>
  95                     <td> \p boost::intrusive::list</td>
  96                     <td><tt><cds/intrusive/striped_set/boost_list.h></tt></td>
  97                     <td>\code
  98                         #include <cds/intrusive/striped_set/boost_list.h>
  99                         #include <cds/intrusive/striped_set.h>
 100                         typedef cds::intrusive::StripedSet<
 101                         boost::intrusive::list<T, boost::intrusive::constant_time_size<true> >,
 102                             cds::opt::less< std::less<T> >
 103                         > striped_set;
 104                     \endcode
 105                     </td>
 106                     <td>
 107                         The list is ordered.
 108                         Template argument pack \p Options <b>must</b> contain cds::opt::less or cds::opt::compare for type \p T stored in the list
 109                     </td>
 110                 </tr>
 111                 <tr>
 112                     <td> \p boost::intrusive::slist</td>
 113                     <td><tt><cds/intrusive/striped_set/boost_slist.h></tt></td>
 114                     <td>\code
 115                         #include <cds/intrusive/striped_set/boost_slist.h>
 116                         #include <cds/intrusive/striped_set.h>
 117                         typedef cds::intrusive::StripedSet<
 118                             boost::intrusive::slist<T, boost::intrusive::constant_time_size<true> >,
 119                             cds::opt::less< std::less<T> >
 120                         > striped_set;
 121                     \endcode
 122                     </td>
 123                     <td>
 124                         The list is ordered.
 125                         Template argument pack \p Options <b>must</b> contain cds::opt::less or cds::opt::compare for type \p T stored in the list
 126                     </td>
 127                 </tr>
 128                 <tr>
 129                     <td> \p boost::intrusive::set</td>
 130                     <td><tt><cds/intrusive/striped_set/boost_set.h></tt></td>
 131                     <td>\code
 132                         #include <cds/intrusive/striped_set/boost_set.h>
 133                         #include <cds/intrusive/striped_set.h>
 134                         typedef cds::intrusive::StripedSet<
 135                             boost::intrusive::set<T, boost::intrusive::constant_time_size<true> >
 136                         > striped_set;
 137                     \endcode
 138                     </td>
 139                     <td>
 140                         Note that \p boost::intrusive::compare option using in \p boost::intrusive::set
 141                         should support \p T type stored in the set and any type \p Q that you can use
 142                         in \p erase and \p find member functions.
 143                     </td>
 144                 </tr>
 145                 <tr>
 146                     <td> \p boost::intrusive::unordered_set</td>
 147                     <td><tt><cds/intrusive/striped_set/boost_unordered_set.h></tt></td>
 148                     <td>\code
 149                         #include <cds/intrusive/striped_set/boost_unordered_set.h>
 150                         #include <cds/intrusive/striped_set.h>
 151                         typedef cds::intrusive::StripedSet<
 152                             boost::intrusive::unordered_set<T
 153                                 ,boost::intrusive::constant_time_size<true>
 154                                 ,boost::intrusive::hash< user_provided_hash_functor >
 155                             >
 156                         > striped_set;
 157                     \endcode
 158                     </td>
 159                     <td>
 160                         You should provide two different hash function h1 and h2 - one for boost::intrusive::unordered_set
 161                         and other for %StripedSet. For the best result, h1 and h2 must be orthogonal i.e. h1(X) != h2(X) for any value X
 162
 163                         The option opt::buffer is used for boost::intrusive::bucket_traits. Default is cds::opt::v::static_buffer< cds::any_type, 256 >.
 164                         The resizing policy should correlate with the buffer capacity.
 165                         The default resizing policy is cds::container::striped_set::load_factor_resizing<256> what gives load factor 1 for
 166                         default bucket buffer that is the best for \p boost::intrusive::unordered_set.
 167                     </td>
 168                 </tr>
 169                 <tr>
 170                     <td> \p boost::intrusive::avl_set</td>
 171                     <td><tt><cds/intrusive/striped_set/boost_avl_set.h></tt></td>
 172                     <td>\code
 173                         #include <cds/intrusive/striped_set/boost_avl_set.h>
 174                         #include <cds/intrusive/striped_set.h>
 175                         typedef cds::intrusive::StripedSet<
 176                             boost::intrusive::avl_set<T, boost::intrusive::constant_time_size<true> >
 177                         > striped_set;
 178                     \endcode
 179                     </td>
 180                     <td>
 181                         Note that \p boost::intrusive::compare option using in \p boost::intrusive::avl_set
 182                         should support \p T type stored in the set and any type \p Q that you can use
 183                         in \p erase and \p find member functions.
 184                     </td>
 185                 </tr>
 186                 <tr>
 187                     <td> \p boost::intrusive::sg_set</td>
 188                     <td><tt><cds/intrusive/striped_set/boost_sg_set.h></tt></td>
 189                     <td>\code
 190                         #include <cds/intrusive/striped_set/boost_sg_set.h>
 191                         #include <cds/intrusive/striped_set.h>
 192                         typedef cds::intrusive::StripedSet<
 193                             boost::intrusive::sg_set<T, boost::intrusive::constant_time_size<true> >
 194                         > striped_set;
 195                     \endcode
 196                     </td>
 197                     <td>
 198                         Note that \p boost::intrusive::compare option using in \p boost::intrusive::sg_set
 199                         should support \p T type stored in the set and any type \p Q that you can use
 200                         in \p erase and \p find member functions.
 201                     </td>
 202                 </tr>
 203                 <tr>
 204                     <td> \p boost::intrusive::splay_set</td>
 205                     <td><tt><cds/intrusive/striped_set/boost_splay_set.h></tt></td>
 206                     <td>\code
 207                         #include <cds/intrusive/striped_set/boost_splay_set.h>
 208                         #include <cds/intrusive/striped_set.h>
 209                         typedef cds::intrusive::StripedSet<
 210                             boost::intrusive::splay_set<T, boost::intrusive::constant_time_size<true> >
 211                         > striped_set;
 212                     \endcode
 213                     </td>
 214                     <td>
 215                         Note that \p boost::intrusive::compare option using in \p boost::intrusive::splay_set
 216                         should support \p T type stored in the set and any type \p Q that you can use
 217                         in \p erase and \p find member functions.
 218                     </td>
 219                 </tr>
 220                 <tr>
 221                     <td> \p boost::intrusive::treap_set</td>
 222                     <td><tt><cds/intrusive/striped_set/boost_treap_set.h></tt></td>
 223                     <td>\code
 224                         #include <cds/intrusive/striped_set/boost_treap_set.h>
 225                         #include <cds/intrusive/striped_set.h>
 226                         typedef cds::intrusive::StripedSet<
 227                             boost::intrusive::treap_set<T, boost::intrusive::constant_time_size<true> >
 228                         > striped_set;
 229                     \endcode
 230                     </td>
 231                     <td>
 232                         Note that \p boost::intrusive::compare option using in \p boost::intrusive::treap_set
 233                         should support \p T type stored in the set and any type \p Q that you can use
 234                         in \p erase and \p find member functions.
 235                     </td>
 236                 </tr>
 237             </table>
 238
 239             You can use another intrusive container type as striped set's bucket.
 240             Suppose, you have a container class \p MyBestContainer and you want to integrate it with \p StripedSet as bucket type.
 241             There are two possibility:
 242             - either your \p MyBestContainer class has native support of bucket's interface;
 243                 in this case, you can use default \p intrusive::striped_set::adapt metafunction;
 244             - or your \p MyBestContainer class does not support bucket's interface, which means, that you should develop a specialization
 245                 <tt>cds::intrusive::striped_set::adapt<MyBestContainer> </tt> metafunction providing necessary interface.
 246
 247             The <tt>intrusive::striped_set::adapt< Container, OptionPack ></tt> metafunction has two template argument:
 248             - \p Container is the class that should be used as the bucket, for example, <tt>boost::intrusive::list< T ></tt>.
 249             - \p OptionPack is the packed options from \p %StripedSet declaration. The \p adapt metafunction can use
 250                 any option from \p OptionPack for its internal use. For example, a \p compare option can be passed to \p adapt
 251                 metafunction via \p OptionPack argument of \p %StripedSet declaration.
 252
 253             See intrusive::striped_set::adapt metafunction for the description of interface that the bucket container must provide
 254             to be \p %StripedSet compatible.
 255     */
 256     template <class Container, CDS_DECL_OPTIONS9>
 257     class StripedSet
 258     {
 259     public:
 260         //@cond
 261         struct default_options {
 262             typedef striped_set::striping<>         mutex_policy;
 263             typedef typename cds::opt::v::hash_selector< cds::opt::none >::type   hash;
 264             typedef cds::atomicity::item_counter    item_counter;
 265             typedef CDS_DEFAULT_ALLOCATOR           allocator;
 266             typedef cds::opt::none                  resizing_policy;
 267             typedef cds::opt::none                  compare;
 268             typedef cds::opt::none                  less;
 269         };
 270
 271         typedef typename cds::opt::make_options<
 272             typename cds::opt::find_type_traits< default_options, CDS_OPTIONS9 >::type
 273             ,CDS_OPTIONS9
 274         >::type   options;
 275         //@endcond
 276
 277         typedef Container                           underlying_container_type   ;   ///< original intrusive container type for the bucket
 278         typedef typename cds::intrusive::striped_set::adapt< underlying_container_type, CDS_OPTIONS9 >::type   bucket_type ;   ///< container type adapted for hash set
 279         typedef typename bucket_type::value_type    value_type  ;   ///< value type stored in the set
 280
 281         typedef typename options::hash              hash            ; ///< Hash functor
 282         typedef typename options::item_counter      item_counter    ; ///< Item counter
 283         typedef typename cds::opt::select_default<
 284             typename options::resizing_policy,
 285             typename bucket_type::default_resizing_policy
 286         >::type                                     resizing_policy ; ///< Resizing policy
 287         typedef typename options::allocator         allocator_type  ; ///< allocator type specified in options.
 288         typedef typename options::mutex_policy      mutex_policy    ; ///< Mutex policy
 289
 290         typedef cds::details::Allocator< bucket_type, allocator_type > bucket_allocator;  ///< bucket allocator type based on allocator_type
 291
 292     protected:
 293         bucket_type *   m_Buckets       ;   ///< Bucket table
 294         size_t          m_nBucketMask   ;   ///< Bucket table size - 1. m_nBucketMask + 1 should be power of two.
 295         item_counter    m_ItemCounter   ;   ///< Item counter
 296         hash            m_Hash          ;   ///< Hash functor
 297
 298         mutex_policy    m_MutexPolicy   ;   ///< Mutex policy
 299         resizing_policy m_ResizingPolicy;   ///< Resizing policy
 300
 301         static const size_t c_nMinimalCapacity = 16 ;   ///< Minimal capacity
 302
 303     protected:
 304         //@cond
 305         typedef typename mutex_policy::scoped_cell_lock     scoped_cell_lock;
 306         typedef typename mutex_policy::scoped_full_lock     scoped_full_lock;
 307         typedef typename mutex_policy::scoped_resize_lock   scoped_resize_lock;
 308
 309 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 310         struct empty_insert_functor {
 311             void operator()( value_type& )
 312             {}
 313         };
 314
 315         struct empty_erase_functor  {
 316             void operator()( value_type const& )
 317             {}
 318         };
 319
 320         struct empty_find_functor {
 321             template <typename Q>
 322             void operator()( value_type& item, Q& val )
 323             {}
 324         };
 325 #   endif
 326         //@endcond
 327
 328     protected:
 329         //@cond
 330         static size_t calc_init_capacity( size_t nCapacity )
 331         {
 332             nCapacity = cds::beans::ceil2( nCapacity );
 333             return nCapacity < c_nMinimalCapacity ? c_nMinimalCapacity : nCapacity;
 334         }
 335
 336         void alloc_bucket_table( size_t nSize )
 337         {
 338             assert( cds::beans::is_power2( nSize ));
 339             m_nBucketMask = nSize - 1;
 340             m_Buckets = bucket_allocator().NewArray( nSize );
 341         }
 342
 343         static void free_bucket_table( bucket_type * pBuckets, size_t nSize )
 344         {
 345             bucket_allocator().Delete( pBuckets, nSize );
 346         }
 347
 348         template <typename Q>
 349         size_t hashing( Q const& v ) const
 350         {
 351             return m_Hash( v );
 352         }
 353
 354         bucket_type * bucket( size_t nHash ) const CDS_NOEXCEPT
 355         {
 356             return m_Buckets + (nHash & m_nBucketMask);
 357         }
 358
 359         template <typename Q, typename Func>
 360         bool find_( Q& val, Func f )
 361         {
 362             size_t nHash = hashing( val );
 363
 364             scoped_cell_lock sl( m_MutexPolicy, nHash );
 365             return bucket( nHash )->find( val, f );
 366         }
 367
 368         template <typename Q, typename Less, typename Func>
 369         bool find_with_( Q& val, Less pred, Func f )
 370         {
 371             size_t nHash = hashing( val );
 372             scoped_cell_lock sl( m_MutexPolicy, nHash );
 373             return bucket( nHash )->find( val, pred, f );
 374         }
 375
 376         void internal_resize( size_t nNewCapacity )
 377         {
 378             // All locks are already locked!
 379             m_MutexPolicy.resize( nNewCapacity );
 380
 381             size_t nOldCapacity = bucket_count();
 382             bucket_type * pOldBuckets = m_Buckets;
 383
 384             alloc_bucket_table( nNewCapacity );
 385
 386             typedef typename bucket_type::iterator bucket_iterator;
 387             bucket_type * pEnd = pOldBuckets + nOldCapacity;
 388             for ( bucket_type * pCur = pOldBuckets; pCur != pEnd; ++pCur ) {
 389                 bucket_iterator itEnd = pCur->end();
 390                 bucket_iterator itNext;
 391                 for ( bucket_iterator it = pCur->begin(); it != itEnd; it = itNext ) {
 392                     itNext = it;
 393                     ++itNext;
 394                     bucket( m_Hash( *it ) )->move_item( *pCur, it );
 395                 }
 396                 pCur->clear();
 397             }
 398
 399             free_bucket_table( pOldBuckets, nOldCapacity );
 400
 401             m_ResizingPolicy.reset();
 402         }
 403
 404         void resize()
 405         {
 406             size_t nOldCapacity = bucket_count();
 407             size_t volatile& refBucketMask = m_nBucketMask;
 408
 409             scoped_resize_lock al( m_MutexPolicy );
 410             if ( al.success() ) {
 411                 if ( nOldCapacity != refBucketMask + 1 ) {
 412                     // someone resized already
 413                     return;
 414                 }
 415
 416                 internal_resize( nOldCapacity * 2 );
 417             }
 418         }
 419
 420         //@endcond
 421
 422     public:
 423         /// Default ctor. The initial capacity is 16.
 424         StripedSet()
 425             : m_Buckets( nullptr )
 426         , m_nBucketMask( c_nMinimalCapacity - 1 )
 427         , m_MutexPolicy( c_nMinimalCapacity )
 428         {
 429             alloc_bucket_table( m_nBucketMask + 1 );
 430         }
 431
 432         /// Ctor with initial capacity specified
 433         StripedSet(
 434             size_t nCapacity    ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
 435         )
 436         : m_Buckets( nullptr )
 437         , m_nBucketMask( calc_init_capacity(nCapacity) - 1 )
 438         , m_MutexPolicy( m_nBucketMask + 1 )
 439         {
 440             alloc_bucket_table( m_nBucketMask + 1 );
 441         }
 442
 443         /// Ctor with resizing policy (copy semantics)
 444         /**
 445             This constructor initializes m_ResizingPolicy member with copy of \p resizingPolicy parameter
 446         */
 447         StripedSet(
 448             size_t nCapacity    ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
 449             ,resizing_policy const& resizingPolicy  ///< Resizing policy
 450         )
 451         : m_Buckets( nullptr )
 452         , m_nBucketMask( ( nCapacity ? calc_init_capacity(nCapacity) : c_nMinimalCapacity ) - 1 )
 453         , m_MutexPolicy( m_nBucketMask + 1 )
 454         , m_ResizingPolicy( resizingPolicy )
 455         {
 456             alloc_bucket_table( m_nBucketMask + 1 );
 457         }
 458
 459 #ifdef CDS_RVALUE_SUPPORT
 460         /// Ctor with resizing policy (move semantics)
 461         /**
 462             This constructor initializes m_ResizingPolicy member moving \p resizingPolicy parameter
 463             Move semantics is used. Available only for the compilers that supports C++11 rvalue reference.
 464         */
 465         StripedSet(
 466             size_t nCapacity    ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
 467             ,resizing_policy&& resizingPolicy  ///< Resizing policy
 468         )
 469         : m_Buckets( nullptr )
 470         , m_nBucketMask( ( nCapacity ? calc_init_capacity(nCapacity) : c_nMinimalCapacity ) - 1 )
 471         , m_MutexPolicy( m_nBucketMask + 1 )
 472         , m_ResizingPolicy( resizingPolicy )
 473         {
 474             alloc_bucket_table( m_nBucketMask + 1 );
 475         }
 476 #endif
 477
 478         /// Destructor destroys internal data
 479         ~StripedSet()
 480         {
 481             free_bucket_table( m_Buckets, m_nBucketMask + 1 );
 482         }
 483
 484     public:
 485         /// Inserts new node
 486         /**
 487             The function inserts \p val in the set if it does not contain
 488             an item with key equal to \p val.
 489
 490             Returns \p true if \p val is placed into the set, \p false otherwise.
 491         */
 492         bool insert( value_type& val )
 493         {
 494 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 495             return insert( val, []( value_type& ) {} );
 496 #       else
 497             return insert( val, empty_insert_functor() );
 498 #       endif
 499         }
 500
 501         /// Inserts new node
 502         /**
 503             The function allows to split creating of new item into two part:
 504             - create item with key only
 505             - insert new item into the set
 506             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 507
 508             The functor signature is:
 509             \code
 510                 void func( value_type& val );
 511             \endcode
 512             where \p val is the item inserted.
 513
 514             The user-defined functor is called only if the inserting is success and can be passed by reference
 515             using <tt>boost::ref</tt>
 516         */
 517         template <typename Func>
 518         bool insert( value_type& val, Func f )
 519         {
 520             bool bOk;
 521             bool bResize;
 522             size_t nHash = hashing( val );
 523             bucket_type * pBucket;
 524             {
 525                 scoped_cell_lock sl( m_MutexPolicy, nHash );
 526                 pBucket = bucket( nHash );
 527                 bOk = pBucket->insert( val, f );
 528                 bResize = bOk && m_ResizingPolicy( ++m_ItemCounter, *this, *pBucket );
 529             }
 530
 531             if ( bResize )
 532                 resize();
 533             return bOk;
 534         }
 535
 536         /// Ensures that the \p val exists in the set
 537         /**
 538             The operation performs inserting or changing data with lock-free manner.
 539
 540             If the item \p val not found in the set, then \p val is inserted into the set.
 541             Otherwise, the functor \p func is called with item found.
 542             The functor signature is:
 543             \code
 544                 void func( bool bNew, value_type& item, value_type& val );
 545             \endcode
 546             with arguments:
 547             - \p bNew - \p true if the item has been inserted, \p false otherwise
 548             - \p item - item of the set
 549             - \p val - argument \p val passed into the \p ensure function
 550             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 551             refers to the same thing.
 552
 553             The functor may change non-key fields of the \p item.
 554
 555             You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
 556
 557             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
 558             \p second is \p true if new item has been added or \p false if the item with \p key
 559             already is in the set.
 560         */
 561         template <typename Func>
 562         std::pair<bool, bool> ensure( value_type& val, Func func )
 563         {
 564             std::pair<bool, bool> result;
 565             bool bResize;
 566             size_t nHash = hashing( val );
 567             bucket_type * pBucket;
 568             {
 569                 scoped_cell_lock sl( m_MutexPolicy, nHash );
 570                 pBucket = bucket( nHash );
 571
 572                 result = pBucket->ensure( val, func );
 573                 bResize = result.first && result.second && m_ResizingPolicy( ++m_ItemCounter, *this, *pBucket );
 574             }
 575
 576             if ( bResize )
 577                 resize();
 578             return result;
 579         }
 580
 581         /// Unlink the item \p val from the set
 582         /**
 583             The function searches the item \p val in the set and unlink it
 584             if it is found and is equal to \p val (here, the equality means that
 585             \p val belongs to the set: if \p item is an item found then
 586             unlink is successful iif <tt>&val == &item</tt>)
 587
 588             The function returns \p true if success and \p false otherwise.
 589         */
 590         bool unlink( value_type& val )
 591         {
 592             bool bOk;
 593             size_t nHash = hashing( val );
 594             {
 595                 scoped_cell_lock sl( m_MutexPolicy, nHash );
 596                 bOk = bucket( nHash )->unlink( val );
 597             }
 598
 599             if ( bOk )
 600                 --m_ItemCounter;
 601             return bOk;
 602         }
 603
 604         /// Deletes the item from the set
 605         /** \anchor cds_intrusive_StripedSet_erase
 606             The function searches an item with key equal to \p val in the set,
 607             unlinks it from the set, and returns a pointer to unlinked item.
 608
 609             If the item with key equal to \p val is not found the function return \p nullptr.
 610
 611             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 612         */
 613         template <typename Q>
 614         value_type * erase( Q const& val )
 615         {
 616 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 617             return erase( val, [](value_type const&) {} );
 618 #       else
 619             return erase( val, empty_erase_functor() );
 620 #       endif
 621         }
 622
 623         /// Deletes the item from the set using \p pred predicate for searching
 624         /**
 625             The function is an analog of \ref cds_intrusive_StripedSet_erase "erase(Q const&)"
 626             but \p pred is used for key comparing
 627             \p Less has the interface like \p std::less.
 628             \p pred must imply the same element order as the comparator used for building the set.
 629         */
 630         template <typename Q, typename Less>
 631         value_type * erase_with( Q const& val, Less pred )
 632         {
 633 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 634             return erase_with( val, pred, [](value_type const&) {} );
 635 #       else
 636             return erase_with( val, pred, empty_erase_functor() );
 637 #       endif
 638         }
 639
 640         /// Deletes the item from the set
 641         /** \anchor cds_intrusive_StripedSet_erase_func
 642
 643             The function searches an item with key equal to \p val in the set,
 644             call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
 645
 646             The \p Func interface is
 647             \code
 648             struct functor {
 649                 void operator()( value_type const& item );
 650             };
 651             \endcode
 652             The functor may be passed by reference with <tt>boost:ref</tt>
 653
 654             If the item with key equal to \p val is not found the function return \p false.
 655
 656             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 657         */
 658         template <typename Q, typename Func>
 659         value_type * erase( Q const& val, Func f )
 660         {
 661             size_t nHash = hashing( val );
 662             value_type * pVal;
 663             {
 664                 scoped_cell_lock sl( m_MutexPolicy, nHash );
 665                 pVal = bucket( nHash )->erase( val, f );
 666             }
 667
 668             if ( pVal )
 669                 --m_ItemCounter;
 670             return pVal;
 671         }
 672
 673         /// Deletes the item from the set using \p pred predicate for searching
 674         /**
 675             The function is an analog of \ref cds_intrusive_StripedSet_erase_func "erase(Q const&, Func)"
 676             but \p pred is used for key comparing
 677             \p Less has the interface like \p std::less.
 678             \p pred must imply the same element order as the comparator used for building the set.
 679         */
 680         template <typename Q, typename Less, typename Func>
 681         value_type * erase_with( Q const& val, Less pred, Func f )
 682         {
 683             size_t nHash = hashing( val );
 684             value_type * pVal;
 685             {
 686                 scoped_cell_lock sl( m_MutexPolicy, nHash );
 687                 pVal = bucket( nHash )->erase( val, pred, f );
 688             }
 689
 690             if ( pVal )
 691                 --m_ItemCounter;
 692             return pVal;
 693         }
 694
 695         /// Find the key \p val
 696         /** \anchor cds_intrusive_StripedSet_find_func
 697             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 698             The interface of \p Func functor is:
 699             \code
 700             struct functor {
 701                 void operator()( value_type& item, Q& val );
 702             };
 703             \endcode
 704             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 705
 706             You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 707
 708             The functor may change non-key fields of \p item.
 709
 710             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 711             may modify both arguments.
 712
 713             Note the hash functor specified for class \p Traits template parameter
 714             should accept a parameter of type \p Q that can be not the same as \p value_type.
 715
 716             The function returns \p true if \p val is found, \p false otherwise.
 717         */
 718         template <typename Q, typename Func>
 719         bool find( Q& val, Func f )
 720         {
 721             return find_( val, f );
 722         }
 723
 724         /// Find the key \p val using \p pred predicate
 725         /**
 726             The function is an analog of \ref cds_intrusive_StripedSet_find_func "find(Q&, Func)"
 727             but \p pred is used for key comparing
 728             \p Less has the interface like \p std::less.
 729             \p pred must imply the same element order as the comparator used for building the set.
 730         */
 731         template <typename Q, typename Less, typename Func>
 732         bool find_with( Q& val, Less pred, Func f )
 733         {
 734             return find_with_( val, pred, f );
 735         }
 736
 737         /// Find the key \p val
 738         /** \anchor cds_intrusive_StripedSet_find_cfunc
 739             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 740             The interface of \p Func functor is:
 741             \code
 742             struct functor {
 743                 void operator()( value_type& item, Q const& val );
 744             };
 745             \endcode
 746             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 747
 748             You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 749
 750             The functor may change non-key fields of \p item.
 751
 752             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 753             may modify both arguments.
 754
 755             The function returns \p true if \p val is found, \p false otherwise.
 756         */
 757         template <typename Q, typename Func>
 758         bool find( Q const& val, Func f )
 759         {
 760             return find_( val, f );
 761         }
 762
 763         /// Find the key \p val using \p pred predicate
 764         /**
 765             The function is an analog of \ref cds_intrusive_StripedSet_find_cfunc "find(Q const&, Func)"
 766             but \p pred is used for key comparing
 767             \p Less has the interface like \p std::less.
 768             \p pred must imply the same element order as the comparator used for building the set.
 769         */
 770         template <typename Q, typename Less, typename Func>
 771         bool find_with( Q const& val, Less pred, Func f )
 772         {
 773             return find_with_( val, pred, f );
 774         }
 775
 776         /// Find the key \p val
 777         /** \anchor cds_intrusive_StripedSet_find_val
 778             The function searches the item with key equal to \p val
 779             and returns \p true if it is found, and \p false otherwise.
 780
 781             Note the hash functor specified for class \p Traits template parameter
 782             should accept a parameter of type \p Q that can be not the same as \p value_type.
 783         */
 784         template <typename Q>
 785         bool find( Q const& val )
 786         {
 787 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 788             return find( val, [](value_type&, Q const& ) {} );
 789 #       else
 790             return find( val, empty_find_functor() );
 791 #       endif
 792         }
 793
 794         /// Find the key \p val using \p pred predicate
 795         /**
 796             The function is an analog of \ref cds_intrusive_StripedSet_find_val "find(Q const&)"
 797             but \p pred is used for key comparing
 798             \p Less has the interface like \p std::less.
 799             \p pred must imply the same element order as the comparator used for building the set.
 800         */
 801         template <typename Q, typename Less>
 802         bool find_with( Q const& val, Less pred )
 803         {
 804 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 805             return find_with( val, pred, [](value_type& , Q const& ) {} );
 806 #       else
 807             return find_with( val, pred, empty_find_functor() );
 808 #       endif
 809         }
 810
 811         /// Clears the set
 812         /**
 813             The function unlinks all items from the set.
 814         */
 815         void clear()
 816         {
 817             // locks entire array
 818             scoped_full_lock sl( m_MutexPolicy );
 819
 820             size_t nBucketCount = bucket_count();
 821             bucket_type * pBucket = m_Buckets;
 822             for ( size_t i = 0; i < nBucketCount; ++i, ++pBucket )
 823                 pBucket->clear();
 824             m_ItemCounter.reset();
 825         }
 826
 827         /// Clears the set and calls \p disposer for each item
 828         /**
 829             The function unlinks all items from the set calling \p disposer for each item.
 830             \p Disposer functor interface is:
 831             \code
 832             struct Disposer{
 833                 void operator()( value_type * p );
 834             };
 835             \endcode
 836         */
 837         template <typename Disposer>
 838         void clear_and_dispose( Disposer disposer )
 839         {
 840             // locks entire array
 841             scoped_full_lock sl( m_MutexPolicy );
 842
 843             size_t nBucketCount = bucket_count();
 844             bucket_type * pBucket = m_Buckets;
 845             for ( size_t i = 0; i < nBucketCount; ++i, ++pBucket )
 846                 pBucket->clear( disposer );
 847             m_ItemCounter.reset();
 848         }
 849
 850         /// Checks if the set is empty
 851         /**
 852             Emptiness is checked by item counting: if item count is zero then the set is empty.
 853         */
 854         bool empty() const
 855         {
 856             return size() == 0;
 857         }
 858
 859         /// Returns item count in the set
 860         size_t size() const
 861         {
 862             return m_ItemCounter;
 863         }
 864
 865         /// Returns the size of hash table
 866         /**
 867             The hash table size is non-constant and can be increased via resizing.
 868         */
 869         size_t bucket_count() const
 870         {
 871             return m_nBucketMask + 1;
 872         }
 873
 874         /// Returns lock array size
 875         size_t lock_count() const
 876         {
 877             return m_MutexPolicy.lock_count();
 878         }
 879
 880         /// Returns resizing policy object
 881         resizing_policy& get_resizing_policy()
 882         {
 883             return m_ResizingPolicy;
 884         }
 885
 886         /// Returns resizing policy (const version)
 887         resizing_policy const& get_resizing_policy() const
 888         {
 889             return m_ResizingPolicy;
 890         }
 891     };
 892 }}  // namespace cds::itrusive
 893
 894 #endif // #ifndef __CDS_INTRUSIVE_STRIPED_SET_H