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