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, 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                     cds::unref( 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> ensure( const Q& val, Func func )
 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                     value_type newItem( val );
 163                     it = m_Vector.insert( it, newItem );
 164                     cds::unref( func )( true, *it, val );
 165                     return std::make_pair( true, true );
 166                 }
 167                 else {
 168                     // already exists
 169                     cds::unref( func )( false, *it, val );
 170                     return std::make_pair( true, false );
 171                 }
 172             }
 173
 174             template <typename Q, typename Func>
 175             bool erase( const Q& key, Func f )
 176             {
 177                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, find_predicate() );
 178                 if ( it == m_Vector.end() || key_comparator()( key, *it ) != 0 )
 179                     return false;
 180
 181                 // key exists
 182                 cds::unref( f )( *it );
 183                 m_Vector.erase( it );
 184                 return true;
 185             }
 186
 187             template <typename Q, typename Less, typename Func>
 188             bool erase( const Q& key, Less pred, Func f )
 189             {
 190                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, pred );
 191                 if ( it == m_Vector.end() || pred( key, *it ) || pred( *it, key ) )
 192                     return false;
 193
 194                 // key exists
 195                 cds::unref( f )( *it );
 196                 m_Vector.erase( it );
 197                 return true;
 198             }
 199
 200             template <typename Q, typename Func>
 201             bool find( Q& val, Func f )
 202             {
 203                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 204                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 )
 205                     return false;
 206
 207                 // key exists
 208                 cds::unref( f )( *it, val );
 209                 return true;
 210             }
 211
 212             template <typename Q, typename Less, typename Func>
 213             bool find( Q& val, Less pred, Func f )
 214             {
 215                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, pred );
 216                 if ( it == m_Vector.end() || pred( val, *it ) || pred( *it, val ) )
 217                     return false;
 218
 219                 // key exists
 220                 cds::unref( f )( *it, val );
 221                 return true;
 222             }
 223
 224
 225             void clear()
 226             {
 227                 m_Vector.clear();
 228             }
 229
 230             iterator begin()                { return m_Vector.begin(); }
 231             const_iterator begin() const    { return m_Vector.begin(); }
 232             iterator end()                  { return m_Vector.end(); }
 233             const_iterator end() const      { return m_Vector.end(); }
 234
 235             void move_item( adapted_container& /*from*/, iterator itWhat )
 236             {
 237                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), *itWhat, find_predicate() );
 238                 assert( it == m_Vector.end() || key_comparator()( *itWhat, *it ) != 0 );
 239
 240                 copy_item()( m_Vector, it, itWhat );
 241             }
 242
 243             size_t size() const
 244             {
 245                 return m_Vector.size();
 246             }
 247         };
 248
 249     public:
 250         typedef adapted_container type ; ///< Result of \p adapt metafunction
 251
 252     };
 253 }}} // namespace cds::intrusive::striped_set
 254
 255 //@endcond
 256
 257 #endif // #ifndef __CDS_CONTAINER_STRIPED_SET_STD_VECTOR_ADAPTER_H