cds/container/striped_set/std_list.h

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