cds/container/striped_map/std_list.h

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