cds/container/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_CONTAINER_STRIPED_SET_BOOST_SLIST_ADAPTER_H
  32 #define CDSLIB_CONTAINER_STRIPED_SET_BOOST_SLIST_ADAPTER_H
  33
  34 #include <functional>   // ref
  35 #include <cds/container/striped_set/adapter.h>
  36 #include <boost/container/slist.hpp>
  37
  38 //@cond
  39 namespace cds { namespace container {
  40     namespace striped_set {
  41
  42         // Copy policy for boost::container::slist
  43         template <typename T, typename Alloc>
  44         struct copy_item_policy< boost::container::slist< T, Alloc > >
  45         {
  46             typedef boost::container::slist< T, Alloc > list_type;
  47             typedef typename list_type::iterator    iterator;
  48
  49             void operator()( list_type& list, iterator itInsert, iterator itWhat )
  50             {
  51                 list.insert_after( itInsert, *itWhat );
  52             }
  53         };
  54
  55         // Swap policy for boost::container::slist
  56         template <typename T, typename Alloc>
  57         struct swap_item_policy< boost::container::slist< T, Alloc > >
  58         {
  59             typedef boost::container::slist< T, Alloc > list_type;
  60             typedef typename list_type::iterator    iterator;
  61
  62             void operator()( list_type& list, iterator itInsert, iterator itWhat )
  63             {
  64                 T newVal;
  65                 itInsert = list.insert_after( itInsert, newVal );
  66                 std::swap( *itInsert, *itWhat );
  67             }
  68         };
  69
  70         // Move policy for boost::container::slist
  71         template <typename T, typename Alloc>
  72         struct move_item_policy< boost::container::slist< T, Alloc > >
  73         {
  74             typedef boost::container::slist< T, Alloc > list_type;
  75             typedef typename list_type::iterator    iterator;
  76
  77             void operator()( list_type& list, iterator itInsert, iterator itWhat )
  78             {
  79                 list.insert_after( itInsert, std::move( *itWhat ));
  80             }
  81         };
  82
  83     }   // namespace striped_set
  84 }} // namespace cds::container
  85
  86 namespace cds { namespace intrusive { namespace striped_set {
  87
  88     /// boost::container::slist adapter for hash set bucket
  89     template <typename T, class Alloc, typename... Options>
  90     class adapt< boost::container::slist<T, Alloc>, Options... >
  91     {
  92     public:
  93         typedef boost::container::slist<T, Alloc>     container_type          ;   ///< underlying container type
  94
  95     private:
  96         /// Adapted container type
  97         class adapted_container: public cds::container::striped_set::adapted_sequential_container
  98         {
  99         public:
 100             typedef typename container_type::value_type value_type  ;   ///< value type stored in the container
 101             typedef typename container_type::iterator      iterator ;   ///< container iterator
 102             typedef typename container_type::const_iterator const_iterator ;    ///< container const iterator
 103
 104             static bool const has_find_with = true;
 105             static bool const has_erase_with = true;
 106
 107         private:
 108             //@cond
 109             typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
 110
 111             typedef typename cds::opt::select<
 112                 typename cds::opt::value<
 113                     typename cds::opt::find_option<
 114                         cds::opt::copy_policy< cds::container::striped_set::move_item >
 115                         , Options...
 116                     >::type
 117                 >::copy_policy
 118                 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
 119                 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
 120                 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
 121             >::type copy_item;
 122
 123             template <typename Q>
 124             std::pair< iterator, bool > find_prev_item( Q const& key )
 125             {
 126                 iterator itPrev = m_List.before_begin();
 127                 iterator itEnd = m_List.end();
 128                 for ( iterator it = m_List.begin(); it != itEnd; ++it ) {
 129                     int nCmp = key_comparator()( key, *it );
 130                     if ( nCmp < 0 )
 131                         itPrev = it;
 132                     else if ( nCmp > 0 )
 133                         break;
 134                     else
 135                         return std::make_pair( itPrev, true );
 136                 }
 137                 return std::make_pair( itPrev, false );
 138             }
 139
 140             template <typename Q, typename Less>
 141             std::pair< iterator, bool > find_prev_item( Q const& key, Less pred )
 142             {
 143                 iterator itPrev = m_List.before_begin();
 144                 iterator itEnd = m_List.end();
 145                 for ( iterator it = m_List.begin(); it != itEnd; ++it ) {
 146                     if ( pred( key, *it ))
 147                         itPrev = it;
 148                     else if ( pred( *it, key ))
 149                         break;
 150                     else
 151                         return std::make_pair( itPrev, true );
 152                 }
 153                 return std::make_pair( itPrev, false );
 154             }
 155
 156             //@endcond
 157
 158         private:
 159             //@cond
 160             container_type  m_List;
 161             //@endcond
 162
 163         public:
 164             adapted_container()
 165             {}
 166
 167             template <typename Q, typename Func>
 168             bool insert( const Q& val, Func f )
 169             {
 170                 std::pair< iterator, bool > pos = find_prev_item( val );
 171                 if ( !pos.second ) {
 172                     value_type newItem( val );
 173                     pos.first = m_List.insert_after( pos.first, newItem );
 174                     f( *pos.first );
 175                     return true;
 176                 }
 177
 178                 // key already exists
 179                 return false;
 180             }
 181
 182             template <typename... Args>
 183             bool emplace( Args&&... args )
 184             {
 185                 value_type val( std::forward<Args>(args)... );
 186                 std::pair< iterator, bool > pos = find_prev_item( val );
 187                 if ( !pos.second ) {
 188                     m_List.emplace_after( pos.first, std::move( val ));
 189                     return true;
 190                 }
 191                 return false;
 192             }
 193
 194             template <typename Q, typename Func>
 195             std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert )
 196             {
 197                 std::pair< iterator, bool > pos = find_prev_item( val );
 198                 if ( !pos.second ) {
 199                     // insert new
 200                     if ( !bAllowInsert )
 201                         return std::make_pair( false, false );
 202
 203                     value_type newItem( val );
 204                     pos.first = m_List.insert_after( pos.first, newItem );
 205                     func( true, *pos.first, val );
 206                     return std::make_pair( true, true );
 207                 }
 208                 else {
 209                     // already exists
 210                     func( false, *(++pos.first), val );
 211                     return std::make_pair( true, false );
 212                 }
 213             }
 214
 215             template <typename Q, typename Func>
 216             bool erase( Q const& key, Func f )
 217             {
 218                 std::pair< iterator, bool > pos = find_prev_item( key );
 219                 if ( !pos.second )
 220                     return false;
 221
 222                 // key exists
 223                 iterator it = pos.first;
 224                 f( *(++it));
 225                 m_List.erase_after( pos.first );
 226
 227                 return true;
 228             }
 229
 230             template <typename Q, typename Less, typename Func>
 231             bool erase( Q const& key, Less pred, Func f )
 232             {
 233                 std::pair< iterator, bool > pos = find_prev_item( key, pred );
 234                 if ( !pos.second )
 235                     return false;
 236
 237                 // key exists
 238                 iterator it = pos.first;
 239                 f( *(++it));
 240                 m_List.erase_after( pos.first );
 241
 242                 return true;
 243             }
 244
 245             template <typename Q, typename Func>
 246             bool find( Q& val, Func f )
 247             {
 248                 std::pair< iterator, bool > pos = find_prev_item( val );
 249                 if ( !pos.second )
 250                     return false;
 251
 252                 // key exists
 253                 f( *(++pos.first), val );
 254                 return true;
 255             }
 256
 257             template <typename Q, typename Less, typename Func>
 258             bool find( Q& val, Less pred, Func f )
 259             {
 260                 std::pair< iterator, bool > pos = find_prev_item( val, pred );
 261                 if ( !pos.second )
 262                     return false;
 263
 264                 // key exists
 265                 f( *(++pos.first), val );
 266                 return true;
 267             }
 268
 269             void clear()
 270             {
 271                 m_List.clear();
 272             }
 273
 274             iterator begin()                { return m_List.begin(); }
 275             const_iterator begin() const    { return m_List.begin(); }
 276             iterator end()                  { return m_List.end(); }
 277             const_iterator end() const      { return m_List.end(); }
 278
 279             void move_item( adapted_container& /*from*/, iterator itWhat )
 280             {
 281                 std::pair< iterator, bool > pos = find_prev_item( *itWhat );
 282                 assert( !pos.second );
 283
 284                 copy_item()( m_List, pos.first, itWhat );
 285             }
 286
 287             size_t size() const
 288             {
 289                 return m_List.size();
 290             }
 291         };
 292
 293     public:
 294         typedef adapted_container type ; ///< Result of \p adapt metafunction
 295
 296     };
 297 }}} // namespace cds::intrusive::striped_set
 298
 299
 300 //@endcond
 301
 302 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_BOOST_SLIST_ADAPTER_H