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 #ifdef CDS_RVALUE_SUPPORT
 605         /// Ctor with resizing policy (move semantics)
 606         /**
 607             This constructor initializes m_ResizingPolicy member moving \p resizingPolicy parameter
 608             Move semantics is used. Available only for the compilers that supports C++11 rvalue reference.
 609         */
 610         StripedMap(
 611             size_t nCapacity    ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
 612             ,resizing_policy&& resizingPolicy  ///< Resizing policy
 613             ) : base_class( nCapacity, std::forward<resizing_policy>(resizingPolicy) )
 614         {}
 615 #endif
 616
 617         /// Destructor destroys internal data
 618         ~StripedMap()
 619         {}
 620
 621     public:
 622         /// Inserts new node with key and default value
 623         /**
 624             The function creates a node with \p key and default value, and then inserts the node created into the map.
 625
 626             Preconditions:
 627             - The \ref key_type should be constructible from a value of type \p K.
 628                 In trivial case, \p K is equal to \ref key_type.
 629             - The \ref mapped_type should be default-constructible.
 630
 631             Returns \p true if inserting successful, \p false otherwise.
 632         */
 633         template <typename K>
 634         bool insert( K const& key )
 635         {
 636 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 637             return insert_key( key, [](value_type&){} );
 638 #       else
 639             return insert_key( key, dummy_insert_functor() );
 640 #       endif
 641         }
 642
 643         /// Inserts new node
 644         /**
 645             The function creates a node with copy of \p val value
 646             and then inserts the node created into the map.
 647
 648             Preconditions:
 649             - The \ref key_type should be constructible from \p key of type \p K.
 650             - The \ref mapped_type should be constructible from \p val of type \p V.
 651
 652             Returns \p true if \p val is inserted into the set, \p false otherwise.
 653         */
 654         template <typename K, typename V>
 655         bool insert( K const& key, V const& val )
 656         {
 657 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 658             return insert_key( key, [&val](value_type& item) { item.second = val ; } );
 659 #       else
 660             insert_value_functor<V> f(val);
 661             return insert_key( key, cds::ref(f) );
 662 #       endif
 663         }
 664
 665         /// Inserts new node and initialize it by a functor
 666         /**
 667             This function inserts new node with key \p key and if inserting is successful then it calls
 668             \p func functor with signature
 669             \code
 670                 struct functor {
 671                     void operator()( value_type& item );
 672                 };
 673             \endcode
 674
 675             The argument \p item of user-defined functor \p func is the reference
 676             to the map's item inserted:
 677                 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
 678                 - <tt>item.second</tt> is a reference to item's value that may be changed.
 679
 680             The user-defined functor can be passed by reference using <tt>boost::ref</tt>
 681             and it is called only if inserting is successful.
 682
 683             The key_type should be constructible from value of type \p K.
 684
 685             The function allows to split creating of new item into two part:
 686             - create item from \p key;
 687             - insert new item into the map;
 688             - if inserting is successful, initialize the value of item by calling \p func functor
 689
 690             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 691             it is preferable that the initialization should be completed only if inserting is successful.
 692         */
 693         template <typename K, typename Func>
 694         bool insert_key( const K& key, Func func )
 695         {
 696             return base_class::insert( key, func );
 697         }
 698
 699 #   ifdef CDS_EMPLACE_SUPPORT
 700         /// For key \p key inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
 701         /**
 702             Returns \p true if inserting successful, \p false otherwise.
 703
 704             This function is available only for compiler that supports
 705             variadic template and move semantics
 706         */
 707         template <typename K, typename... Args>
 708         bool emplace( K&& key, Args&&... args )
 709         {
 710             bool bOk;
 711             bool bResize;
 712             size_t nHash = base_class::hashing( std::forward<K>(key));
 713             bucket_type * pBucket;
 714             {
 715                 scoped_cell_lock sl( base_class::m_MutexPolicy, nHash );
 716                 pBucket = base_class::bucket( nHash );
 717
 718                 bOk = pBucket->emplace( std::forward<K>(key), std::forward<Args>(args)...);
 719                 bResize = bOk && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
 720             }
 721
 722             if ( bResize )
 723                 base_class::resize();
 724
 725             return bOk;
 726         }
 727 #   endif
 728
 729         /// Ensures that the \p key exists in the map
 730         /**
 731             The operation performs inserting or changing data with lock-free manner.
 732
 733             If the \p key not found in the map, then the new item created from \p key
 734             is inserted into the map (note that in this case the \ref key_type should be
 735             constructible from type \p K).
 736             Otherwise, the functor \p func is called with item found.
 737             The functor \p Func may be a function with signature:
 738             \code
 739                 void func( bool bNew, value_type& item );
 740             \endcode
 741             or a functor:
 742             \code
 743                 struct my_functor {
 744                     void operator()( bool bNew, value_type& item );
 745                 };
 746             \endcode
 747
 748             with arguments:
 749             - \p bNew - \p true if the item has been inserted, \p false otherwise
 750             - \p item - item of the list
 751
 752             The functor may change any fields of the \p item.second that is \ref mapped_type.
 753
 754             You may pass \p func argument by reference using <tt>boost::ref</tt>.
 755
 756             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 757             \p second is true if new item has been added or \p false if the item with \p key
 758             already is in the list.
 759         */
 760         template <typename K, typename Func>
 761         std::pair<bool, bool> ensure( K const& key, Func func )
 762         {
 763             std::pair<bool, bool> result;
 764             bool bResize;
 765             size_t nHash = base_class::hashing( key );
 766             bucket_type * pBucket;
 767             {
 768                 scoped_cell_lock sl( base_class::m_MutexPolicy, nHash );
 769                 pBucket = base_class::bucket( nHash );
 770
 771                 result = pBucket->ensure( key, func );
 772                 bResize = result.first && result.second && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
 773             }
 774
 775             if ( bResize )
 776                 base_class::resize();
 777             return result;
 778         }
 779
 780         /// Delete \p key from the map
 781         /** \anchor cds_nonintrusive_StripedMap_erase
 782
 783             Return \p true if \p key is found and deleted, \p false otherwise
 784         */
 785         template <typename K>
 786         bool erase( K const& key )
 787         {
 788             return base_class::erase( key );
 789         }
 790
 791 #ifdef CDS_CXX11_DEFAULT_FUNCTION_TEMPLATE_ARGS_SUPPORT
 792         /// Deletes the item from the map using \p pred predicate for searching
 793         /**
 794             The function is an analog of \ref cds_nonintrusive_StripedMap_erase "erase(K const&)"
 795             but \p pred is used for key comparing.
 796             \p Less functor has the interface like \p std::less.
 797             \p pred must imply the same element order as the comparator used for building the map.
 798
 799             @note This function is enabled if the compiler supports C++11
 800             default template arguments for function template <b>and</b> the underlying container
 801             supports \p %erase_with feature.
 802         */
 803         template < typename K, typename Less
 804             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type >
 805         bool erase_with( K const& key, Less pred )
 806         {
 807 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 808             return erase_with( key, pred, [](value_type const&) {} );
 809 #       else
 810             return erase_with( key, pred, typename base_class::empty_erase_functor() );
 811 #       endif
 812         }
 813 #endif
 814
 815         /// Delete \p key from the map
 816         /** \anchor cds_nonintrusive_StripedMap_erase_func
 817
 818             The function searches an item with key \p key, calls \p f functor
 819             and deletes the item. If \p key is not found, the functor is not called.
 820
 821             The functor \p Func interface:
 822             \code
 823             struct extractor {
 824                 void operator()(value_type& item) { ... }
 825             };
 826             \endcode
 827             The functor may be passed by reference using <tt>boost:ref</tt>
 828
 829             Return \p true if key is found and deleted, \p false otherwise
 830
 831             See also: \ref erase
 832         */
 833         template <typename K, typename Func>
 834         bool erase( K const& key, Func f )
 835         {
 836             return base_class::erase( key, f );
 837         }
 838
 839 #ifdef CDS_CXX11_DEFAULT_FUNCTION_TEMPLATE_ARGS_SUPPORT
 840         /// Deletes the item from the map using \p pred predicate for searching
 841         /**
 842             The function is an analog of \ref cds_nonintrusive_StripedMap_erase_func "erase(K const&, Func)"
 843             but \p pred is used for key comparing.
 844             \p Less functor has the interface like \p std::less.
 845             \p pred must imply the same element order as the comparator used for building the map.
 846
 847             @note This function is enabled if the compiler supports C++11
 848             default template arguments for function template <b>and</b> the underlying container
 849             supports \p %erase_with feature.
 850         */
 851         template <typename K, typename Less, typename Func
 852             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type >
 853         bool erase_with( K const& key, Less pred, Func f )
 854         {
 855             return base_class::erase_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(), f );
 856         }
 857 #endif
 858
 859         /// Find the key \p key
 860         /** \anchor cds_nonintrusive_StripedMap_find_func
 861
 862             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 863             The interface of \p Func functor is:
 864             \code
 865             struct functor {
 866                 void operator()( value_type& item );
 867             };
 868             \endcode
 869             where \p item is the item found.
 870
 871             You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 872
 873             The functor may change \p item.second.
 874
 875             The function returns \p true if \p key is found, \p false otherwise.
 876         */
 877         template <typename K, typename Func>
 878         bool find( K const& key, Func f )
 879         {
 880 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 881             return base_class::find( key, [&f]( value_type& pair, K const& ) mutable { cds::unref(f)(pair); } );
 882 #       else
 883             find_functor_wrapper<Func> fw(f);
 884             return base_class::find( key, cds::ref(fw) );
 885 #       endif
 886         }
 887
 888 #ifdef CDS_CXX11_DEFAULT_FUNCTION_TEMPLATE_ARGS_SUPPORT
 889         /// Find the key \p val using \p pred predicate
 890         /**
 891             The function is an analog of \ref cds_nonintrusive_StripedMap_find_func "find(K const&, Func)"
 892             but \p pred is used for key comparing
 893             \p Less has the interface like \p std::less.
 894             \p pred must imply the same element order as the comparator used for building the set.
 895
 896             @note This function is enabled if the compiler supports C++11
 897             default template arguments for function template <b>and</b> the underlying container
 898             supports \p %find_with feature.
 899         */
 900         template <typename K, typename Less, typename Func
 901             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
 902         bool find_with( K const& key, Less pred, Func f )
 903         {
 904 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 905             return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(),
 906                 [&f]( value_type& pair, K const& ) mutable { cds::unref(f)(pair); } );
 907 #       else
 908             find_functor_wrapper<Func> fw(f);
 909             return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(), cds::ref(fw) );
 910 #       endif
 911         }
 912 #endif
 913
 914         /// Find the key \p key
 915         /** \anchor cds_nonintrusive_StripedMap_find_val
 916
 917             The function searches the item with key equal to \p key
 918             and returns \p true if it is found, and \p false otherwise.
 919         */
 920         template <typename K>
 921         bool find( K const& key )
 922         {
 923             return base_class::find( key );
 924         }
 925
 926 #ifdef CDS_CXX11_DEFAULT_FUNCTION_TEMPLATE_ARGS_SUPPORT
 927         /// Find the key \p val using \p pred predicate
 928         /**
 929             The function is an analog of \ref cds_nonintrusive_StripedMap_find_val "find(K const&)"
 930             but \p pred is used for key comparing
 931             \p Less has the interface like \p std::less.
 932             \p pred must imply the same element order as the comparator used for building the set.
 933
 934             @note This function is enabled if the compiler supports C++11
 935             default template arguments for function template <b>and</b> the underlying container
 936             supports \p %find_with feature.
 937         */
 938         template <typename K, typename Less
 939             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
 940         bool find_with( K const& key, Less pred )
 941         {
 942             return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >() );
 943         }
 944 #endif
 945
 946         /// Clears the map
 947         void clear()
 948         {
 949             base_class::clear();
 950         }
 951
 952         /// Checks if the map is empty
 953         /**
 954             Emptiness is checked by item counting: if item count is zero then the map is empty.
 955         */
 956         bool empty() const
 957         {
 958             return base_class::empty();
 959         }
 960
 961         /// Returns item count in the map
 962         size_t size() const
 963         {
 964             return base_class::size();
 965         }
 966
 967         /// Returns the size of hash table
 968         /**
 969             The hash table size is non-constant and can be increased via resizing.
 970         */
 971         size_t bucket_count() const
 972         {
 973             return base_class::bucket_count();
 974         }
 975
 976         /// Returns lock array size
 977         /**
 978             The lock array size is constant.
 979         */
 980         size_t lock_count() const
 981         {
 982             return base_class::lock_count();
 983         }
 984
 985         /// Returns resizing policy object
 986         resizing_policy& get_resizing_policy()
 987         {
 988             return base_class::get_resizing_policy();
 989         }
 990
 991         /// Returns resizing policy (const version)
 992         resizing_policy const& get_resizing_policy() const
 993         {
 994             return base_class::get_resizing_policy();
 995         }
 996     };
 997
 998 }}  // namespace cds::container
 999
1000 #endif // #ifndef __CDS_CONTAINER_STRIPED_MAP_H