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.
  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
 181         using cds::intrusive::striped_set::load_factor_resizing;
 182         using cds::intrusive::striped_set::single_bucket_size_threshold;
 183         using cds::intrusive::striped_set::no_resizing;
 184
 185         using cds::intrusive::striped_set::striping;
 186         using cds::intrusive::striped_set::refinable;
 187         //@endcond
 188
 189         //@cond
 190         namespace details {
 191
 192             template <class Set>
 193             struct boost_set_copy_policies
 194             {
 195                 struct copy_item_policy
 196                 {
 197                     typedef Set set_type;
 198                     typedef typename set_type::iterator iterator;
 199
 200                     void operator()( set_type& set, iterator itWhat )
 201                     {
 202                         set.insert( *itWhat );
 203                     }
 204                 };
 205
 206                 typedef copy_item_policy swap_item_policy;
 207
 208               struct move_item_policy
 209                 {
 210                     typedef Set set_type;
 211                     typedef typename set_type::iterator iterator;
 212
 213                     void operator()( set_type& set, iterator itWhat )
 214                     {
 215                         set.insert( std::move( *itWhat ) );
 216                     }
 217                 };
 218             };
 219
 220             template <class Set, typename... Options>
 221             class boost_set_adapter: public striped_set::adapted_container
 222             {
 223             public:
 224                 typedef Set container_type;
 225
 226                 typedef typename container_type::value_type     value_type      ;   ///< value type stored in the container
 227                 typedef typename container_type::iterator       iterator        ;   ///< container iterator
 228                 typedef typename container_type::const_iterator const_iterator  ;   ///< container const iterator
 229
 230                 static bool const has_find_with = false;
 231                 static bool const has_erase_with = false;
 232
 233             private:
 234                 typedef typename cds::opt::select<
 235                     typename cds::opt::value<
 236                         typename cds::opt::find_option<
 237                             cds::opt::copy_policy< cds::container::striped_set::move_item >
 238                             , Options...
 239                         >::type
 240                     >::copy_policy
 241                     , cds::container::striped_set::copy_item, copy_item_policy<container_type>
 242                     , cds::container::striped_set::swap_item, swap_item_policy<container_type>
 243                     , cds::container::striped_set::move_item, move_item_policy<container_type>
 244                 >::type copy_item;
 245
 246             private:
 247                 container_type  m_Set;
 248
 249             public:
 250                 boost_set_adapter()
 251                 {}
 252
 253                 container_type& base_container()
 254                 {
 255                     return m_Set;
 256                 }
 257
 258                 template <typename Q, typename Func>
 259                 bool insert( const Q& val, Func f )
 260                 {
 261                     std::pair<iterator, bool> res = m_Set.insert( value_type(val) );
 262                     if ( res.second )
 263                         f( const_cast<value_type&>(*res.first) );
 264                     return res.second;
 265                 }
 266
 267                 template <typename... Args>
 268                 bool emplace( Args&&... args )
 269                 {
 270                     std::pair<iterator, bool> res = m_Set.emplace( std::forward<Args>(args)... );
 271                     return res.second;
 272                 }
 273
 274                 template <typename Q, typename Func>
 275                 std::pair<bool, bool> ensure( const Q& val, Func func )
 276                 {
 277                     std::pair<iterator, bool> res = m_Set.insert( value_type(val) );
 278                     func( res.second, const_cast<value_type&>(*res.first), val );
 279                     return std::make_pair( true, res.second );
 280                 }
 281
 282                 template <typename Q, typename Func>
 283                 bool erase( const Q& key, Func f )
 284                 {
 285                     const_iterator it = m_Set.find( value_type(key) );
 286                     if ( it == m_Set.end() )
 287                         return false;
 288                     f( const_cast<value_type&>(*it) );
 289                     m_Set.erase( it );
 290                     return true;
 291                 }
 292
 293                 template <typename Q, typename Func>
 294                 bool find( Q& val, Func f )
 295                 {
 296                     iterator it = m_Set.find( value_type(val) );
 297                     if ( it == m_Set.end() )
 298                         return false;
 299                     f( const_cast<value_type&>(*it), val );
 300                     return true;
 301                 }
 302
 303                 void clear()
 304                 {
 305                     m_Set.clear();
 306                 }
 307
 308                 iterator begin()                { return m_Set.begin(); }
 309                 const_iterator begin() const    { return m_Set.begin(); }
 310                 iterator end()                  { return m_Set.end(); }
 311                 const_iterator end() const      { return m_Set.end(); }
 312
 313                 void move_item( adapted_container& /*from*/, iterator itWhat )
 314                 {
 315                     assert( m_Set.find( *itWhat ) == m_Set.end() );
 316                     copy_item()( m_Set, itWhat );
 317                 }
 318
 319                 size_t size() const
 320                 {
 321                     return m_Set.size();
 322                 }
 323             };
 324
 325             template <class Map>
 326             struct boost_map_copy_policies {
 327                 struct copy_item_policy {
 328                     typedef Map map_type;
 329                     typedef typename map_type::value_type pair_type;
 330                     typedef typename map_type::iterator    iterator;
 331
 332                     void operator()( map_type& map, iterator itWhat )
 333                     {
 334                         map.insert( *itWhat );
 335                     }
 336                 };
 337
 338                 struct swap_item_policy {
 339                     typedef Map map_type;
 340                     typedef typename map_type::value_type pair_type;
 341                     typedef typename map_type::iterator    iterator;
 342
 343                     void operator()( map_type& map, iterator itWhat )
 344                     {
 345                         std::pair< iterator, bool > ret = map.insert( pair_type( itWhat->first, typename pair_type::second_type() ));
 346                         assert( ret.second )    ;   // successful insertion
 347                         std::swap( ret.first->second, itWhat->second );
 348                     }
 349                 };
 350
 351                 struct move_item_policy {
 352                     typedef Map map_type;
 353                     typedef typename map_type::value_type pair_type;
 354                     typedef typename map_type::iterator    iterator;
 355
 356                     void operator()( map_type& map, iterator itWhat  )
 357                     {
 358                         map.insert( std::move( *itWhat ) );
 359                     }
 360                 };
 361             };
 362
 363             template <class Map, typename... Options>
 364             class boost_map_adapter: public striped_set::adapted_container
 365             {
 366             public:
 367                 typedef Map container_type;
 368
 369                 typedef typename container_type::value_type value_type  ;   ///< value type stored in the container
 370                 typedef typename container_type::key_type   key_type;
 371                 typedef typename container_type::mapped_type    mapped_type;
 372                 typedef typename container_type::iterator       iterator        ;   ///< container iterator
 373                 typedef typename container_type::const_iterator const_iterator  ;   ///< container const iterator
 374
 375                 static bool const has_find_with = false;
 376                 static bool const has_erase_with = false;
 377
 378             private:
 379                 typedef typename cds::opt::select<
 380                     typename cds::opt::value<
 381                     typename cds::opt::find_option<
 382                         cds::opt::copy_policy< cds::container::striped_set::move_item >
 383                         , Options...
 384                     >::type
 385                     >::copy_policy
 386                     , cds::container::striped_set::copy_item, copy_item_policy<container_type>
 387                     , cds::container::striped_set::swap_item, swap_item_policy<container_type>
 388                     , cds::container::striped_set::move_item, move_item_policy<container_type>
 389                 >::type copy_item;
 390
 391             private:
 392                 container_type  m_Map;
 393
 394             public:
 395                 template <typename Q, typename Func>
 396                 bool insert( const Q& key, Func f )
 397                 {
 398                     std::pair<iterator, bool> res = m_Map.insert( value_type( key, mapped_type() ) );
 399                     if ( res.second )
 400                         f( *res.first );
 401                     return res.second;
 402                 }
 403
 404                 template <typename Q, typename... Args>
 405                 bool emplace( Q&& key, Args&&... args )
 406                 {
 407                     std::pair<iterator, bool> res = m_Map.emplace( std::forward<Q>(key), std::move( mapped_type( std::forward<Args>(args)...)));
 408                     return res.second;
 409                 }
 410
 411                 template <typename Q, typename Func>
 412                 std::pair<bool, bool> ensure( const Q& val, Func func )
 413                 {
 414                     std::pair<iterator, bool> res = m_Map.insert( value_type( val, mapped_type() ));
 415                     func( res.second, *res.first );
 416                     return std::make_pair( true, res.second );
 417                 }
 418
 419                 template <typename Q, typename Func>
 420                 bool erase( const Q& key, Func f )
 421                 {
 422                     iterator it = m_Map.find( key_type(key) );
 423                     if ( it == m_Map.end() )
 424                         return false;
 425                     f( *it );
 426                     m_Map.erase( it );
 427                     return true;
 428                 }
 429
 430                 template <typename Q, typename Func>
 431                 bool find( Q& val, Func f )
 432                 {
 433                     iterator it = m_Map.find( key_type(val) );
 434                     if ( it == m_Map.end() )
 435                         return false;
 436                     f( *it, val );
 437                     return true;
 438                 }
 439
 440                 void clear()
 441                 {
 442                     m_Map.clear();
 443                 }
 444
 445                 iterator begin()                { return m_Map.begin(); }
 446                 const_iterator begin() const    { return m_Map.begin(); }
 447                 iterator end()                  { return m_Map.end(); }
 448                 const_iterator end() const      { return m_Map.end(); }
 449
 450                 void move_item( adapted_container& /*from*/, iterator itWhat )
 451                 {
 452                     assert( m_Map.find( itWhat->first ) == m_Map.end() );
 453                     copy_item()( m_Map, itWhat );
 454                 }
 455
 456                 size_t size() const
 457                 {
 458                     return m_Map.size();
 459                 }
 460             };
 461
 462         } // namespace details
 463         //@endcond
 464
 465     }   // namespace striped_set
 466 }} // namespace cds::container
 467
 468
 469 #endif // #ifndef __CDS_CONTAINER_STRIPED_SET_ADAPTER_H