cds/container/striped_set/boost_list.h

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