cds/container/striped_set/adapter.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_STRIPED_SET_ADAPTER_H
   4 #define CDSLIB_CONTAINER_STRIPED_SET_ADAPTER_H
   5
   6 #include <cds/intrusive/striped_set/adapter.h>
   7 #include <cds/intrusive/striped_set/striping_policy.h>
   8
   9 namespace cds { namespace container {
  10     /// Striped hash set related definitions
  11     namespace striped_set {
  12
  13         //@cond
  14         struct copy_item    ;   // copy_item_policy tag
  15         template <typename Container>
  16         struct copy_item_policy;
  17
  18         struct swap_item    ;   // swap_item_policy tag
  19         template <typename Container>
  20         struct swap_item_policy;
  21
  22         struct move_item    ;   // move_item_policy tag
  23         template <typename Container>
  24         struct move_item_policy;
  25         //@endcond
  26
  27 #ifdef CDS_DOXYGEN_INVOKED
  28         /// Default adapter for hash set
  29         /**
  30             By default, the metafunction does not make any transformation for container type \p Container.
  31             \p Container should provide interface suitable for the hash set.
  32
  33             The \p Options template argument contains a list of options
  34             that has been passed to cds::container::StripedSet.
  35
  36         <b>Bucket interface</b>
  37
  38             The result of metafunction is a container (a bucket) that should support the following interface:
  39
  40             Public typedefs that the bucket should provide:
  41                 - \p value_type - the type of the item in the bucket
  42                 - \p iterator - bucket's item iterator
  43                 - \p const_iterator - bucket's item constant iterator
  44                 - \p default_resizing_policy - defalt resizing policy preferable for the container.
  45                     By default, the library defines striped_set::load_factor_resizing<4> for sequential containers like
  46                     std::list, std::vector, and striped_set::no_resizing for ordered container like std::set,
  47                     std::unordered_set.
  48
  49             <b>Insert value \p val of type \p Q</b>
  50             \code template <typename Q, typename Func> bool insert( const Q& val, Func f ) ; \endcode
  51                 The function allows to split creating of new item into two part:
  52                 - create item with key only from \p val
  53                 - try to insert new item into the container
  54                 - if inserting is success, calls \p f functor to initialize value-field of the new item.
  55
  56                 The functor signature is:
  57                 \code
  58                     void func( value_type& item );
  59                 \endcode
  60                 where \p item is the item inserted.
  61
  62                 The type \p Q can differ from \ref value_type of items storing in the container.
  63                 Therefore, the \p value_type should be comparable with type \p Q and constructible from type \p Q,
  64
  65                 The user-defined functor is called only if the inserting is success.
  66                 <hr>
  67
  68             <b>Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt></b>
  69             \code template <typename... Args> bool emplace( Args&&... args ) ; \endcode
  70                 Returns \p true if inserting successful, \p false otherwise.
  71
  72                 This function should be available only for compiler that supports
  73                 variadic template and move semantics
  74             <hr>
  75
  76             <b>Updates \p item</b>
  77             \code template <typename Q, typename Func> std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert ) \endcode
  78                 The operation performs inserting or changing data.
  79
  80                 If the \p val key not found in the container, then the new item created from \p val
  81                 is inserted iff \p bAllowInsert is \p true. Otherwise, the functor \p func is called with the item found.
  82                 The \p Func functor has interface:
  83                 \code
  84                     void func( bool bNew, value_type& item, const Q& val );
  85                 \endcode
  86                 or like a functor:
  87                 \code
  88                     struct my_functor {
  89                         void operator()( bool bNew, value_type& item, const Q& val );
  90                     };
  91                 \endcode
  92
  93                 where arguments are:
  94                 - \p bNew - \p true if the item has been inserted, \p false otherwise
  95                 - \p item - container's item
  96                 - \p val - argument \p val passed into the \p update() function
  97
  98                 The functor can change non-key fields of the \p item.
  99
 100                 The type \p Q can differ from \ref value_type of items storing in the container.
 101                 Therefore, the \p value_type should be comparable with type \p Q and constructible from type \p Q,
 102
 103                 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 104                 \p second is true if new item has been added or \p false if the item with \p val key
 105                 already exists.
 106                 <hr>
 107
 108
 109             <b>Delete \p key</b>
 110             \code template <typename Q, typename Func> bool erase( const Q& key, Func f ) \endcode
 111                 The function searches an item with key \p key, calls \p f functor
 112                 and deletes the item. If \p key is not found, the functor is not called.
 113
 114                 The functor \p Func interface is:
 115                 \code
 116                 struct extractor {
 117                     void operator()(value_type const& val);
 118                 };
 119                 \endcode
 120
 121                 The type \p Q can differ from \ref value_type of items storing in the container.
 122                 Therefore, the \p value_type should be comparable with type \p Q.
 123
 124                 Return \p true if key is found and deleted, \p false otherwise
 125                 <hr>
 126
 127
 128             <b>Find the key \p val </b>
 129             \code template <typename Q, typename Func> bool find( Q& val, Func f ) \endcode
 130                 The function searches the item with key equal to \p val and calls the functor \p f for item found.
 131                 The interface of \p Func functor is:
 132                 \code
 133                 struct functor {
 134                     void operator()( value_type& item, Q& val );
 135                 };
 136                 \endcode
 137                 where \p item is the item found, \p val is the <tt>find</tt> function argument.
 138
 139                 The functor can change non-key fields of \p item.
 140                 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 141                 can modify both arguments.
 142
 143                 The type \p Q can differ from \ref value_type of items storing in the container.
 144                 Therefore, the \p value_type should be comparable with type \p Q.
 145
 146                 The function returns \p true if \p val is found, \p false otherwise.
 147                 <hr>
 148
 149             <b>Clears the container</b>
 150             \code void clear() \endcode
 151             <hr>
 152
 153             <b>Get size of bucket</b>
 154             \code size_t size() const \endcode
 155             This function can be required by some resizing policy
 156             <hr>
 157
 158             <b>Move item when resizing</b>
 159             \code void move_item( adapted_container& from, iterator it ) \endcode
 160             This helper function is invented for the set resizing when the item
 161             pointed by \p it iterator is copied from an old bucket \p from to a new bucket
 162             pointed by \p this.
 163             <hr>
 164
 165         */
 166         template < typename Container, typename... Options>
 167         class adapt
 168         {
 169         public:
 170             typedef Container   type            ;   ///< adapted container type
 171             typedef typename type::value_type value_type  ;   ///< value type stored in the container
 172         };
 173 #else   // CDS_DOXYGEN_INVOKED
 174         using cds::intrusive::striped_set::adapt;
 175 #endif
 176
 177         //@cond
 178         using cds::intrusive::striped_set::adapted_sequential_container;
 179         using cds::intrusive::striped_set::adapted_container;
 180         //@endcond
 181
 182         ///@copydoc cds::intrusive::striped_set::load_factor_resizing
 183         template <size_t LoadFactor>
 184         using load_factor_resizing = cds::intrusive::striped_set::load_factor_resizing<LoadFactor>;
 185
 186         ///@copydoc cds::intrusive::striped_set::rational_load_factor_resizing
 187         template <size_t Numerator, size_t Denominator = 1>
 188         using rational_load_factor_resizing = cds::intrusive::striped_set::rational_load_factor_resizing<Numerator, Denominator>;
 189
 190         ///@copydoc cds::intrusive::striped_set::single_bucket_size_threshold
 191         template <size_t Threshold>
 192         using single_bucket_size_threshold = cds::intrusive::striped_set::single_bucket_size_threshold<Threshold>;
 193
 194         ///@copydoc cds::intrusive::striped_set::no_resizing
 195         typedef cds::intrusive::striped_set::no_resizing no_resizing;
 196
 197         ///@copydoc cds::intrusive::striped_set::striping
 198         template <class Lock = std::mutex, class Alloc = CDS_DEFAULT_ALLOCATOR >
 199         using striping = cds::intrusive::striped_set::striping<Lock, Alloc>;
 200
 201         ///@copydoc cds::intrusive::striped_set::refinable
 202         template <
 203             class RecursiveLock = std::recursive_mutex,
 204             typename BackOff = cds::backoff::yield,
 205             class Alloc = CDS_DEFAULT_ALLOCATOR
 206         >
 207         using refinable = cds::intrusive::striped_set::refinable<RecursiveLock, BackOff, Alloc >;
 208
 209         //@cond
 210         namespace details {
 211
 212             template <class Set>
 213             struct boost_set_copy_policies
 214             {
 215                 struct copy_item_policy
 216                 {
 217                     typedef Set set_type;
 218                     typedef typename set_type::iterator iterator;
 219
 220                     void operator()( set_type& set, iterator itWhat )
 221                     {
 222                         set.insert( *itWhat );
 223                     }
 224                 };
 225
 226                 typedef copy_item_policy swap_item_policy;
 227
 228               struct move_item_policy
 229                 {
 230                     typedef Set set_type;
 231                     typedef typename set_type::iterator iterator;
 232
 233                     void operator()( set_type& set, iterator itWhat )
 234                     {
 235                         set.insert( std::move( *itWhat ) );
 236                     }
 237                 };
 238             };
 239
 240             template <class Set, typename... Options>
 241             class boost_set_adapter: public striped_set::adapted_container
 242             {
 243             public:
 244                 typedef Set container_type;
 245
 246                 typedef typename container_type::value_type     value_type      ;   ///< value type stored in the container
 247                 typedef typename container_type::iterator       iterator        ;   ///< container iterator
 248                 typedef typename container_type::const_iterator const_iterator  ;   ///< container const iterator
 249
 250                 static bool const has_find_with = false;
 251                 static bool const has_erase_with = false;
 252
 253             private:
 254                 typedef typename cds::opt::select<
 255                     typename cds::opt::value<
 256                         typename cds::opt::find_option<
 257                             cds::opt::copy_policy< cds::container::striped_set::move_item >
 258                             , Options...
 259                         >::type
 260                     >::copy_policy
 261                     , cds::container::striped_set::copy_item, copy_item_policy<container_type>
 262                     , cds::container::striped_set::swap_item, swap_item_policy<container_type>
 263                     , cds::container::striped_set::move_item, move_item_policy<container_type>
 264                 >::type copy_item;
 265
 266             private:
 267                 container_type  m_Set;
 268
 269             public:
 270                 boost_set_adapter()
 271                 {}
 272
 273                 container_type& base_container()
 274                 {
 275                     return m_Set;
 276                 }
 277
 278                 template <typename Q, typename Func>
 279                 bool insert( const Q& val, Func f )
 280                 {
 281                     std::pair<iterator, bool> res = m_Set.insert( value_type(val) );
 282                     if ( res.second )
 283                         f( const_cast<value_type&>(*res.first) );
 284                     return res.second;
 285                 }
 286
 287                 template <typename... Args>
 288                 bool emplace( Args&&... args )
 289                 {
 290                     std::pair<iterator, bool> res = m_Set.emplace( std::forward<Args>(args)... );
 291                     return res.second;
 292                 }
 293
 294                 template <typename Q, typename Func>
 295                 std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert )
 296                 {
 297                     if ( bAllowInsert ) {
 298                         std::pair<iterator, bool> res = m_Set.insert( value_type(val) );
 299                         func( res.second, const_cast<value_type&>(*res.first), val );
 300                         return std::make_pair( true, res.second );
 301                     }
 302                     else {
 303                         auto it = m_Set.find( val );
 304                         if ( it == m_Set.end() )
 305                             return std::make_pair( false, false );
 306                         func( false, const_cast<value_type&>(*it), val );
 307                         return std::make_pair( true, false );
 308                     }
 309                 }
 310
 311                 template <typename Q, typename Func>
 312                 bool erase( const Q& key, Func f )
 313                 {
 314                     const_iterator it = m_Set.find( value_type(key) );
 315                     if ( it == m_Set.end() )
 316                         return false;
 317                     f( const_cast<value_type&>(*it) );
 318                     m_Set.erase( it );
 319                     return true;
 320                 }
 321
 322                 template <typename Q, typename Func>
 323                 bool find( Q& val, Func f )
 324                 {
 325                     iterator it = m_Set.find( value_type(val) );
 326                     if ( it == m_Set.end() )
 327                         return false;
 328                     f( const_cast<value_type&>(*it), val );
 329                     return true;
 330                 }
 331
 332                 void clear()
 333                 {
 334                     m_Set.clear();
 335                 }
 336
 337                 iterator begin()                { return m_Set.begin(); }
 338                 const_iterator begin() const    { return m_Set.begin(); }
 339                 iterator end()                  { return m_Set.end(); }
 340                 const_iterator end() const      { return m_Set.end(); }
 341
 342                 void move_item( adapted_container& /*from*/, iterator itWhat )
 343                 {
 344                     assert( m_Set.find( *itWhat ) == m_Set.end() );
 345                     copy_item()( m_Set, itWhat );
 346                 }
 347
 348                 size_t size() const
 349                 {
 350                     return m_Set.size();
 351                 }
 352             };
 353
 354             template <class Map>
 355             struct boost_map_copy_policies {
 356                 struct copy_item_policy {
 357                     typedef Map map_type;
 358                     typedef typename map_type::value_type pair_type;
 359                     typedef typename map_type::iterator    iterator;
 360
 361                     void operator()( map_type& map, iterator itWhat )
 362                     {
 363                         map.insert( *itWhat );
 364                     }
 365                 };
 366
 367                 struct swap_item_policy {
 368                     typedef Map map_type;
 369                     typedef typename map_type::value_type pair_type;
 370                     typedef typename map_type::iterator    iterator;
 371
 372                     void operator()( map_type& map, iterator itWhat )
 373                     {
 374                         std::pair< iterator, bool > ret = map.insert( pair_type( itWhat->first, typename pair_type::second_type() ));
 375                         assert( ret.second )    ;   // successful insertion
 376                         std::swap( ret.first->second, itWhat->second );
 377                     }
 378                 };
 379
 380                 struct move_item_policy {
 381                     typedef Map map_type;
 382                     typedef typename map_type::value_type pair_type;
 383                     typedef typename map_type::iterator    iterator;
 384
 385                     void operator()( map_type& map, iterator itWhat  )
 386                     {
 387                         map.insert( std::move( *itWhat ) );
 388                     }
 389                 };
 390             };
 391
 392             template <class Map, typename... Options>
 393             class boost_map_adapter: public striped_set::adapted_container
 394             {
 395             public:
 396                 typedef Map container_type;
 397
 398                 typedef typename container_type::value_type value_type  ;   ///< value type stored in the container
 399                 typedef typename container_type::key_type   key_type;
 400                 typedef typename container_type::mapped_type    mapped_type;
 401                 typedef typename container_type::iterator       iterator        ;   ///< container iterator
 402                 typedef typename container_type::const_iterator const_iterator  ;   ///< container const iterator
 403
 404                 static bool const has_find_with = false;
 405                 static bool const has_erase_with = false;
 406
 407             private:
 408                 typedef typename cds::opt::select<
 409                     typename cds::opt::value<
 410                     typename cds::opt::find_option<
 411                         cds::opt::copy_policy< cds::container::striped_set::move_item >
 412                         , Options...
 413                     >::type
 414                     >::copy_policy
 415                     , cds::container::striped_set::copy_item, copy_item_policy<container_type>
 416                     , cds::container::striped_set::swap_item, swap_item_policy<container_type>
 417                     , cds::container::striped_set::move_item, move_item_policy<container_type>
 418                 >::type copy_item;
 419
 420             private:
 421                 container_type  m_Map;
 422
 423             public:
 424                 template <typename Q, typename Func>
 425                 bool insert( const Q& key, Func f )
 426                 {
 427                     std::pair<iterator, bool> res = m_Map.insert( value_type( key, mapped_type() ) );
 428                     if ( res.second )
 429                         f( *res.first );
 430                     return res.second;
 431                 }
 432
 433                 template <typename Q, typename... Args>
 434                 bool emplace( Q&& key, Args&&... args )
 435                 {
 436                     std::pair<iterator, bool> res = m_Map.emplace( std::forward<Q>(key), std::move( mapped_type( std::forward<Args>(args)...)));
 437                     return res.second;
 438                 }
 439
 440                 template <typename Q, typename Func>
 441                 std::pair<bool, bool> update( const Q& key, Func func, bool bAllowInsert )
 442                 {
 443                     if ( bAllowInsert ) {
 444                         std::pair<iterator, bool> res = m_Map.insert( value_type( key, mapped_type() ));
 445                         func( res.second, *res.first );
 446                         return std::make_pair( true, res.second );
 447                     }
 448                     else {
 449                         auto it = m_Map.find(key_type( key ));
 450                         if ( it == end() )
 451                             return std::make_pair( false, false );
 452                         func( false, *it );
 453                         return std::make_pair( true, false );
 454                     }
 455                 }
 456
 457                 template <typename Q, typename Func>
 458                 bool erase( const Q& key, Func f )
 459                 {
 460                     iterator it = m_Map.find( key_type(key) );
 461                     if ( it == m_Map.end() )
 462                         return false;
 463                     f( *it );
 464                     m_Map.erase( it );
 465                     return true;
 466                 }
 467
 468                 template <typename Q, typename Func>
 469                 bool find( Q& val, Func f )
 470                 {
 471                     iterator it = m_Map.find( key_type(val) );
 472                     if ( it == m_Map.end() )
 473                         return false;
 474                     f( *it, val );
 475                     return true;
 476                 }
 477
 478                 void clear()
 479                 {
 480                     m_Map.clear();
 481                 }
 482
 483                 iterator begin()                { return m_Map.begin(); }
 484                 const_iterator begin() const    { return m_Map.begin(); }
 485                 iterator end()                  { return m_Map.end(); }
 486                 const_iterator end() const      { return m_Map.end(); }
 487
 488                 void move_item( adapted_container& /*from*/, iterator itWhat )
 489                 {
 490                     assert( m_Map.find( itWhat->first ) == m_Map.end() );
 491                     copy_item()( m_Map, itWhat );
 492                 }
 493
 494                 size_t size() const
 495                 {
 496                     return m_Map.size();
 497                 }
 498             };
 499
 500         } // namespace details
 501         //@endcond
 502
 503     }   // namespace striped_set
 504 }} // namespace cds::container
 505
 506
 507 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_ADAPTER_H