cds/container/striped_map.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_STRIPED_MAP_H
   4 #define CDSLIB_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 cds::opt::mutex_policy - concurrent access policy.
  72                 Available policies: \p striped_set::striping, \p striped_set::refinable.
  73                 Default is \p %striped_set::striping.
  74             - \p cds::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 cds::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 cds::opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
  79             - \p cds::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 cds::opt::allocator - the allocator type using for memory allocation of bucket table and lock array. Default is \ref CDS_DEFAULT_ALLOCATOR.
  83             - \p cds::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 cds::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_with( 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_with( 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_with( 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         /// Updates the node
 640         /**
 641             The operation performs inserting or changing data with lock-free manner.
 642
 643             If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true.
 644             Otherwise, the functor \p func is called with item found.
 645
 646             The functor signature is:
 647             \code
 648                 struct my_functor {
 649                     void operator()( bool bNew, value_type& item );
 650                 };
 651             \endcode
 652             with arguments:
 653             - \p bNew - \p true if the item has been inserted, \p false otherwise
 654             - \p item - item of the map
 655
 656             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 657             \p second is true if new item has been added or \p false if the item with \p key
 658             already is in the map.
 659         */
 660         template <typename K, typename Func>
 661         std::pair<bool, bool> update( K const& key, Func func, bool bAllowInsert = true )
 662         {
 663             std::pair<bool, bool> result;
 664             bool bResize;
 665             size_t nHash = base_class::hashing( key );
 666             bucket_type * pBucket;
 667             {
 668                 scoped_cell_lock sl( base_class::m_MutexPolicy, nHash );
 669                 pBucket = base_class::bucket( nHash );
 670
 671                 result = pBucket->update( key, func, bAllowInsert );
 672                 bResize = result.first && result.second && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
 673             }
 674
 675             if ( bResize )
 676                 base_class::resize();
 677             return result;
 678         }
 679         //@cond
 680         template <typename K, typename Func>
 681         CDS_DEPRECATED("ensure() is deprecated, use update() instead")
 682         std::pair<bool, bool> ensure( K const& key, Func func )
 683         {
 684             return update( key, func, true );
 685         }
 686
 687         /// Delete \p key from the map
 688         /** \anchor cds_nonintrusive_StripedMap_erase
 689
 690             Return \p true if \p key is found and deleted, \p false otherwise
 691         */
 692         template <typename K>
 693         bool erase( K const& key )
 694         {
 695             return base_class::erase( key );
 696         }
 697
 698         /// Deletes the item from the map using \p pred predicate for searching
 699         /**
 700             The function is an analog of \ref cds_nonintrusive_StripedMap_erase "erase(K const&)"
 701             but \p pred is used for key comparing.
 702             \p Less functor has the interface like \p std::less.
 703             \p pred must imply the same element order as the comparator used for building the map.
 704
 705             @note This function is enabled if the compiler supports C++11
 706             default template arguments for function template <b>and</b> the underlying container
 707             supports \p %erase_with feature.
 708         */
 709         template < typename K, typename Less
 710             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type >
 711         bool erase_with( K const& key, Less pred )
 712         {
 713             return erase_with( key, pred, [](value_type const&) {} );
 714         }
 715
 716         /// Delete \p key from the map
 717         /** \anchor cds_nonintrusive_StripedMap_erase_func
 718
 719             The function searches an item with key \p key, calls \p f functor
 720             and deletes the item. If \p key is not found, the functor is not called.
 721
 722             The functor \p Func interface:
 723             \code
 724             struct extractor {
 725                 void operator()(value_type& item) { ... }
 726             };
 727             \endcode
 728
 729             Return \p true if key is found and deleted, \p false otherwise
 730         */
 731         template <typename K, typename Func>
 732         bool erase( K const& key, Func f )
 733         {
 734             return base_class::erase( key, f );
 735         }
 736
 737         /// Deletes the item from the map using \p pred predicate for searching
 738         /**
 739             The function is an analog of \ref cds_nonintrusive_StripedMap_erase_func "erase(K const&, Func)"
 740             but \p pred is used for key comparing.
 741             \p Less functor has the interface like \p std::less.
 742             \p pred must imply the same element order as the comparator used for building the map.
 743
 744             @note This function is enabled if the compiler supports C++11
 745             default template arguments for function template <b>and</b> the underlying container
 746             supports \p %erase_with feature.
 747         */
 748         template <typename K, typename Less, typename Func
 749             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type >
 750         bool erase_with( K const& key, Less pred, Func f )
 751         {
 752             CDS_UNUSED( pred );
 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             CDS_UNUSED( pred );
 794             return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(),
 795                 [&f]( value_type& pair, K const& ) mutable { f(pair); } );
 796         }
 797
 798         /// Checks whether the map contains \p key
 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 contains( K const& key )
 805         {
 806             return base_class::contains( key );
 807         }
 808         //@cond
 809         template <typename K>
 810         CDS_DEPRECATED("use contains()")
 811         bool find( K const& key )
 812         {
 813             return contains( key );
 814         }
 815         //@endcond
 816
 817         /// Checks whether the set contains \p key using \p pred predicate for searching
 818         /**
 819             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 820             \p Less functor has the interface like \p std::less.
 821             \p Less must imply the same element order as the comparator used for building the set.
 822
 823             @note This function is enabled if the compiler supports C++11
 824             default template arguments for function template <b>and</b> the underlying container
 825             supports \p %contains() feature.
 826         */
 827         template <typename K, typename Less
 828             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
 829         bool contains( K const& key, Less pred )
 830         {
 831             CDS_UNUSED( pred );
 832             return base_class::contains( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >() );
 833         }
 834         //@cond
 835         template <typename K, typename Less
 836             ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
 837         CDS_DEPRECATED("use contains()")
 838         bool find_with( K const& key, Less pred )
 839         {
 840             return contains( key, pred );
 841         }
 842         //@endcond
 843
 844         /// Clears the map
 845         void clear()
 846         {
 847             base_class::clear();
 848         }
 849
 850         /// Checks if the map is empty
 851         /**
 852             Emptiness is checked by item counting: if item count is zero then the map is empty.
 853         */
 854         bool empty() const
 855         {
 856             return base_class::empty();
 857         }
 858
 859         /// Returns item count in the map
 860         size_t size() const
 861         {
 862             return base_class::size();
 863         }
 864
 865         /// Returns the size of hash table
 866         /**
 867             The hash table size is non-constant and can be increased via resizing.
 868         */
 869         size_t bucket_count() const
 870         {
 871             return base_class::bucket_count();
 872         }
 873
 874         /// Returns lock array size
 875         /**
 876             The lock array size is constant.
 877         */
 878         size_t lock_count() const
 879         {
 880             return base_class::lock_count();
 881         }
 882
 883         /// Returns resizing policy object
 884         resizing_policy& get_resizing_policy()
 885         {
 886             return base_class::get_resizing_policy();
 887         }
 888
 889         /// Returns resizing policy (const version)
 890         resizing_policy const& get_resizing_policy() const
 891         {
 892             return base_class::get_resizing_policy();
 893         }
 894     };
 895
 896 }}  // namespace cds::container
 897
 898 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_MAP_H