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             - \p opt::mutex_policy - concurrent access policy.
  72                 Available policies: \p intrusive::striped_set::striping, \p intrusive::striped_set::refinable.
  73                 Default is %striped_set::striping.
  74             - \p opt::hash - hash functor. Default option value see <tt>opt::v::hash_selector<opt::none> </tt>
  75                 which selects default hash functor for your compiler.
  76             - \p opt::compare - key comparison functor. No default functor is provided.
  77                 If the option is not specified, the \p %opt::less is used.
  78             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
  79             - \p 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 counter
  81                 like as \p atomicity::empty_item_counter is not suitable.
  82             - \p opt::allocator - the allocator type using for memory allocation of bucket table and lock array. Default is \ref CDS_DEFAULT_ALLOCATOR.
  83             - \p 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 <tt>striped_set::load_factor_resizing<4> </tt>;
  86                     for other type of containers like \p std::map, \p std::unordered_map the resizing policy is \p striped_set::no_resizing.
  87                 See \ref cds_striped_resizing_policy "available resizing policy".
  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             - \p 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 \p striped_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>striped_set::adapt<AnyContainer, Options...> </tt> metafunction does not make any wrapping to \p AnyContainer,
 112             so, the result <tt>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 \p cds::opt::less or \p 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 boost::container::slist</td>
 177                     <td><tt><cds/container/striped_map/boost_slist.h></tt></td>
 178                     <td>\code
 179                         #include <cds/container/hash_smap/boost_slist.h>
 180                         #include <cds/container/striped_hash_map.h>
 181                         typedef cds::container::StripedMap<
 182                             boost::container::slist< std::pair< const Key, T > >
 183                         > striped_map;
 184                     \endcode
 185                     </td>
 186                     <td>
 187                         The type of values stored in the \p boost::container::slist must be <tt> std::pair< const Key, T > </tt>,
 188                         where \p Key - key type,  and \p T - value type. The list is ordered.
 189                         \p Options <b>must</b> contain \p cds::opt::less or \p cds::opt::compare.
 190                     </td>
 191                 </tr>
 192                 <tr>
 193                     <td> \p boost::container::list</td>
 194                     <td><tt><cds/container/striped_map/boost_list.h></tt></td>
 195                     <td>\code
 196                         #include <cds/container/striped_map/boost_list.h>
 197                         #include <cds/container/striped_hash_map.h>
 198                         typedef cds::container::StripedMap<
 199                             boost::container::list< std::pair< const Key, T > >
 200                         > striped_map;
 201                     \endcode
 202                     </td>
 203                     <td>
 204                         The type of values stored in the \p boost::container::list must be <tt> std::pair< const Key, T > </tt>,
 205                         where \p Key - key type,  and \p T - value type. The list is ordered.
 206                         \p Options <b>must</b> contain \p cds::opt::less or \p cds::opt::compare.
 207                     </td>
 208                 </tr>
 209                 <tr>
 210                     <td> \p boost::container::map</td>
 211                     <td><tt><cds/container/striped_map/boost_map.h></tt></td>
 212                     <td>\code
 213                         #include <cds/container/striped_map/boost_map.h>
 214                         #include <cds/container/striped_hash_map.h>
 215                         typedef cds::container::StripedMap<
 216                             boost::container::map< Key, T, std::pair< const Key, T> >
 217                         > striped_map;
 218                     \endcode
 219                     </td>
 220                     <td>
 221                     </td>
 222                 </tr>
 223                 <tr>
 224                     <td> \p boost::container::flat_map</td>
 225                     <td><tt><cds/container/striped_map/boost_flat_map.h></tt></td>
 226                     <td>\code
 227                         #include <cds/container/striped_map/boost_flat_map.h>
 228                         #include <cds/container/striped_hash_map.h>
 229                         typedef cds::container::StripedMap<
 230                             boost::container::flat_map< Key, T,
 231                                 std::less< std::pair< const Key, T> >
 232                             >
 233                         > striped_map;
 234                     \endcode
 235                     </td>
 236                     <td>
 237                     </td>
 238                 </tr>
 239                 <tr>
 240                     <td> \p boost::unordered_map</td>
 241                     <td><tt><cds/container/striped_map/boost_unordered_map.h></tt></td>
 242                     <td>\code
 243                         #include <cds/container/striped_map/boost_unordered_map.h>
 244                         #include <cds/container/refinable_hash_map.h>
 245                         typedef cds::container::StripedMap<
 246                             boost::unordered_map< Key, T, boost::hash<Key>, std::equal_to<Key> >
 247                         > refinable_map;
 248                     \endcode
 249                     </td>
 250                     <td>
 251                     </td>
 252                 </tr>
 253             </table>
 254
 255
 256             You can use another container type as map's bucket.
 257             Suppose, you have a container class \p MyBestContainer and you want to integrate it with \p %StripedMap as bucket type.
 258             There are two possibility:
 259             - either your \p MyBestContainer class has native support of bucket's interface;
 260                 in this case, you can use default <tt>striped_set::adapt</tt> metafunction;
 261             - or your \p MyBestContainer class does not support bucket's interface, which means, that you should develop a specialization
 262                 <tt>cds::container::striped_set::adapt<MyBestContainer> </tt> metafunction providing necessary interface.
 263
 264             The <tt>striped_set::adapt< Container, Options... ></tt> metafunction has two template argument:
 265             - \p Container is the class that should be used as the bucket, for example, <tt>std::list< std::pair< Key, T > ></tt>.
 266             - \p Options pack is the options from \p %StripedMap declaration. The \p adapt metafunction can use
 267                 any option from \p Options for its internal use. For example, a \p compare option can be passed to \p adapt
 268                 metafunction via \p Options argument of \p %StripedMap declaration.
 269
 270             See striped_set::adapt metafunction for the description of interface that the bucket container must provide
 271             to be \p %StripedMap compatible.
 272
 273         <b>Copy policy</b>
 274             There are three predefined copy policy:
 275             - \p cds::container::striped_set::copy_item - copy item from old bucket to new one when resizing using copy ctor. It is default policy for
 276                 any compiler that do not support move semantics
 277             - \p cds::container::striped_set::move_item - move item from old bucket to new one when resizing using move semantics. It is default policy for
 278                 any compiler that support move semantics. If compiler does not support move semantics, the move policy is the same as \p copy_item
 279             - \p cds::container::striped_set::swap_item - copy item from old bucket to new one when resizing using \p std::swap. Not all containers support
 280                 this copy policy, see details in table below.
 281
 282             You can define your own copy policy specifically for your case.
 283             Note, right copy policy can significantly improve the performance of resizing.
 284
 285             <table>
 286                 <tr>
 287                     <th>Container</th>
 288                     <th>Policies</th>
 289                 </tr>
 290                 <tr>
 291                     <td>
 292                         - \p std::list
 293                         - \p boost::list
 294                     </td>
 295                     <td>\code
 296                         struct copy_item {
 297                             void operator()(
 298                                 std::list< std::pair<const Key, T> >& list,
 299                                 std::list<std::pair<const Key, T> >::iterator itInsert,
 300                                 std::list<std::pair<const Key, T> >::iterator itWhat )
 301                             {
 302                                 list.insert( itInsert, *itWhat );
 303                             }
 304                         } \endcode
 305
 306                         \code
 307                         // The type T stored in the list must be swappable
 308                         struct swap_item {
 309                             void operator()(
 310                                 std::list< std::pair<const Key, T> >& list,
 311                                 std::list<std::pair<const Key, T> >::iterator itInsert,
 312                                 std::list<std::pair<const Key, T> >::iterator itWhat )
 313                             {
 314                                 std::pair<Key, T> newVal( itWhat->first, T() );
 315                                 std::swap( list.insert( itInsert, newVal )->second, itWhat->second );
 316                             }
 317                         } \endcode
 318
 319                         \code
 320                         struct move_item {
 321                             void operator()(
 322                                 std::list< std::pair<const Key, T> >& list,
 323                                 std::list<std::pair<const Key, T> >::iterator itInsert,
 324                                 std::list<std::pair<const Key, T> >::iterator itWhat )
 325                             {
 326                                 list.insert( itInsert, std::move( *itWhat ) );
 327                             }
 328                         } \endcode
 329                     </td>
 330                 </tr>
 331                 <tr>
 332                     <td>
 333                         - \p std::map
 334                         - \p std::unordered_map
 335                         - \p boost::container::map
 336                         - \p boost::container::flat_map
 337                         - \p boost::unordered_map
 338                     </td>
 339                     <td>\code
 340                         struct copy_item {
 341                             void operator()( std::map< Key, T>& map, std::map<Key, T>::iterator itWhat )
 342                             {
 343                                 map.insert( *itWhat );
 344                             }
 345                         } \endcode
 346
 347                     \code
 348                         struct swap_item {
 349                             void operator()( std::map< Key, T>& map, std::map<Key, T>::iterator itWhat )
 350                             {
 351                                 std::swap(
 352                                     map.insert(
 353                                         std::map::value_type( itWhat->first, T() ) ).first->second
 354                                         , itWhat->second
 355                                 ));
 356                             }
 357                         } \endcode
 358                         \p T type must be swappable.
 359
 360                     \code
 361                         struct move_item {
 362                             void operator()( std::map< Key, T>& map, std::map<Key, T>::iterator itWhat )
 363                             {
 364                                 map.insert( std::move( *itWhat ));
 365                             }
 366                         } \endcode
 367                 </tr>
 368                 <tr>
 369                     <td> \p boost::container::slist</td>
 370                     <td>\code
 371                         struct copy_item {
 372                             void operator()(
 373                                 bc::slist< std::pair<const Key, T> >& list,
 374                                 bc::slist<std::pair<const Key, T> >::iterator itInsert,
 375                                 bc::slist<std::pair<const Key, T> >::iterator itWhat )
 376                             {
 377                                 list.insert_after( itInsert, *itWhat );
 378                             }
 379                         } \endcode
 380
 381                         \code
 382                         // The type T stored in the list must be swappable
 383                         struct swap_item {
 384                             void operator()(
 385                                 bc::slist< std::pair<const Key, T> >& list,
 386                                 bc::slist<std::pair<const Key, T> >::iterator itInsert,
 387                                 bc::slist<std::pair<const Key, T> >::iterator itWhat )
 388                             {
 389                                 std::pair<Key, T> newVal( itWhat->first, T() );
 390                                 std::swap( list.insert( itInsert, newVal )->second, itWhat->second );
 391                             }
 392                         } \endcode
 393
 394                         \code
 395                         struct move_item {
 396                             void operator()(
 397                                 bc::slist< std::pair<const Key, T> >& list,
 398                                 bc::slist<std::pair<const Key, T> >::iterator itInsert,
 399                                 bc::slist<std::pair<const Key, T> >::iterator itWhat )
 400                             {
 401                                 list.insert_after( itInsert, std::move( *itWhat ) );
 402                             }
 403                         } \endcode
 404                     </td>
 405                 </tr>
 406             </table>
 407
 408         <b>Advanced functions</b>
 409
 410         The library provides some advanced functions like \p erase_with(), \p find_with(),
 411         that cannot be supported by all underlying containers.
 412         The table below shows whether underlying container supports those functions
 413         (the sign "+" means "container supports the function"):
 414
 415         <table>
 416             <tr>
 417                 <th>Container</th>
 418                 <th>\p find_with</th>
 419                 <th>\p erse_with</th>
 420             </tr>
 421             <tr>
 422                 <td> \p std::list</td>
 423                 <td>+</td>
 424                 <td>+</td>
 425             </tr>
 426             <tr>
 427                 <td> \p std::map</td>
 428                 <td>-</td>
 429                 <td>-</td>
 430             </tr>
 431             <tr>
 432                 <td> \p std::unordered_map</td>
 433                 <td>-</td>
 434                 <td>-</td>
 435             </tr>
 436             <tr>
 437                 <td> \p boost::container::slist</td>
 438                 <td>+</td>
 439                 <td>+</td>
 440             </tr>
 441             <tr>
 442                 <td> \p boost::container::list</td>
 443                 <td>+</td>
 444                 <td>+</td>
 445             </tr>
 446             <tr>
 447                 <td> \p boost::container::map</td>
 448                 <td>-</td>
 449                 <td>-</td>
 450             </tr>
 451             <tr>
 452                 <td> \p boost::container::flat_map</td>
 453                 <td>-</td>
 454                 <td>-</td>
 455             </tr>
 456             <tr>
 457                 <td> \p boost::unordered_map</td>
 458                 <td>-</td>
 459                 <td>-</td>
 460             </tr>
 461         </table>
 462
 463     **/
 464 template <class Container, typename... Options>
 465     class StripedMap
 466 #ifdef CDS_DOXYGEN_INVOKED
 467         : protected StripedSet<Container, Options...>
 468 #else
 469         : protected details::make_striped_map< Container, Options...>::type
 470 #endif
 471     {
 472         //@cond
 473         typedef typename details::make_striped_map< Container, Options...>::type base_class;
 474         //@endcond
 475
 476     public:
 477         //@cond
 478         typedef typename base_class::default_options    default_options;
 479         typedef typename base_class::options            options;
 480         //@endcond
 481
 482         typedef Container                           underlying_container_type   ;   ///< original intrusive container type for the bucket
 483         typedef typename base_class::bucket_type    bucket_type ;   ///< container type adapted for hash set
 484         typedef typename bucket_type::value_type    value_type  ;   ///< pair type (<tt> std::pair<key_type const, mapped_type> </tt>)
 485         typedef typename value_type::first_type     key_type    ;   ///< key type
 486         typedef typename value_type::second_type    mapped_type ;   ///< mapped type
 487
 488         typedef typename base_class::hash               hash            ; ///< Hash functor
 489         typedef typename base_class::item_counter       item_counter    ; ///< Item counter
 490         typedef typename base_class::resizing_policy    resizing_policy ; ///< Resizing policy
 491         typedef typename base_class::allocator_type     allocator_type  ; ///< allocator type specified in options.
 492         typedef typename base_class::mutex_policy       mutex_policy    ; ///< Mutex policy
 493
 494     protected:
 495         //@cond
 496         typedef typename base_class::scoped_cell_lock   scoped_cell_lock;
 497         typedef typename base_class::scoped_full_lock   scoped_full_lock;
 498         typedef typename base_class::scoped_resize_lock scoped_resize_lock;
 499         //@endcond
 500
 501     private:
 502         //@cond
 503         struct key_accessor {
 504             key_type const& operator()( value_type const& p ) const
 505             {
 506                 return p.first;
 507             }
 508         };
 509         //@endcond
 510
 511     public:
 512         /// Default ctor. The initial capacity is 16.
 513         StripedMap()
 514         : base_class()
 515         {}
 516
 517         /// Ctor with initial capacity specified
 518         StripedMap(
 519             size_t nCapacity    ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
 520         ) : base_class( nCapacity )
 521         {}
 522
 523         /// Ctor with resizing policy (copy semantics)
 524         /**
 525             This constructor initializes m_ResizingPolicy member with copy of \p resizingPolicy parameter
 526         */
 527         StripedMap(
 528             size_t nCapacity    ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
 529             ,resizing_policy const& resizingPolicy  ///< Resizing policy
 530         ) : base_class( nCapacity, resizingPolicy )
 531         {}
 532
 533         /// Ctor with resizing policy (move semantics)
 534         /**
 535             This constructor initializes m_ResizingPolicy member moving \p resizingPolicy parameter
 536             Move semantics is used. Available only for the compilers that supports C++11 rvalue reference.
 537         */
 538         StripedMap(
 539             size_t nCapacity    ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
 540             ,resizing_policy&& resizingPolicy  ///< Resizing policy
 541             ) : base_class( nCapacity, std::forward<resizing_policy>(resizingPolicy) )
 542         {}
 543
 544         /// Destructor destroys internal data
 545         ~StripedMap()
 546         {}
 547
 548     public:
 549         /// Inserts new node with key and default value
 550         /**
 551             The function creates a node with \p key and default value, and then inserts the node created into the map.
 552
 553             Preconditions:
 554             - The \p key_type should be constructible from a value of type \p K.
 555                 In trivial case, \p K is equal to \p key_type.
 556             - The \p mapped_type should be default-constructible.
 557
 558             Returns \p true if inserting successful, \p false otherwise.
 559         */
 560         template <typename K>
 561         bool insert( K const& key )
 562         {
 563             return insert_key( key, [](value_type&){} );
 564         }
 565
 566         /// Inserts new node
 567         /**
 568             The function creates a node with copy of \p val value
 569             and then inserts the node created into the map.
 570
 571             Preconditions:
 572             - The \p key_type should be constructible from \p key of type \p K.
 573             - The \p mapped_type should be constructible from \p val of type \p V.
 574
 575             Returns \p true if \p val is inserted into the set, \p false otherwise.
 576         */
 577         template <typename K, typename V>
 578         bool insert( K const& key, V const& val )
 579         {
 580             return insert_key( key, [&val](value_type& item) { item.second = val ; } );
 581         }
 582
 583         /// Inserts new node and initialize it by a functor
 584         /**
 585             This function inserts new node with key \p key and if inserting is successful then it calls
 586             \p func functor with signature
 587             \code
 588                 struct functor {
 589                     void operator()( value_type& item );
 590                 };
 591             \endcode
 592
 593             The argument \p item of user-defined functor \p func is the reference
 594             to the map's item inserted:
 595                 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
 596                 - <tt>item.second</tt> is a reference to item's value that may be changed.
 597
 598             The key_type should be constructible from value of type \p K.
 599
 600             The function allows to split creating of new item into two part:
 601             - create item from \p key;
 602             - insert new item into the map;
 603             - if inserting is successful, initialize the value of item by calling \p func functor
 604
 605             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 606             it is preferable that the initialization should be completed only if inserting is successful.
 607         */
 608         template <typename K, typename Func>
 609         bool insert_key( const K& key, Func func )
 610         {
 611             return base_class::insert( key, func );
 612         }
 613
 614         /// For key \p key inserts data of type \p mapped_type created in-place from \p args
 615         /**
 616             Returns \p true if inserting successful, \p false otherwise.
 617         */
 618         template <typename K, typename... Args>
 619         bool emplace( K&& key, Args&&... args )
 620         {
 621             bool bOk;
 622             bool bResize;
 623             size_t nHash = base_class::hashing( std::forward<K>(key));
 624             bucket_type * pBucket;
 625             {
 626                 scoped_cell_lock sl( base_class::m_MutexPolicy, nHash );
 627                 pBucket = base_class::bucket( nHash );
 628
 629                 bOk = pBucket->emplace( std::forward<K>(key), std::forward<Args>(args)...);
 630                 bResize = bOk && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
 631             }
 632
 633             if ( bResize )
 634                 base_class::resize();
 635
 636             return bOk;
 637         }
 638
 639         /// Ensures that the \p key exists in the map
 640         /**
 641             The operation performs inserting or changing data with lock-free manner.
 642
 643             If the \p key not found in the map, then the new item created from \p key
 644             is inserted into the map (note that in this case the \p key_type should be
 645             constructible from type \p K).
 646             Otherwise, the functor \p func is called with item found.
 647             The functor \p Func may be a function with signature:
 648             \code
 649                 void func( bool bNew, value_type& item );
 650             \endcode
 651             or a functor:
 652             \code
 653                 struct my_functor {
 654                     void operator()( bool bNew, value_type& item );
 655                 };
 656             \endcode
 657
 658             with arguments:
 659             - \p bNew - \p true if the item has been inserted, \p false otherwise
 660             - \p item - item of the list
 661
 662             The functor may change any fields of the \p item.second that is \p mapped_type.
 663
 664             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 665             \p second is true if new item has been added or \p false if the item with \p key
 666             already is in the list.
 667         */
 668         template <typename K, typename Func>
 669         std::pair<bool, bool> ensure( K const& key, Func func )
 670         {
 671             std::pair<bool, bool> result;
 672             bool bResize;
 673             size_t nHash = base_class::hashing( key );
 674             bucket_type * pBucket;
 675             {
 676                 scoped_cell_lock sl( base_class::m_MutexPolicy, nHash );
 677                 pBucket = base_class::bucket( nHash );
 678
 679                 result = pBucket->ensure( key, func );
 680                 bResize = result.first && result.second && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
 681             }
 682
 683             if ( bResize )
 684                 base_class::resize();
 685             return result;
 686         }
 687
 688         /// Delete \p key from the map
 689         /** \anchor cds_nonintrusive_StripedMap_erase
 690
 691             Return \p true if \p key is found and deleted, \p false otherwise
 692         */
 693         template <typename K>
 694         bool erase( K const& key )
 695         {
 696             return base_class::erase( key );
 697         }
 698
 699         /// Deletes the item from the map using \p pred predicate for searching
 700         /**
 701             The function is an analog of \ref cds_nonintrusive_StripedMap_erase "erase(K const&)"
 702             but \p pred is used for key comparing.
 703             \p Less functor has the interface like \p std::less.
 704             \p pred must imply the same element order as the comparator used for building the map.
 705
 706             @note This function is enabled if the compiler supports C++11
 707             default template arguments for function template <b>and</b> the underlying container
 708             supports \p %erase_with feature.
 709         */
 710         template < typename K, typename Less
 711             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type >
 712         bool erase_with( K const& key, Less pred )
 713         {
 714             return erase_with( key, pred, [](value_type const&) {} );
 715         }
 716
 717         /// Delete \p key from the map
 718         /** \anchor cds_nonintrusive_StripedMap_erase_func
 719
 720             The function searches an item with key \p key, calls \p f functor
 721             and deletes the item. If \p key is not found, the functor is not called.
 722
 723             The functor \p Func interface:
 724             \code
 725             struct extractor {
 726                 void operator()(value_type& item) { ... }
 727             };
 728             \endcode
 729
 730             Return \p true if key is found and deleted, \p false otherwise
 731         */
 732         template <typename K, typename Func>
 733         bool erase( K const& key, Func f )
 734         {
 735             return base_class::erase( key, f );
 736         }
 737
 738         /// Deletes the item from the map using \p pred predicate for searching
 739         /**
 740             The function is an analog of \ref cds_nonintrusive_StripedMap_erase_func "erase(K const&, Func)"
 741             but \p pred is used for key comparing.
 742             \p Less functor has the interface like \p std::less.
 743             \p pred must imply the same element order as the comparator used for building the map.
 744
 745             @note This function is enabled if the compiler supports C++11
 746             default template arguments for function template <b>and</b> the underlying container
 747             supports \p %erase_with feature.
 748         */
 749         template <typename K, typename Less, typename Func
 750             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type >
 751         bool erase_with( K const& key, Less pred, Func f )
 752         {
 753             return base_class::erase_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(), f );
 754         }
 755
 756         /// Find the key \p key
 757         /** \anchor cds_nonintrusive_StripedMap_find_func
 758
 759             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 760             The interface of \p Func functor is:
 761             \code
 762             struct functor {
 763                 void operator()( value_type& item );
 764             };
 765             \endcode
 766             where \p item is the item found.
 767
 768             The functor may change \p item.second.
 769
 770             The function returns \p true if \p key is found, \p false otherwise.
 771         */
 772         template <typename K, typename Func>
 773         bool find( K const& key, Func f )
 774         {
 775             return base_class::find( key, [&f]( value_type& pair, K const& ) mutable { f(pair); } );
 776         }
 777
 778         /// Find the key \p val using \p pred predicate
 779         /**
 780             The function is an analog of \ref cds_nonintrusive_StripedMap_find_func "find(K const&, Func)"
 781             but \p pred is used for key comparing
 782             \p Less has the interface like \p std::less.
 783             \p pred must imply the same element order as the comparator used for building the set.
 784
 785             @note This function is enabled if the compiler supports C++11
 786             default template arguments for function template <b>and</b> the underlying container
 787             supports \p %find_with feature.
 788         */
 789         template <typename K, typename Less, typename Func
 790             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
 791         bool find_with( K const& key, Less pred, Func f )
 792         {
 793             return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(),
 794                 [&f]( value_type& pair, K const& ) mutable { f(pair); } );
 795         }
 796
 797         /// Find the key \p key
 798         /** \anchor cds_nonintrusive_StripedMap_find_val
 799
 800             The function searches the item with key equal to \p key
 801             and returns \p true if it is found, and \p false otherwise.
 802         */
 803         template <typename K>
 804         bool find( K const& key )
 805         {
 806             return base_class::find( key );
 807         }
 808
 809         /// Find the key \p val using \p pred predicate
 810         /**
 811             The function is an analog of \ref cds_nonintrusive_StripedMap_find_val "find(K const&)"
 812             but \p pred is used for key comparing
 813             \p Less has the interface like \p std::less.
 814             \p pred must imply the same element order as the comparator used for building the set.
 815
 816             @note This function is enabled if the compiler supports C++11
 817             default template arguments for function template <b>and</b> the underlying container
 818             supports \p %find_with feature.
 819         */
 820         template <typename K, typename Less
 821             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
 822         bool find_with( K const& key, Less pred )
 823         {
 824             return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >() );
 825         }
 826
 827         /// Clears the map
 828         void clear()
 829         {
 830             base_class::clear();
 831         }
 832
 833         /// Checks if the map is empty
 834         /**
 835             Emptiness is checked by item counting: if item count is zero then the map is empty.
 836         */
 837         bool empty() const
 838         {
 839             return base_class::empty();
 840         }
 841
 842         /// Returns item count in the map
 843         size_t size() const
 844         {
 845             return base_class::size();
 846         }
 847
 848         /// Returns the size of hash table
 849         /**
 850             The hash table size is non-constant and can be increased via resizing.
 851         */
 852         size_t bucket_count() const
 853         {
 854             return base_class::bucket_count();
 855         }
 856
 857         /// Returns lock array size
 858         /**
 859             The lock array size is constant.
 860         */
 861         size_t lock_count() const
 862         {
 863             return base_class::lock_count();
 864         }
 865
 866         /// Returns resizing policy object
 867         resizing_policy& get_resizing_policy()
 868         {
 869             return base_class::get_resizing_policy();
 870         }
 871
 872         /// Returns resizing policy (const version)
 873         resizing_policy const& get_resizing_policy() const
 874         {
 875             return base_class::get_resizing_policy();
 876         }
 877     };
 878
 879 }}  // namespace cds::container
 880
 881 #endif // #ifndef __CDS_CONTAINER_STRIPED_MAP_H