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 user-defined functor can be passed by reference using <tt>boost::ref</tt>
 626             and it is called only if inserting is successful.
 627
 628             The key_type should be constructible from value of type \p K.
 629
 630             The function allows to split creating of new item into two part:
 631             - create item from \p key;
 632             - insert new item into the map;
 633             - if inserting is successful, initialize the value of item by calling \p func functor
 634
 635             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 636             it is preferable that the initialization should be completed only if inserting is successful.
 637         */
 638         template <typename K, typename Func>
 639         bool insert_key( const K& key, Func func )
 640         {
 641             return base_class::insert( key, func );
 642         }
 643
 644         /// For key \p key inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
 645         /**
 646             Returns \p true if inserting successful, \p false otherwise.
 647         */
 648         template <typename K, typename... Args>
 649         bool emplace( K&& key, Args&&... args )
 650         {
 651             bool bOk;
 652             bool bResize;
 653             size_t nHash = base_class::hashing( std::forward<K>(key));
 654             bucket_type * pBucket;
 655             {
 656                 scoped_cell_lock sl( base_class::m_MutexPolicy, nHash );
 657                 pBucket = base_class::bucket( nHash );
 658
 659                 bOk = pBucket->emplace( std::forward<K>(key), std::forward<Args>(args)...);
 660                 bResize = bOk && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
 661             }
 662
 663             if ( bResize )
 664                 base_class::resize();
 665
 666             return bOk;
 667         }
 668
 669         /// Ensures that the \p key exists in the map
 670         /**
 671             The operation performs inserting or changing data with lock-free manner.
 672
 673             If the \p key not found in the map, then the new item created from \p key
 674             is inserted into the map (note that in this case the \ref key_type should be
 675             constructible from type \p K).
 676             Otherwise, the functor \p func is called with item found.
 677             The functor \p Func may be a function with signature:
 678             \code
 679                 void func( bool bNew, value_type& item );
 680             \endcode
 681             or a functor:
 682             \code
 683                 struct my_functor {
 684                     void operator()( bool bNew, value_type& item );
 685                 };
 686             \endcode
 687
 688             with arguments:
 689             - \p bNew - \p true if the item has been inserted, \p false otherwise
 690             - \p item - item of the list
 691
 692             The functor may change any fields of the \p item.second that is \ref mapped_type.
 693
 694             You may pass \p func argument by reference using <tt>boost::ref</tt>.
 695
 696             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 697             \p second is true if new item has been added or \p false if the item with \p key
 698             already is in the list.
 699         */
 700         template <typename K, typename Func>
 701         std::pair<bool, bool> ensure( K const& key, Func func )
 702         {
 703             std::pair<bool, bool> result;
 704             bool bResize;
 705             size_t nHash = base_class::hashing( key );
 706             bucket_type * pBucket;
 707             {
 708                 scoped_cell_lock sl( base_class::m_MutexPolicy, nHash );
 709                 pBucket = base_class::bucket( nHash );
 710
 711                 result = pBucket->ensure( key, func );
 712                 bResize = result.first && result.second && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
 713             }
 714
 715             if ( bResize )
 716                 base_class::resize();
 717             return result;
 718         }
 719
 720         /// Delete \p key from the map
 721         /** \anchor cds_nonintrusive_StripedMap_erase
 722
 723             Return \p true if \p key is found and deleted, \p false otherwise
 724         */
 725         template <typename K>
 726         bool erase( K const& key )
 727         {
 728             return base_class::erase( key );
 729         }
 730
 731         /// Deletes the item from the map using \p pred predicate for searching
 732         /**
 733             The function is an analog of \ref cds_nonintrusive_StripedMap_erase "erase(K const&)"
 734             but \p pred is used for key comparing.
 735             \p Less functor has the interface like \p std::less.
 736             \p pred must imply the same element order as the comparator used for building the map.
 737
 738             @note This function is enabled if the compiler supports C++11
 739             default template arguments for function template <b>and</b> the underlying container
 740             supports \p %erase_with feature.
 741         */
 742         template < typename K, typename Less
 743             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type >
 744         bool erase_with( K const& key, Less pred )
 745         {
 746             return erase_with( key, pred, [](value_type const&) {} );
 747         }
 748
 749         /// Delete \p key from the map
 750         /** \anchor cds_nonintrusive_StripedMap_erase_func
 751
 752             The function searches an item with key \p key, calls \p f functor
 753             and deletes the item. If \p key is not found, the functor is not called.
 754
 755             The functor \p Func interface:
 756             \code
 757             struct extractor {
 758                 void operator()(value_type& item) { ... }
 759             };
 760             \endcode
 761             The functor may be passed by reference using <tt>boost:ref</tt>
 762
 763             Return \p true if key is found and deleted, \p false otherwise
 764
 765             See also: \ref erase
 766         */
 767         template <typename K, typename Func>
 768         bool erase( K const& key, Func f )
 769         {
 770             return base_class::erase( key, f );
 771         }
 772
 773         /// Deletes the item from the map using \p pred predicate for searching
 774         /**
 775             The function is an analog of \ref cds_nonintrusive_StripedMap_erase_func "erase(K const&, Func)"
 776             but \p pred is used for key comparing.
 777             \p Less functor has the interface like \p std::less.
 778             \p pred must imply the same element order as the comparator used for building the map.
 779
 780             @note This function is enabled if the compiler supports C++11
 781             default template arguments for function template <b>and</b> the underlying container
 782             supports \p %erase_with feature.
 783         */
 784         template <typename K, typename Less, typename Func
 785             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type >
 786         bool erase_with( K const& key, Less pred, Func f )
 787         {
 788             return base_class::erase_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(), f );
 789         }
 790
 791         /// Find the key \p key
 792         /** \anchor cds_nonintrusive_StripedMap_find_func
 793
 794             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 795             The interface of \p Func functor is:
 796             \code
 797             struct functor {
 798                 void operator()( value_type& item );
 799             };
 800             \endcode
 801             where \p item is the item found.
 802
 803             You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 804
 805             The functor may change \p item.second.
 806
 807             The function returns \p true if \p key is found, \p false otherwise.
 808         */
 809         template <typename K, typename Func>
 810         bool find( K const& key, Func f )
 811         {
 812             return base_class::find( key, [&f]( value_type& pair, K const& ) mutable { cds::unref(f)(pair); } );
 813         }
 814
 815         /// Find the key \p val using \p pred predicate
 816         /**
 817             The function is an analog of \ref cds_nonintrusive_StripedMap_find_func "find(K const&, Func)"
 818             but \p pred is used for key comparing
 819             \p Less has the interface like \p std::less.
 820             \p pred must imply the same element order as the comparator used for building the set.
 821
 822             @note This function is enabled if the compiler supports C++11
 823             default template arguments for function template <b>and</b> the underlying container
 824             supports \p %find_with feature.
 825         */
 826         template <typename K, typename Less, typename Func
 827             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
 828         bool find_with( K const& key, Less pred, Func f )
 829         {
 830             return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(),
 831                 [&f]( value_type& pair, K const& ) mutable { cds::unref(f)(pair); } );
 832         }
 833
 834         /// Find the key \p key
 835         /** \anchor cds_nonintrusive_StripedMap_find_val
 836
 837             The function searches the item with key equal to \p key
 838             and returns \p true if it is found, and \p false otherwise.
 839         */
 840         template <typename K>
 841         bool find( K const& key )
 842         {
 843             return base_class::find( key );
 844         }
 845
 846         /// Find the key \p val using \p pred predicate
 847         /**
 848             The function is an analog of \ref cds_nonintrusive_StripedMap_find_val "find(K const&)"
 849             but \p pred is used for key comparing
 850             \p Less has the interface like \p std::less.
 851             \p pred must imply the same element order as the comparator used for building the set.
 852
 853             @note This function is enabled if the compiler supports C++11
 854             default template arguments for function template <b>and</b> the underlying container
 855             supports \p %find_with feature.
 856         */
 857         template <typename K, typename Less
 858             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
 859         bool find_with( K const& key, Less pred )
 860         {
 861             return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >() );
 862         }
 863
 864         /// Clears the map
 865         void clear()
 866         {
 867             base_class::clear();
 868         }
 869
 870         /// Checks if the map is empty
 871         /**
 872             Emptiness is checked by item counting: if item count is zero then the map is empty.
 873         */
 874         bool empty() const
 875         {
 876             return base_class::empty();
 877         }
 878
 879         /// Returns item count in the map
 880         size_t size() const
 881         {
 882             return base_class::size();
 883         }
 884
 885         /// Returns the size of hash table
 886         /**
 887             The hash table size is non-constant and can be increased via resizing.
 888         */
 889         size_t bucket_count() const
 890         {
 891             return base_class::bucket_count();
 892         }
 893
 894         /// Returns lock array size
 895         /**
 896             The lock array size is constant.
 897         */
 898         size_t lock_count() const
 899         {
 900             return base_class::lock_count();
 901         }
 902
 903         /// Returns resizing policy object
 904         resizing_policy& get_resizing_policy()
 905         {
 906             return base_class::get_resizing_policy();
 907         }
 908
 909         /// Returns resizing policy (const version)
 910         resizing_policy const& get_resizing_policy() const
 911         {
 912             return base_class::get_resizing_policy();
 913         }
 914     };
 915
 916 }}  // namespace cds::container
 917
 918 #endif // #ifndef __CDS_CONTAINER_STRIPED_MAP_H