cds/container/striped_set/boost_vector.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_STRIPED_SET_BOOST_VECTOR_ADAPTER_H
   4 #define __CDS_CONTAINER_STRIPED_SET_BOOST_VECTOR_ADAPTER_H
   5
   6 #include <boost/version.hpp>
   7 #if BOOST_VERSION < 104800
   8 #   error "For boost::container::vector you must use boost 1.48 or above"
   9 #endif
  10
  11 #include <cds/container/striped_set/adapter.h>     // lower_bound
  12 #include <cds/ref.h>
  13 #include <boost/container/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::vector
  22         template <typename T, typename Alloc>
  23         struct copy_item_policy< boost::container::vector< T, Alloc > >
  24         {
  25             typedef boost::container::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::vector
  35         template <typename T, typename Alloc>
  36         struct swap_item_policy< boost::container::vector< T, Alloc > >
  37         {
  38             typedef boost::container::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::vector
  50         template <typename T, typename Alloc>
  51         struct move_item_policy< boost::container::vector< T, Alloc > >
  52         {
  53             typedef boost::container::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     }   // namespace striped_set
  62 }} // namespace cds::container
  63
  64 namespace cds { namespace intrusive { namespace striped_set {
  65
  66     /// boost::container::vector adapter for hash set bucket
  67     template <typename T, class Alloc, CDS_SPEC_OPTIONS>
  68     class adapt< boost::container::vector<T, Alloc>, CDS_OPTIONS >
  69     {
  70     public:
  71         typedef boost::container::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             template <typename Q, typename Func>
 129             bool insert( const Q& val, Func f )
 130             {
 131                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 132                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 133                     value_type newItem( val );
 134                     it = m_Vector.insert( it, newItem );
 135                     cds::unref( f )( *it );
 136                     return true;
 137                 }
 138                 return false;
 139             }
 140
 141 #           ifdef CDS_EMPLACE_SUPPORT
 142             template <typename... Args>
 143             bool emplace( Args&&... args )
 144             {
 145                 value_type val( std::forward<Args>(args)... );
 146                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 147                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 148                     it = m_Vector.emplace( it, std::move( val ) );
 149                     return true;
 150                 }
 151                 return false;
 152             }
 153 #           endif
 154
 155             template <typename Q, typename Func>
 156             std::pair<bool, bool> ensure( const Q& val, Func func )
 157             {
 158                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 159                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 160                     // insert new
 161                     value_type newItem( val );
 162                     it = m_Vector.insert( it, newItem );
 163                     cds::unref( func )( true, *it, val );
 164                     return std::make_pair( true, true );
 165                 }
 166                 else {
 167                     // already exists
 168                     cds::unref( func )( false, *it, val );
 169                     return std::make_pair( true, false );
 170                 }
 171             }
 172
 173             template <typename Q, typename Func>
 174             bool erase( const Q& key, Func f )
 175             {
 176                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, find_predicate() );
 177                 if ( it == m_Vector.end() || key_comparator()( key, *it ) != 0 )
 178                     return false;
 179
 180                 // key exists
 181                 cds::unref( f )( *it );
 182                 m_Vector.erase( it );
 183                 return true;
 184             }
 185
 186             template <typename Q, typename Less, typename Func>
 187             bool erase( Q const& key, Less pred, Func f )
 188             {
 189                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, pred );
 190                 if ( it == m_Vector.end() || pred( key, *it ) || pred( *it, key ) )
 191                     return false;
 192
 193                 // key exists
 194                 cds::unref( f )( *it );
 195                 m_Vector.erase( it );
 196                 return true;
 197             }
 198
 199             template <typename Q, typename Func>
 200             bool find( Q& val, Func f )
 201             {
 202                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 203                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 )
 204                     return false;
 205
 206                 // key exists
 207                 cds::unref( f )( *it, val );
 208                 return true;
 209             }
 210
 211             template <typename Q, typename Less, typename Func>
 212             bool find( Q& val, Less pred, Func f )
 213             {
 214                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, pred );
 215                 if ( it == m_Vector.end() || pred( val, *it ) || pred( *it, val ) )
 216                     return false;
 217
 218                 // key exists
 219                 cds::unref( f )( *it, val );
 220                 return true;
 221             }
 222
 223             /// Clears the container
 224             void clear()
 225             {
 226                 m_Vector.clear();
 227             }
 228
 229             iterator begin()                { return m_Vector.begin(); }
 230             const_iterator begin() const    { return m_Vector.begin(); }
 231             iterator end()                  { return m_Vector.end(); }
 232             const_iterator end() const      { return m_Vector.end(); }
 233
 234             void move_item( adapted_container& /*from*/, iterator itWhat )
 235             {
 236                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), *itWhat, find_predicate() );
 237                 assert( it == m_Vector.end() || key_comparator()( *itWhat, *it ) != 0 );
 238
 239                 copy_item()( m_Vector, it, itWhat );
 240             }
 241
 242             size_t size() const
 243             {
 244                 return m_Vector.size();
 245             }
 246         };
 247
 248     public:
 249         typedef adapted_container type ; ///< Result of \p adapt metafunction
 250
 251     };
 252 }}} // namespace cds::intrusive::striped_set
 253
 254
 255 //@endcond
 256
 257 #endif // #ifndef __CDS_CONTAINER_STRIPED_SET_BOOST_VECTOR_ADAPTER_H