cds/container/striped_set/std_list.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_CONTAINER_STRIPED_SET_STD_LIST_ADAPTER_H
  32 #define CDSLIB_CONTAINER_STRIPED_SET_STD_LIST_ADAPTER_H
  33
  34 #include <functional>   // ref
  35 #include <list>
  36 #include <algorithm>    // std::lower_bound
  37 #include <cds/container/striped_set/adapter.h>
  38
  39 #undef CDS_STD_LIST_SIZE_CXX11_CONFORM
  40 #if !( defined(__GLIBCXX__ ) && (!defined(_GLIBCXX_USE_CXX11_ABI) || _GLIBCXX_USE_CXX11_ABI == 0 ))
  41 #   define CDS_STD_LIST_SIZE_CXX11_CONFORM
  42 #endif
  43
  44 //@cond
  45 namespace cds { namespace container {
  46     namespace striped_set {
  47
  48         // Copy policy for std::list
  49         template <typename T, typename Alloc>
  50         struct copy_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                 itInsert = list.insert( itInsert, *itWhat );
  58             }
  59         };
  60
  61         // Swap policy for std::list
  62         template <typename T, typename Alloc>
  63         struct swap_item_policy< std::list< T, Alloc > >
  64         {
  65             typedef std::list< T, Alloc > list_type;
  66             typedef typename list_type::iterator iterator;
  67
  68             void operator()( list_type& list, iterator itInsert, iterator itWhat )
  69             {
  70                 typename list_type::value_type newVal;
  71                 itInsert = list.insert( itInsert, newVal );
  72                 std::swap( *itWhat, *itInsert );
  73             }
  74         };
  75
  76         // Move policy for std::list
  77         template <typename T, typename Alloc>
  78         struct move_item_policy< std::list< T, Alloc > >
  79         {
  80             typedef std::list< T, Alloc > list_type;
  81             typedef typename list_type::iterator iterator;
  82
  83             void operator()( list_type& list, iterator itInsert, iterator itWhat )
  84             {
  85                 list.insert( itInsert, std::move( *itWhat ));
  86             }
  87         };
  88     }   // namespace striped_set
  89 }} // namespace cds::container
  90
  91 namespace cds { namespace intrusive { namespace striped_set {
  92
  93     /// std::list adapter for hash set bucket
  94     template <typename T, class Alloc, typename... Options>
  95     class adapt< std::list<T, Alloc>, Options... >
  96     {
  97     public:
  98         typedef std::list<T, Alloc>     container_type          ;   ///< underlying container type
  99
 100     private:
 101         /// Adapted container type
 102         class adapted_container: public cds::container::striped_set::adapted_sequential_container
 103         {
 104         public:
 105             typedef typename container_type::value_type value_type  ;   ///< value type stored in the container
 106             typedef typename container_type::iterator      iterator ;   ///< container iterator
 107             typedef typename container_type::const_iterator const_iterator ;    ///< container const iterator
 108
 109             static bool const has_find_with = true;
 110             static bool const has_erase_with = true;
 111
 112         private:
 113             //@cond
 114             typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
 115
 116
 117             typedef typename cds::opt::select<
 118                 typename cds::opt::value<
 119                     typename cds::opt::find_option<
 120                         cds::opt::copy_policy< cds::container::striped_set::move_item >
 121                         , Options...
 122                     >::type
 123                 >::copy_policy
 124                 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
 125                 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
 126                 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
 127             >::type copy_item;
 128
 129             struct find_predicate
 130             {
 131                 bool operator()( value_type const& i1, value_type const& i2) const
 132                 {
 133                     return key_comparator()( i1, i2 ) < 0;
 134                 }
 135
 136                 template <typename Q>
 137                 bool operator()( Q const& i1, value_type const& i2) const
 138                 {
 139                     return key_comparator()( i1, i2 ) < 0;
 140                 }
 141
 142                 template <typename Q>
 143                 bool operator()( value_type const& i1, Q const& i2) const
 144                 {
 145                     return key_comparator()( i1, i2 ) < 0;
 146                 }
 147             };
 148             //@endcond
 149
 150         private:
 151             //@cond
 152             container_type  m_List;
 153 #       if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 154             // GCC C++ lib bug:
 155             // In GCC, the complexity of std::list::size() is O(N)
 156             // (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561)
 157             // Fixed in GCC 5
 158             size_t          m_nSize ;   // list size
 159 #       endif
 160             //@endcond
 161
 162         public:
 163             adapted_container()
 164 #       if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 165                 : m_nSize(0)
 166 #       endif
 167             {}
 168
 169             template <typename Q, typename Func>
 170             bool insert( const Q& val, Func f )
 171             {
 172                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate());
 173                 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 ) {
 174                     value_type newItem( val );
 175                     it = m_List.insert( it, newItem );
 176                     f( *it );
 177
 178 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 179                     ++m_nSize;
 180 #           endif
 181                     return true;
 182                 }
 183
 184                 // key already exists
 185                 return false;
 186             }
 187
 188             template <typename... Args>
 189             bool emplace( Args&&... args )
 190             {
 191                 value_type val(std::forward<Args>(args)...);
 192                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate());
 193                 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 ) {
 194                     it = m_List.emplace( it, std::move( val ));
 195 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 196                     ++m_nSize;
 197 #           endif
 198                     return true;
 199                 }
 200                 return false;
 201             }
 202
 203             template <typename Q, typename Func>
 204             std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert )
 205             {
 206                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate());
 207                 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 ) {
 208                     // insert new
 209                     if ( !bAllowInsert )
 210                         return std::make_pair( false, false );
 211
 212                     value_type newItem( val );
 213                     it = m_List.insert( it, newItem );
 214                     func( true, *it, val );
 215 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 216                     ++m_nSize;
 217 #           endif
 218                     return std::make_pair( true, true );
 219                 }
 220                 else {
 221                     // already exists
 222                     func( false, *it, val );
 223                     return std::make_pair( true, false );
 224                 }
 225             }
 226
 227             template <typename Q, typename Func>
 228             bool erase( const Q& key, Func f )
 229             {
 230                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate());
 231                 if ( it == m_List.end() || key_comparator()( key, *it ) != 0 )
 232                     return false;
 233
 234                 // key exists
 235                 f( *it );
 236                 m_List.erase( it );
 237 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 238                 --m_nSize;
 239 #           endif
 240
 241                 return true;
 242             }
 243
 244             template <typename Q, typename Less, typename Func>
 245             bool erase( Q const& key, Less pred, Func f )
 246             {
 247                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, pred );
 248                 if ( it == m_List.end() || pred( key, *it ) || pred( *it, key ))
 249                     return false;
 250
 251                 // key exists
 252                 f( *it );
 253                 m_List.erase( it );
 254 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 255                 --m_nSize;
 256 #           endif
 257
 258                 return true;
 259             }
 260
 261             template <typename Q, typename Func>
 262             bool find( Q& val, Func f )
 263             {
 264                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate());
 265                 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 )
 266                     return false;
 267
 268                 // key exists
 269                 f( *it, val );
 270                 return true;
 271             }
 272
 273             template <typename Q, typename Less, typename Func>
 274             bool find( Q& val, Less pred, Func f )
 275             {
 276                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, pred );
 277                 if ( it == m_List.end() || pred( val, *it ) || pred( *it, val ))
 278                     return false;
 279
 280                 // key exists
 281                 f( *it, val );
 282                 return true;
 283             }
 284
 285             /// Clears the container
 286             void clear()
 287             {
 288                 m_List.clear();
 289             }
 290
 291             iterator begin()                { return m_List.begin(); }
 292             const_iterator begin() const    { return m_List.begin(); }
 293             iterator end()                  { return m_List.end(); }
 294             const_iterator end() const      { return m_List.end(); }
 295
 296             void move_item( adapted_container& /*from*/, iterator itWhat )
 297             {
 298                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), *itWhat, find_predicate());
 299                 assert( it == m_List.end() || key_comparator()( *itWhat, *it ) != 0 );
 300
 301                 copy_item()( m_List, it, itWhat );
 302 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 303                 ++m_nSize;
 304 #           endif
 305             }
 306
 307             size_t size() const
 308             {
 309 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 310                 return m_nSize;
 311 #           else
 312                 return m_List.size();
 313 #           endif
 314
 315             }
 316         };
 317
 318     public:
 319         typedef adapted_container type ; ///< Result of \p adapt metafunction
 320
 321     };
 322 }}}
 323
 324
 325 //@endcond
 326
 327 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_STD_LIST_ADAPTER_H