cds/container/striped_set/adapter.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_CONTAINER_STRIPED_SET_ADAPTER_H
  32 #define CDSLIB_CONTAINER_STRIPED_SET_ADAPTER_H
  33
  34 #include <cds/intrusive/striped_set/adapter.h>
  35 #include <cds/intrusive/striped_set/striping_policy.h>
  36
  37 namespace cds { namespace container {
  38     /// Striped hash set related definitions
  39     namespace striped_set {
  40
  41         //@cond
  42         struct copy_item    ;   // copy_item_policy tag
  43         template <typename Container>
  44         struct copy_item_policy;
  45
  46         struct swap_item    ;   // swap_item_policy tag
  47         template <typename Container>
  48         struct swap_item_policy;
  49
  50         struct move_item    ;   // move_item_policy tag
  51         template <typename Container>
  52         struct move_item_policy;
  53         //@endcond
  54
  55 #ifdef CDS_DOXYGEN_INVOKED
  56         /// Default adapter for hash set
  57         /**
  58             By default, the metafunction does not make any transformation for container type \p Container.
  59             \p Container should provide interface suitable for the hash set.
  60
  61             The \p Options template argument contains a list of options
  62             that has been passed to cds::container::StripedSet.
  63
  64         <b>Bucket interface</b>
  65
  66             The result of metafunction is a container (a bucket) that should support the following interface:
  67
  68             Public typedefs that the bucket should provide:
  69                 - \p value_type - the type of the item in the bucket
  70                 - \p iterator - bucket's item iterator
  71                 - \p const_iterator - bucket's item constant iterator
  72                 - \p default_resizing_policy - defalt resizing policy preferable for the container.
  73                     By default, the library defines striped_set::load_factor_resizing<4> for sequential containers like
  74                     std::list, std::vector, and striped_set::no_resizing for ordered container like std::set,
  75                     std::unordered_set.
  76
  77             <b>Insert value \p val of type \p Q</b>
  78             \code template <typename Q, typename Func> bool insert( const Q& val, Func f ) ; \endcode
  79                 The function allows to split creating of new item into two part:
  80                 - create item with key only from \p val
  81                 - try to insert new item into the container
  82                 - if inserting is success, calls \p f functor to initialize value-field of the new item.
  83
  84                 The functor signature is:
  85                 \code
  86                     void func( value_type& item );
  87                 \endcode
  88                 where \p item is the item inserted.
  89
  90                 The type \p Q can differ from \ref value_type of items storing in the container.
  91                 Therefore, the \p value_type should be comparable with type \p Q and constructible from type \p Q,
  92
  93                 The user-defined functor is called only if the inserting is success.
  94                 <hr>
  95
  96             <b>Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt></b>
  97             \code template <typename... Args> bool emplace( Args&&... args ) ; \endcode
  98                 Returns \p true if inserting successful, \p false otherwise.
  99
 100                 This function should be available only for compiler that supports
 101                 variadic template and move semantics
 102             <hr>
 103
 104             <b>Updates \p item</b>
 105             \code template <typename Q, typename Func> std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert ) \endcode
 106                 The operation performs inserting or changing data.
 107
 108                 If the \p val key not found in the container, then the new item created from \p val
 109                 is inserted iff \p bAllowInsert is \p true. Otherwise, the functor \p func is called with the item found.
 110                 The \p Func functor has interface:
 111                 \code
 112                     void func( bool bNew, value_type& item, const Q& val );
 113                 \endcode
 114                 or like a functor:
 115                 \code
 116                     struct my_functor {
 117                         void operator()( bool bNew, value_type& item, const Q& val );
 118                     };
 119                 \endcode
 120
 121                 where arguments are:
 122                 - \p bNew - \p true if the item has been inserted, \p false otherwise
 123                 - \p item - container's item
 124                 - \p val - argument \p val passed into the \p update() function
 125
 126                 The functor can change non-key fields of the \p item.
 127
 128                 The type \p Q can differ from \ref value_type of items storing in the container.
 129                 Therefore, the \p value_type should be comparable with type \p Q and constructible from type \p Q,
 130
 131                 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 132                 \p second is true if new item has been added or \p false if the item with \p val key
 133                 already exists.
 134                 <hr>
 135
 136
 137             <b>Delete \p key</b>
 138             \code template <typename Q, typename Func> bool erase( const Q& key, Func f ) \endcode
 139                 The function searches an item with key \p key, calls \p f functor
 140                 and deletes the item. If \p key is not found, the functor is not called.
 141
 142                 The functor \p Func interface is:
 143                 \code
 144                 struct extractor {
 145                     void operator()(value_type const& val);
 146                 };
 147                 \endcode
 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                 Return \p true if key is found and deleted, \p false otherwise
 153                 <hr>
 154
 155
 156             <b>Find the key \p val </b>
 157             \code template <typename Q, typename Func> bool find( Q& val, Func f ) \endcode
 158                 The function searches the item with key equal to \p val and calls the functor \p f for item found.
 159                 The interface of \p Func functor is:
 160                 \code
 161                 struct functor {
 162                     void operator()( value_type& item, Q& val );
 163                 };
 164                 \endcode
 165                 where \p item is the item found, \p val is the <tt>find</tt> function argument.
 166
 167                 The functor can change non-key fields of \p item.
 168                 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 169                 can modify both arguments.
 170
 171                 The type \p Q can differ from \ref value_type of items storing in the container.
 172                 Therefore, the \p value_type should be comparable with type \p Q.
 173
 174                 The function returns \p true if \p val is found, \p false otherwise.
 175                 <hr>
 176
 177             <b>Clears the container</b>
 178             \code void clear() \endcode
 179             <hr>
 180
 181             <b>Get size of bucket</b>
 182             \code size_t size() const \endcode
 183             This function can be required by some resizing policy
 184             <hr>
 185
 186             <b>Move item when resizing</b>
 187             \code void move_item( adapted_container& from, iterator it ) \endcode
 188             This helper function is invented for the set resizing when the item
 189             pointed by \p it iterator is copied from an old bucket \p from to a new bucket
 190             pointed by \p this.
 191             <hr>
 192
 193         */
 194         template < typename Container, typename... Options>
 195         class adapt
 196         {
 197         public:
 198             typedef Container   type            ;   ///< adapted container type
 199             typedef typename type::value_type value_type  ;   ///< value type stored in the container
 200         };
 201 #else   // CDS_DOXYGEN_INVOKED
 202         using cds::intrusive::striped_set::adapt;
 203 #endif
 204
 205         //@cond
 206         using cds::intrusive::striped_set::adapted_sequential_container;
 207         using cds::intrusive::striped_set::adapted_container;
 208         //@endcond
 209
 210         ///@copydoc cds::intrusive::striped_set::load_factor_resizing
 211         template <size_t LoadFactor>
 212         using load_factor_resizing = cds::intrusive::striped_set::load_factor_resizing<LoadFactor>;
 213
 214         ///@copydoc cds::intrusive::striped_set::rational_load_factor_resizing
 215         template <size_t Numerator, size_t Denominator = 1>
 216         using rational_load_factor_resizing = cds::intrusive::striped_set::rational_load_factor_resizing<Numerator, Denominator>;
 217
 218         ///@copydoc cds::intrusive::striped_set::single_bucket_size_threshold
 219         template <size_t Threshold>
 220         using single_bucket_size_threshold = cds::intrusive::striped_set::single_bucket_size_threshold<Threshold>;
 221
 222         ///@copydoc cds::intrusive::striped_set::no_resizing
 223         typedef cds::intrusive::striped_set::no_resizing no_resizing;
 224
 225         ///@copydoc cds::intrusive::striped_set::striping
 226         template <class Lock = std::mutex, class Alloc = CDS_DEFAULT_ALLOCATOR >
 227         using striping = cds::intrusive::striped_set::striping<Lock, Alloc>;
 228
 229         ///@copydoc cds::intrusive::striped_set::refinable
 230         template <
 231             class RecursiveLock = std::recursive_mutex,
 232             typename BackOff = cds::backoff::yield,
 233             class Alloc = CDS_DEFAULT_ALLOCATOR
 234         >
 235         using refinable = cds::intrusive::striped_set::refinable<RecursiveLock, BackOff, Alloc >;
 236
 237         //@cond
 238         namespace details {
 239
 240             template <class Set>
 241             struct boost_set_copy_policies
 242             {
 243                 struct copy_item_policy
 244                 {
 245                     typedef Set set_type;
 246                     typedef typename set_type::iterator iterator;
 247
 248                     void operator()( set_type& set, iterator itWhat )
 249                     {
 250                         set.insert( *itWhat );
 251                     }
 252                 };
 253
 254                 typedef copy_item_policy swap_item_policy;
 255
 256               struct move_item_policy
 257                 {
 258                     typedef Set set_type;
 259                     typedef typename set_type::iterator iterator;
 260
 261                     void operator()( set_type& set, iterator itWhat )
 262                     {
 263                         set.insert( std::move( *itWhat ) );
 264                     }
 265                 };
 266             };
 267
 268             template <class Set, typename... Options>
 269             class boost_set_adapter: public striped_set::adapted_container
 270             {
 271             public:
 272                 typedef Set container_type;
 273
 274                 typedef typename container_type::value_type     value_type      ;   ///< value type stored in the container
 275                 typedef typename container_type::iterator       iterator        ;   ///< container iterator
 276                 typedef typename container_type::const_iterator const_iterator  ;   ///< container const iterator
 277
 278                 static bool const has_find_with = false;
 279                 static bool const has_erase_with = false;
 280
 281             private:
 282                 typedef typename cds::opt::select<
 283                     typename cds::opt::value<
 284                         typename cds::opt::find_option<
 285                             cds::opt::copy_policy< cds::container::striped_set::move_item >
 286                             , Options...
 287                         >::type
 288                     >::copy_policy
 289                     , cds::container::striped_set::copy_item, copy_item_policy<container_type>
 290                     , cds::container::striped_set::swap_item, swap_item_policy<container_type>
 291                     , cds::container::striped_set::move_item, move_item_policy<container_type>
 292                 >::type copy_item;
 293
 294             private:
 295                 container_type  m_Set;
 296
 297             public:
 298                 boost_set_adapter()
 299                 {}
 300
 301                 container_type& base_container()
 302                 {
 303                     return m_Set;
 304                 }
 305
 306                 template <typename Q, typename Func>
 307                 bool insert( const Q& val, Func f )
 308                 {
 309                     std::pair<iterator, bool> res = m_Set.insert( value_type(val) );
 310                     if ( res.second )
 311                         f( const_cast<value_type&>(*res.first) );
 312                     return res.second;
 313                 }
 314
 315                 template <typename... Args>
 316                 bool emplace( Args&&... args )
 317                 {
 318                     std::pair<iterator, bool> res = m_Set.emplace( std::forward<Args>(args)... );
 319                     return res.second;
 320                 }
 321
 322                 template <typename Q, typename Func>
 323                 std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert )
 324                 {
 325                     if ( bAllowInsert ) {
 326                         std::pair<iterator, bool> res = m_Set.insert( value_type(val) );
 327                         func( res.second, const_cast<value_type&>(*res.first), val );
 328                         return std::make_pair( true, res.second );
 329                     }
 330                     else {
 331                         auto it = m_Set.find( value_type( val ));
 332                         if ( it == m_Set.end() )
 333                             return std::make_pair( false, false );
 334                         func( false, const_cast<value_type&>(*it), val );
 335                         return std::make_pair( true, false );
 336                     }
 337                 }
 338
 339                 template <typename Q, typename Func>
 340                 bool erase( const Q& key, Func f )
 341                 {
 342                     const_iterator it = m_Set.find( value_type(key) );
 343                     if ( it == m_Set.end() )
 344                         return false;
 345                     f( const_cast<value_type&>(*it) );
 346                     m_Set.erase( it );
 347                     return true;
 348                 }
 349
 350                 template <typename Q, typename Func>
 351                 bool find( Q& val, Func f )
 352                 {
 353                     iterator it = m_Set.find( value_type(val) );
 354                     if ( it == m_Set.end() )
 355                         return false;
 356                     f( const_cast<value_type&>(*it), val );
 357                     return true;
 358                 }
 359
 360                 void clear()
 361                 {
 362                     m_Set.clear();
 363                 }
 364
 365                 iterator begin()                { return m_Set.begin(); }
 366                 const_iterator begin() const    { return m_Set.begin(); }
 367                 iterator end()                  { return m_Set.end(); }
 368                 const_iterator end() const      { return m_Set.end(); }
 369
 370                 void move_item( adapted_container& /*from*/, iterator itWhat )
 371                 {
 372                     assert( m_Set.find( *itWhat ) == m_Set.end() );
 373                     copy_item()( m_Set, itWhat );
 374                 }
 375
 376                 size_t size() const
 377                 {
 378                     return m_Set.size();
 379                 }
 380             };
 381
 382             template <class Map>
 383             struct boost_map_copy_policies {
 384                 struct copy_item_policy {
 385                     typedef Map map_type;
 386                     typedef typename map_type::value_type pair_type;
 387                     typedef typename map_type::iterator    iterator;
 388
 389                     void operator()( map_type& map, iterator itWhat )
 390                     {
 391                         map.insert( *itWhat );
 392                     }
 393                 };
 394
 395                 struct swap_item_policy {
 396                     typedef Map map_type;
 397                     typedef typename map_type::value_type pair_type;
 398                     typedef typename map_type::iterator    iterator;
 399
 400                     void operator()( map_type& map, iterator itWhat )
 401                     {
 402                         std::pair< iterator, bool > ret = map.insert( pair_type( itWhat->first, typename pair_type::second_type() ));
 403                         assert( ret.second )    ;   // successful insertion
 404                         std::swap( ret.first->second, itWhat->second );
 405                     }
 406                 };
 407
 408                 struct move_item_policy {
 409                     typedef Map map_type;
 410                     typedef typename map_type::value_type pair_type;
 411                     typedef typename map_type::iterator    iterator;
 412
 413                     void operator()( map_type& map, iterator itWhat  )
 414                     {
 415                         map.insert( std::move( *itWhat ) );
 416                     }
 417                 };
 418             };
 419
 420             template <class Map, typename... Options>
 421             class boost_map_adapter: public striped_set::adapted_container
 422             {
 423             public:
 424                 typedef Map container_type;
 425
 426                 typedef typename container_type::value_type value_type  ;   ///< value type stored in the container
 427                 typedef typename container_type::key_type   key_type;
 428                 typedef typename container_type::mapped_type    mapped_type;
 429                 typedef typename container_type::iterator       iterator        ;   ///< container iterator
 430                 typedef typename container_type::const_iterator const_iterator  ;   ///< container const iterator
 431
 432                 static bool const has_find_with = false;
 433                 static bool const has_erase_with = false;
 434
 435             private:
 436                 typedef typename cds::opt::select<
 437                     typename cds::opt::value<
 438                     typename cds::opt::find_option<
 439                         cds::opt::copy_policy< cds::container::striped_set::move_item >
 440                         , Options...
 441                     >::type
 442                     >::copy_policy
 443                     , cds::container::striped_set::copy_item, copy_item_policy<container_type>
 444                     , cds::container::striped_set::swap_item, swap_item_policy<container_type>
 445                     , cds::container::striped_set::move_item, move_item_policy<container_type>
 446                 >::type copy_item;
 447
 448             private:
 449                 container_type  m_Map;
 450
 451             public:
 452                 template <typename Q, typename Func>
 453                 bool insert( const Q& key, Func f )
 454                 {
 455                     std::pair<iterator, bool> res = m_Map.insert( value_type( key_type( key ), mapped_type() ) );
 456                     if ( res.second )
 457                         f( *res.first );
 458                     return res.second;
 459                 }
 460
 461                 template <typename Q, typename... Args>
 462                 bool emplace( Q&& key, Args&&... args )
 463                 {
 464                     std::pair<iterator, bool> res = m_Map.emplace( key_type( std::forward<Q>( key )), mapped_type( std::forward<Args>( args )...));
 465                     return res.second;
 466                 }
 467
 468                 template <typename Q, typename Func>
 469                 std::pair<bool, bool> update( const Q& key, Func func, bool bAllowInsert )
 470                 {
 471                     if ( bAllowInsert ) {
 472                         std::pair<iterator, bool> res = m_Map.insert( value_type( key_type( key ), mapped_type() ));
 473                         func( res.second, *res.first );
 474                         return std::make_pair( true, res.second );
 475                     }
 476                     else {
 477                         auto it = m_Map.find( key_type( key ));
 478                         if ( it == end() )
 479                             return std::make_pair( false, false );
 480                         func( false, *it );
 481                         return std::make_pair( true, false );
 482                     }
 483                 }
 484
 485                 template <typename Q, typename Func>
 486                 bool erase( const Q& key, Func f )
 487                 {
 488                     iterator it = m_Map.find( key_type( key ));
 489                     if ( it == m_Map.end() )
 490                         return false;
 491                     f( *it );
 492                     m_Map.erase( it );
 493                     return true;
 494                 }
 495
 496                 template <typename Q, typename Func>
 497                 bool find( Q& val, Func f )
 498                 {
 499                     iterator it = m_Map.find( key_type( val ));
 500                     if ( it == m_Map.end() )
 501                         return false;
 502                     f( *it, val );
 503                     return true;
 504                 }
 505
 506                 void clear()
 507                 {
 508                     m_Map.clear();
 509                 }
 510
 511                 iterator begin()                { return m_Map.begin(); }
 512                 const_iterator begin() const    { return m_Map.begin(); }
 513                 iterator end()                  { return m_Map.end(); }
 514                 const_iterator end() const      { return m_Map.end(); }
 515
 516                 void move_item( adapted_container& /*from*/, iterator itWhat )
 517                 {
 518                     assert( m_Map.find( itWhat->first ) == m_Map.end() );
 519                     copy_item()( m_Map, itWhat );
 520                 }
 521
 522                 size_t size() const
 523                 {
 524                     return m_Map.size();
 525                 }
 526             };
 527
 528         } // namespace details
 529         //@endcond
 530
 531     }   // namespace striped_set
 532 }} // namespace cds::container
 533
 534
 535 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_ADAPTER_H