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