cds/container/striped_set/boost_stable_vector.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_STRIPED_SET_BOOST_STABLE_VECTOR_ADAPTER_H
   4 #define __CDS_CONTAINER_STRIPED_SET_BOOST_STABLE_VECTOR_ADAPTER_H
   5
   6 #include <boost/version.hpp>
   7 #if BOOST_VERSION < 104800
   8 #   error "For boost::container::stable_vector you must use boost 1.48 or above"
   9 #endif
  10
  11 #include <cds/container/striped_set/adapter.h>
  12 #include <cds/ref.h>
  13 #include <boost/container/stable_vector.hpp>
  14 #include <algorithm>    // std::lower_bound
  15 #include <utility>      // std::pair
  16
  17 //@cond
  18 namespace cds { namespace container {
  19     namespace striped_set {
  20
  21         // Copy policy for boost::container::stable_vector
  22         template <typename T, typename Alloc>
  23         struct copy_item_policy< boost::container::stable_vector< T, Alloc > >
  24         {
  25             typedef boost::container::stable_vector< T, Alloc > vector_type;
  26             typedef typename vector_type::iterator iterator;
  27
  28             void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
  29             {
  30                 vec.insert( itInsert, *itWhat );
  31             }
  32         };
  33
  34         // Swap policy for boost::container::stable_vector
  35         template <typename T, typename Alloc>
  36         struct swap_item_policy< boost::container::stable_vector< T, Alloc > >
  37         {
  38             typedef boost::container::stable_vector< T, Alloc > vector_type;
  39             typedef typename vector_type::iterator iterator;
  40
  41             void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
  42             {
  43                 typename vector_type::value_type newVal;
  44                 itInsert = vec.insert( itInsert, newVal );
  45                 std::swap( *itInsert, *itWhat );
  46             }
  47         };
  48
  49 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
  50         // Move policy for boost::container::stable_vector
  51         template <typename T, typename Alloc>
  52         struct move_item_policy< boost::container::stable_vector< T, Alloc > >
  53         {
  54             typedef boost::container::stable_vector< T, Alloc > vector_type;
  55             typedef typename vector_type::iterator iterator;
  56
  57             void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
  58             {
  59                 vec.insert( itInsert, std::move( *itWhat ));
  60             }
  61         };
  62 #endif
  63
  64     }   // namespace striped_set
  65 }} // namespace cds::container
  66
  67 namespace cds { namespace intrusive { namespace striped_set {
  68     /// boost::container::stable_vector adapter for hash set bucket
  69     template <typename T, class Alloc, CDS_SPEC_OPTIONS>
  70     class adapt< boost::container::stable_vector<T, Alloc>, CDS_OPTIONS >
  71     {
  72     public:
  73         typedef boost::container::stable_vector<T, Alloc>     container_type          ;   ///< underlying container type
  74
  75     private:
  76         /// Adapted container type
  77         class adapted_container: public cds::container::striped_set::adapted_sequential_container
  78         {
  79         public:
  80             typedef typename container_type::value_type value_type  ;   ///< value type stored in the container
  81             typedef typename container_type::iterator      iterator ;   ///< container iterator
  82             typedef typename container_type::const_iterator const_iterator ;    ///< container const iterator
  83
  84             static bool const has_find_with = true;
  85             static bool const has_erase_with = true;
  86
  87         private:
  88             //@cond
  89             typedef typename cds::opt::details::make_comparator_from_option_list< value_type, CDS_OPTIONS >::type key_comparator;
  90
  91             typedef typename cds::opt::select<
  92                 typename cds::opt::value<
  93                     typename cds::opt::find_option<
  94                         cds::opt::copy_policy< cds::container::striped_set::move_item >
  95                         , CDS_OPTIONS
  96                     >::type
  97                 >::copy_policy
  98                 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
  99                 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
 100 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
 101                 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
 102 #endif
 103             >::type copy_item;
 104
 105             struct find_predicate
 106             {
 107                 bool operator()( value_type const& i1, value_type const& i2) const
 108                 {
 109                     return key_comparator()( i1, i2 ) < 0;
 110                 }
 111
 112                 template <typename Q>
 113                 bool operator()( Q const& i1, value_type const& i2) const
 114                 {
 115                     return key_comparator()( i1, i2 ) < 0;
 116                 }
 117
 118                 template <typename Q>
 119                 bool operator()( value_type const& i1, Q const& i2) const
 120                 {
 121                     return key_comparator()( i1, i2 ) < 0;
 122                 }
 123             };
 124             //@endcond
 125
 126         private:
 127             //@cond
 128             container_type  m_Vector;
 129             //@endcond
 130
 131         public:
 132
 133             /// Insert value \p val of type \p Q into the container
 134             /**
 135                 The function allows to split creating of new item into two part:
 136                 - create item with key only from \p val
 137                 - try to insert new item into the container
 138                 - if inserting is success, calls \p f functor to initialize value-field of the new item.
 139
 140                 The functor signature is:
 141                 \code
 142                     void func( value_type& item );
 143                 \endcode
 144                 where \p item is the item inserted.
 145
 146                 The type \p Q may differ from \ref value_type of items storing in the container.
 147                 Therefore, the \p value_type should be comparable with type \p Q and constructible from type \p Q,
 148
 149                 The user-defined functor is called only if the inserting is success. It may be passed by reference
 150                 using <tt>boost::ref</tt>
 151             */
 152             template <typename Q, typename Func>
 153             bool insert( const Q& val, Func f )
 154             {
 155                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 156                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 157                     value_type newItem( val );
 158                     it = m_Vector.insert( it, newItem );
 159                     cds::unref( f )( *it );
 160                     return true;
 161                 }
 162                 return false;
 163             }
 164
 165 #           ifdef CDS_EMPLACE_SUPPORT
 166             template <typename... Args>
 167             bool emplace( Args&&... args )
 168             {
 169                 value_type val( std::forward<Args>(args)... );
 170                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 171                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 172                     it = m_Vector.emplace( it, std::move( val ) );
 173                     return true;
 174                 }
 175                 return false;
 176             }
 177 #           endif
 178
 179             /// Ensures that the \p item exists in the container
 180             /**
 181                 The operation performs inserting or changing data.
 182
 183                 If the \p val key not found in the container, then the new item created from \p val
 184                 is inserted. Otherwise, the functor \p func is called with the item found.
 185                 The \p Func functor has interface:
 186                 \code
 187                     void func( bool bNew, value_type& item, const Q& val );
 188                 \endcode
 189                 or like a functor:
 190                 \code
 191                     struct my_functor {
 192                         void operator()( bool bNew, value_type& item, const Q& val );
 193                     };
 194                 \endcode
 195
 196                 where arguments are:
 197                 - \p bNew - \p true if the item has been inserted, \p false otherwise
 198                 - \p item - container's item
 199                 - \p val - argument \p val passed into the \p ensure function
 200
 201                 The functor may change non-key fields of the \p item.
 202
 203                 The type \p Q may differ from \ref value_type of items storing in the container.
 204                 Therefore, the \p value_type should be comparable with type \p Q and constructible from type \p Q,
 205
 206                 You may pass \p func argument by reference using <tt>boost::ref</tt>.
 207
 208                 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 209                 \p second is true if new item has been added or \p false if the item with \p val key
 210                 already exists.
 211             */
 212             template <typename Q, typename Func>
 213             std::pair<bool, bool> ensure( const Q& val, Func func )
 214             {
 215                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 216                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 217                     // insert new
 218                     value_type newItem( val );
 219                     it = m_Vector.insert( it, newItem );
 220                     cds::unref( func )( true, *it, val );
 221                     return std::make_pair( true, true );
 222                 }
 223                 else {
 224                     // already exists
 225                     cds::unref( func )( false, *it, val );
 226                     return std::make_pair( true, false );
 227                 }
 228             }
 229
 230             /// Delete \p key
 231             /**
 232                 The function searches an item with key \p key, calls \p f functor
 233                 and deletes the item. If \p key is not found, the functor is not called.
 234
 235                 The functor \p Func interface is:
 236                 \code
 237                 struct extractor {
 238                     void operator()(value_type const& val);
 239                 };
 240                 \endcode
 241                 The functor may be passed by reference using <tt>boost:ref</tt>
 242
 243                 The type \p Q may differ from \ref value_type of items storing in the container.
 244                 Therefore, the \p value_type should be comparable with type \p Q.
 245
 246                 Return \p true if key is found and deleted, \p false otherwise
 247             */
 248             template <typename Q, typename Func>
 249             bool erase( const Q& key, Func f )
 250             {
 251                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, find_predicate() );
 252                 if ( it == m_Vector.end() || key_comparator()( key, *it ) != 0 )
 253                     return false;
 254
 255                 // key exists
 256                 cds::unref( f )( *it );
 257                 m_Vector.erase( it );
 258                 return true;
 259             }
 260
 261             template <typename Q, typename Less, typename Func>
 262             bool erase( const Q& key, Less pred, Func f )
 263             {
 264                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, pred );
 265                 if ( it == m_Vector.end() || pred( key, *it ) || pred( *it, key ) )
 266                     return false;
 267
 268                 // key exists
 269                 cds::unref( f )( *it );
 270                 m_Vector.erase( it );
 271                 return true;
 272             }
 273
 274             /// Find the key \p val
 275             /**
 276                 The function searches the item with key equal to \p val and calls the functor \p f for item found.
 277                 The interface of \p Func functor is:
 278                 \code
 279                 struct functor {
 280                     void operator()( value_type& item, Q& val );
 281                 };
 282                 \endcode
 283                 where \p item is the item found, \p val is the <tt>find</tt> function argument.
 284
 285                 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 286
 287                 The functor may change non-key fields of \p item.
 288                 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 289                 may modify both arguments.
 290
 291                 The type \p Q may differ from \ref value_type of items storing in the container.
 292                 Therefore, the \p value_type should be comparable with type \p Q.
 293
 294                 The function returns \p true if \p val is found, \p false otherwise.
 295             */
 296             template <typename Q, typename Func>
 297             bool find( Q& val, Func f )
 298             {
 299                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 300                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 )
 301                     return false;
 302
 303                 // key exists
 304                 cds::unref( f )( *it, val );
 305                 return true;
 306             }
 307
 308             template <typename Q, typename Less, typename Func>
 309             bool find( Q& val, Less pred, Func f )
 310             {
 311                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, pred );
 312                 if ( it == m_Vector.end() || pred( val, *it ) || pred( *it, val ) )
 313                     return false;
 314
 315                 // key exists
 316                 cds::unref( f )( *it, val );
 317                 return true;
 318             }
 319
 320             /// Clears the container
 321             void clear()
 322             {
 323                 m_Vector.clear();
 324             }
 325
 326             iterator begin()                { return m_Vector.begin(); }
 327             const_iterator begin() const    { return m_Vector.begin(); }
 328             iterator end()                  { return m_Vector.end(); }
 329             const_iterator end() const      { return m_Vector.end(); }
 330
 331             void move_item( adapted_container& /*from*/, iterator itWhat )
 332             {
 333                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), *itWhat, find_predicate() );
 334                 assert( it == m_Vector.end() || key_comparator()( *itWhat, *it ) != 0 );
 335
 336                 copy_item()( m_Vector, it, itWhat );
 337             }
 338
 339             size_t size() const
 340             {
 341                 return m_Vector.size();
 342             }
 343         };
 344
 345     public:
 346         typedef adapted_container type ; ///< Result of \p adapt metafunction
 347
 348     };
 349 }}} // namespace cds::intrusive::striped_set
 350
 351
 352 //@endcond
 353
 354 #endif // #ifndef __CDS_CONTAINER_STRIPED_SET_BOOST_STABLE_VECTOR_ADAPTER_H