cds/container/striped_map/boost_list.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_STRIPED_MAP_BOOST_LIST_ADAPTER_H
   4 #define CDSLIB_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 <functional>   // ref
  12 #include <algorithm>    // std::lower_bound
  13 #include <utility>      // std::pair
  14 #include <cds/container/striped_set/adapter.h>
  15 #include <boost/container/list.hpp>
  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         // Move policy for map
  52         template <typename K, typename T, typename Alloc>
  53         struct move_item_policy< boost::container::list< std::pair< K const, T >, Alloc > >
  54         {
  55             typedef std::pair< K const, T>          pair_type;
  56             typedef boost::container::list< pair_type, Alloc >   list_type;
  57             typedef typename list_type::iterator    iterator;
  58
  59             void operator()( list_type& list, iterator itInsert, iterator itWhat )
  60             {
  61                 list.insert( itInsert, std::move( *itWhat ) );
  62             }
  63         };
  64     } // namespace striped_set
  65 }} // namespace cds:container
  66
  67 namespace cds { namespace intrusive { namespace striped_set {
  68
  69     /// boost::container::list adapter for hash map bucket
  70     template <typename Key, typename T, class Alloc, typename... Options>
  71     class adapt< boost::container::list< std::pair<Key const, T>, Alloc>, Options... >
  72     {
  73     public:
  74         typedef boost::container::list< std::pair<Key const, T>, Alloc>     container_type          ;   ///< underlying container type
  75
  76     private:
  77         /// Adapted container type
  78         class adapted_container: public cds::container::striped_set::adapted_sequential_container
  79         {
  80         public:
  81             typedef typename container_type::value_type value_type  ;   ///< value type stored in the container
  82             typedef typename value_type::first_type     key_type;
  83             typedef typename value_type::second_type    mapped_type;
  84             typedef typename container_type::iterator   iterator    ;   ///< container iterator
  85             typedef typename container_type::const_iterator const_iterator ;    ///< container const iterator
  86
  87             static bool const has_find_with = true;
  88             static bool const has_erase_with = true;
  89
  90         private:
  91             //@cond
  92             typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
  93
  94             typedef typename cds::opt::select<
  95                 typename cds::opt::value<
  96                     typename cds::opt::find_option<
  97                         cds::opt::copy_policy< cds::container::striped_set::move_item >
  98                         , Options...
  99                     >::type
 100                 >::copy_policy
 101                 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
 102                 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
 103                 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
 104             >::type copy_item;
 105
 106             struct find_predicate
 107             {
 108                 bool operator()( value_type const& i1, value_type const& i2) const
 109                 {
 110                     return key_comparator()( i1.first, i2.first ) < 0;
 111                 }
 112
 113                 template <typename Q>
 114                 bool operator()( Q const& i1, value_type const& i2) const
 115                 {
 116                     return key_comparator()( i1, i2.first ) < 0;
 117                 }
 118
 119                 template <typename Q>
 120                 bool operator()( value_type const& i1, Q const& i2) const
 121                 {
 122                     return key_comparator()( i1.first, i2 ) < 0;
 123                 }
 124             };
 125             //@endcond
 126
 127         private:
 128             //@cond
 129             container_type  m_List;
 130             //@endcond
 131
 132         public:
 133             adapted_container()
 134             {}
 135
 136             template <typename Q, typename Func>
 137             bool insert( const Q& key, Func f )
 138             {
 139                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
 140                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
 141                     //value_type newItem( key );
 142                     it = m_List.insert( it, value_type( key, mapped_type()) );
 143                     f( *it );
 144
 145                     return true;
 146                 }
 147
 148                 // key already exists
 149                 return false;
 150             }
 151
 152             template <typename K, typename... Args>
 153             bool emplace( K&& key, Args&&... args )
 154             {
 155                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
 156                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
 157                     m_List.emplace( it, std::forward<K>(key), std::move( mapped_type( std::forward<Args>(args)... )) );
 158                     return true;
 159                 }
 160                 return false;
 161             }
 162
 163             template <typename Q, typename Func>
 164             std::pair<bool, bool> update( const Q& key, Func func, bool bAllowInsert )
 165             {
 166                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
 167                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
 168                     // insert new
 169                     if ( !bAllowInsert )
 170                         return std::make_pair( false, false );
 171
 172                     value_type newItem( key, mapped_type() );
 173                     it = m_List.insert( it, newItem );
 174                     func( true, *it );
 175
 176                     return std::make_pair( true, true );
 177                 }
 178                 else {
 179                     // already exists
 180                     func( false, *it );
 181                     return std::make_pair( true, false );
 182                 }
 183             }
 184
 185             template <typename Q, typename Func>
 186             bool erase( Q const& key, Func f )
 187             {
 188                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
 189                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 )
 190                     return false;
 191
 192                 // key exists
 193                 f( *it );
 194                 m_List.erase( it );
 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                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, pred );
 203                 if ( it == m_List.end() || pred( key, it->first ) || pred(it->first, key) )
 204                     return false;
 205
 206                 // key exists
 207                 f( *it );
 208                 m_List.erase( it );
 209
 210                 return true;
 211             }
 212
 213             template <typename Q, typename Func>
 214             bool find( Q& val, Func f )
 215             {
 216                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
 217                 if ( it == m_List.end() || key_comparator()( val, it->first ) != 0 )
 218                     return false;
 219
 220                 // key exists
 221                 f( *it, val );
 222                 return true;
 223             }
 224
 225             template <typename Q, typename Less, typename Func>
 226             bool find( Q& val, Less pred, Func f )
 227             {
 228                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, pred );
 229                 if ( it == m_List.end() || pred( val, it->first ) || pred( it->first, val ) )
 230                     return false;
 231
 232                 // key exists
 233                 f( *it, val );
 234                 return true;
 235             }
 236
 237             /// Clears the container
 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                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), *itWhat, find_predicate() );
 251                 assert( it == m_List.end() || key_comparator()( itWhat->first, it->first ) != 0 );
 252
 253                 copy_item()( m_List, it, 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
 267 }}} // namespace cds::intrusive::striped_set
 268 //@endcond
 269
 270 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_MAP_BOOST_LIST_ADAPTER_H