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 <cds/container/striped_set/adapter.h>
   7 #include <cds/ref.h>
   8 #include <list>
   9 #include <algorithm>    // std::lower_bound
  10 #include <utility>      // std::pair
  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 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
  47         // Move policy for map
  48         template <typename K, typename T, typename Alloc>
  49         struct move_item_policy< std::list< std::pair< K const, T >, Alloc > >
  50         {
  51             typedef std::pair< K const, T>          pair_type;
  52             typedef std::list< pair_type, Alloc >   list_type;
  53             typedef typename list_type::iterator    iterator;
  54
  55             void operator()( list_type& list, iterator itInsert, iterator itWhat )
  56             {
  57                 list.insert( itInsert, std::move( *itWhat ) );
  58             }
  59         };
  60 #endif
  61     } // namespace striped_set
  62 }} // namespace cds:container
  63
  64 namespace cds { namespace intrusive { namespace striped_set {
  65
  66     /// std::list adapter for hash map bucket
  67     template <typename Key, typename T, class Alloc, CDS_SPEC_OPTIONS>
  68     class adapt< std::list< std::pair<Key const, T>, Alloc>, CDS_OPTIONS >
  69     {
  70     public:
  71         typedef std::list< std::pair<Key const, T>, Alloc>     container_type          ;   ///< underlying container type
  72
  73     private:
  74         /// Adapted container type
  75         class adapted_container: public cds::container::striped_set::adapted_sequential_container
  76         {
  77         public:
  78             typedef typename container_type::value_type     value_type  ;   ///< value type stored in the container
  79             typedef typename value_type::first_type         key_type;
  80             typedef typename value_type::second_type        mapped_type;
  81             typedef typename container_type::iterator       iterator    ;   ///< container iterator
  82             typedef typename container_type::const_iterator const_iterator ;    ///< container const iterator
  83
  84             static bool const has_find_with = true;
  85             static bool const has_erase_with = true;
  86
  87         private:
  88             //@cond
  89             typedef typename cds::opt::details::make_comparator_from_option_list< value_type, CDS_OPTIONS >::type key_comparator;
  90
  91
  92             typedef typename cds::opt::select<
  93                 typename cds::opt::value<
  94                     typename cds::opt::find_option<
  95                         cds::opt::copy_policy< cds::container::striped_set::move_item >
  96                         , CDS_OPTIONS
  97                     >::type
  98                 >::copy_policy
  99                 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
 100                 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
 101 #ifdef CDS_MOVE_SEMANTICS_SUPPORT
 102                 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
 103 #endif
 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 #       ifdef __GLIBCXX__
 131             // GCC C++ lib bug:
 132             // In GCC (at least up to 4.7.x), the complexity of std::list::size() is O(N)
 133             // (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561)
 134             size_t          m_nSize ;   // list size
 135 #       endif
 136             //@endcond
 137
 138         public:
 139             adapted_container()
 140 #       ifdef __GLIBCXX__
 141                 : m_nSize(0)
 142 #       endif
 143             {}
 144
 145             template <typename Q, typename Func>
 146             bool insert( const Q& key, Func f )
 147             {
 148                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
 149                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
 150                     //value_type newItem( key );
 151                     it = m_List.insert( it, value_type( key, mapped_type()) );
 152                     cds::unref( f )( *it );
 153
 154 #           ifdef __GLIBCXX__
 155                     ++m_nSize;
 156 #           endif
 157                     return true;
 158                 }
 159
 160                 // key already exists
 161                 return false;
 162             }
 163
 164 #           ifdef CDS_EMPLACE_SUPPORT
 165             template <typename K, typename... Args>
 166             bool emplace( K&& key, Args&&... args )
 167             {
 168                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
 169                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
 170                     //value_type newItem( key );
 171                     it = m_List.emplace( it, value_type( std::forward<K>(key), std::move( mapped_type( std::forward<Args>(args)...) )) );
 172
 173 #           ifdef __GLIBCXX__
 174                     ++m_nSize;
 175 #           endif
 176                     return true;
 177                 }
 178                 return false;
 179             }
 180 #           endif
 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                     cds::unref( func )( true, *it );
 191 #           ifdef __GLIBCXX__
 192                     ++m_nSize;
 193 #           endif
 194                     return std::make_pair( true, true );
 195                 }
 196                 else {
 197                     // already exists
 198                     cds::unref( 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                 cds::unref( f )( *it );
 212                 m_List.erase( it );
 213 #           ifdef __GLIBCXX__
 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                 cds::unref( f )( *it );
 229                 m_List.erase( it );
 230 #           ifdef __GLIBCXX__
 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                 cds::unref( 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                 cds::unref( 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 #           ifdef __GLIBCXX__
 278                 ++m_nSize;
 279 #           endif
 280             }
 281
 282             size_t size() const
 283             {
 284 #           ifdef __GLIBCXX__
 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 __CDS_CONTAINER_STRIPED_MAP_STD_LIST_ADAPTER_H