cds/intrusive/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-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_INTRUSIVE_STRIPED_SET_BOOST_LIST_ADAPTER_H
  32 #define CDSLIB_INTRUSIVE_STRIPED_SET_BOOST_LIST_ADAPTER_H
  33
  34 #include <boost/intrusive/list.hpp>
  35 #include <cds/intrusive/striped_set/adapter.h>
  36
  37 //@cond
  38 namespace cds { namespace intrusive { namespace striped_set {
  39
  40     namespace details {
  41         template <typename List, typename... Options >
  42         class adapt_boost_list
  43         {
  44         public:
  45             typedef List container_type;   ///< underlying intrusive container type
  46
  47         private:
  48             /// Adapted intrusive container
  49             class adapted_container : public cds::intrusive::striped_set::adapted_sequential_container
  50             {
  51             public:
  52                 typedef typename container_type::value_type     value_type;   ///< value type stored in the container
  53                 typedef typename container_type::iterator       iterator;   ///< container iterator
  54                 typedef typename container_type::const_iterator const_iterator;    ///< container const iterator
  55                 typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
  56
  57             private:
  58                 struct find_predicate
  59                 {
  60                     bool operator()( value_type const& i1, value_type const& i2 ) const
  61                     {
  62                         return key_comparator()(i1, i2) < 0;
  63                     }
  64
  65                     template <typename Q>
  66                     bool operator()( Q const& i1, value_type const& i2 ) const
  67                     {
  68                         return key_comparator()(i1, i2) < 0;
  69                     }
  70
  71                     template <typename Q>
  72                     bool operator()( value_type const& i1, Q const& i2 ) const
  73                     {
  74                         return key_comparator()(i1, i2) < 0;
  75                     }
  76                 };
  77
  78                 template <typename Q, typename Pred>
  79                 iterator find_key( Q const& key, Pred pred )
  80                 {
  81                     iterator itEnd = m_List.end();
  82                     iterator it;
  83                     for ( it = m_List.begin(); it != itEnd; ++it ) {
  84                         if ( !pred( *it, key ))
  85                             break;
  86                     }
  87                     return it;
  88                 }
  89
  90             private:
  91                 container_type  m_List;
  92
  93             public:
  94                 adapted_container()
  95                 {}
  96
  97                 container_type& base_container()
  98                 {
  99                     return m_List;
 100                 }
 101
 102                 template <typename Func>
 103                 bool insert( value_type& val, Func f )
 104                 {
 105                     iterator it = find_key( val, find_predicate());
 106                     if ( it == m_List.end() || key_comparator()(val, *it) != 0 ) {
 107                         m_List.insert( it, val );
 108                         f( val );
 109
 110                         return true;
 111                     }
 112
 113                     // key already exists
 114                     return false;
 115                 }
 116
 117                 template <typename Func>
 118                 std::pair<bool, bool> update( value_type& val, Func f, bool bAllowInsert )
 119                 {
 120                     iterator it = find_key( val, find_predicate());
 121                     if ( it == m_List.end() || key_comparator()(val, *it) != 0 ) {
 122                         // insert new
 123                         if ( !bAllowInsert )
 124                             return std::make_pair( false, false );
 125
 126                         m_List.insert( it, val );
 127                         f( true, val, val );
 128                         return std::make_pair( true, true );
 129                     }
 130                     else {
 131                         // already exists
 132                         f( false, *it, val );
 133                         return std::make_pair( true, false );
 134                     }
 135                 }
 136
 137                 bool unlink( value_type& val )
 138                 {
 139                     iterator it = find_key( val, find_predicate());
 140                     if ( it == m_List.end() || &(*it) != &val )
 141                         return false;
 142
 143                     m_List.erase( it );
 144                     return true;
 145                 }
 146
 147                 template <typename Q, typename Func>
 148                 value_type * erase( Q const& key, Func f )
 149                 {
 150                     iterator it = find_key( key, find_predicate());
 151                     if ( it == m_List.end() || key_comparator()(key, *it) != 0 )
 152                         return nullptr;
 153
 154                     // key exists
 155                     value_type& val = *it;
 156                     f( val );
 157                     m_List.erase( it );
 158
 159                     return &val;
 160                 }
 161
 162                 template <typename Q, typename Less, typename Func>
 163                 value_type * erase( Q const& key, Less pred, Func f )
 164                 {
 165                     iterator it = find_key( key, pred );
 166                     if ( it == m_List.end() || pred( key, *it ) || pred( *it, key ))
 167                         return nullptr;
 168
 169                     // key exists
 170                     value_type& val = *it;
 171                     f( val );
 172                     m_List.erase( it );
 173
 174                     return &val;
 175                 }
 176
 177                 template <typename Q, typename Func>
 178                 bool find( Q& key, Func f )
 179                 {
 180                     return find( key, find_predicate(), f );
 181                 }
 182
 183                 template <typename Q, typename Less, typename Func>
 184                 bool find( Q& key, Less pred, Func f )
 185                 {
 186                     iterator it = find_key( key, pred );
 187                     if ( it == m_List.end() || pred( key, *it ) || pred( *it, key ))
 188                         return false;
 189
 190                     // key exists
 191                     f( *it, key );
 192                     return true;
 193                 }
 194
 195                 void clear()
 196                 {
 197                     m_List.clear();
 198                 }
 199
 200                 template <typename Disposer>
 201                 void clear( Disposer disposer )
 202                 {
 203                     m_List.clear_and_dispose( disposer );
 204                 }
 205
 206                 iterator begin() { return m_List.begin(); }
 207                 const_iterator begin() const { return m_List.begin(); }
 208                 iterator end() { return m_List.end(); }
 209                 const_iterator end() const { return m_List.end(); }
 210
 211                 size_t size() const
 212                 {
 213                     return (size_t)m_List.size();
 214                 }
 215
 216                 void move_item( adapted_container& from, iterator itWhat )
 217                 {
 218                     value_type& val = *itWhat;
 219                     from.base_container().erase( itWhat );
 220                     insert( val, []( value_type& ) {} );
 221                 }
 222
 223             };
 224         public:
 225             typedef adapted_container   type;  ///< Result of the metafunction
 226         };
 227     } // namespace details
 228
 229 #if CDS_COMPILER == CDS_COMPILER_INTEL && CDS_COMPILER_VERSION <= 1500
 230     template <typename T, typename P1, typename P2, typename P3, typename P4, typename... Options>
 231     class adapt< boost::intrusive::list< T, P1, P2, P3, P4 >, Options... >
 232         : public details::adapt_boost_list< boost::intrusive::list< T, P1, P2, P3, P4 >, Options... >
 233     {};
 234 #else
 235     template <typename T, typename... BIOptions, typename... Options>
 236     class adapt< boost::intrusive::list< T, BIOptions... >, Options... >
 237         : public details::adapt_boost_list< boost::intrusive::list< T, BIOptions... >, Options... >
 238     {};
 239 #endif
 240
 241 }}} // namespace cds::intrusive::striped_set
 242 //@endcond
 243
 244 #endif // #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_BOOST_LIST_ADAPTER_H