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