cds/container/striped_set/boost_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-2016
   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_BOOST_VECTOR_ADAPTER_H
  32 #define CDSLIB_CONTAINER_STRIPED_SET_BOOST_VECTOR_ADAPTER_H
  33
  34 #include <boost/version.hpp>
  35 #if BOOST_VERSION < 104800
  36 #   error "For boost::container::vector you must use boost 1.48 or above"
  37 #endif
  38
  39 #include <functional>   // ref
  40 #include <algorithm>    // std::lower_bound
  41 #include <utility>      // std::pair
  42 #include <cds/container/striped_set/adapter.h>     // lower_bound
  43 #include <boost/container/vector.hpp>
  44
  45 //@cond
  46 namespace cds { namespace container {
  47     namespace striped_set {
  48
  49         // Copy policy for boost::container::vector
  50         template <typename T, typename Alloc>
  51         struct copy_item_policy< boost::container::vector< T, Alloc > >
  52         {
  53             typedef boost::container::vector< T, Alloc > vector_type;
  54             typedef typename vector_type::iterator iterator;
  55
  56             void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
  57             {
  58                 vec.insert( itInsert, *itWhat );
  59             }
  60         };
  61
  62         // Swap policy for boost::container::vector
  63         template <typename T, typename Alloc>
  64         struct swap_item_policy< boost::container::vector< T, Alloc > >
  65         {
  66             typedef boost::container::vector< T, Alloc > vector_type;
  67             typedef typename vector_type::iterator iterator;
  68
  69             void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
  70             {
  71                 typename vector_type::value_type newVal;
  72                 itInsert = vec.insert( itInsert, newVal );
  73                 std::swap( *itInsert, *itWhat );
  74             }
  75         };
  76
  77         // Move policy for boost::container::vector
  78         template <typename T, typename Alloc>
  79         struct move_item_policy< boost::container::vector< T, Alloc > >
  80         {
  81             typedef boost::container::vector< T, Alloc > vector_type;
  82             typedef typename vector_type::iterator iterator;
  83
  84             void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
  85             {
  86                 vec.insert( itInsert, std::move( *itWhat ));
  87             }
  88         };
  89     }   // namespace striped_set
  90 }} // namespace cds::container
  91
  92 namespace cds { namespace intrusive { namespace striped_set {
  93
  94     /// boost::container::vector adapter for hash set bucket
  95     template <typename T, class Alloc, typename... Options>
  96     class adapt< boost::container::vector<T, Alloc>, Options... >
  97     {
  98     public:
  99         typedef boost::container::vector<T, Alloc>     container_type          ;   ///< underlying container type
 100
 101     private:
 102         /// Adapted container type
 103         class adapted_container: public cds::container::striped_set::adapted_sequential_container
 104         {
 105         public:
 106             typedef typename container_type::value_type value_type  ;   ///< value type stored in the container
 107             typedef typename container_type::iterator      iterator ;   ///< container iterator
 108             typedef typename container_type::const_iterator const_iterator ;    ///< container const iterator
 109
 110             static bool const has_find_with = true;
 111             static bool const has_erase_with = true;
 112
 113         private:
 114             //@cond
 115             typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
 116
 117             typedef typename cds::opt::select<
 118                 typename cds::opt::value<
 119                     typename cds::opt::find_option<
 120                         cds::opt::copy_policy< cds::container::striped_set::move_item >
 121                         , Options...
 122                     >::type
 123                 >::copy_policy
 124                 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
 125                 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
 126                 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
 127             >::type copy_item;
 128
 129             struct find_predicate
 130             {
 131                 bool operator()( value_type const& i1, value_type const& i2) const
 132                 {
 133                     return key_comparator()( i1, i2 ) < 0;
 134                 }
 135
 136                 template <typename Q>
 137                 bool operator()( Q const& i1, value_type const& i2) const
 138                 {
 139                     return key_comparator()( i1, i2 ) < 0;
 140                 }
 141
 142                 template <typename Q>
 143                 bool operator()( value_type const& i1, Q const& i2) const
 144                 {
 145                     return key_comparator()( i1, i2 ) < 0;
 146                 }
 147             };
 148             //@endcond
 149
 150         private:
 151             //@cond
 152             container_type  m_Vector;
 153             //@endcond
 154
 155         public:
 156             template <typename Q, typename Func>
 157             bool insert( const Q& val, Func f )
 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                     value_type newItem( val );
 162                     it = m_Vector.insert( it, newItem );
 163                     f( *it );
 164                     return true;
 165                 }
 166                 return false;
 167             }
 168
 169             template <typename... Args>
 170             bool emplace( Args&&... args )
 171             {
 172                 value_type val( std::forward<Args>(args)... );
 173                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 174                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 175                     it = m_Vector.emplace( it, std::move( val ) );
 176                     return true;
 177                 }
 178                 return false;
 179             }
 180
 181             template <typename Q, typename Func>
 182             std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert )
 183             {
 184                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 185                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 186                     // insert new
 187                     if ( !bAllowInsert )
 188                         return std::make_pair( false, false );
 189
 190                     value_type newItem( val );
 191                     it = m_Vector.insert( it, newItem );
 192                     func( true, *it, val );
 193                     return std::make_pair( true, true );
 194                 }
 195                 else {
 196                     // already exists
 197                     func( false, *it, val );
 198                     return std::make_pair( true, false );
 199                 }
 200             }
 201
 202             template <typename Q, typename Func>
 203             bool erase( const Q& key, Func f )
 204             {
 205                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, find_predicate() );
 206                 if ( it == m_Vector.end() || key_comparator()( key, *it ) != 0 )
 207                     return false;
 208
 209                 // key exists
 210                 f( *it );
 211                 m_Vector.erase( it );
 212                 return true;
 213             }
 214
 215             template <typename Q, typename Less, typename Func>
 216             bool erase( Q const& key, Less pred, Func f )
 217             {
 218                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, pred );
 219                 if ( it == m_Vector.end() || pred( key, *it ) || pred( *it, key ) )
 220                     return false;
 221
 222                 // key exists
 223                 f( *it );
 224                 m_Vector.erase( it );
 225                 return true;
 226             }
 227
 228             template <typename Q, typename Func>
 229             bool find( Q& val, Func f )
 230             {
 231                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate() );
 232                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 )
 233                     return false;
 234
 235                 // key exists
 236                 f( *it, val );
 237                 return true;
 238             }
 239
 240             template <typename Q, typename Less, typename Func>
 241             bool find( Q& val, Less pred, Func f )
 242             {
 243                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, pred );
 244                 if ( it == m_Vector.end() || pred( val, *it ) || pred( *it, val ) )
 245                     return false;
 246
 247                 // key exists
 248                 f( *it, val );
 249                 return true;
 250             }
 251
 252             /// Clears the container
 253             void clear()
 254             {
 255                 m_Vector.clear();
 256             }
 257
 258             iterator begin()                { return m_Vector.begin(); }
 259             const_iterator begin() const    { return m_Vector.begin(); }
 260             iterator end()                  { return m_Vector.end(); }
 261             const_iterator end() const      { return m_Vector.end(); }
 262
 263             void move_item( adapted_container& /*from*/, iterator itWhat )
 264             {
 265                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), *itWhat, find_predicate() );
 266                 assert( it == m_Vector.end() || key_comparator()( *itWhat, *it ) != 0 );
 267
 268                 copy_item()( m_Vector, it, itWhat );
 269             }
 270
 271             size_t size() const
 272             {
 273                 return m_Vector.size();
 274             }
 275         };
 276
 277     public:
 278         typedef adapted_container type ; ///< Result of \p adapt metafunction
 279
 280     };
 281 }}} // namespace cds::intrusive::striped_set
 282
 283
 284 //@endcond
 285
 286 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_BOOST_VECTOR_ADAPTER_H