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, typename... BIOptons, typename... Options>
  13     class adapt< boost::intrusive::slist< T, BIOptons... >, Options... >
  14     {
  15     public:
  16         typedef boost::intrusive::slist< T, BIOptons... >  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, 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         private:
  87             container_type  m_List;
  88
  89         public:
  90             adapted_container()
  91             {}
  92
  93             container_type& base_container()
  94             {
  95                 return m_List;
  96             }
  97
  98             template <typename Func>
  99             bool insert( value_type& val, Func f )
 100             {
 101                 std::pair< iterator, bool > pos = find_prev_item( val );
 102                 if ( !pos.second ) {
 103                     m_List.insert_after( pos.first, val );
 104                     cds::unref( f )( val );
 105                     return true;
 106                 }
 107
 108                 // key already exists
 109                 return false;
 110             }
 111
 112             template <typename Func>
 113             std::pair<bool, bool> ensure( value_type& val, Func f )
 114             {
 115                 std::pair< iterator, bool > pos = find_prev_item( val );
 116                 if ( !pos.second ) {
 117                     // insert new
 118                     m_List.insert_after( pos.first, val );
 119                     cds::unref( f )( true, val, val );
 120                     return std::make_pair( true, true );
 121                 }
 122                 else {
 123                     // already exists
 124                     cds::unref( f )( false, *(++pos.first), val );
 125                     return std::make_pair( true, false );
 126                 }
 127             }
 128
 129             bool unlink( value_type& val )
 130             {
 131                 std::pair< iterator, bool > pos = find_prev_item( val );
 132                 if ( !pos.second )
 133                     return false;
 134
 135                 ++pos.first;
 136                 if ( &(*pos.first) != &val )
 137                     return false;
 138
 139                 m_List.erase( pos.first );
 140                 return true;
 141             }
 142
 143             template <typename Q, typename Func>
 144             value_type * erase( Q const& key, Func f )
 145             {
 146                 return erase_( key, key_comparator(), f );
 147             }
 148
 149             template <typename Q, typename Less, typename Func>
 150             value_type * erase( Q const& key, Less pred, Func f )
 151             {
 152                 return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
 153             }
 154
 155             template <typename Q, typename Func>
 156             bool find( Q& key, Func f )
 157             {
 158                 std::pair< iterator, bool > pos = find_prev_item( key );
 159                 if ( !pos.second )
 160                     return false;
 161
 162                 // key exists
 163                 cds::unref( f )( *(++pos.first), key );
 164                 return true;
 165             }
 166
 167             template <typename Q, typename Less, typename Func>
 168             bool find( Q& key, Less pred, Func f )
 169             {
 170                 std::pair< iterator, bool > pos = find_prev_item( key, pred );
 171                 if ( !pos.second )
 172                     return false;
 173
 174                 // key exists
 175                 cds::unref( f )( *(++pos.first), key );
 176                 return true;
 177             }
 178
 179             void clear()
 180             {
 181                 m_List.clear();
 182             }
 183
 184             template <typename Disposer>
 185             void clear( Disposer disposer )
 186             {
 187                 m_List.clear_and_dispose( disposer );
 188             }
 189
 190             iterator begin()                { return m_List.begin(); }
 191             const_iterator begin() const    { return m_List.begin(); }
 192             iterator end()                  { return m_List.end(); }
 193             const_iterator end() const      { return m_List.end(); }
 194
 195             size_t size() const
 196             {
 197                 return (size_t) m_List.size();
 198             }
 199
 200             void move_item( adapted_container& from, iterator itWhat )
 201             {
 202                 value_type& val = *itWhat;
 203                 from.base_container().erase( itWhat );
 204                 insert( val, []( value_type& ) {} );
 205             }
 206
 207         };
 208     public:
 209         typedef adapted_container   type ;  ///< Result of the metafunction
 210     };
 211 }}} // namespace cds::intrusive::striped_set
 212 //@endcond
 213
 214 #endif // #ifndef __CDS_INTRUSIVE_STRIPED_SET_BOOST_SLIST_ADAPTER_H