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