cds/intrusive/striped_set/boost_list.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_STRIPED_SET_BOOST_LIST_ADAPTER_H
   4 #define __CDS_INTRUSIVE_STRIPED_SET_BOOST_LIST_ADAPTER_H
   5
   6 #include <boost/intrusive/list.hpp>
   7 #include <cds/intrusive/striped_set/adapter.h>
   8
   9 //@cond
  10 namespace cds { namespace intrusive { namespace striped_set {
  11
  12     namespace details {
  13         template <typename List, typename... Options >
  14         class adapt_boost_list
  15         {
  16         public:
  17             typedef List container_type;   ///< underlying intrusive container type
  18
  19         private:
  20             /// Adapted intrusive container
  21             class adapted_container : public cds::intrusive::striped_set::adapted_sequential_container
  22             {
  23             public:
  24                 typedef typename container_type::value_type     value_type;   ///< value type stored in the container
  25                 typedef typename container_type::iterator       iterator;   ///< container iterator
  26                 typedef typename container_type::const_iterator const_iterator;    ///< container const iterator
  27                 typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
  28
  29             private:
  30                 struct find_predicate
  31                 {
  32                     bool operator()( value_type const& i1, value_type const& i2 ) const
  33                     {
  34                         return key_comparator()(i1, i2) < 0;
  35                     }
  36
  37                     template <typename Q>
  38                     bool operator()( Q const& i1, value_type const& i2 ) const
  39                     {
  40                         return key_comparator()(i1, i2) < 0;
  41                     }
  42
  43                     template <typename Q>
  44                     bool operator()( value_type const& i1, Q const& i2 ) const
  45                     {
  46                         return key_comparator()(i1, i2) < 0;
  47                     }
  48                 };
  49
  50                 template <typename Q, typename Pred>
  51                 iterator find_key( Q const& key, Pred pred )
  52                 {
  53                     iterator itEnd = m_List.end();
  54                     iterator it;
  55                     for ( it = m_List.begin(); it != itEnd; ++it ) {
  56                         if ( !pred( *it, key ) )
  57                             break;
  58                     }
  59                     return it;
  60                 }
  61
  62             private:
  63                 container_type  m_List;
  64
  65             public:
  66                 adapted_container()
  67                 {}
  68
  69                 container_type& base_container()
  70                 {
  71                     return m_List;
  72                 }
  73
  74                 template <typename Func>
  75                 bool insert( value_type& val, Func f )
  76                 {
  77                     iterator it = find_key( val, find_predicate() );
  78                     if ( it == m_List.end() || key_comparator()(val, *it) != 0 ) {
  79                         m_List.insert( it, val );
  80                         f( val );
  81
  82                         return true;
  83                     }
  84
  85                     // key already exists
  86                     return false;
  87                 }
  88
  89                 template <typename Func>
  90                 std::pair<bool, bool> ensure( value_type& val, Func f )
  91                 {
  92                     iterator it = find_key( val, find_predicate() );
  93                     if ( it == m_List.end() || key_comparator()(val, *it) != 0 ) {
  94                         // insert new
  95                         m_List.insert( it, val );
  96                         f( true, val, val );
  97                         return std::make_pair( true, true );
  98                     }
  99                     else {
 100                         // already exists
 101                         f( false, *it, val );
 102                         return std::make_pair( true, false );
 103                     }
 104                 }
 105
 106                 bool unlink( value_type& val )
 107                 {
 108                     iterator it = find_key( val, find_predicate() );
 109                     if ( it == m_List.end() || &(*it) != &val )
 110                         return false;
 111
 112                     m_List.erase( it );
 113                     return true;
 114                 }
 115
 116                 template <typename Q, typename Func>
 117                 value_type * erase( Q const& key, Func f )
 118                 {
 119                     iterator it = find_key( key, find_predicate() );
 120                     if ( it == m_List.end() || key_comparator()(key, *it) != 0 )
 121                         return nullptr;
 122
 123                     // key exists
 124                     value_type& val = *it;
 125                     f( val );
 126                     m_List.erase( it );
 127
 128                     return &val;
 129                 }
 130
 131                 template <typename Q, typename Less, typename Func>
 132                 value_type * erase( Q const& key, Less pred, Func f )
 133                 {
 134                     iterator it = find_key( key, pred );
 135                     if ( it == m_List.end() || pred( key, *it ) || pred( *it, key ) )
 136                         return nullptr;
 137
 138                     // key exists
 139                     value_type& val = *it;
 140                     f( val );
 141                     m_List.erase( it );
 142
 143                     return &val;
 144                 }
 145
 146                 template <typename Q, typename Func>
 147                 bool find( Q& key, Func f )
 148                 {
 149                     return find( key, find_predicate(), f );
 150                 }
 151
 152                 template <typename Q, typename Less, typename Func>
 153                 bool find( Q& key, Less pred, Func f )
 154                 {
 155                     iterator it = find_key( key, pred );
 156                     if ( it == m_List.end() || pred( key, *it ) || pred( *it, key ) )
 157                         return false;
 158
 159                     // key exists
 160                     f( *it, key );
 161                     return true;
 162                 }
 163
 164                 void clear()
 165                 {
 166                     m_List.clear();
 167                 }
 168
 169                 template <typename Disposer>
 170                 void clear( Disposer disposer )
 171                 {
 172                     m_List.clear_and_dispose( disposer );
 173                 }
 174
 175                 iterator begin() { return m_List.begin(); }
 176                 const_iterator begin() const { return m_List.begin(); }
 177                 iterator end() { return m_List.end(); }
 178                 const_iterator end() const { return m_List.end(); }
 179
 180                 size_t size() const
 181                 {
 182                     return (size_t)m_List.size();
 183                 }
 184
 185                 void move_item( adapted_container& from, iterator itWhat )
 186                 {
 187                     value_type& val = *itWhat;
 188                     from.base_container().erase( itWhat );
 189                     insert( val, []( value_type& ) {} );
 190                 }
 191
 192             };
 193         public:
 194             typedef adapted_container   type;  ///< Result of the metafunction
 195         };
 196     } // namespace details
 197
 198 #if CDS_COMPILER == CDS_COMPILER_INTEL && CDS_COMPILER_VERSION <= 1500
 199     template <typename T, typename P1, typename P2, typename P3, typename P4, typename... Options>
 200     class adapt< boost::intrusive::list< T, P1, P2, P3, P4 >, Options... >
 201         : public details::adapt_boost_list< boost::intrusive::list< T, P1, P2, P3, P4 >, Options... >
 202     {};
 203 #else
 204     template <typename T, typename... BIOptions, typename... Options>
 205     class adapt< boost::intrusive::list< T, BIOptions... >, Options... >
 206         : public details::adapt_boost_list< boost::intrusive::list< T, BIOptions... >, Options... >
 207     {};
 208 #endif
 209
 210 }}} // namespace cds::intrusive::striped_set
 211 //@endcond
 212
 213 #endif // #ifndef __CDS_INTRUSIVE_STRIPED_SET_BOOST_LIST_ADAPTER_H