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