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