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