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