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