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