cds/container/striped_map/boost_list.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_STRIPED_MAP_BOOST_LIST_ADAPTER_H
   4 #define __CDS_CONTAINER_STRIPED_MAP_BOOST_LIST_ADAPTER_H
   5
   6 #include <boost/version.hpp>
   7 #if BOOST_VERSION < 104800
   8 #   error "For boost::container::list you must use boost 1.48 or above"
   9 #endif
  10
  11 #include <cds/container/striped_set/adapter.h>
  12 #include <cds/ref.h>
  13 #include <boost/container/list.hpp>
  14 #include <algorithm>    // std::lower_bound
  15 #include <utility>      // std::pair
  16
  17 //@cond
  18 namespace cds { namespace container {
  19     namespace striped_set {
  20
  21         // Copy policy for map
  22         template <typename K, typename T, typename Alloc>
  23         struct copy_item_policy< boost::container::list< std::pair< K const, T >, Alloc > >
  24         {
  25             typedef std::pair< K const, T>  pair_type;
  26             typedef boost::container::list< pair_type, Alloc > list_type;
  27             typedef typename list_type::iterator    iterator;
  28
  29             void operator()( list_type& list, iterator itInsert, iterator itWhat )
  30             {
  31                 list.insert( itInsert, *itWhat );
  32             }
  33         };
  34
  35         // Swap policy for map
  36         template <typename K, typename T, typename Alloc>
  37         struct swap_item_policy< boost::container::list< std::pair< K const, T >, Alloc > >
  38         {
  39             typedef std::pair< K const, T>  pair_type;
  40             typedef boost::container::list< pair_type, Alloc > list_type;
  41             typedef typename list_type::iterator    iterator;
  42
  43             void operator()( list_type& list, iterator itInsert, iterator itWhat )
  44             {
  45                 pair_type newVal( itWhat->first, typename pair_type::second_type() );
  46                 itInsert = list.insert( itInsert, newVal );
  47                 std::swap( itInsert->second, itWhat->second );
  48             }
  49         };
  50
  51 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
  52         // Move policy for map
  53         template <typename K, typename T, typename Alloc>
  54         struct move_item_policy< boost::container::list< std::pair< K const, T >, Alloc > >
  55         {
  56             typedef std::pair< K const, T>          pair_type;
  57             typedef boost::container::list< pair_type, Alloc >   list_type;
  58             typedef typename list_type::iterator    iterator;
  59
  60             void operator()( list_type& list, iterator itInsert, iterator itWhat )
  61             {
  62                 list.insert( itInsert, std::move( *itWhat ) );
  63             }
  64         };
  65 #endif
  66     } // namespace striped_set
  67 }} // namespace cds:container
  68
  69 namespace cds { namespace intrusive { namespace striped_set {
  70
  71     /// boost::container::list adapter for hash map bucket
  72     template <typename Key, typename T, class Alloc, CDS_SPEC_OPTIONS>
  73     class adapt< boost::container::list< std::pair<Key const, T>, Alloc>, CDS_OPTIONS >
  74     {
  75     public:
  76         typedef boost::container::list< std::pair<Key const, T>, Alloc>     container_type          ;   ///< underlying container type
  77
  78     private:
  79         /// Adapted container type
  80         class adapted_container: public cds::container::striped_set::adapted_sequential_container
  81         {
  82         public:
  83             typedef typename container_type::value_type value_type  ;   ///< value type stored in the container
  84             typedef typename value_type::first_type     key_type;
  85             typedef typename value_type::second_type    mapped_type;
  86             typedef typename container_type::iterator   iterator    ;   ///< container iterator
  87             typedef typename container_type::const_iterator const_iterator ;    ///< container const iterator
  88
  89             static bool const has_find_with = true;
  90             static bool const has_erase_with = true;
  91
  92         private:
  93             //@cond
  94             typedef typename cds::opt::details::make_comparator_from_option_list< value_type, CDS_OPTIONS >::type key_comparator;
  95
  96             typedef typename cds::opt::select<
  97                 typename cds::opt::value<
  98                     typename cds::opt::find_option<
  99                         cds::opt::copy_policy< cds::container::striped_set::move_item >
 100                         , CDS_OPTIONS
 101                     >::type
 102                 >::copy_policy
 103                 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
 104                 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
 105 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
 106                 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
 107 #endif
 108             >::type copy_item;
 109
 110             struct find_predicate
 111             {
 112                 bool operator()( value_type const& i1, value_type const& i2) const
 113                 {
 114                     return key_comparator()( i1.first, i2.first ) < 0;
 115                 }
 116
 117                 template <typename Q>
 118                 bool operator()( Q const& i1, value_type const& i2) const
 119                 {
 120                     return key_comparator()( i1, i2.first ) < 0;
 121                 }
 122
 123                 template <typename Q>
 124                 bool operator()( value_type const& i1, Q const& i2) const
 125                 {
 126                     return key_comparator()( i1.first, i2 ) < 0;
 127                 }
 128             };
 129             //@endcond
 130
 131         private:
 132             //@cond
 133             container_type  m_List;
 134             //@endcond
 135
 136         public:
 137             adapted_container()
 138             {}
 139
 140             template <typename Q, typename Func>
 141             bool insert( const Q& key, Func f )
 142             {
 143                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
 144                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
 145                     //value_type newItem( key );
 146                     it = m_List.insert( it, value_type( key, mapped_type()) );
 147                     cds::unref( f )( *it );
 148
 149                     return true;
 150                 }
 151
 152                 // key already exists
 153                 return false;
 154             }
 155
 156 #           ifdef CDS_EMPLACE_SUPPORT
 157             template <typename K, typename... Args>
 158             bool emplace( K&& key, Args&&... args )
 159             {
 160                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
 161                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
 162                     m_List.emplace( it, std::forward<K>(key), std::move( mapped_type( std::forward<Args>(args)... )) );
 163                     return true;
 164                 }
 165                 return false;
 166             }
 167 #           endif
 168
 169             template <typename Q, typename Func>
 170             std::pair<bool, bool> ensure( const Q& key, Func func )
 171             {
 172                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
 173                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
 174                     // insert new
 175                     value_type newItem( key, mapped_type() );
 176                     it = m_List.insert( it, newItem );
 177                     cds::unref( func )( true, *it );
 178
 179                     return std::make_pair( true, true );
 180                 }
 181                 else {
 182                     // already exists
 183                     cds::unref( func )( false, *it );
 184                     return std::make_pair( true, false );
 185                 }
 186             }
 187
 188             template <typename Q, typename Func>
 189             bool erase( Q const& key, Func f )
 190             {
 191                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
 192                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 )
 193                     return false;
 194
 195                 // key exists
 196                 cds::unref( f )( *it );
 197                 m_List.erase( it );
 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                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, pred );
 206                 if ( it == m_List.end() || pred( key, it->first ) || pred(it->first, key) )
 207                     return false;
 208
 209                 // key exists
 210                 cds::unref( f )( *it );
 211                 m_List.erase( it );
 212
 213                 return true;
 214             }
 215
 216             template <typename Q, typename Func>
 217             bool find( Q& val, Func f )
 218             {
 219                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
 220                 if ( it == m_List.end() || key_comparator()( val, it->first ) != 0 )
 221                     return false;
 222
 223                 // key exists
 224                 cds::unref( f )( *it, 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                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, pred );
 232                 if ( it == m_List.end() || pred( val, it->first ) || pred( it->first, val ) )
 233                     return false;
 234
 235                 // key exists
 236                 cds::unref( f )( *it, val );
 237                 return true;
 238             }
 239
 240             /// Clears the container
 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                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), *itWhat, find_predicate() );
 254                 assert( it == m_List.end() || key_comparator()( itWhat->first, it->first ) != 0 );
 255
 256                 copy_item()( m_List, it, 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
 270 }}} // namespace cds::intrusive::striped_set
 271 //@endcond
 272
 273 #endif // #ifndef __CDS_CONTAINER_STRIPED_MAP_BOOST_LIST_ADAPTER_H