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-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_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                     value_type newItem( key, mapped_type() );
 182                     pos.first = m_List.insert_after( pos.first, newItem );
 183                     f( *pos.first );
 184                     return true;
 185                 }
 186
 187                 // key already exists
 188                 return false;
 189             }
 190
 191             template <typename K, typename... Args>
 192             bool emplace( K&& key, Args&&... args )
 193             {
 194                 std::pair< iterator, bool > pos = find_prev_item( key );
 195                 if ( !pos.second ) {
 196                     m_List.emplace_after( pos.first, std::forward<K>(key), std::move( mapped_type( std::forward<Args>(args)... )));
 197                     return true;
 198                 }
 199                 return false;
 200             }
 201
 202             template <typename Q, typename Func>
 203             std::pair<bool, bool> update( const Q& key, Func func, bool bAllowInsert )
 204             {
 205                 std::pair< iterator, bool > pos = find_prev_item( key );
 206                 if ( !pos.second ) {
 207                     // insert new
 208                     if ( !bAllowInsert )
 209                         return std::make_pair( false, false );
 210
 211                     value_type newItem( key, mapped_type() );
 212                     pos.first = m_List.insert_after( pos.first, newItem );
 213                     func( true, *pos.first );
 214                     return std::make_pair( true, true );
 215                 }
 216                 else {
 217                     // already exists
 218                     func( false, *(++pos.first) );
 219                     return std::make_pair( true, false );
 220                 }
 221             }
 222
 223             template <typename Q, typename Func>
 224             bool erase( Q const& key, Func f )
 225             {
 226                 std::pair< iterator, bool > pos = find_prev_item( key );
 227                 if ( !pos.second )
 228                     return false;
 229
 230                 // key exists
 231                 iterator it = pos.first;
 232                 f( *(++it) );
 233                 m_List.erase_after( pos.first );
 234
 235                 return true;
 236             }
 237
 238             template <typename Q, typename Less, typename Func>
 239             bool erase( Q const& key, Less pred, Func f )
 240             {
 241                 std::pair< iterator, bool > pos = find_prev_item( key, pred );
 242                 if ( !pos.second )
 243                     return false;
 244
 245                 // key exists
 246                 iterator it = pos.first;
 247                 f( *(++it) );
 248                 m_List.erase_after( pos.first );
 249
 250                 return true;
 251             }
 252
 253             template <typename Q, typename Func>
 254             bool find( Q& val, Func f )
 255             {
 256                 std::pair< iterator, bool > pos = find_prev_item( val );
 257                 if ( !pos.second )
 258                     return false;
 259
 260                 // key exists
 261                 f( *(++pos.first), val );
 262                 return true;
 263             }
 264
 265             template <typename Q, typename Less, typename Func>
 266             bool find( Q& val, Less pred, Func f )
 267             {
 268                 std::pair< iterator, bool > pos = find_prev_item( val, pred );
 269                 if ( !pos.second )
 270                     return false;
 271
 272                 // key exists
 273                 f( *(++pos.first), val );
 274                 return true;
 275             }
 276
 277             void clear()
 278             {
 279                 m_List.clear();
 280             }
 281
 282             iterator begin()                { return m_List.begin(); }
 283             const_iterator begin() const    { return m_List.begin(); }
 284             iterator end()                  { return m_List.end(); }
 285             const_iterator end() const      { return m_List.end(); }
 286
 287             void move_item( adapted_container& /*from*/, iterator itWhat )
 288             {
 289                 std::pair< iterator, bool > pos = find_prev_item( itWhat->first );
 290                 assert( !pos.second );
 291
 292                 copy_item()( m_List, pos.first, itWhat );
 293             }
 294
 295             size_t size() const
 296             {
 297                 return m_List.size();
 298             }
 299         };
 300
 301     public:
 302         typedef adapted_container type ; ///< Result of \p adapt metafunction
 303
 304     };
 305 }}} // namespace cds::intrusive::striped_set
 306
 307
 308 //@endcond
 309
 310 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_MAP_BOOST_SLIST_ADAPTER_H