cds/container/striped_set/std_vector.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_CONTAINER_STRIPED_SET_STD_VECTOR_ADAPTER_H
  32 #define CDSLIB_CONTAINER_STRIPED_SET_STD_VECTOR_ADAPTER_H
  33
  34 #include <functional>   // ref
  35 #include <vector>
  36 #include <algorithm>    // std::lower_bound
  37 #include <utility>      // std::pair
  38 #include <cds/container/striped_set/adapter.h>     // lower_bound
  39
  40 //@cond
  41 namespace cds { namespace container {
  42     namespace striped_set {
  43
  44         // Copy policy for std::vector
  45         template <typename T, typename Alloc>
  46         struct copy_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, *itWhat );
  54             }
  55         };
  56
  57         // Swap policy for std::vector
  58         template <typename T, typename Alloc>
  59         struct swap_item_policy< std::vector< T, Alloc > >
  60         {
  61             typedef std::vector< T, Alloc > vector_type;
  62             typedef typename vector_type::iterator iterator;
  63
  64             void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
  65             {
  66                 typename vector_type::value_type newVal;
  67                 itInsert = vec.insert( itInsert, newVal );
  68                 std::swap( *itInsert, *itWhat );
  69             }
  70         };
  71
  72         // Move policy for std::vector
  73         template <typename T, typename Alloc>
  74         struct move_item_policy< std::vector< T, Alloc > >
  75         {
  76             typedef std::vector< T, Alloc > vector_type;
  77             typedef typename vector_type::iterator iterator;
  78
  79             void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
  80             {
  81                 vec.insert( itInsert, std::move( *itWhat ));
  82             }
  83         };
  84
  85     }   // namespace striped_set
  86 }} // namespace cds::container
  87
  88 namespace cds { namespace intrusive { namespace striped_set {
  89
  90     /// std::vector adapter for hash set bucket
  91     template <typename T, class Alloc, typename... Options>
  92     class adapt< std::vector<T, Alloc>, Options... >
  93     {
  94     public:
  95         typedef std::vector<T, Alloc>     container_type          ;   ///< underlying container type
  96
  97     private:
  98         /// Adapted container type
  99         class adapted_container: public cds::container::striped_set::adapted_sequential_container
 100         {
 101         public:
 102             typedef typename container_type::value_type value_type  ;   ///< value type stored in the container
 103             typedef typename container_type::iterator      iterator ;   ///< container iterator
 104             typedef typename container_type::const_iterator const_iterator ;    ///< container const iterator
 105
 106             static bool const has_find_with = true;
 107             static bool const has_erase_with = true;
 108
 109         private:
 110             //@cond
 111             typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
 112
 113             typedef typename cds::opt::select<
 114                 typename cds::opt::value<
 115                     typename cds::opt::find_option<
 116                         cds::opt::copy_policy< cds::container::striped_set::move_item >
 117                         , Options...
 118                     >::type
 119                 >::copy_policy
 120                 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
 121                 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
 122                 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
 123             >::type copy_item;
 124
 125             struct find_predicate
 126             {
 127                 bool operator()( value_type const& i1, value_type const& i2) const
 128                 {
 129                     return key_comparator()( i1, i2 ) < 0;
 130                 }
 131
 132                 template <typename Q>
 133                 bool operator()( Q const& i1, value_type const& i2) const
 134                 {
 135                     return key_comparator()( i1, i2 ) < 0;
 136                 }
 137
 138                 template <typename Q>
 139                 bool operator()( value_type const& i1, Q const& i2) const
 140                 {
 141                     return key_comparator()( i1, i2 ) < 0;
 142                 }
 143             };
 144             //@endcond
 145
 146         private:
 147             //@cond
 148             container_type  m_Vector;
 149             //@endcond
 150
 151         public:
 152
 153             template <typename Q, typename Func>
 154             bool insert( const Q& val, Func f )
 155             {
 156                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate());
 157                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 158                     value_type newItem( val );
 159                     it = m_Vector.insert( it, newItem );
 160                     f( *it );
 161                     return true;
 162                 }
 163                 return false;
 164             }
 165
 166             template <typename... Args>
 167             bool emplace( Args&&... args )
 168             {
 169 #if CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC12
 170                 // MS VC++ 2013 internal compiler error
 171                 // Use assignment workaround, see http://connect.microsoft.com/VisualStudio/feedback/details/804941/visual-studio-2013-rc-c-internal-compiler-error-with-std-forward
 172                 value_type val = value_type(std::forward<Args>(args)...);
 173 #else
 174                 value_type val( std::forward<Args>(args)... );
 175 #endif
 176                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate());
 177                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 178                     it = m_Vector.emplace( it, std::move( val ));
 179                     return true;
 180                 }
 181                 return false;
 182             }
 183
 184             template <typename Q, typename Func>
 185             std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert )
 186             {
 187                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate());
 188                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 189                     // insert new
 190                     if ( !bAllowInsert )
 191                         return std::make_pair( false, false );
 192
 193                     value_type newItem( val );
 194                     it = m_Vector.insert( it, newItem );
 195                     func( true, *it, val );
 196                     return std::make_pair( true, true );
 197                 }
 198                 else {
 199                     // already exists
 200                     func( false, *it, val );
 201                     return std::make_pair( true, false );
 202                 }
 203             }
 204
 205             template <typename Q, typename Func>
 206             bool erase( const Q& key, Func f )
 207             {
 208                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, find_predicate());
 209                 if ( it == m_Vector.end() || key_comparator()( key, *it ) != 0 )
 210                     return false;
 211
 212                 // key exists
 213                 f( *it );
 214                 m_Vector.erase( it );
 215                 return true;
 216             }
 217
 218             template <typename Q, typename Less, typename Func>
 219             bool erase( const Q& key, Less pred, Func f )
 220             {
 221                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, pred );
 222                 if ( it == m_Vector.end() || pred( key, *it ) || pred( *it, key ))
 223                     return false;
 224
 225                 // key exists
 226                 f( *it );
 227                 m_Vector.erase( it );
 228                 return true;
 229             }
 230
 231             template <typename Q, typename Func>
 232             bool find( Q& val, Func f )
 233             {
 234                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate());
 235                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 )
 236                     return false;
 237
 238                 // key exists
 239                 f( *it, val );
 240                 return true;
 241             }
 242
 243             template <typename Q, typename Less, typename Func>
 244             bool find( Q& val, Less pred, Func f )
 245             {
 246                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, pred );
 247                 if ( it == m_Vector.end() || pred( val, *it ) || pred( *it, val ))
 248                     return false;
 249
 250                 // key exists
 251                 f( *it, val );
 252                 return true;
 253             }
 254
 255
 256             void clear()
 257             {
 258                 m_Vector.clear();
 259             }
 260
 261             iterator begin()                { return m_Vector.begin(); }
 262             const_iterator begin() const    { return m_Vector.begin(); }
 263             iterator end()                  { return m_Vector.end(); }
 264             const_iterator end() const      { return m_Vector.end(); }
 265
 266             void move_item( adapted_container& /*from*/, iterator itWhat )
 267             {
 268                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), *itWhat, find_predicate());
 269                 assert( it == m_Vector.end() || key_comparator()( *itWhat, *it ) != 0 );
 270
 271                 copy_item()( m_Vector, it, itWhat );
 272             }
 273
 274             size_t size() const
 275             {
 276                 return m_Vector.size();
 277             }
 278         };
 279
 280     public:
 281         typedef adapted_container type ; ///< Result of \p adapt metafunction
 282
 283     };
 284 }}} // namespace cds::intrusive::striped_set
 285
 286 //@endcond
 287
 288 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_STD_VECTOR_ADAPTER_H