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>Ensures that the \p item exists in the container</b>
  77             \code template <typename Q, typename Func> std::pair<bool, bool> ensure( const Q& val, Func func ) \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. 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 ensure 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> ensure( const Q& val, Func func )
 296                 {
 297                     std::pair<iterator, bool> res = m_Set.insert( value_type(val) );
 298                     func( res.second, const_cast<value_type&>(*res.first), val );
 299                     return std::make_pair( true, res.second );
 300                 }
 301
 302                 template <typename Q, typename Func>
 303                 bool erase( const Q& key, Func f )
 304                 {
 305                     const_iterator it = m_Set.find( value_type(key) );
 306                     if ( it == m_Set.end() )
 307                         return false;
 308                     f( const_cast<value_type&>(*it) );
 309                     m_Set.erase( it );
 310                     return true;
 311                 }
 312
 313                 template <typename Q, typename Func>
 314                 bool find( Q& val, Func f )
 315                 {
 316                     iterator it = m_Set.find( value_type(val) );
 317                     if ( it == m_Set.end() )
 318                         return false;
 319                     f( const_cast<value_type&>(*it), val );
 320                     return true;
 321                 }
 322
 323                 void clear()
 324                 {
 325                     m_Set.clear();
 326                 }
 327
 328                 iterator begin()                { return m_Set.begin(); }
 329                 const_iterator begin() const    { return m_Set.begin(); }
 330                 iterator end()                  { return m_Set.end(); }
 331                 const_iterator end() const      { return m_Set.end(); }
 332
 333                 void move_item( adapted_container& /*from*/, iterator itWhat )
 334                 {
 335                     assert( m_Set.find( *itWhat ) == m_Set.end() );
 336                     copy_item()( m_Set, itWhat );
 337                 }
 338
 339                 size_t size() const
 340                 {
 341                     return m_Set.size();
 342                 }
 343             };
 344
 345             template <class Map>
 346             struct boost_map_copy_policies {
 347                 struct copy_item_policy {
 348                     typedef Map map_type;
 349                     typedef typename map_type::value_type pair_type;
 350                     typedef typename map_type::iterator    iterator;
 351
 352                     void operator()( map_type& map, iterator itWhat )
 353                     {
 354                         map.insert( *itWhat );
 355                     }
 356                 };
 357
 358                 struct swap_item_policy {
 359                     typedef Map map_type;
 360                     typedef typename map_type::value_type pair_type;
 361                     typedef typename map_type::iterator    iterator;
 362
 363                     void operator()( map_type& map, iterator itWhat )
 364                     {
 365                         std::pair< iterator, bool > ret = map.insert( pair_type( itWhat->first, typename pair_type::second_type() ));
 366                         assert( ret.second )    ;   // successful insertion
 367                         std::swap( ret.first->second, itWhat->second );
 368                     }
 369                 };
 370
 371                 struct move_item_policy {
 372                     typedef Map map_type;
 373                     typedef typename map_type::value_type pair_type;
 374                     typedef typename map_type::iterator    iterator;
 375
 376                     void operator()( map_type& map, iterator itWhat  )
 377                     {
 378                         map.insert( std::move( *itWhat ) );
 379                     }
 380                 };
 381             };
 382
 383             template <class Map, typename... Options>
 384             class boost_map_adapter: public striped_set::adapted_container
 385             {
 386             public:
 387                 typedef Map container_type;
 388
 389                 typedef typename container_type::value_type value_type  ;   ///< value type stored in the container
 390                 typedef typename container_type::key_type   key_type;
 391                 typedef typename container_type::mapped_type    mapped_type;
 392                 typedef typename container_type::iterator       iterator        ;   ///< container iterator
 393                 typedef typename container_type::const_iterator const_iterator  ;   ///< container const iterator
 394
 395                 static bool const has_find_with = false;
 396                 static bool const has_erase_with = false;
 397
 398             private:
 399                 typedef typename cds::opt::select<
 400                     typename cds::opt::value<
 401                     typename cds::opt::find_option<
 402                         cds::opt::copy_policy< cds::container::striped_set::move_item >
 403                         , Options...
 404                     >::type
 405                     >::copy_policy
 406                     , cds::container::striped_set::copy_item, copy_item_policy<container_type>
 407                     , cds::container::striped_set::swap_item, swap_item_policy<container_type>
 408                     , cds::container::striped_set::move_item, move_item_policy<container_type>
 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                         f( *res.first );
 421                     return res.second;
 422                 }
 423
 424                 template <typename Q, typename... Args>
 425                 bool emplace( Q&& key, Args&&... args )
 426                 {
 427                     std::pair<iterator, bool> res = m_Map.emplace( std::forward<Q>(key), std::move( mapped_type( std::forward<Args>(args)...)));
 428                     return res.second;
 429                 }
 430
 431                 template <typename Q, typename Func>
 432                 std::pair<bool, bool> ensure( const Q& val, Func func )
 433                 {
 434                     std::pair<iterator, bool> res = m_Map.insert( value_type( val, mapped_type() ));
 435                     func( res.second, *res.first );
 436                     return std::make_pair( true, res.second );
 437                 }
 438
 439                 template <typename Q, typename Func>
 440                 bool erase( const Q& key, Func f )
 441                 {
 442                     iterator it = m_Map.find( key_type(key) );
 443                     if ( it == m_Map.end() )
 444                         return false;
 445                     f( *it );
 446                     m_Map.erase( it );
 447                     return true;
 448                 }
 449
 450                 template <typename Q, typename Func>
 451                 bool find( Q& val, Func f )
 452                 {
 453                     iterator it = m_Map.find( key_type(val) );
 454                     if ( it == m_Map.end() )
 455                         return false;
 456                     f( *it, val );
 457                     return true;
 458                 }
 459
 460                 void clear()
 461                 {
 462                     m_Map.clear();
 463                 }
 464
 465                 iterator begin()                { return m_Map.begin(); }
 466                 const_iterator begin() const    { return m_Map.begin(); }
 467                 iterator end()                  { return m_Map.end(); }
 468                 const_iterator end() const      { return m_Map.end(); }
 469
 470                 void move_item( adapted_container& /*from*/, iterator itWhat )
 471                 {
 472                     assert( m_Map.find( itWhat->first ) == m_Map.end() );
 473                     copy_item()( m_Map, itWhat );
 474                 }
 475
 476                 size_t size() const
 477                 {
 478                     return m_Map.size();
 479                 }
 480             };
 481
 482         } // namespace details
 483         //@endcond
 484
 485     }   // namespace striped_set
 486 }} // namespace cds::container
 487
 488
 489 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_ADAPTER_H