cds/container/striped_map/std_list.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_CONTAINER_STRIPED_MAP_STD_LIST_ADAPTER_H
   4 #define CDSLIB_CONTAINER_STRIPED_MAP_STD_LIST_ADAPTER_H
   5
   6 #include <list>
   7 #include <functional>   // ref
   8 #include <algorithm>    // std::lower_bound
   9 #include <utility>      // std::pair
  10 #include <cds/container/striped_set/adapter.h>
  11
  12 #undef CDS_STD_LIST_SIZE_CXX11_CONFORM
  13 #if !( defined(__GLIBCXX__ ) && (!defined(_GLIBCXX_USE_CXX11_ABI) || _GLIBCXX_USE_CXX11_ABI == 0 ))
  14 #   define CDS_STD_LIST_SIZE_CXX11_CONFORM
  15 #endif
  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< std::list< std::pair< K const, T >, Alloc > >
  24         {
  25             typedef std::pair< K const, T>  pair_type;
  26             typedef std::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< std::list< std::pair< K const, T >, Alloc > >
  38         {
  39             typedef std::pair< K const, T>  pair_type;
  40             typedef std::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< std::list< std::pair< K const, T >, Alloc > >
  54         {
  55             typedef std::pair< K const, T>          pair_type;
  56             typedef std::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     /// std::list adapter for hash map bucket
  70     template <typename Key, typename T, class Alloc, typename... Options>
  71     class adapt< std::list< std::pair<Key const, T>, Alloc>, Options... >
  72     {
  73     public:
  74         typedef std::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
  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                         , 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                 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
 105             >::type copy_item;
 106
 107             struct find_predicate
 108             {
 109                 bool operator()( value_type const& i1, value_type const& i2) const
 110                 {
 111                     return key_comparator()( i1.first, i2.first ) < 0;
 112                 }
 113
 114                 template <typename Q>
 115                 bool operator()( Q const& i1, value_type const& i2) const
 116                 {
 117                     return key_comparator()( i1, i2.first ) < 0;
 118                 }
 119
 120                 template <typename Q>
 121                 bool operator()( value_type const& i1, Q const& i2) const
 122                 {
 123                     return key_comparator()( i1.first, i2 ) < 0;
 124                 }
 125             };
 126             //@endcond
 127
 128         private:
 129             //@cond
 130             container_type  m_List;
 131 #       if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 132             // GCC C++ lib bug:
 133             // In GCC (at least up to 4.7.x), the complexity of std::list::size() is O(N)
 134             // (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561)
 135             // Fixed in GCC 5
 136             size_t          m_nSize ;   // list size
 137 #       endif
 138             //@endcond
 139
 140         public:
 141             adapted_container()
 142 #       if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 143                 : m_nSize(0)
 144 #       endif
 145             {}
 146
 147             template <typename Q, typename Func>
 148             bool insert( const Q& key, Func f )
 149             {
 150                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
 151                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
 152                     //value_type newItem( key );
 153                     it = m_List.insert( it, value_type( key, mapped_type()) );
 154                     f( *it );
 155
 156 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 157                     ++m_nSize;
 158 #           endif
 159                     return true;
 160                 }
 161
 162                 // key already exists
 163                 return false;
 164             }
 165
 166             template <typename K, typename... Args>
 167             bool emplace( K&& key, Args&&... args )
 168             {
 169                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
 170                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
 171                     //value_type newItem( key );
 172                     it = m_List.emplace( it, value_type( std::forward<K>(key), std::move( mapped_type( std::forward<Args>(args)...) )) );
 173
 174 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 175                     ++m_nSize;
 176 #           endif
 177                     return true;
 178                 }
 179                 return false;
 180             }
 181
 182             template <typename Q, typename Func>
 183             std::pair<bool, bool> ensure( const Q& key, Func func )
 184             {
 185                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
 186                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
 187                     // insert new
 188                     value_type newItem( key, mapped_type() );
 189                     it = m_List.insert( it, newItem );
 190                     func( true, *it );
 191 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 192                     ++m_nSize;
 193 #           endif
 194                     return std::make_pair( true, true );
 195                 }
 196                 else {
 197                     // already exists
 198                     func( false, *it );
 199                     return std::make_pair( true, false );
 200                 }
 201             }
 202
 203             template <typename Q, typename Func>
 204             bool erase( Q const& key, Func f )
 205             {
 206                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
 207                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 )
 208                     return false;
 209
 210                 // key exists
 211                 f( *it );
 212                 m_List.erase( it );
 213 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 214                 --m_nSize;
 215 #           endif
 216
 217                 return true;
 218             }
 219
 220             template <typename Q, typename Less, typename Func>
 221             bool erase( Q const& key, Less pred, Func f )
 222             {
 223                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, pred );
 224                 if ( it == m_List.end() || pred( key, it->first ) || pred( it->first, key ) )
 225                     return false;
 226
 227                 // key exists
 228                 f( *it );
 229                 m_List.erase( it );
 230 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 231                 --m_nSize;
 232 #           endif
 233
 234                 return true;
 235             }
 236
 237             template <typename Q, typename Func>
 238             bool find( Q& val, Func f )
 239             {
 240                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
 241                 if ( it == m_List.end() || key_comparator()( val, it->first ) != 0 )
 242                     return false;
 243
 244                 // key exists
 245                 f( *it, val );
 246                 return true;
 247             }
 248
 249             template <typename Q, typename Less, typename Func>
 250             bool find( Q& val, Less pred, Func f )
 251             {
 252                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, pred );
 253                 if ( it == m_List.end() || pred( val, it->first ) || pred( it->first, val ) )
 254                     return false;
 255
 256                 // key exists
 257                 f( *it, val );
 258                 return true;
 259             }
 260
 261             void clear()
 262             {
 263                 m_List.clear();
 264             }
 265
 266             iterator begin()                { return m_List.begin(); }
 267             const_iterator begin() const    { return m_List.begin(); }
 268             iterator end()                  { return m_List.end(); }
 269             const_iterator end() const      { return m_List.end(); }
 270
 271             void move_item( adapted_container& /*from*/, iterator itWhat )
 272             {
 273                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), *itWhat, find_predicate() );
 274                 assert( it == m_List.end() || key_comparator()( itWhat->first, it->first ) != 0 );
 275
 276                 copy_item()( m_List, it, itWhat );
 277 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 278                 ++m_nSize;
 279 #           endif
 280             }
 281
 282             size_t size() const
 283             {
 284 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 285                 return m_nSize;
 286 #           else
 287                 return m_List.size();
 288 #           endif
 289
 290             }
 291         };
 292
 293     public:
 294         typedef adapted_container type ; ///< Result of \p adapt metafunction
 295
 296     };
 297 }}} // namespace cds::intrusive::striped_set
 298
 299 //@endcond
 300
 301 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_MAP_STD_LIST_ADAPTER_H