cds/container/striped_set.h

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