cds/container/striped_set/boost_slist.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_STRIPED_SET_BOOST_SLIST_ADAPTER_H
   4 #define __CDS_CONTAINER_STRIPED_SET_BOOST_SLIST_ADAPTER_H
   5
   6 #include <cds/container/striped_set/adapter.h>
   7 #include <cds/ref.h>
   8 #include <boost/container/slist.hpp>
   9
  10 //@cond
  11 namespace cds { namespace container {
  12     namespace striped_set {
  13
  14         // Copy policy for boost::container::slist
  15         template <typename T, typename Alloc>
  16         struct copy_item_policy< boost::container::slist< T, Alloc > >
  17         {
  18             typedef boost::container::slist< T, Alloc > list_type;
  19             typedef typename list_type::iterator    iterator;
  20
  21             void operator()( list_type& list, iterator itInsert, iterator itWhat )
  22             {
  23                 list.insert_after( itInsert, *itWhat );
  24             }
  25         };
  26
  27         // Swap policy for boost::container::slist
  28         template <typename T, typename Alloc>
  29         struct swap_item_policy< boost::container::slist< T, Alloc > >
  30         {
  31             typedef boost::container::slist< T, Alloc > list_type;
  32             typedef typename list_type::iterator    iterator;
  33
  34             void operator()( list_type& list, iterator itInsert, iterator itWhat )
  35             {
  36                 T newVal;
  37                 itInsert = list.insert_after( itInsert, newVal );
  38                 std::swap( *itInsert, *itWhat );
  39             }
  40         };
  41
  42 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
  43         // Move policy for boost::container::slist
  44         template <typename T, typename Alloc>
  45         struct move_item_policy< boost::container::slist< T, Alloc > >
  46         {
  47             typedef boost::container::slist< T, Alloc > list_type;
  48             typedef typename list_type::iterator    iterator;
  49
  50             void operator()( list_type& list, iterator itInsert, iterator itWhat )
  51             {
  52                 list.insert_after( itInsert, std::move( *itWhat ) );
  53             }
  54         };
  55 #endif
  56
  57     }   // namespace striped_set
  58 }} // namespace cds::container
  59
  60 namespace cds { namespace intrusive { namespace striped_set {
  61
  62     /// boost::container::slist adapter for hash set bucket
  63     template <typename T, class Alloc, CDS_SPEC_OPTIONS>
  64     class adapt< boost::container::slist<T, Alloc>, CDS_OPTIONS >
  65     {
  66     public:
  67         typedef boost::container::slist<T, Alloc>     container_type          ;   ///< underlying container type
  68
  69     private:
  70         /// Adapted container type
  71         class adapted_container: public cds::container::striped_set::adapted_sequential_container
  72         {
  73         public:
  74             typedef typename container_type::value_type value_type  ;   ///< value type stored in the container
  75             typedef typename container_type::iterator      iterator ;   ///< container iterator
  76             typedef typename container_type::const_iterator const_iterator ;    ///< container const iterator
  77
  78             static bool const has_find_with = true;
  79             static bool const has_erase_with = true;
  80
  81         private:
  82             //@cond
  83             typedef typename cds::opt::details::make_comparator_from_option_list< value_type, CDS_OPTIONS >::type key_comparator;
  84
  85             typedef typename cds::opt::select<
  86                 typename cds::opt::value<
  87                     typename cds::opt::find_option<
  88                         cds::opt::copy_policy< cds::container::striped_set::move_item >
  89                         , CDS_OPTIONS
  90                     >::type
  91                 >::copy_policy
  92                 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
  93                 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
  94 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
  95                 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
  96 #endif
  97             >::type copy_item;
  98
  99             template <typename Q>
 100             std::pair< iterator, bool > find_prev_item( Q const& key )
 101             {
 102                 iterator itPrev = m_List.before_begin();
 103                 iterator itEnd = m_List.end();
 104                 for ( iterator it = m_List.begin(); it != itEnd; ++it ) {
 105                     int nCmp = key_comparator()( key, *it );
 106                     if ( nCmp < 0 )
 107                         itPrev = it;
 108                     else if ( nCmp > 0 )
 109                         break;
 110                     else
 111                         return std::make_pair( itPrev, true );
 112                 }
 113                 return std::make_pair( itPrev, false );
 114             }
 115
 116             template <typename Q, typename Less>
 117             std::pair< iterator, bool > find_prev_item( Q const& key, Less pred )
 118             {
 119                 iterator itPrev = m_List.before_begin();
 120                 iterator itEnd = m_List.end();
 121                 for ( iterator it = m_List.begin(); it != itEnd; ++it ) {
 122                     if ( pred( key, *it ))
 123                         itPrev = it;
 124                     else if ( pred( *it, key ) )
 125                         break;
 126                     else
 127                         return std::make_pair( itPrev, true );
 128                 }
 129                 return std::make_pair( itPrev, false );
 130             }
 131
 132             //@endcond
 133
 134         private:
 135             //@cond
 136             container_type  m_List;
 137             //@endcond
 138
 139         public:
 140             adapted_container()
 141             {}
 142
 143             template <typename Q, typename Func>
 144             bool insert( const Q& val, Func f )
 145             {
 146                 std::pair< iterator, bool > pos = find_prev_item( val );
 147                 if ( !pos.second ) {
 148                     value_type newItem( val );
 149                     pos.first = m_List.insert_after( pos.first, newItem );
 150                     cds::unref( f )( *pos.first );
 151                     return true;
 152                 }
 153
 154                 // key already exists
 155                 return false;
 156             }
 157
 158 #           ifdef CDS_EMPLACE_SUPPORT
 159             template <typename... Args>
 160             bool emplace( Args&&... args )
 161             {
 162                 value_type val( std::forward<Args>(args)... );
 163                 std::pair< iterator, bool > pos = find_prev_item( val );
 164                 if ( !pos.second ) {
 165                     m_List.emplace_after( pos.first, std::move( val ) );
 166                     return true;
 167                 }
 168                 return false;
 169             }
 170 #           endif
 171
 172             template <typename Q, typename Func>
 173             std::pair<bool, bool> ensure( const Q& val, Func func )
 174             {
 175                 std::pair< iterator, bool > pos = find_prev_item( val );
 176                 if ( !pos.second ) {
 177                     // insert new
 178                     value_type newItem( val );
 179                     pos.first = m_List.insert_after( pos.first, newItem );
 180                     cds::unref( func )( true, *pos.first, val );
 181                     return std::make_pair( true, true );
 182                 }
 183                 else {
 184                     // already exists
 185                     cds::unref( func )( false, *(++pos.first), val );
 186                     return std::make_pair( true, false );
 187                 }
 188             }
 189
 190             template <typename Q, typename Func>
 191             bool erase( Q const& key, Func f )
 192             {
 193                 std::pair< iterator, bool > pos = find_prev_item( key );
 194                 if ( !pos.second )
 195                     return false;
 196
 197                 // key exists
 198                 iterator it = pos.first;
 199                 cds::unref( f )( *(++it) );
 200                 m_List.erase_after( pos.first );
 201
 202                 return true;
 203             }
 204
 205             template <typename Q, typename Less, typename Func>
 206             bool erase( Q const& key, Less pred, Func f )
 207             {
 208                 std::pair< iterator, bool > pos = find_prev_item( key, pred );
 209                 if ( !pos.second )
 210                     return false;
 211
 212                 // key exists
 213                 iterator it = pos.first;
 214                 cds::unref( f )( *(++it) );
 215                 m_List.erase_after( pos.first );
 216
 217                 return true;
 218             }
 219
 220             template <typename Q, typename Func>
 221             bool find( Q& val, Func f )
 222             {
 223                 std::pair< iterator, bool > pos = find_prev_item( val );
 224                 if ( !pos.second )
 225                     return false;
 226
 227                 // key exists
 228                 cds::unref( f )( *(++pos.first), val );
 229                 return true;
 230             }
 231
 232             template <typename Q, typename Less, typename Func>
 233             bool find( Q& val, Less pred, Func f )
 234             {
 235                 std::pair< iterator, bool > pos = find_prev_item( val, pred );
 236                 if ( !pos.second )
 237                     return false;
 238
 239                 // key exists
 240                 cds::unref( f )( *(++pos.first), val );
 241                 return true;
 242             }
 243
 244             void clear()
 245             {
 246                 m_List.clear();
 247             }
 248
 249             iterator begin()                { return m_List.begin(); }
 250             const_iterator begin() const    { return m_List.begin(); }
 251             iterator end()                  { return m_List.end(); }
 252             const_iterator end() const      { return m_List.end(); }
 253
 254             void move_item( adapted_container& /*from*/, iterator itWhat )
 255             {
 256                 std::pair< iterator, bool > pos = find_prev_item( *itWhat );
 257                 assert( !pos.second );
 258
 259                 copy_item()( m_List, pos.first, itWhat );
 260             }
 261
 262             size_t size() const
 263             {
 264                 return m_List.size();
 265             }
 266         };
 267
 268     public:
 269         typedef adapted_container type ; ///< Result of \p adapt metafunction
 270
 271     };
 272 }}} // namespace cds::intrusive::striped_set
 273
 274
 275 //@endcond
 276
 277 #endif // #ifndef __CDS_CONTAINER_STRIPED_SET_BOOST_SLIST_ADAPTER_H