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