cds/container/striped_set/boost_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-2016
   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_BOOST_LIST_ADAPTER_H
  32 #define CDSLIB_CONTAINER_STRIPED_SET_BOOST_LIST_ADAPTER_H
  33
  34 #include <boost/version.hpp>
  35 #if BOOST_VERSION < 104800
  36 #   error "For boost::container::list you must use boost 1.48 or above"
  37 #endif
  38
  39 #include <algorithm>    // std::lower_bound
  40 #include <functional>   // ref
  41 #include <cds/container/striped_set/adapter.h>
  42 #include <boost/container/list.hpp>
  43
  44 //@cond
  45 namespace cds { namespace container {
  46     namespace striped_set {
  47
  48         // Copy policy for boost::container::list
  49         template <typename T, typename Alloc>
  50         struct copy_item_policy< boost::container::list< T, Alloc > >
  51         {
  52             typedef boost::container::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 boost::container::list
  62         template <typename T, typename Alloc>
  63         struct swap_item_policy< boost::container::list< T, Alloc > >
  64         {
  65             typedef boost::container::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 boost::container::list
  77         template <typename T, typename Alloc>
  78         struct move_item_policy< boost::container::list< T, Alloc > >
  79         {
  80             typedef boost::container::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     /// boost::container::list adapter for hash set bucket
  94     template <typename T, class Alloc, typename... Options>
  95     class adapt< boost::container::list<T, Alloc>, Options... >
  96     {
  97     public:
  98         typedef boost::container::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             typedef typename cds::opt::select<
 117                 typename cds::opt::value<
 118                     typename cds::opt::find_option<
 119                         cds::opt::copy_policy< cds::container::striped_set::move_item >
 120                         , Options...
 121                     >::type
 122                 >::copy_policy
 123                 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
 124                 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
 125                 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
 126             >::type copy_item;
 127
 128             struct find_predicate
 129             {
 130                 bool operator()( value_type const& i1, value_type const& i2) const
 131                 {
 132                     return key_comparator()( i1, i2 ) < 0;
 133                 }
 134
 135                 template <typename Q>
 136                 bool operator()( Q const& i1, value_type const& i2) const
 137                 {
 138                     return key_comparator()( i1, i2 ) < 0;
 139                 }
 140
 141                 template <typename Q>
 142                 bool operator()( value_type const& i1, Q const& i2) const
 143                 {
 144                     return key_comparator()( i1, i2 ) < 0;
 145                 }
 146             };
 147             //@endcond
 148
 149         private:
 150             //@cond
 151             container_type  m_List;
 152             //@endcond
 153
 154         public:
 155             adapted_container()
 156             {}
 157
 158             template <typename Q, typename Func>
 159             bool insert( Q const& val, Func f )
 160             {
 161                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
 162                 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 ) {
 163                     value_type newItem( val );
 164                     it = m_List.insert( it, newItem );
 165                     f( *it );
 166
 167                     return true;
 168                 }
 169
 170                 // key already exists
 171                 return false;
 172             }
 173
 174             template <typename... Args>
 175             bool emplace( Args&&... args )
 176             {
 177                 value_type val( std::forward<Args>(args)... );
 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                     m_List.emplace( it, std::move( val ) );
 181                     return true;
 182                 }
 183                 return false;
 184             }
 185
 186             template <typename Q, typename Func>
 187             std::pair<bool, bool> update( Q const& val, Func func, bool bAllowInsert )
 188             {
 189                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
 190                 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 ) {
 191                     // insert new
 192                     if ( !bAllowInsert )
 193                         return std::make_pair( false, false );
 194
 195                     value_type newItem( val );
 196                     it = m_List.insert( it, newItem );
 197                     func( true, *it, val );
 198                     return std::make_pair( true, true );
 199                 }
 200                 else {
 201                     // already exists
 202                     func( false, *it, val );
 203                     return std::make_pair( true, false );
 204                 }
 205             }
 206
 207             template <typename Q, typename Func>
 208             bool erase( Q const& key, Func f )
 209             {
 210                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate() );
 211                 if ( it == m_List.end() || key_comparator()( key, *it ) != 0 )
 212                     return false;
 213
 214                 // key exists
 215                 f( *it );
 216                 m_List.erase( it );
 217
 218                 return true;
 219             }
 220
 221             template <typename Q, typename Less, typename Func>
 222             bool erase( Q const& key, Less pred, Func f )
 223             {
 224                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, pred );
 225                 if ( it == m_List.end() || pred( key, *it ) || pred( *it, key ) )
 226                     return false;
 227
 228                 // key exists
 229                 f( *it );
 230                 m_List.erase( it );
 231
 232                 return true;
 233             }
 234
 235             template <typename Q, typename Func>
 236             bool find( Q& val, Func f )
 237             {
 238                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
 239                 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 )
 240                     return false;
 241
 242                 // key exists
 243                 f( *it, val );
 244                 return true;
 245             }
 246
 247             template <typename Q, typename Less, typename Func>
 248             bool find( Q& val, Less pred, Func f )
 249             {
 250                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, pred );
 251                 if ( it == m_List.end() || pred( val, *it ) || pred( *it, val ) )
 252                     return false;
 253
 254                 // key exists
 255                 f( *it, val );
 256                 return true;
 257             }
 258
 259             /// Clears the container
 260             void clear()
 261             {
 262                 m_List.clear();
 263             }
 264
 265             iterator begin()                { return m_List.begin(); }
 266             const_iterator begin() const    { return m_List.begin(); }
 267             iterator end()                  { return m_List.end(); }
 268             const_iterator end() const      { return m_List.end(); }
 269
 270             void move_item( adapted_container& /*from*/, iterator itWhat )
 271             {
 272                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), *itWhat, find_predicate() );
 273                 assert( it == m_List.end() || key_comparator()( *itWhat, *it ) != 0 );
 274
 275                 copy_item()( m_List, it, itWhat );
 276             }
 277
 278             size_t size() const
 279             {
 280                 return m_List.size();
 281             }
 282         };
 283
 284     public:
 285         typedef adapted_container type ; ///< Result of \p adapt metafunction
 286
 287     };
 288 }}} // namespace cds::intrsive::striped_set
 289 //@endcond
 290
 291 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_BOOST_LIST_ADAPTER_H