cds/intrusive/striped_set/boost_slist.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_STRIPED_SET_BOOST_SLIST_ADAPTER_H
   4 #define __CDS_INTRUSIVE_STRIPED_SET_BOOST_SLIST_ADAPTER_H
   5
   6 #include <boost/intrusive/slist.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_OPTIONS5, CDS_SPEC_OPTIONS>
  13     class adapt< boost::intrusive::slist< T, CDS_BOOST_INTRUSIVE_OPTIONS5 >, CDS_OPTIONS >
  14     {
  15     public:
  16         typedef boost::intrusive::slist< T, CDS_BOOST_INTRUSIVE_OPTIONS5 >  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
  27             typedef typename cds::opt::details::make_comparator_from_option_list< value_type, CDS_OPTIONS >::type key_comparator;
  28
  29         private:
  30
  31             template <typename Q, typename Less>
  32             std::pair< iterator, bool > find_prev_item( Q const& key, Less pred )
  33             {
  34                 iterator itPrev = m_List.before_begin();
  35                 iterator itEnd = m_List.end();
  36                 for ( iterator it = m_List.begin(); it != itEnd; ++it ) {
  37                     if ( pred( key, *it ) )
  38                         itPrev = it;
  39                     else if ( pred( *it, key ) )
  40                         break;
  41                     else
  42                         return std::make_pair( itPrev, true );
  43                 }
  44                 return std::make_pair( itPrev, false );
  45             }
  46
  47             template <typename Q>
  48             std::pair< iterator, bool > find_prev_item( Q const& key )
  49             {
  50                 return find_prev_item_cmp( key, key_comparator() );
  51             }
  52
  53             template <typename Q, typename Compare>
  54             std::pair< iterator, bool > find_prev_item_cmp( Q const& key, Compare cmp )
  55             {
  56                 iterator itPrev = m_List.before_begin();
  57                 iterator itEnd = m_List.end();
  58                 for ( iterator it = m_List.begin(); it != itEnd; ++it ) {
  59                     int nCmp = cmp( key, *it );
  60                     if ( nCmp < 0 )
  61                         itPrev = it;
  62                     else if ( nCmp > 0 )
  63                         break;
  64                     else
  65                         return std::make_pair( itPrev, true );
  66                 }
  67                 return std::make_pair( itPrev, false );
  68             }
  69
  70             template <typename Q, typename Compare, typename Func>
  71             value_type * erase_( Q const& key, Compare cmp, Func f )
  72             {
  73                 std::pair< iterator, bool > pos = find_prev_item_cmp( key, cmp );
  74                 if ( !pos.second )
  75                     return nullptr;
  76
  77                 // key exists
  78                 iterator it = pos.first;
  79                 value_type& val = *(++it);
  80                 cds::unref( f )( val );
  81                 m_List.erase_after( pos.first );
  82
  83                 return &val;
  84             }
  85
  86
  87 #       ifndef CDS_CXX11_LAMBDA_SUPPORT
  88             struct empty_insert_functor {
  89                 void operator()( value_type& )
  90                 {}
  91             };
  92 #       endif
  93
  94         private:
  95             container_type  m_List;
  96
  97         public:
  98             adapted_container()
  99             {}
 100
 101             container_type& base_container()
 102             {
 103                 return m_List;
 104             }
 105
 106             template <typename Func>
 107             bool insert( value_type& val, Func f )
 108             {
 109                 std::pair< iterator, bool > pos = find_prev_item( val );
 110                 if ( !pos.second ) {
 111                     m_List.insert_after( pos.first, val );
 112                     cds::unref( f )( val );
 113                     return true;
 114                 }
 115
 116                 // key already exists
 117                 return false;
 118             }
 119
 120             template <typename Func>
 121             std::pair<bool, bool> ensure( value_type& val, Func f )
 122             {
 123                 std::pair< iterator, bool > pos = find_prev_item( val );
 124                 if ( !pos.second ) {
 125                     // insert new
 126                     m_List.insert_after( pos.first, val );
 127                     cds::unref( f )( true, val, val );
 128                     return std::make_pair( true, true );
 129                 }
 130                 else {
 131                     // already exists
 132                     cds::unref( f )( false, *(++pos.first), val );
 133                     return std::make_pair( true, false );
 134                 }
 135             }
 136
 137             bool unlink( value_type& val )
 138             {
 139                 std::pair< iterator, bool > pos = find_prev_item( val );
 140                 if ( !pos.second )
 141                     return false;
 142
 143                 ++pos.first;
 144                 if ( &(*pos.first) != &val )
 145                     return false;
 146
 147                 m_List.erase( pos.first );
 148                 return true;
 149             }
 150
 151             template <typename Q, typename Func>
 152             value_type * erase( Q const& key, Func f )
 153             {
 154                 return erase_( key, key_comparator(), f );
 155             }
 156
 157             template <typename Q, typename Less, typename Func>
 158             value_type * erase( Q const& key, Less pred, Func f )
 159             {
 160                 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
 161             }
 162
 163             template <typename Q, typename Func>
 164             bool find( Q& key, Func f )
 165             {
 166                 std::pair< iterator, bool > pos = find_prev_item( key );
 167                 if ( !pos.second )
 168                     return false;
 169
 170                 // key exists
 171                 cds::unref( f )( *(++pos.first), key );
 172                 return true;
 173             }
 174
 175             template <typename Q, typename Less, typename Func>
 176             bool find( Q& key, Less pred, Func f )
 177             {
 178                 std::pair< iterator, bool > pos = find_prev_item( key, pred );
 179                 if ( !pos.second )
 180                     return false;
 181
 182                 // key exists
 183                 cds::unref( f )( *(++pos.first), key );
 184                 return true;
 185             }
 186
 187             void clear()
 188             {
 189                 m_List.clear();
 190             }
 191
 192             template <typename Disposer>
 193             void clear( Disposer disposer )
 194             {
 195                 m_List.clear_and_dispose( disposer );
 196             }
 197
 198             iterator begin()                { return m_List.begin(); }
 199             const_iterator begin() const    { return m_List.begin(); }
 200             iterator end()                  { return m_List.end(); }
 201             const_iterator end() const      { return m_List.end(); }
 202
 203             size_t size() const
 204             {
 205                 return (size_t) m_List.size();
 206             }
 207
 208             void move_item( adapted_container& from, iterator itWhat )
 209             {
 210                 value_type& val = *itWhat;
 211                 from.base_container().erase( itWhat );
 212 #           ifdef CDS_CXX11_LAMBDA_SUPPORT
 213                 insert( val, []( value_type& ) {} );
 214 #           else
 215                 insert( val, empty_insert_functor() );
 216 #           endif
 217             }
 218
 219         };
 220     public:
 221         typedef adapted_container   type ;  ///< Result of the metafunction
 222     };
 223 }}} // namespace cds::intrusive::striped_set
 224 //@endcond
 225
 226 #endif // #ifndef __CDS_INTRUSIVE_STRIPED_SET_BOOST_SLIST_ADAPTER_H