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