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