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