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         // 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, CDS_SPEC_OPTIONS>
  62     class adapt< boost::container::slist<T, Alloc>, CDS_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, CDS_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                         , CDS_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                     cds::unref( f )( *pos.first );
 147                     return true;
 148                 }
 149
 150                 // key already exists
 151                 return false;
 152             }
 153
 154 #           ifdef CDS_EMPLACE_SUPPORT
 155             template <typename... Args>
 156             bool emplace( Args&&... args )
 157             {
 158                 value_type val( std::forward<Args>(args)... );
 159                 std::pair< iterator, bool > pos = find_prev_item( val );
 160                 if ( !pos.second ) {
 161                     m_List.emplace_after( pos.first, std::move( val ) );
 162                     return true;
 163                 }
 164                 return false;
 165             }
 166 #           endif
 167
 168             template <typename Q, typename Func>
 169             std::pair<bool, bool> ensure( const Q& val, Func func )
 170             {
 171                 std::pair< iterator, bool > pos = find_prev_item( val );
 172                 if ( !pos.second ) {
 173                     // insert new
 174                     value_type newItem( val );
 175                     pos.first = m_List.insert_after( pos.first, newItem );
 176                     cds::unref( func )( true, *pos.first, val );
 177                     return std::make_pair( true, true );
 178                 }
 179                 else {
 180                     // already exists
 181                     cds::unref( func )( false, *(++pos.first), val );
 182                     return std::make_pair( true, false );
 183                 }
 184             }
 185
 186             template <typename Q, typename Func>
 187             bool erase( Q const& key, Func f )
 188             {
 189                 std::pair< iterator, bool > pos = find_prev_item( key );
 190                 if ( !pos.second )
 191                     return false;
 192
 193                 // key exists
 194                 iterator it = pos.first;
 195                 cds::unref( f )( *(++it) );
 196                 m_List.erase_after( pos.first );
 197
 198                 return true;
 199             }
 200
 201             template <typename Q, typename Less, typename Func>
 202             bool erase( Q const& key, Less pred, Func f )
 203             {
 204                 std::pair< iterator, bool > pos = find_prev_item( key, pred );
 205                 if ( !pos.second )
 206                     return false;
 207
 208                 // key exists
 209                 iterator it = pos.first;
 210                 cds::unref( f )( *(++it) );
 211                 m_List.erase_after( pos.first );
 212
 213                 return true;
 214             }
 215
 216             template <typename Q, typename Func>
 217             bool find( Q& val, Func f )
 218             {
 219                 std::pair< iterator, bool > pos = find_prev_item( val );
 220                 if ( !pos.second )
 221                     return false;
 222
 223                 // key exists
 224                 cds::unref( f )( *(++pos.first), val );
 225                 return true;
 226             }
 227
 228             template <typename Q, typename Less, typename Func>
 229             bool find( Q& val, Less pred, Func f )
 230             {
 231                 std::pair< iterator, bool > pos = find_prev_item( val, pred );
 232                 if ( !pos.second )
 233                     return false;
 234
 235                 // key exists
 236                 cds::unref( f )( *(++pos.first), val );
 237                 return true;
 238             }
 239
 240             void clear()
 241             {
 242                 m_List.clear();
 243             }
 244
 245             iterator begin()                { return m_List.begin(); }
 246             const_iterator begin() const    { return m_List.begin(); }
 247             iterator end()                  { return m_List.end(); }
 248             const_iterator end() const      { return m_List.end(); }
 249
 250             void move_item( adapted_container& /*from*/, iterator itWhat )
 251             {
 252                 std::pair< iterator, bool > pos = find_prev_item( *itWhat );
 253                 assert( !pos.second );
 254
 255                 copy_item()( m_List, pos.first, itWhat );
 256             }
 257
 258             size_t size() const
 259             {
 260                 return m_List.size();
 261             }
 262         };
 263
 264     public:
 265         typedef adapted_container type ; ///< Result of \p adapt metafunction
 266
 267     };
 268 }}} // namespace cds::intrusive::striped_set
 269
 270
 271 //@endcond
 272
 273 #endif // #ifndef __CDS_CONTAINER_STRIPED_SET_BOOST_SLIST_ADAPTER_H