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     protected:
 300         bucket_type *   m_Buckets       ;   ///< Bucket table
 301         size_t          m_nBucketMask   ;   ///< Bucket table size - 1. m_nBucketMask + 1 should be power of two.
 302         item_counter    m_ItemCounter   ;   ///< Item counter
 303         hash            m_Hash          ;   ///< Hash functor
 304
 305         mutex_policy    m_MutexPolicy   ;   ///< Mutex policy
 306         resizing_policy m_ResizingPolicy;   ///< Resizing policy
 307
 308         static const size_t c_nMinimalCapacity = 16 ;   ///< Minimal capacity
 309
 310     protected:
 311         //@cond
 312         typedef typename mutex_policy::scoped_cell_lock     scoped_cell_lock;
 313         typedef typename mutex_policy::scoped_full_lock     scoped_full_lock;
 314         typedef typename mutex_policy::scoped_resize_lock   scoped_resize_lock;
 315         //@endcond
 316
 317     protected:
 318         //@cond
 319         static size_t calc_init_capacity( size_t nCapacity )
 320         {
 321             nCapacity = cds::beans::ceil2( nCapacity );
 322             return nCapacity < c_nMinimalCapacity ? c_nMinimalCapacity : nCapacity;
 323         }
 324
 325         void alloc_bucket_table( size_t nSize )
 326         {
 327             assert( cds::beans::is_power2( nSize ));
 328             m_nBucketMask = nSize - 1;
 329             m_Buckets = bucket_allocator().NewArray( nSize );
 330         }
 331
 332         static void free_bucket_table( bucket_type * pBuckets, size_t nSize )
 333         {
 334             bucket_allocator().Delete( pBuckets, nSize );
 335         }
 336
 337         template <typename Q>
 338         size_t hashing( Q const& v ) const
 339         {
 340             return m_Hash( v );
 341         }
 342
 343         bucket_type * bucket( size_t nHash ) const CDS_NOEXCEPT
 344         {
 345             return m_Buckets + (nHash & m_nBucketMask);
 346         }
 347
 348         template <typename Q, typename Func>
 349         bool find_( Q& val, Func f )
 350         {
 351             size_t nHash = hashing( val );
 352
 353             scoped_cell_lock sl( m_MutexPolicy, nHash );
 354             return bucket( nHash )->find( val, f );
 355         }
 356
 357         template <typename Q, typename Less, typename Func>
 358         bool find_with_( Q& val, Less pred, Func f )
 359         {
 360             size_t nHash = hashing( val );
 361             scoped_cell_lock sl( m_MutexPolicy, nHash );
 362             return bucket( nHash )->find( val, pred, f );
 363         }
 364
 365         void internal_resize( size_t nNewCapacity )
 366         {
 367             // All locks are already locked!
 368             m_MutexPolicy.resize( nNewCapacity );
 369
 370             size_t nOldCapacity = bucket_count();
 371             bucket_type * pOldBuckets = m_Buckets;
 372
 373             alloc_bucket_table( nNewCapacity );
 374
 375             typedef typename bucket_type::iterator bucket_iterator;
 376             bucket_type * pEnd = pOldBuckets + nOldCapacity;
 377             for ( bucket_type * pCur = pOldBuckets; pCur != pEnd; ++pCur ) {
 378                 bucket_iterator itEnd = pCur->end();
 379                 bucket_iterator itNext;
 380                 for ( bucket_iterator it = pCur->begin(); it != itEnd; it = itNext ) {
 381                     itNext = it;
 382                     ++itNext;
 383                     bucket( m_Hash( *it ) )->move_item( *pCur, it );
 384                 }
 385                 pCur->clear();
 386             }
 387
 388             free_bucket_table( pOldBuckets, nOldCapacity );
 389
 390             m_ResizingPolicy.reset();
 391         }
 392
 393         void resize()
 394         {
 395             size_t nOldCapacity = bucket_count();
 396             size_t volatile& refBucketMask = m_nBucketMask;
 397
 398             scoped_resize_lock al( m_MutexPolicy );
 399             if ( al.success() ) {
 400                 if ( nOldCapacity != refBucketMask + 1 ) {
 401                     // someone resized already
 402                     return;
 403                 }
 404
 405                 internal_resize( nOldCapacity * 2 );
 406             }
 407         }
 408
 409         //@endcond
 410
 411     public:
 412         /// Default ctor. The initial capacity is 16.
 413         StripedSet()
 414             : m_Buckets( nullptr )
 415         , m_nBucketMask( c_nMinimalCapacity - 1 )
 416         , m_MutexPolicy( c_nMinimalCapacity )
 417         {
 418             alloc_bucket_table( m_nBucketMask + 1 );
 419         }
 420
 421         /// Ctor with initial capacity specified
 422         StripedSet(
 423             size_t nCapacity    ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
 424         )
 425         : m_Buckets( nullptr )
 426         , m_nBucketMask( calc_init_capacity(nCapacity) - 1 )
 427         , m_MutexPolicy( m_nBucketMask + 1 )
 428         {
 429             alloc_bucket_table( m_nBucketMask + 1 );
 430         }
 431
 432         /// Ctor with resizing policy (copy semantics)
 433         /**
 434             This constructor initializes m_ResizingPolicy member with copy of \p resizingPolicy parameter
 435         */
 436         StripedSet(
 437             size_t nCapacity    ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
 438             ,resizing_policy const& resizingPolicy  ///< Resizing policy
 439         )
 440         : m_Buckets( nullptr )
 441         , m_nBucketMask( ( nCapacity ? calc_init_capacity(nCapacity) : c_nMinimalCapacity ) - 1 )
 442         , m_MutexPolicy( m_nBucketMask + 1 )
 443         , m_ResizingPolicy( resizingPolicy )
 444         {
 445             alloc_bucket_table( m_nBucketMask + 1 );
 446         }
 447
 448         /// Ctor with resizing policy (move semantics)
 449         /**
 450             This constructor initializes m_ResizingPolicy member moving \p resizingPolicy parameter
 451             Move semantics is used.
 452         */
 453         StripedSet(
 454             size_t nCapacity    ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
 455             ,resizing_policy&& resizingPolicy  ///< Resizing policy
 456         )
 457         : m_Buckets( nullptr )
 458         , m_nBucketMask( ( nCapacity ? calc_init_capacity(nCapacity) : c_nMinimalCapacity ) - 1 )
 459         , m_MutexPolicy( m_nBucketMask + 1 )
 460         , m_ResizingPolicy( std::forward<resizing_policy>( resizingPolicy ) )
 461         {
 462             alloc_bucket_table( m_nBucketMask + 1 );
 463         }
 464
 465         /// Destructor destroys internal data
 466         ~StripedSet()
 467         {
 468             free_bucket_table( m_Buckets, m_nBucketMask + 1 );
 469         }
 470
 471     public:
 472         /// Inserts new node
 473         /**
 474             The function inserts \p val in the set if it does not contain
 475             an item with key equal to \p val.
 476
 477             Returns \p true if \p val is placed into the set, \p false otherwise.
 478         */
 479         bool insert( value_type& val )
 480         {
 481             return insert( val, []( value_type& ) {} );
 482         }
 483
 484         /// Inserts new node
 485         /**
 486             The function allows to split creating of new item into two part:
 487             - create item with key only
 488             - insert new item into the set
 489             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 490
 491             The functor signature is:
 492             \code
 493                 void func( value_type& val );
 494             \endcode
 495             where \p val is the item inserted.
 496         */
 497         template <typename Func>
 498         bool insert( value_type& val, Func f )
 499         {
 500             bool bOk;
 501             bool bResize;
 502             size_t nHash = hashing( val );
 503             bucket_type * pBucket;
 504             {
 505                 scoped_cell_lock sl( m_MutexPolicy, nHash );
 506                 pBucket = bucket( nHash );
 507                 bOk = pBucket->insert( val, f );
 508                 bResize = bOk && m_ResizingPolicy( ++m_ItemCounter, *this, *pBucket );
 509             }
 510
 511             if ( bResize )
 512                 resize();
 513             return bOk;
 514         }
 515
 516         /// Ensures that the \p val exists in the set
 517         /**
 518             The operation performs inserting or changing data with lock-free manner.
 519
 520             If the item \p val not found in the set, then \p val is inserted into the set.
 521             Otherwise, the functor \p func is called with item found.
 522             The functor signature is:
 523             \code
 524                 void func( bool bNew, value_type& item, value_type& val );
 525             \endcode
 526             with arguments:
 527             - \p bNew - \p true if the item has been inserted, \p false otherwise
 528             - \p item - item of the set
 529             - \p val - argument \p val passed into the \p ensure function
 530             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 531             refers to the same thing.
 532
 533             The functor may change non-key fields of the \p item.
 534
 535             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
 536             \p second is \p true if new item has been added or \p false if the item with \p key
 537             already is in the set.
 538         */
 539         template <typename Func>
 540         std::pair<bool, bool> ensure( value_type& val, Func func )
 541         {
 542             std::pair<bool, bool> result;
 543             bool bResize;
 544             size_t nHash = hashing( val );
 545             bucket_type * pBucket;
 546             {
 547                 scoped_cell_lock sl( m_MutexPolicy, nHash );
 548                 pBucket = bucket( nHash );
 549
 550                 result = pBucket->ensure( val, func );
 551                 bResize = result.first && result.second && m_ResizingPolicy( ++m_ItemCounter, *this, *pBucket );
 552             }
 553
 554             if ( bResize )
 555                 resize();
 556             return result;
 557         }
 558
 559         /// Unlink the item \p val from the set
 560         /**
 561             The function searches the item \p val in the set and unlink it
 562             if it is found and is equal to \p val (here, the equality means that
 563             \p val belongs to the set: if \p item is an item found then
 564             unlink is successful iif <tt>&val == &item</tt>)
 565
 566             The function returns \p true if success and \p false otherwise.
 567         */
 568         bool unlink( value_type& val )
 569         {
 570             bool bOk;
 571             size_t nHash = hashing( val );
 572             {
 573                 scoped_cell_lock sl( m_MutexPolicy, nHash );
 574                 bOk = bucket( nHash )->unlink( val );
 575             }
 576
 577             if ( bOk )
 578                 --m_ItemCounter;
 579             return bOk;
 580         }
 581
 582         /// Deletes the item from the set
 583         /** \anchor cds_intrusive_StripedSet_erase
 584             The function searches an item with key equal to \p val in the set,
 585             unlinks it from the set, and returns a pointer to unlinked item.
 586
 587             If the item with key equal to \p val is not found the function return \p nullptr.
 588
 589             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 590         */
 591         template <typename Q>
 592         value_type * erase( Q const& val )
 593         {
 594             return erase( val, [](value_type const&) {} );
 595         }
 596
 597         /// Deletes the item from the set using \p pred predicate for searching
 598         /**
 599             The function is an analog of \ref cds_intrusive_StripedSet_erase "erase(Q const&)"
 600             but \p pred is used for key comparing
 601             \p Less has the interface like \p std::less.
 602             \p pred must imply the same element order as the comparator used for building the set.
 603         */
 604         template <typename Q, typename Less>
 605         value_type * erase_with( Q const& val, Less pred )
 606         {
 607             return erase_with( val, pred, [](value_type const&) {} );
 608         }
 609
 610         /// Deletes the item from the set
 611         /** \anchor cds_intrusive_StripedSet_erase_func
 612
 613             The function searches an item with key equal to \p val in the set,
 614             call \p f functor with item found, unlinks it from the set, and returns a pointer to unlinked item.
 615
 616             The \p Func interface is
 617             \code
 618             struct functor {
 619                 void operator()( value_type const& item );
 620             };
 621             \endcode
 622
 623             If the item with key equal to \p val is not found the function return \p false.
 624
 625             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 626         */
 627         template <typename Q, typename Func>
 628         value_type * erase( Q const& val, Func f )
 629         {
 630             size_t nHash = hashing( val );
 631             value_type * pVal;
 632             {
 633                 scoped_cell_lock sl( m_MutexPolicy, nHash );
 634                 pVal = bucket( nHash )->erase( val, f );
 635             }
 636
 637             if ( pVal )
 638                 --m_ItemCounter;
 639             return pVal;
 640         }
 641
 642         /// Deletes the item from the set using \p pred predicate for searching
 643         /**
 644             The function is an analog of \ref cds_intrusive_StripedSet_erase_func "erase(Q const&, Func)"
 645             but \p pred is used for key comparing
 646             \p Less has the interface like \p std::less.
 647             \p pred must imply the same element order as the comparator used for building the set.
 648         */
 649         template <typename Q, typename Less, typename Func>
 650         value_type * erase_with( Q const& val, Less pred, Func f )
 651         {
 652             size_t nHash = hashing( val );
 653             value_type * pVal;
 654             {
 655                 scoped_cell_lock sl( m_MutexPolicy, nHash );
 656                 pVal = bucket( nHash )->erase( val, pred, f );
 657             }
 658
 659             if ( pVal )
 660                 --m_ItemCounter;
 661             return pVal;
 662         }
 663
 664         /// Find the key \p val
 665         /** \anchor cds_intrusive_StripedSet_find_func
 666             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 667             The interface of \p Func functor is:
 668             \code
 669             struct functor {
 670                 void operator()( value_type& item, Q& val );
 671             };
 672             \endcode
 673             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 674
 675             The functor may change non-key fields of \p item.
 676
 677             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 678             may modify both arguments.
 679
 680             Note the hash functor specified for class \p Traits template parameter
 681             should accept a parameter of type \p Q that can be not the same as \p value_type.
 682
 683             The function returns \p true if \p val is found, \p false otherwise.
 684         */
 685         template <typename Q, typename Func>
 686         bool find( Q& val, Func f )
 687         {
 688             return find_( val, f );
 689         }
 690
 691         /// Find the key \p val using \p pred predicate
 692         /**
 693             The function is an analog of \ref cds_intrusive_StripedSet_find_func "find(Q&, Func)"
 694             but \p pred is used for key comparing
 695             \p Less has the interface like \p std::less.
 696             \p pred must imply the same element order as the comparator used for building the set.
 697         */
 698         template <typename Q, typename Less, typename Func>
 699         bool find_with( Q& val, Less pred, Func f )
 700         {
 701             return find_with_( val, pred, f );
 702         }
 703
 704         /// Find the key \p val
 705         /** \anchor cds_intrusive_StripedSet_find_cfunc
 706             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 707             The interface of \p Func functor is:
 708             \code
 709             struct functor {
 710                 void operator()( value_type& item, Q const& val );
 711             };
 712             \endcode
 713             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 714
 715             The functor may change non-key fields of \p item.
 716
 717             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 718             may modify both arguments.
 719
 720             The function returns \p true if \p val is found, \p false otherwise.
 721         */
 722         template <typename Q, typename Func>
 723         bool find( Q const& val, Func f )
 724         {
 725             return find_( val, f );
 726         }
 727
 728         /// Find the key \p val using \p pred predicate
 729         /**
 730             The function is an analog of \ref cds_intrusive_StripedSet_find_cfunc "find(Q const&, Func)"
 731             but \p pred is used for key comparing
 732             \p Less has the interface like \p std::less.
 733             \p pred must imply the same element order as the comparator used for building the set.
 734         */
 735         template <typename Q, typename Less, typename Func>
 736         bool find_with( Q const& val, Less pred, Func f )
 737         {
 738             return find_with_( val, pred, f );
 739         }
 740
 741         /// Find the key \p val
 742         /** \anchor cds_intrusive_StripedSet_find_val
 743             The function searches the item with key equal to \p val
 744             and returns \p true if it is found, and \p false otherwise.
 745
 746             Note the hash functor specified for class \p Traits template parameter
 747             should accept a parameter of type \p Q that can be not the same as \p value_type.
 748         */
 749         template <typename Q>
 750         bool find( Q const& val )
 751         {
 752             return find( val, [](value_type&, Q const& ) {} );
 753         }
 754
 755         /// Find the key \p val using \p pred predicate
 756         /**
 757             The function is an analog of \ref cds_intrusive_StripedSet_find_val "find(Q const&)"
 758             but \p pred is used for key comparing
 759             \p Less has the interface like \p std::less.
 760             \p pred must imply the same element order as the comparator used for building the set.
 761         */
 762         template <typename Q, typename Less>
 763         bool find_with( Q const& val, Less pred )
 764         {
 765             return find_with( val, pred, [](value_type& , Q const& ) {} );
 766         }
 767
 768         /// Clears the set
 769         /**
 770             The function unlinks all items from the set.
 771         */
 772         void clear()
 773         {
 774             // locks entire array
 775             scoped_full_lock sl( m_MutexPolicy );
 776
 777             size_t nBucketCount = bucket_count();
 778             bucket_type * pBucket = m_Buckets;
 779             for ( size_t i = 0; i < nBucketCount; ++i, ++pBucket )
 780                 pBucket->clear();
 781             m_ItemCounter.reset();
 782         }
 783
 784         /// Clears the set and calls \p disposer for each item
 785         /**
 786             The function unlinks all items from the set calling \p disposer for each item.
 787             \p Disposer functor interface is:
 788             \code
 789             struct Disposer{
 790                 void operator()( value_type * p );
 791             };
 792             \endcode
 793         */
 794         template <typename Disposer>
 795         void clear_and_dispose( Disposer disposer )
 796         {
 797             // locks entire array
 798             scoped_full_lock sl( m_MutexPolicy );
 799
 800             size_t nBucketCount = bucket_count();
 801             bucket_type * pBucket = m_Buckets;
 802             for ( size_t i = 0; i < nBucketCount; ++i, ++pBucket )
 803                 pBucket->clear( disposer );
 804             m_ItemCounter.reset();
 805         }
 806
 807         /// Checks if the set is empty
 808         /**
 809             Emptiness is checked by item counting: if item count is zero then the set is empty.
 810         */
 811         bool empty() const
 812         {
 813             return size() == 0;
 814         }
 815
 816         /// Returns item count in the set
 817         size_t size() const
 818         {
 819             return m_ItemCounter;
 820         }
 821
 822         /// Returns the size of hash table
 823         /**
 824             The hash table size is non-constant and can be increased via resizing.
 825         */
 826         size_t bucket_count() const
 827         {
 828             return m_nBucketMask + 1;
 829         }
 830
 831         /// Returns lock array size
 832         size_t lock_count() const
 833         {
 834             return m_MutexPolicy.lock_count();
 835         }
 836
 837         /// Returns resizing policy object
 838         resizing_policy& get_resizing_policy()
 839         {
 840             return m_ResizingPolicy;
 841         }
 842
 843         /// Returns resizing policy (const version)
 844         resizing_policy const& get_resizing_policy() const
 845         {
 846             return m_ResizingPolicy;
 847         }
 848     };
 849 }}  // namespace cds::itrusive
 850
 851 #endif // #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_H