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         // 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, CDS_SPEC_OPTIONS>
  64     class adapt< std::vector<T, Alloc>, CDS_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, CDS_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                         , CDS_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                     cds::unref( f )( *it );
 133                     return true;
 134                 }
 135                 return false;
 136             }
 137
 138 #           ifdef CDS_EMPLACE_SUPPORT
 139             template <typename... Args>
 140             bool emplace( Args&&... args )
 141             {
 142 #if CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC12
 143                 // MS VC++ 2013 internal compiler error
 144                 // Use assignment workaround, see http://connect.microsoft.com/VisualStudio/feedback/details/804941/visual-studio-2013-rc-c-internal-compiler-error-with-std-forward
 145                 value_type val = value_type(std::forward<Args>(args)...);
 146 #else
 147                 value_type val( std::forward<Args>(args)... );
 148 #endif
 149                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 150                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 151                     it = m_Vector.emplace( it, std::move( val ) );
 152                     return true;
 153                 }
 154                 return false;
 155             }
 156 #           endif
 157
 158             template <typename Q, typename Func>
 159             std::pair<bool, bool> ensure( const Q& val, Func func )
 160             {
 161                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 162                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 163                     // insert new
 164                     value_type newItem( val );
 165                     it = m_Vector.insert( it, newItem );
 166                     cds::unref( func )( true, *it, val );
 167                     return std::make_pair( true, true );
 168                 }
 169                 else {
 170                     // already exists
 171                     cds::unref( func )( false, *it, val );
 172                     return std::make_pair( true, false );
 173                 }
 174             }
 175
 176             template <typename Q, typename Func>
 177             bool erase( const Q& key, Func f )
 178             {
 179                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, find_predicate() );
 180                 if ( it == m_Vector.end() || key_comparator()( key, *it ) != 0 )
 181                     return false;
 182
 183                 // key exists
 184                 cds::unref( f )( *it );
 185                 m_Vector.erase( it );
 186                 return true;
 187             }
 188
 189             template <typename Q, typename Less, typename Func>
 190             bool erase( const Q& key, Less pred, Func f )
 191             {
 192                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, pred );
 193                 if ( it == m_Vector.end() || pred( key, *it ) || pred( *it, key ) )
 194                     return false;
 195
 196                 // key exists
 197                 cds::unref( f )( *it );
 198                 m_Vector.erase( it );
 199                 return true;
 200             }
 201
 202             template <typename Q, typename Func>
 203             bool find( Q& val, Func f )
 204             {
 205                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 206                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 )
 207                     return false;
 208
 209                 // key exists
 210                 cds::unref( f )( *it, val );
 211                 return true;
 212             }
 213
 214             template <typename Q, typename Less, typename Func>
 215             bool find( Q& val, Less pred, Func f )
 216             {
 217                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, pred );
 218                 if ( it == m_Vector.end() || pred( val, *it ) || pred( *it, val ) )
 219                     return false;
 220
 221                 // key exists
 222                 cds::unref( f )( *it, val );
 223                 return true;
 224             }
 225
 226
 227             void clear()
 228             {
 229                 m_Vector.clear();
 230             }
 231
 232             iterator begin()                { return m_Vector.begin(); }
 233             const_iterator begin() const    { return m_Vector.begin(); }
 234             iterator end()                  { return m_Vector.end(); }
 235             const_iterator end() const      { return m_Vector.end(); }
 236
 237             void move_item( adapted_container& /*from*/, iterator itWhat )
 238             {
 239                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), *itWhat, find_predicate() );
 240                 assert( it == m_Vector.end() || key_comparator()( *itWhat, *it ) != 0 );
 241
 242                 copy_item()( m_Vector, it, itWhat );
 243             }
 244
 245             size_t size() const
 246             {
 247                 return m_Vector.size();
 248             }
 249         };
 250
 251     public:
 252         typedef adapted_container type ; ///< Result of \p adapt metafunction
 253
 254     };
 255 }}} // namespace cds::intrusive::striped_set
 256
 257 //@endcond
 258
 259 #endif // #ifndef __CDS_CONTAINER_STRIPED_SET_STD_VECTOR_ADAPTER_H