cds/intrusive/striped_set.h

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