cds/container/striped_map/boost_slist.h

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