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 <functional>   // ref
  12 #include <algorithm>    // std::lower_bound
  13 #include <utility>      // std::pair
  14 #include <cds/container/striped_set/adapter.h>
  15 #include <boost/container/stable_vector.hpp>
  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, typename... Options>
  68     class adapt< boost::container::stable_vector<T, Alloc>, 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, 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                         , 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.
 146             */
 147             template <typename Q, typename Func>
 148             bool insert( const Q& val, Func f )
 149             {
 150                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 151                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 152                     value_type newItem( val );
 153                     it = m_Vector.insert( it, newItem );
 154                     f( *it );
 155                     return true;
 156                 }
 157                 return false;
 158             }
 159
 160             template <typename... Args>
 161             bool emplace( Args&&... args )
 162             {
 163                 value_type val( std::forward<Args>(args)... );
 164                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 165                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 166                     it = m_Vector.emplace( it, std::move( val ) );
 167                     return true;
 168                 }
 169                 return false;
 170             }
 171
 172             /// Ensures that the \p item exists in the container
 173             /**
 174                 The operation performs inserting or changing data.
 175
 176                 If the \p val key not found in the container, then the new item created from \p val
 177                 is inserted. Otherwise, the functor \p func is called with the item found.
 178                 The \p Func functor has interface:
 179                 \code
 180                     void func( bool bNew, value_type& item, const Q& val );
 181                 \endcode
 182                 or like a functor:
 183                 \code
 184                     struct my_functor {
 185                         void operator()( bool bNew, value_type& item, const Q& val );
 186                     };
 187                 \endcode
 188
 189                 where arguments are:
 190                 - \p bNew - \p true if the item has been inserted, \p false otherwise
 191                 - \p item - container's item
 192                 - \p val - argument \p val passed into the \p ensure function
 193
 194                 The functor may change non-key fields of the \p item.
 195
 196                 The type \p Q may differ from \ref value_type of items storing in the container.
 197                 Therefore, the \p value_type should be comparable with type \p Q and constructible from type \p Q,
 198
 199                 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 200                 \p second is true if new item has been added or \p false if the item with \p val key
 201                 already exists.
 202             */
 203             template <typename Q, typename Func>
 204             std::pair<bool, bool> ensure( const Q& val, Func func )
 205             {
 206                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 207                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 208                     // insert new
 209                     value_type newItem( val );
 210                     it = m_Vector.insert( it, newItem );
 211                     func( true, *it, val );
 212                     return std::make_pair( true, true );
 213                 }
 214                 else {
 215                     // already exists
 216                     func( false, *it, val );
 217                     return std::make_pair( true, false );
 218                 }
 219             }
 220
 221             /// Delete \p key
 222             /**
 223                 The function searches an item with key \p key, calls \p f functor
 224                 and deletes the item. If \p key is not found, the functor is not called.
 225
 226                 The functor \p Func interface is:
 227                 \code
 228                 struct extractor {
 229                     void operator()(value_type const& val);
 230                 };
 231                 \endcode
 232
 233                 The type \p Q may differ from \ref value_type of items storing in the container.
 234                 Therefore, the \p value_type should be comparable with type \p Q.
 235
 236                 Return \p true if key is found and deleted, \p false otherwise
 237             */
 238             template <typename Q, typename Func>
 239             bool erase( const Q& key, Func f )
 240             {
 241                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, find_predicate() );
 242                 if ( it == m_Vector.end() || key_comparator()( key, *it ) != 0 )
 243                     return false;
 244
 245                 // key exists
 246                 f( *it );
 247                 m_Vector.erase( it );
 248                 return true;
 249             }
 250
 251             template <typename Q, typename Less, typename Func>
 252             bool erase( const Q& key, Less pred, Func f )
 253             {
 254                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, pred );
 255                 if ( it == m_Vector.end() || pred( key, *it ) || pred( *it, key ) )
 256                     return false;
 257
 258                 // key exists
 259                 f( *it );
 260                 m_Vector.erase( it );
 261                 return true;
 262             }
 263
 264             /// Find the key \p val
 265             /**
 266                 The function searches the item with key equal to \p val and calls the functor \p f for item found.
 267                 The interface of \p Func functor is:
 268                 \code
 269                 struct functor {
 270                     void operator()( value_type& item, Q& val );
 271                 };
 272                 \endcode
 273                 where \p item is the item found, \p val is the <tt>find</tt> function argument.
 274
 275                 The functor may change non-key fields of \p item.
 276                 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 277                 may modify both arguments.
 278
 279                 The type \p Q may differ from \ref value_type of items storing in the container.
 280                 Therefore, the \p value_type should be comparable with type \p Q.
 281
 282                 The function returns \p true if \p val is found, \p false otherwise.
 283             */
 284             template <typename Q, typename Func>
 285             bool find( Q& val, Func f )
 286             {
 287                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 288                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 )
 289                     return false;
 290
 291                 // key exists
 292                 f( *it, val );
 293                 return true;
 294             }
 295
 296             template <typename Q, typename Less, typename Func>
 297             bool find( Q& val, Less pred, Func f )
 298             {
 299                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, pred );
 300                 if ( it == m_Vector.end() || pred( val, *it ) || pred( *it, val ) )
 301                     return false;
 302
 303                 // key exists
 304                 f( *it, val );
 305                 return true;
 306             }
 307
 308             /// Clears the container
 309             void clear()
 310             {
 311                 m_Vector.clear();
 312             }
 313
 314             iterator begin()                { return m_Vector.begin(); }
 315             const_iterator begin() const    { return m_Vector.begin(); }
 316             iterator end()                  { return m_Vector.end(); }
 317             const_iterator end() const      { return m_Vector.end(); }
 318
 319             void move_item( adapted_container& /*from*/, iterator itWhat )
 320             {
 321                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), *itWhat, find_predicate() );
 322                 assert( it == m_Vector.end() || key_comparator()( *itWhat, *it ) != 0 );
 323
 324                 copy_item()( m_Vector, it, itWhat );
 325             }
 326
 327             size_t size() const
 328             {
 329                 return m_Vector.size();
 330             }
 331         };
 332
 333     public:
 334         typedef adapted_container type ; ///< Result of \p adapt metafunction
 335
 336     };
 337 }}} // namespace cds::intrusive::striped_set
 338
 339
 340 //@endcond
 341
 342 #endif // #ifndef __CDS_CONTAINER_STRIPED_SET_BOOST_STABLE_VECTOR_ADAPTER_H