cds/container/striped_set/std_vector.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_STRIPED_SET_STD_VECTOR_ADAPTER_H
   4 #define CDSLIB_CONTAINER_STRIPED_SET_STD_VECTOR_ADAPTER_H
   5
   6 #include <functional>   // ref
   7 #include <vector>
   8 #include <algorithm>    // std::lower_bound
   9 #include <utility>      // std::pair
  10 #include <cds/container/striped_set/adapter.h>     // lower_bound
  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         // Move policy for std::vector
  45         template <typename T, typename Alloc>
  46         struct move_item_policy< std::vector< T, Alloc > >
  47         {
  48             typedef std::vector< T, Alloc > vector_type;
  49             typedef typename vector_type::iterator iterator;
  50
  51             void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
  52             {
  53                 vec.insert( itInsert, std::move( *itWhat ));
  54             }
  55         };
  56
  57     }   // namespace striped_set
  58 }} // namespace cds::container
  59
  60 namespace cds { namespace intrusive { namespace striped_set {
  61
  62     /// std::vector adapter for hash set bucket
  63     template <typename T, class Alloc, typename... Options>
  64     class adapt< std::vector<T, Alloc>, Options... >
  65     {
  66     public:
  67         typedef std::vector<T, Alloc>     container_type          ;   ///< underlying container type
  68
  69     private:
  70         /// Adapted container type
  71         class adapted_container: public cds::container::striped_set::adapted_sequential_container
  72         {
  73         public:
  74             typedef typename container_type::value_type value_type  ;   ///< value type stored in the container
  75             typedef typename container_type::iterator      iterator ;   ///< container iterator
  76             typedef typename container_type::const_iterator const_iterator ;    ///< container const iterator
  77
  78             static bool const has_find_with = true;
  79             static bool const has_erase_with = true;
  80
  81         private:
  82             //@cond
  83             typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
  84
  85             typedef typename cds::opt::select<
  86                 typename cds::opt::value<
  87                     typename cds::opt::find_option<
  88                         cds::opt::copy_policy< cds::container::striped_set::move_item >
  89                         , Options...
  90                     >::type
  91                 >::copy_policy
  92                 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
  93                 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
  94                 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
  95             >::type copy_item;
  96
  97             struct find_predicate
  98             {
  99                 bool operator()( value_type const& i1, value_type const& i2) const
 100                 {
 101                     return key_comparator()( i1, i2 ) < 0;
 102                 }
 103
 104                 template <typename Q>
 105                 bool operator()( Q const& i1, value_type const& i2) const
 106                 {
 107                     return key_comparator()( i1, i2 ) < 0;
 108                 }
 109
 110                 template <typename Q>
 111                 bool operator()( value_type const& i1, Q const& i2) const
 112                 {
 113                     return key_comparator()( i1, i2 ) < 0;
 114                 }
 115             };
 116             //@endcond
 117
 118         private:
 119             //@cond
 120             container_type  m_Vector;
 121             //@endcond
 122
 123         public:
 124
 125             template <typename Q, typename Func>
 126             bool insert( const Q& val, Func f )
 127             {
 128                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 129                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 130                     value_type newItem( val );
 131                     it = m_Vector.insert( it, newItem );
 132                     f( *it );
 133                     return true;
 134                 }
 135                 return false;
 136             }
 137
 138             template <typename... Args>
 139             bool emplace( Args&&... args )
 140             {
 141 #if CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC12
 142                 // MS VC++ 2013 internal compiler error
 143                 // Use assignment workaround, see http://connect.microsoft.com/VisualStudio/feedback/details/804941/visual-studio-2013-rc-c-internal-compiler-error-with-std-forward
 144                 value_type val = value_type(std::forward<Args>(args)...);
 145 #else
 146                 value_type val( std::forward<Args>(args)... );
 147 #endif
 148                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 149                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 150                     it = m_Vector.emplace( it, std::move( val ) );
 151                     return true;
 152                 }
 153                 return false;
 154             }
 155
 156             template <typename Q, typename Func>
 157             std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert )
 158             {
 159                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 160                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 161                     // insert new
 162                     if ( !bAllowInsert )
 163                         return std::make_pair( false, false );
 164
 165                     value_type newItem( val );
 166                     it = m_Vector.insert( it, newItem );
 167                     func( true, *it, val );
 168                     return std::make_pair( true, true );
 169                 }
 170                 else {
 171                     // already exists
 172                     func( false, *it, val );
 173                     return std::make_pair( true, false );
 174                 }
 175             }
 176
 177             template <typename Q, typename Func>
 178             bool erase( const Q& key, Func f )
 179             {
 180                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, find_predicate() );
 181                 if ( it == m_Vector.end() || key_comparator()( key, *it ) != 0 )
 182                     return false;
 183
 184                 // key exists
 185                 f( *it );
 186                 m_Vector.erase( it );
 187                 return true;
 188             }
 189
 190             template <typename Q, typename Less, typename Func>
 191             bool erase( const Q& key, Less pred, Func f )
 192             {
 193                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, pred );
 194                 if ( it == m_Vector.end() || pred( key, *it ) || pred( *it, key ) )
 195                     return false;
 196
 197                 // key exists
 198                 f( *it );
 199                 m_Vector.erase( it );
 200                 return true;
 201             }
 202
 203             template <typename Q, typename Func>
 204             bool find( Q& val, Func f )
 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                     return false;
 209
 210                 // key exists
 211                 f( *it, val );
 212                 return true;
 213             }
 214
 215             template <typename Q, typename Less, typename Func>
 216             bool find( Q& val, Less pred, Func f )
 217             {
 218                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, pred );
 219                 if ( it == m_Vector.end() || pred( val, *it ) || pred( *it, val ) )
 220                     return false;
 221
 222                 // key exists
 223                 f( *it, val );
 224                 return true;
 225             }
 226
 227
 228             void clear()
 229             {
 230                 m_Vector.clear();
 231             }
 232
 233             iterator begin()                { return m_Vector.begin(); }
 234             const_iterator begin() const    { return m_Vector.begin(); }
 235             iterator end()                  { return m_Vector.end(); }
 236             const_iterator end() const      { return m_Vector.end(); }
 237
 238             void move_item( adapted_container& /*from*/, iterator itWhat )
 239             {
 240                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), *itWhat, find_predicate() );
 241                 assert( it == m_Vector.end() || key_comparator()( *itWhat, *it ) != 0 );
 242
 243                 copy_item()( m_Vector, it, itWhat );
 244             }
 245
 246             size_t size() const
 247             {
 248                 return m_Vector.size();
 249             }
 250         };
 251
 252     public:
 253         typedef adapted_container type ; ///< Result of \p adapt metafunction
 254
 255     };
 256 }}} // namespace cds::intrusive::striped_set
 257
 258 //@endcond
 259
 260 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_STD_VECTOR_ADAPTER_H