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