cds/container/striped_set/boost_slist.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_STRIPED_SET_BOOST_SLIST_ADAPTER_H
   4 #define CDSLIB_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> update( const Q& val, Func func, bool bAllowInsert )
 168             {
 169                 std::pair< iterator, bool > pos = find_prev_item( val );
 170                 if ( !pos.second ) {
 171                     // insert new
 172                     if ( !bAllowInsert )
 173                         return std::make_pair( false, false );
 174
 175                     value_type newItem( val );
 176                     pos.first = m_List.insert_after( pos.first, newItem );
 177                     func( true, *pos.first, val );
 178                     return std::make_pair( true, true );
 179                 }
 180                 else {
 181                     // already exists
 182                     func( false, *(++pos.first), val );
 183                     return std::make_pair( true, false );
 184                 }
 185             }
 186
 187             template <typename Q, typename Func>
 188             bool erase( Q const& key, Func f )
 189             {
 190                 std::pair< iterator, bool > pos = find_prev_item( key );
 191                 if ( !pos.second )
 192                     return false;
 193
 194                 // key exists
 195                 iterator it = pos.first;
 196                 f( *(++it) );
 197                 m_List.erase_after( pos.first );
 198
 199                 return true;
 200             }
 201
 202             template <typename Q, typename Less, typename Func>
 203             bool erase( Q const& key, Less pred, Func f )
 204             {
 205                 std::pair< iterator, bool > pos = find_prev_item( key, pred );
 206                 if ( !pos.second )
 207                     return false;
 208
 209                 // key exists
 210                 iterator it = pos.first;
 211                 f( *(++it) );
 212                 m_List.erase_after( pos.first );
 213
 214                 return true;
 215             }
 216
 217             template <typename Q, typename Func>
 218             bool find( Q& val, Func f )
 219             {
 220                 std::pair< iterator, bool > pos = find_prev_item( val );
 221                 if ( !pos.second )
 222                     return false;
 223
 224                 // key exists
 225                 f( *(++pos.first), val );
 226                 return true;
 227             }
 228
 229             template <typename Q, typename Less, typename Func>
 230             bool find( Q& val, Less pred, Func f )
 231             {
 232                 std::pair< iterator, bool > pos = find_prev_item( val, pred );
 233                 if ( !pos.second )
 234                     return false;
 235
 236                 // key exists
 237                 f( *(++pos.first), val );
 238                 return true;
 239             }
 240
 241             void clear()
 242             {
 243                 m_List.clear();
 244             }
 245
 246             iterator begin()                { return m_List.begin(); }
 247             const_iterator begin() const    { return m_List.begin(); }
 248             iterator end()                  { return m_List.end(); }
 249             const_iterator end() const      { return m_List.end(); }
 250
 251             void move_item( adapted_container& /*from*/, iterator itWhat )
 252             {
 253                 std::pair< iterator, bool > pos = find_prev_item( *itWhat );
 254                 assert( !pos.second );
 255
 256                 copy_item()( m_List, pos.first, itWhat );
 257             }
 258
 259             size_t size() const
 260             {
 261                 return m_List.size();
 262             }
 263         };
 264
 265     public:
 266         typedef adapted_container type ; ///< Result of \p adapt metafunction
 267
 268     };
 269 }}} // namespace cds::intrusive::striped_set
 270
 271
 272 //@endcond
 273
 274 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_BOOST_SLIST_ADAPTER_H