cds/container/striped_set/adapter.h

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