cds/container/striped_set.h

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