cds/container/striped_map/std_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_STD_LIST_ADAPTER_H
  32 #define CDSLIB_CONTAINER_STRIPED_MAP_STD_LIST_ADAPTER_H
  33
  34 #include <list>
  35 #include <functional>   // ref
  36 #include <algorithm>    // std::lower_bound
  37 #include <utility>      // std::pair
  38 #include <cds/container/striped_set/adapter.h>
  39
  40 #undef CDS_STD_LIST_SIZE_CXX11_CONFORM
  41 #if !( defined(__GLIBCXX__ ) && (!defined(_GLIBCXX_USE_CXX11_ABI) || _GLIBCXX_USE_CXX11_ABI == 0 ))
  42 #   define CDS_STD_LIST_SIZE_CXX11_CONFORM
  43 #endif
  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< std::list< std::pair< K const, T >, Alloc > >
  52         {
  53             typedef std::pair< K const, T>  pair_type;
  54             typedef std::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< std::list< std::pair< K const, T >, Alloc > >
  66         {
  67             typedef std::pair< K const, T>  pair_type;
  68             typedef std::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< std::list< std::pair< K const, T >, Alloc > >
  82         {
  83             typedef std::pair< K const, T>          pair_type;
  84             typedef std::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     /// std::list adapter for hash map bucket
  98     template <typename Key, typename T, class Alloc, typename... Options>
  99     class adapt< std::list< std::pair<Key const, T>, Alloc>, Options... >
 100     {
 101     public:
 102         typedef std::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
 123             typedef typename cds::opt::select<
 124                 typename cds::opt::value<
 125                     typename cds::opt::find_option<
 126                         cds::opt::copy_policy< cds::container::striped_set::move_item >
 127                         , Options...
 128                     >::type
 129                 >::copy_policy
 130                 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
 131                 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
 132                 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
 133             >::type copy_item;
 134
 135             struct find_predicate
 136             {
 137                 bool operator()( value_type const& i1, value_type const& i2) const
 138                 {
 139                     return key_comparator()( i1.first, i2.first ) < 0;
 140                 }
 141
 142                 template <typename Q>
 143                 bool operator()( Q const& i1, value_type const& i2) const
 144                 {
 145                     return key_comparator()( i1, i2.first ) < 0;
 146                 }
 147
 148                 template <typename Q>
 149                 bool operator()( value_type const& i1, Q const& i2) const
 150                 {
 151                     return key_comparator()( i1.first, i2 ) < 0;
 152                 }
 153             };
 154             //@endcond
 155
 156         private:
 157             //@cond
 158             container_type  m_List;
 159 #       if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 160             // GCC C++ lib bug:
 161             // In GCC (at least up to 4.7.x), the complexity of std::list::size() is O(N)
 162             // (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561)
 163             // Fixed in GCC 5
 164             size_t          m_nSize ;   // list size
 165 #       endif
 166             //@endcond
 167
 168         public:
 169             adapted_container()
 170 #       if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 171                 : m_nSize(0)
 172 #       endif
 173             {}
 174
 175             template <typename Q, typename Func>
 176             bool insert( const Q& key, Func f )
 177             {
 178                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate());
 179                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
 180                     it = m_List.insert( it, value_type( key_type( key ), mapped_type()));
 181                     f( *it );
 182
 183 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 184                     ++m_nSize;
 185 #           endif
 186                     return true;
 187                 }
 188
 189                 // key already exists
 190                 return false;
 191             }
 192
 193             template <typename K, typename... Args>
 194             bool emplace( K&& key, Args&&... args )
 195             {
 196                 value_type val( key_type( std::forward<K>( key )), mapped_type( std::forward<Args>( args )... ));
 197                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val.first, find_predicate());
 198                 if ( it == m_List.end() || key_comparator()( val.first, it->first ) != 0 ) {
 199                     it = m_List.emplace( it, std::move( val ));
 200
 201 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 202                     ++m_nSize;
 203 #           endif
 204                     return true;
 205                 }
 206                 return false;
 207             }
 208
 209             template <typename Q, typename Func>
 210             std::pair<bool, bool> update( const Q& key, Func func, bool bAllowInsert )
 211             {
 212                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate());
 213                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 ) {
 214                     // insert new
 215                     if ( !bAllowInsert )
 216                         return std::make_pair( false, false );
 217
 218                     it = m_List.insert( it, value_type( key_type( key ), mapped_type()));
 219                     func( true, *it );
 220 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 221                     ++m_nSize;
 222 #           endif
 223                     return std::make_pair( true, true );
 224                 }
 225                 else {
 226                     // already exists
 227                     func( false, *it );
 228                     return std::make_pair( true, false );
 229                 }
 230             }
 231
 232             template <typename Q, typename Func>
 233             bool erase( Q const& key, Func f )
 234             {
 235                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, find_predicate());
 236                 if ( it == m_List.end() || key_comparator()( key, it->first ) != 0 )
 237                     return false;
 238
 239                 // key exists
 240                 f( *it );
 241                 m_List.erase( it );
 242 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 243                 --m_nSize;
 244 #           endif
 245
 246                 return true;
 247             }
 248
 249             template <typename Q, typename Less, typename Func>
 250             bool erase( Q const& key, Less pred, Func f )
 251             {
 252                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), key, pred );
 253                 if ( it == m_List.end() || pred( key, it->first ) || pred( it->first, key ))
 254                     return false;
 255
 256                 // key exists
 257                 f( *it );
 258                 m_List.erase( it );
 259 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 260                 --m_nSize;
 261 #           endif
 262
 263                 return true;
 264             }
 265
 266             template <typename Q, typename Func>
 267             bool find( Q& val, Func f )
 268             {
 269                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate());
 270                 if ( it == m_List.end() || key_comparator()( val, it->first ) != 0 )
 271                     return false;
 272
 273                 // key exists
 274                 f( *it, val );
 275                 return true;
 276             }
 277
 278             template <typename Q, typename Less, typename Func>
 279             bool find( Q& val, Less pred, Func f )
 280             {
 281                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, pred );
 282                 if ( it == m_List.end() || pred( val, it->first ) || pred( it->first, val ))
 283                     return false;
 284
 285                 // key exists
 286                 f( *it, val );
 287                 return true;
 288             }
 289
 290             void clear()
 291             {
 292                 m_List.clear();
 293             }
 294
 295             iterator begin()                { return m_List.begin(); }
 296             const_iterator begin() const    { return m_List.begin(); }
 297             iterator end()                  { return m_List.end(); }
 298             const_iterator end() const      { return m_List.end(); }
 299
 300             void move_item( adapted_container& /*from*/, iterator itWhat )
 301             {
 302                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), *itWhat, find_predicate());
 303                 assert( it == m_List.end() || key_comparator()( itWhat->first, it->first ) != 0 );
 304
 305                 copy_item()( m_List, it, itWhat );
 306 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 307                 ++m_nSize;
 308 #           endif
 309             }
 310
 311             size_t size() const
 312             {
 313 #           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
 314                 return m_nSize;
 315 #           else
 316                 return m_List.size();
 317 #           endif
 318
 319             }
 320         };
 321
 322     public:
 323         typedef adapted_container type ; ///< Result of \p adapt metafunction
 324
 325     };
 326 }}} // namespace cds::intrusive::striped_set
 327
 328 //@endcond
 329
 330 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_MAP_STD_LIST_ADAPTER_H