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