cds/container/striped_map.h

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