cds/container/striped_set/std_vector.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_STRIPED_SET_STD_VECTOR_ADAPTER_H
   4 #define __CDS_CONTAINER_STRIPED_SET_STD_VECTOR_ADAPTER_H
   5
   6 #include <cds/container/striped_set/adapter.h>     // lower_bound
   7 #include <cds/ref.h>
   8 #include <vector>
   9 #include <algorithm>    // std::lower_bound
  10 #include <utility>      // std::pair
  11
  12 //@cond
  13 namespace cds { namespace container {
  14     namespace striped_set {
  15
  16         // Copy policy for std::vector
  17         template <typename T, typename Alloc>
  18         struct copy_item_policy< std::vector< T, Alloc > >
  19         {
  20             typedef std::vector< T, Alloc > vector_type;
  21             typedef typename vector_type::iterator iterator;
  22
  23             void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
  24             {
  25                 vec.insert( itInsert, *itWhat );
  26             }
  27         };
  28
  29         // Swap policy for std::vector
  30         template <typename T, typename Alloc>
  31         struct swap_item_policy< std::vector< T, Alloc > >
  32         {
  33             typedef std::vector< T, Alloc > vector_type;
  34             typedef typename vector_type::iterator iterator;
  35
  36             void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
  37             {
  38                 typename vector_type::value_type newVal;
  39                 itInsert = vec.insert( itInsert, newVal );
  40                 std::swap( *itInsert, *itWhat );
  41             }
  42         };
  43
  44 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
  45         // Move policy for std::vector
  46         template <typename T, typename Alloc>
  47         struct move_item_policy< std::vector< T, Alloc > >
  48         {
  49             typedef std::vector< T, Alloc > vector_type;
  50             typedef typename vector_type::iterator iterator;
  51
  52             void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
  53             {
  54                 vec.insert( itInsert, std::move( *itWhat ));
  55             }
  56         };
  57 #endif
  58
  59     }   // namespace striped_set
  60 }} // namespace cds::container
  61
  62 namespace cds { namespace intrusive { namespace striped_set {
  63
  64     /// std::vector adapter for hash set bucket
  65     template <typename T, class Alloc, CDS_SPEC_OPTIONS>
  66     class adapt< std::vector<T, Alloc>, CDS_OPTIONS >
  67     {
  68     public:
  69         typedef std::vector<T, Alloc>     container_type          ;   ///< underlying container type
  70
  71     private:
  72         /// Adapted container type
  73         class adapted_container: public cds::container::striped_set::adapted_sequential_container
  74         {
  75         public:
  76             typedef typename container_type::value_type value_type  ;   ///< value type stored in the container
  77             typedef typename container_type::iterator      iterator ;   ///< container iterator
  78             typedef typename container_type::const_iterator const_iterator ;    ///< container const iterator
  79
  80             static bool const has_find_with = true;
  81             static bool const has_erase_with = true;
  82
  83         private:
  84             //@cond
  85             typedef typename cds::opt::details::make_comparator_from_option_list< value_type, CDS_OPTIONS >::type key_comparator;
  86
  87             typedef typename cds::opt::select<
  88                 typename cds::opt::value<
  89                     typename cds::opt::find_option<
  90                         cds::opt::copy_policy< cds::container::striped_set::move_item >
  91                         , CDS_OPTIONS
  92                     >::type
  93                 >::copy_policy
  94                 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
  95                 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
  96 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
  97                 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
  98 #endif
  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             template <typename Q, typename Func>
 130             bool insert( const Q& val, Func f )
 131             {
 132                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 133                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 134                     value_type newItem( val );
 135                     it = m_Vector.insert( it, newItem );
 136                     cds::unref( f )( *it );
 137                     return true;
 138                 }
 139                 return false;
 140             }
 141
 142 #           ifdef CDS_EMPLACE_SUPPORT
 143             template <typename... Args>
 144             bool emplace( Args&&... args )
 145             {
 146 #if CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC12
 147                 // MS VC++ 2013 internal compiler error
 148                 // Use assignment workaround, see http://connect.microsoft.com/VisualStudio/feedback/details/804941/visual-studio-2013-rc-c-internal-compiler-error-with-std-forward
 149                 value_type val = value_type(std::forward<Args>(args)...);
 150 #else
 151                 value_type val( std::forward<Args>(args)... );
 152 #endif
 153                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 154                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 155                     it = m_Vector.emplace( it, std::move( val ) );
 156                     return true;
 157                 }
 158                 return false;
 159             }
 160 #           endif
 161
 162             template <typename Q, typename Func>
 163             std::pair<bool, bool> ensure( const Q& val, Func func )
 164             {
 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                     // insert new
 168                     value_type newItem( val );
 169                     it = m_Vector.insert( it, newItem );
 170                     cds::unref( func )( true, *it, val );
 171                     return std::make_pair( true, true );
 172                 }
 173                 else {
 174                     // already exists
 175                     cds::unref( func )( false, *it, val );
 176                     return std::make_pair( true, false );
 177                 }
 178             }
 179
 180             template <typename Q, typename Func>
 181             bool erase( const Q& key, Func f )
 182             {
 183                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, find_predicate() );
 184                 if ( it == m_Vector.end() || key_comparator()( key, *it ) != 0 )
 185                     return false;
 186
 187                 // key exists
 188                 cds::unref( f )( *it );
 189                 m_Vector.erase( it );
 190                 return true;
 191             }
 192
 193             template <typename Q, typename Less, typename Func>
 194             bool erase( const Q& key, Less pred, Func f )
 195             {
 196                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, pred );
 197                 if ( it == m_Vector.end() || pred( key, *it ) || pred( *it, key ) )
 198                     return false;
 199
 200                 // key exists
 201                 cds::unref( f )( *it );
 202                 m_Vector.erase( it );
 203                 return true;
 204             }
 205
 206             template <typename Q, typename Func>
 207             bool find( Q& val, Func f )
 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                     return false;
 212
 213                 // key exists
 214                 cds::unref( f )( *it, val );
 215                 return true;
 216             }
 217
 218             template <typename Q, typename Less, typename Func>
 219             bool find( Q& val, Less pred, Func f )
 220             {
 221                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, pred );
 222                 if ( it == m_Vector.end() || pred( val, *it ) || pred( *it, val ) )
 223                     return false;
 224
 225                 // key exists
 226                 cds::unref( f )( *it, val );
 227                 return true;
 228             }
 229
 230
 231             void clear()
 232             {
 233                 m_Vector.clear();
 234             }
 235
 236             iterator begin()                { return m_Vector.begin(); }
 237             const_iterator begin() const    { return m_Vector.begin(); }
 238             iterator end()                  { return m_Vector.end(); }
 239             const_iterator end() const      { return m_Vector.end(); }
 240
 241             void move_item( adapted_container& /*from*/, iterator itWhat )
 242             {
 243                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), *itWhat, find_predicate() );
 244                 assert( it == m_Vector.end() || key_comparator()( *itWhat, *it ) != 0 );
 245
 246                 copy_item()( m_Vector, it, itWhat );
 247             }
 248
 249             size_t size() const
 250             {
 251                 return m_Vector.size();
 252             }
 253         };
 254
 255     public:
 256         typedef adapted_container type ; ///< Result of \p adapt metafunction
 257
 258     };
 259 }}} // namespace cds::intrusive::striped_set
 260
 261 //@endcond
 262
 263 #endif // #ifndef __CDS_CONTAINER_STRIPED_SET_STD_VECTOR_ADAPTER_H