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