cds/intrusive/striped_set/adapter.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_STRIPED_SET_ADAPTER_H
   4 #define __CDS_INTRUSIVE_STRIPED_SET_ADAPTER_H
   5
   6 #include <cds/opt/options.h>
   7 #include <cds/intrusive/striped_set/resizing_policy.h>
   8 #include <cds/opt/hash.h>
   9 #include <cds/opt/compare.h>    // cds::opt::details::make_comparator - for some adapt specializations
  10 #include <cds/ref.h>
  11
  12 namespace cds { namespace intrusive {
  13
  14     /// StripedSet related definitions
  15     namespace striped_set {
  16
  17         /// Default adapter for intrusive striped/refinable hash set
  18         /**
  19             By default, the metafunction does not make any transformation for container type \p Container.
  20             \p Container should provide interface suitable for the hash set.
  21
  22             The \p SetOptions template argument contains option pack
  23             that has been passed to cds::intrusive::StripedSet.
  24
  25         <b>Bucket interface</b>
  26
  27             The result of metafunction is a container (a bucket) that should support the following interface:
  28
  29             Public typedefs that the bucket should provide:
  30                 - \p value_type - the type of the item in the bucket
  31                 - \p iterator - bucket's item iterator
  32                 - \p const_iterator - bucket's item constant iterator
  33                 - \p default_resizing_policy - default resizing policy preferable for the container.
  34                     By default, the library defines cds::container::striped_set::load_factor_resizing<4> for sequential containers like
  35                     boost::intrusive::list,  and cds::container::striped_set::no_resizing for ordered container like boost::intrusive::set.
  36
  37             <b>Insert value \p val of type \p Q</b>
  38             \code template <typename Func> bool insert( value_type& val, Func f ) ; \endcode
  39                 Inserts \p val into the container and, if inserting is successful, calls functor \p f
  40                 with \p val.
  41
  42                 The functor signature is:
  43                 \code
  44                 struct functor {
  45                     void operator()( value_type& item );
  46                 };
  47                 \endcode
  48                 where \p item is the item inserted.
  49
  50                 The user-defined functor \p f is called only if the inserting is success. It can be passed by reference
  51                 using <tt>boost::ref</tt>
  52                 <hr>
  53
  54             <b>Ensures that the \p item exists in the container</b>
  55             \code template <typename Func> std::pair<bool, bool> ensure( value_type& val, Func f ) \endcode
  56                 The operation performs inserting or changing data.
  57
  58                 If the \p val key not found in the container, then \p val is inserted.
  59                 Otherwise, the functor \p f is called with the item found.
  60
  61                 The \p Func functor has the following interface:
  62                 \code
  63                     void func( bool bNew, value_type& item, value_type& val );
  64                 \endcode
  65                 or like a functor:
  66                 \code
  67                     struct functor {
  68                         void operator()( bool bNew, value_type& item, value_type& val );
  69                     };
  70                 \endcode
  71
  72                 where arguments are:
  73                 - \p bNew - \p true if the item has been inserted, \p false otherwise
  74                 - \p item - container's item
  75                 - \p val - argument \p val passed into the \p ensure function
  76
  77                 If \p val has been inserted (i.e. <tt>bNew == true</tt>) then \p item and \p val
  78                 are the same element: <tt>&item == &val</tt>. Otherwise, they are different.
  79
  80                 The functor can change non-key fields of the \p item.
  81
  82                 You can pass \p f argument by reference using <tt>boost::ref</tt>.
  83
  84                 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
  85                 \p second is true if new item has been added or \p false if the item with \p val key
  86                 already exists.
  87                 <hr>
  88
  89             <b>Unlink an item</b>
  90             \code bool unlink( value_type& val ) \endcode
  91                 Unlink \p val from the container if \p val belongs to it.
  92                 <hr>
  93
  94             <b>Erase \p key</b>
  95             \code template <typename Q, typename Func> bool erase( Q const& key, Func f ) \endcode
  96                 The function searches an item with key \p key, calls \p f functor
  97                 and erases the item. If \p key is not found, the functor is not called.
  98
  99                 The functor \p Func interface is:
 100                 \code
 101                 struct functor {
 102                     void operator()(value_type& val);
 103                 };
 104                 \endcode
 105                 The functor can be passed by reference using <tt>boost:ref</tt>
 106
 107                 The type \p Q can differ from \ref value_type of items storing in the container.
 108                 Therefore, the \p value_type should be comparable with type \p Q.
 109
 110                 Return \p true if key is found and deleted, \p false otherwise
 111                 <hr>
 112
 113
 114             <b>Find the key \p val </b>
 115             \code
 116             template <typename Q, typename Func> bool find( Q& val, Func f )
 117             template <typename Q, typename Compare, typename Func> bool find( Q& val, Compare cmp, Func f )
 118             \endcode
 119                 The function searches the item with key equal to \p val and calls the functor \p f for item found.
 120                 The interface of \p Func functor is:
 121                 \code
 122                 struct functor {
 123                     void operator()( value_type& item, Q& val );
 124                 };
 125                 \endcode
 126                 where \p item is the item found, \p val is the <tt>find</tt> function argument.
 127
 128                 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 129
 130                 The functor can change non-key fields of \p item.
 131                 The \p val argument may be non-const since it can be used as \p f functor destination i.e., the functor
 132                 can modify both arguments.
 133
 134                 The type \p Q can differ from \ref value_type of items storing in the container.
 135                 Therefore, the \p value_type should be comparable with type \p Q.
 136
 137                 The first form uses default \p compare function used for key ordering.
 138                 The second form allows to point specific \p Compare functor \p cmp
 139                 that can compare \p value_typwe and \p Q type. The interface of \p Compare is the same as \p std::less.
 140
 141                 The function returns \p true if \p val is found, \p false otherwise.
 142                 <hr>
 143
 144             <b>Clears the container</b>
 145             \code
 146             void clear()
 147             template <typename Disposer> void clear( Disposer disposer )
 148             \endcode
 149             Second form calls \p disposer for each item in the container before clearing.
 150             <hr>
 151
 152             <b>Get size of bucket</b>
 153             \code size_t size() const \endcode
 154             This function may be required by some resizing policy
 155             <hr>
 156
 157             <b>Iterators</b>
 158             \code
 159             iterator begin();
 160             const_iterator begin() const;
 161             iterator end();
 162             const_iterator end() const;
 163             \endcode
 164             <hr>
 165
 166             <b>Move item when resizing</b>
 167             \code void move_item( adapted_container& from, iterator it ) \endcode
 168                 This helper function is invented for the set resizing when the item
 169                 pointed by \p it iterator is copied from old bucket \p from to a new bucket
 170                 pointed by \p this.
 171             <hr>
 172
 173         */
 174         template < typename Container, CDS_DECL_OPTIONS >
 175         class adapt
 176         {
 177         public:
 178             typedef Container   type            ;   ///< adapted container type
 179             typedef typename type::value_type value_type  ;   ///< value type stored in the container
 180         };
 181
 182         //@cond
 183         struct adapted_sequential_container
 184         {
 185             typedef striped_set::load_factor_resizing<4>   default_resizing_policy;
 186         };
 187
 188         struct adapted_container
 189         {
 190             typedef striped_set::no_resizing   default_resizing_policy;
 191         };
 192         //@endcond
 193
 194         //@cond
 195         namespace details {
 196             template <typename Set>
 197             class boost_intrusive_set_adapter: public cds::intrusive::striped_set::adapted_container
 198             {
 199             public:
 200                 typedef Set container_type;
 201
 202                 typedef typename container_type::value_type     value_type      ;   ///< value type stored in the container
 203                 typedef typename container_type::iterator       iterator        ;   ///< container iterator
 204                 typedef typename container_type::const_iterator const_iterator  ;   ///< container const iterator
 205
 206                 typedef typename container_type::value_compare  key_comparator;
 207
 208             private:
 209 #       ifndef CDS_CXX11_LAMBDA_SUPPORT
 210                 struct empty_insert_functor {
 211                     void operator()( value_type& )
 212                     {}
 213                 };
 214 #       endif
 215
 216                 container_type  m_Set;
 217
 218             public:
 219                 boost_intrusive_set_adapter()
 220                 {}
 221
 222                 container_type& base_container()
 223                 {
 224                     return m_Set;
 225                 }
 226
 227                 template <typename Func>
 228                 bool insert( value_type& val, Func f )
 229                 {
 230                     std::pair<iterator, bool> res = m_Set.insert( val );
 231                     if ( res.second )
 232                         cds::unref(f)( val );
 233                     return res.second;
 234                 }
 235
 236                 template <typename Func>
 237                 std::pair<bool, bool> ensure( value_type& val, Func f )
 238                 {
 239                     std::pair<iterator, bool> res = m_Set.insert( val );
 240                     cds::unref(f)( res.second, *res.first, val );
 241                     return std::make_pair( true, res.second );
 242                 }
 243
 244                 bool unlink( value_type& val )
 245                 {
 246                     iterator it = m_Set.find( value_type(val) );
 247                     if ( it == m_Set.end() || &(*it) != &val )
 248                         return false;
 249                     m_Set.erase( it );
 250                     return true;
 251                 }
 252
 253                 template <typename Q, typename Func>
 254                 value_type * erase( Q const& key, Func f )
 255                 {
 256                     iterator it = m_Set.find( key, key_comparator() );
 257                     if ( it == m_Set.end() )
 258                         return null_ptr<value_type *>();
 259                     value_type& val = *it;
 260                     cds::unref(f)( val );
 261                     m_Set.erase( it );
 262                     return &val;
 263                 }
 264
 265                 template <typename Q, typename Less, typename Func>
 266                 value_type * erase( Q const& key, Less pred, Func f )
 267                 {
 268                     iterator it = m_Set.find( key, pred );
 269                     if ( it == m_Set.end() )
 270                         return null_ptr<value_type *>();
 271                     value_type& val = *it;
 272                     cds::unref(f)( val );
 273                     m_Set.erase( it );
 274                     return &val;
 275                 }
 276
 277                 template <typename Q, typename Func>
 278                 bool find( Q& key, Func f )
 279                 {
 280                     return find( key, key_comparator(), f );
 281                 }
 282
 283                 template <typename Q, typename Compare, typename Func>
 284                 bool find( Q& key, Compare cmp, Func f )
 285                 {
 286                     iterator it = m_Set.find( key, cmp );
 287                     if ( it == m_Set.end() )
 288                         return false;
 289                     cds::unref(f)( *it, key );
 290                     return true;
 291                 }
 292
 293                 void clear()
 294                 {
 295                     m_Set.clear();
 296                 }
 297
 298                 template <typename Disposer>
 299                 void clear( Disposer disposer )
 300                 {
 301                     m_Set.clear_and_dispose( disposer );
 302                 }
 303
 304                 iterator begin()                { return m_Set.begin(); }
 305                 const_iterator begin() const    { return m_Set.begin(); }
 306                 iterator end()                  { return m_Set.end(); }
 307                 const_iterator end() const      { return m_Set.end(); }
 308
 309                 size_t size() const
 310                 {
 311                     return (size_t) m_Set.size();
 312                 }
 313
 314                 void move_item( boost_intrusive_set_adapter& from, iterator itWhat )
 315                 {
 316                     value_type& val = *itWhat;
 317                     from.base_container().erase( itWhat );
 318 #           ifdef CDS_CXX11_LAMBDA_SUPPORT
 319                     insert( val, []( value_type& ) {} );
 320 #           else
 321                     insert( val, empty_insert_functor() );
 322 #           endif
 323                 }
 324             };
 325         }   // namespace details
 326         //@endcond
 327
 328     } // namespace striped_set
 329 }} // namespace cds::intrusive
 330
 331 //@cond
 332 #if defined(CDS_CXX11_VARIADIC_TEMPLATE_SUPPORT) && defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 333 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS3    typename... BIOptions
 334 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS4    typename... BIOptions
 335 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS5    typename... BIOptions
 336 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS6    typename... BIOptions
 337 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS7    typename... BIOptions
 338 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS8    typename... BIOptions
 339 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS9    typename... BIOptions
 340 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS10    typename... BIOptions
 341
 342 #   define CDS_BOOST_INTRUSIVE_OPTIONS3    BIOptions...
 343 #   define CDS_BOOST_INTRUSIVE_OPTIONS4    BIOptions...
 344 #   define CDS_BOOST_INTRUSIVE_OPTIONS5    BIOptions...
 345 #   define CDS_BOOST_INTRUSIVE_OPTIONS6    BIOptions...
 346 #   define CDS_BOOST_INTRUSIVE_OPTIONS7    BIOptions...
 347 #   define CDS_BOOST_INTRUSIVE_OPTIONS8    BIOptions...
 348 #   define CDS_BOOST_INTRUSIVE_OPTIONS9    BIOptions...
 349 #   define CDS_BOOST_INTRUSIVE_OPTIONS10    BIOptions...
 350 #else
 351 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS3    typename BIO1, typename BIO2, typename BIO3
 352 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS4    CDS_BOOST_INTRUSIVE_DECL_OPTIONS3, typename BIO4
 353 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS5    CDS_BOOST_INTRUSIVE_DECL_OPTIONS4, typename BIO5
 354 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS6    CDS_BOOST_INTRUSIVE_DECL_OPTIONS5, typename BIO6
 355 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS7    CDS_BOOST_INTRUSIVE_DECL_OPTIONS6, typename BIO7
 356 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS8    CDS_BOOST_INTRUSIVE_DECL_OPTIONS7, typename BIO8
 357 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS9    CDS_BOOST_INTRUSIVE_DECL_OPTIONS8, typename BIO9
 358 #   define CDS_BOOST_INTRUSIVE_DECL_OPTIONS10   CDS_BOOST_INTRUSIVE_DECL_OPTIONS9, typename BIO10
 359
 360 #   define CDS_BOOST_INTRUSIVE_OPTIONS3    BIO1,BIO2,BIO3
 361 #   define CDS_BOOST_INTRUSIVE_OPTIONS4    CDS_BOOST_INTRUSIVE_OPTIONS3, BIO4
 362 #   define CDS_BOOST_INTRUSIVE_OPTIONS5    CDS_BOOST_INTRUSIVE_OPTIONS4, BIO5
 363 #   define CDS_BOOST_INTRUSIVE_OPTIONS6    CDS_BOOST_INTRUSIVE_OPTIONS5, BIO6
 364 #   define CDS_BOOST_INTRUSIVE_OPTIONS7    CDS_BOOST_INTRUSIVE_OPTIONS6, BIO7
 365 #   define CDS_BOOST_INTRUSIVE_OPTIONS8    CDS_BOOST_INTRUSIVE_OPTIONS7, BIO8
 366 #   define CDS_BOOST_INTRUSIVE_OPTIONS9    CDS_BOOST_INTRUSIVE_OPTIONS8, BIO9
 367 #   define CDS_BOOST_INTRUSIVE_OPTIONS10   CDS_BOOST_INTRUSIVE_OPTIONS9, BIO10
 368 #endif
 369 //@endcond
 370
 371 #endif // #ifndef __CDS_INTRUSIVE_STRIPED_SET_ADAPTER_H