cds/intrusive/striped_set/boost_slist.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_INTRUSIVE_STRIPED_SET_BOOST_SLIST_ADAPTER_H
  32 #define CDSLIB_INTRUSIVE_STRIPED_SET_BOOST_SLIST_ADAPTER_H
  33
  34 #include <boost/intrusive/slist.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 <class List, typename... Options>
  42         class adapt_boost_slist
  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
  56                 typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
  57
  58             private:
  59
  60                 template <typename Q, typename Less>
  61                 std::pair< iterator, bool > find_prev_item( Q const& key, Less pred )
  62                 {
  63                     iterator itPrev = m_List.before_begin();
  64                     iterator itEnd = m_List.end();
  65                     for ( iterator it = m_List.begin(); it != itEnd; ++it ) {
  66                         if ( pred( key, *it ))
  67                             itPrev = it;
  68                         else if ( pred( *it, key ))
  69                             break;
  70                         else
  71                             return std::make_pair( itPrev, true );
  72                     }
  73                     return std::make_pair( itPrev, false );
  74                 }
  75
  76                 template <typename Q>
  77                 std::pair< iterator, bool > find_prev_item( Q const& key )
  78                 {
  79                     return find_prev_item_cmp( key, key_comparator());
  80                 }
  81
  82                 template <typename Q, typename Compare>
  83                 std::pair< iterator, bool > find_prev_item_cmp( Q const& key, Compare cmp )
  84                 {
  85                     iterator itPrev = m_List.before_begin();
  86                     iterator itEnd = m_List.end();
  87                     for ( iterator it = m_List.begin(); it != itEnd; ++it ) {
  88                         int nCmp = cmp( key, *it );
  89                         if ( nCmp < 0 )
  90                             itPrev = it;
  91                         else if ( nCmp > 0 )
  92                             break;
  93                         else
  94                             return std::make_pair( itPrev, true );
  95                     }
  96                     return std::make_pair( itPrev, false );
  97                 }
  98
  99                 template <typename Q, typename Compare, typename Func>
 100                 value_type * erase_( Q const& key, Compare cmp, Func f )
 101                 {
 102                     std::pair< iterator, bool > pos = find_prev_item_cmp( key, cmp );
 103                     if ( !pos.second )
 104                         return nullptr;
 105
 106                     // key exists
 107                     iterator it = pos.first;
 108                     value_type& val = *(++it);
 109                     f( val );
 110                     m_List.erase_after( pos.first );
 111
 112                     return &val;
 113                 }
 114
 115             private:
 116                 container_type  m_List;
 117
 118             public:
 119                 adapted_container()
 120                 {}
 121
 122                 container_type& base_container()
 123                 {
 124                     return m_List;
 125                 }
 126
 127                 template <typename Func>
 128                 bool insert( value_type& val, Func f )
 129                 {
 130                     std::pair< iterator, bool > pos = find_prev_item( val );
 131                     if ( !pos.second ) {
 132                         m_List.insert_after( pos.first, val );
 133                         f( val );
 134                         return true;
 135                     }
 136
 137                     // key already exists
 138                     return false;
 139                 }
 140
 141                 template <typename Func>
 142                 std::pair<bool, bool> update( value_type& val, Func f, bool bAllowInsert )
 143                 {
 144                     std::pair< iterator, bool > pos = find_prev_item( val );
 145                     if ( !pos.second ) {
 146                         // insert new
 147                         if ( !bAllowInsert )
 148                             return std::make_pair( false, false );
 149
 150                         m_List.insert_after( pos.first, val );
 151                         f( true, val, val );
 152                         return std::make_pair( true, true );
 153                     }
 154                     else {
 155                         // already exists
 156                         f( false, *(++pos.first), val );
 157                         return std::make_pair( true, false );
 158                     }
 159                 }
 160
 161                 bool unlink( value_type& val )
 162                 {
 163                     std::pair< iterator, bool > pos = find_prev_item( val );
 164                     if ( !pos.second )
 165                         return false;
 166
 167                     ++pos.first;
 168                     if ( &(*pos.first) != &val )
 169                         return false;
 170
 171                     m_List.erase( pos.first );
 172                     return true;
 173                 }
 174
 175                 template <typename Q, typename Func>
 176                 value_type * erase( Q const& key, Func f )
 177                 {
 178                     return erase_( key, key_comparator(), f );
 179                 }
 180
 181                 template <typename Q, typename Less, typename Func>
 182                 value_type * erase( Q const& key, Less /*pred*/, Func f )
 183                 {
 184                     return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
 185                 }
 186
 187                 template <typename Q, typename Func>
 188                 bool find( Q& key, Func f )
 189                 {
 190                     std::pair< iterator, bool > pos = find_prev_item( key );
 191                     if ( !pos.second )
 192                         return false;
 193
 194                     // key exists
 195                     f( *(++pos.first), key );
 196                     return true;
 197                 }
 198
 199                 template <typename Q, typename Less, typename Func>
 200                 bool find( Q& key, Less pred, Func f )
 201                 {
 202                     std::pair< iterator, bool > pos = find_prev_item( key, pred );
 203                     if ( !pos.second )
 204                         return false;
 205
 206                     // key exists
 207                     f( *(++pos.first), key );
 208                     return true;
 209                 }
 210
 211                 void clear()
 212                 {
 213                     m_List.clear();
 214                 }
 215
 216                 template <typename Disposer>
 217                 void clear( Disposer disposer )
 218                 {
 219                     m_List.clear_and_dispose( disposer );
 220                 }
 221
 222                 iterator begin() { return m_List.begin(); }
 223                 const_iterator begin() const { return m_List.begin(); }
 224                 iterator end() { return m_List.end(); }
 225                 const_iterator end() const { return m_List.end(); }
 226
 227                 size_t size() const
 228                 {
 229                     return (size_t)m_List.size();
 230                 }
 231
 232                 void move_item( adapted_container& from, iterator itWhat )
 233                 {
 234                     value_type& val = *itWhat;
 235                     from.base_container().erase( itWhat );
 236                     insert( val, []( value_type& ) {} );
 237                 }
 238
 239             };
 240         public:
 241             typedef adapted_container   type;  ///< Result of the metafunction
 242         };
 243     } // namespace details
 244
 245 #if CDS_COMPILER == CDS_COMPILER_INTEL && CDS_COMPILER_VERSION <= 1500
 246     template <typename T, typename P1, typename P2, typename P3, typename P4, typename P5, typename... Options>
 247     class adapt< boost::intrusive::slist< T, P1, P2, P3, P4, P5 >, Options... >
 248         : public details::adapt_boost_slist< boost::intrusive::slist< T, P1, P2, P3, P4, P5 >, Options... >
 249     {};
 250 #else
 251     template <typename T, typename... BIOptions, typename... Options>
 252     class adapt< boost::intrusive::slist< T, BIOptions... >, Options... >
 253         : public details::adapt_boost_slist< boost::intrusive::slist< T, BIOptions... >, Options... >
 254     {};
 255 #endif
 256
 257 }}} // namespace cds::intrusive::striped_set
 258 //@endcond
 259
 260 #endif // #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_BOOST_SLIST_ADAPTER_H