cds/intrusive/striped_set/boost_slist.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_BOOST_SLIST_ADAPTER_H
   4 #define CDSLIB_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> update( value_type& val, Func f, bool bAllowInsert )
 115                 {
 116                     std::pair< iterator, bool > pos = find_prev_item( val );
 117                     if ( !pos.second ) {
 118                         // insert new
 119                         if ( !bAllowInsert )
 120                             return std::make_pair( false, false );
 121
 122                         m_List.insert_after( pos.first, val );
 123                         f( true, val, val );
 124                         return std::make_pair( true, true );
 125                     }
 126                     else {
 127                         // already exists
 128                         f( false, *(++pos.first), val );
 129                         return std::make_pair( true, false );
 130                     }
 131                 }
 132
 133                 bool unlink( value_type& val )
 134                 {
 135                     std::pair< iterator, bool > pos = find_prev_item( val );
 136                     if ( !pos.second )
 137                         return false;
 138
 139                     ++pos.first;
 140                     if ( &(*pos.first) != &val )
 141                         return false;
 142
 143                     m_List.erase( pos.first );
 144                     return true;
 145                 }
 146
 147                 template <typename Q, typename Func>
 148                 value_type * erase( Q const& key, Func f )
 149                 {
 150                     return erase_( key, key_comparator(), f );
 151                 }
 152
 153                 template <typename Q, typename Less, typename Func>
 154                 value_type * erase( Q const& key, Less /*pred*/, Func f )
 155                 {
 156                     return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
 157                 }
 158
 159                 template <typename Q, typename Func>
 160                 bool find( Q& key, Func f )
 161                 {
 162                     std::pair< iterator, bool > pos = find_prev_item( key );
 163                     if ( !pos.second )
 164                         return false;
 165
 166                     // key exists
 167                     f( *(++pos.first), key );
 168                     return true;
 169                 }
 170
 171                 template <typename Q, typename Less, typename Func>
 172                 bool find( Q& key, Less pred, Func f )
 173                 {
 174                     std::pair< iterator, bool > pos = find_prev_item( key, pred );
 175                     if ( !pos.second )
 176                         return false;
 177
 178                     // key exists
 179                     f( *(++pos.first), key );
 180                     return true;
 181                 }
 182
 183                 void clear()
 184                 {
 185                     m_List.clear();
 186                 }
 187
 188                 template <typename Disposer>
 189                 void clear( Disposer disposer )
 190                 {
 191                     m_List.clear_and_dispose( disposer );
 192                 }
 193
 194                 iterator begin() { return m_List.begin(); }
 195                 const_iterator begin() const { return m_List.begin(); }
 196                 iterator end() { return m_List.end(); }
 197                 const_iterator end() const { return m_List.end(); }
 198
 199                 size_t size() const
 200                 {
 201                     return (size_t)m_List.size();
 202                 }
 203
 204                 void move_item( adapted_container& from, iterator itWhat )
 205                 {
 206                     value_type& val = *itWhat;
 207                     from.base_container().erase( itWhat );
 208                     insert( val, []( value_type& ) {} );
 209                 }
 210
 211             };
 212         public:
 213             typedef adapted_container   type;  ///< Result of the metafunction
 214         };
 215     } // namespace details
 216
 217 #if CDS_COMPILER == CDS_COMPILER_INTEL && CDS_COMPILER_VERSION <= 1500
 218     template <typename T, typename P1, typename P2, typename P3, typename P4, typename P5, typename... Options>
 219     class adapt< boost::intrusive::slist< T, P1, P2, P3, P4, P5 >, Options... >
 220         : public details::adapt_boost_slist< boost::intrusive::slist< T, P1, P2, P3, P4, P5 >, Options... >
 221     {};
 222 #else
 223     template <typename T, typename... BIOptions, typename... Options>
 224     class adapt< boost::intrusive::slist< T, BIOptions... >, Options... >
 225         : public details::adapt_boost_slist< boost::intrusive::slist< T, BIOptions... >, Options... >
 226     {};
 227 #endif
 228
 229 }}} // namespace cds::intrusive::striped_set
 230 //@endcond
 231
 232 #endif // #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_BOOST_SLIST_ADAPTER_H