cds/container/striped_set/std_list.h

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