cds/intrusive/striped_set/boost_unordered_set.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_INTRUSIVE_STRIPED_SET_BOOST_UNORDERED_SET_ADAPTER_H
  32 #define CDSLIB_INTRUSIVE_STRIPED_SET_BOOST_UNORDERED_SET_ADAPTER_H
  33
  34 #include <boost/intrusive/unordered_set.hpp>
  35 #include <cds/intrusive/striped_set/adapter.h>
  36 #include <cds/opt/buffer.h>
  37
  38 //@cond
  39 namespace cds { namespace intrusive { namespace striped_set {
  40
  41     namespace details {
  42         template <class Set, typename... Options>
  43         class adapt_boost_unordered_set
  44         {
  45         public:
  46             typedef Set container_type;   ///< underlying intrusive container type
  47
  48         private:
  49             class adapted_container
  50             {
  51             public:
  52                 typedef typename container_type::value_type     value_type;   ///< value type stored in the container
  53                 typedef typename container_type::iterator       iterator;   ///< container iterator
  54                 typedef typename container_type::const_iterator const_iterator;   ///< container const iterator
  55
  56                 typedef typename opt::value <
  57                     typename opt::find_option <
  58                         opt::buffer< opt::v::initialized_static_buffer< cds::any_type, 256 > >,
  59                         Options...
  60                     > ::type
  61                 > ::buffer    initial_buffer_type;
  62                 typedef typename initial_buffer_type::template rebind< typename container_type::bucket_type >::other buffer_type;
  63                 typedef cds::intrusive::striped_set::load_factor_resizing<256>   default_resizing_policy;
  64
  65             private:
  66                 template <typename Compare>
  67                 struct equal_from_compare
  68                 {
  69                     Compare& m_cmp;
  70                     equal_from_compare( Compare& cmp )
  71                         : m_cmp( cmp )
  72                     {}
  73
  74                     equal_from_compare( equal_from_compare const& src )
  75                         : m_cmp( src.m_cmp )
  76                     {}
  77
  78                     template <typename A, typename B>
  79                     bool operator()( A& a, B& b ) const
  80                     {
  81                         return !m_cmp( a, b ) && !m_cmp( b, a );
  82                     }
  83
  84                     template <typename A, typename B>
  85                     bool operator()( A& a, B& b )
  86                     {
  87                         return !m_cmp( a, b ) && !m_cmp( b, a );
  88                     }
  89                 };
  90
  91                 buffer_type     m_Buckets;   // buffer should be declared first since it is used in m_Set ctor.
  92                 container_type  m_Set;
  93
  94             public:
  95                 adapted_container()
  96                     : m_Set( typename container_type::bucket_traits( m_Buckets.buffer(), m_Buckets.capacity()))
  97                 {}
  98
  99                 container_type& base_container()
 100                 {
 101                     return m_Set;
 102                 }
 103
 104                 template <typename Func>
 105                 bool insert( value_type& val, Func f )
 106                 {
 107                     std::pair<iterator, bool> res = m_Set.insert( val );
 108                     if ( res.second )
 109                         f( val );
 110                     return res.second;
 111                 }
 112
 113                 template <typename Func>
 114                 std::pair<bool, bool> update( value_type& val, Func f, bool bAllowInsert )
 115                 {
 116                     if ( bAllowInsert ) {
 117                         std::pair<iterator, bool> res = m_Set.insert( val );
 118                         f( res.second, *res.first, val );
 119                         return std::make_pair( true, res.second );
 120                     }
 121                     else {
 122                         auto it = m_Set.find( val );
 123                         if ( it == m_Set.end())
 124                             return std::make_pair( false, false );
 125                         f( false, *it, val );
 126                         return std::make_pair( true, false );
 127                     }
 128                 }
 129
 130                 bool unlink( value_type& val )
 131                 {
 132                     iterator it = m_Set.find( value_type( val ));
 133                     if ( it == m_Set.end() || &(*it) != &val )
 134                         return false;
 135                     m_Set.erase( it );
 136                     return true;
 137                 }
 138
 139                 template <typename Q, typename Func>
 140                 value_type * erase( Q const& key, Func f )
 141                 {
 142                     iterator it = m_Set.find( key, typename container_type::hasher(), typename container_type::key_equal());
 143                     if ( it == m_Set.end())
 144                         return nullptr;
 145                     value_type& val = *it;
 146                     f( val );
 147                     m_Set.erase( it );
 148                     return &val;
 149                 }
 150
 151                 template <typename Q, typename Less, typename Func>
 152                 value_type * erase( Q const& key, Less pred, Func f )
 153                 {
 154                     iterator it = m_Set.find( key, typename container_type::hasher(), equal_from_compare<Less>( pred ));
 155                     if ( it == m_Set.end())
 156                         return nullptr;
 157                     value_type& val = *it;
 158                     f( val );
 159                     m_Set.erase( it );
 160                     return &val;
 161                 }
 162
 163                 template <typename Q, typename Func>
 164                 bool find( Q& key, Func f )
 165                 {
 166                     iterator it = m_Set.find( key, typename container_type::hasher(), typename container_type::key_equal());
 167                     if ( it == m_Set.end())
 168                         return false;
 169                     f( *it, key );
 170                     return true;
 171                 }
 172
 173                 template <typename Q, typename Less, typename Func>
 174                 bool find( Q& key, Less pred, Func f )
 175                 {
 176                     iterator it = m_Set.find( key, typename container_type::hasher(), equal_from_compare<Less>( pred ));
 177                     if ( it == m_Set.end())
 178                         return false;
 179                     f( *it, key );
 180                     return true;
 181                 }
 182
 183                 void clear()
 184                 {
 185                     m_Set.clear();
 186                 }
 187
 188                 template <typename Disposer>
 189                 void clear( Disposer disposer )
 190                 {
 191                     m_Set.clear_and_dispose( disposer );
 192                 }
 193
 194                 iterator begin() { return m_Set.begin(); }
 195                 const_iterator begin() const { return m_Set.begin(); }
 196                 iterator end() { return m_Set.end(); }
 197                 const_iterator end() const { return m_Set.end(); }
 198
 199                 size_t size() const
 200                 {
 201                     return (size_t)m_Set.size();
 202                 }
 203
 204                 void move_item( adapted_container& from, iterator itWhat )
 205                 {
 206                     value_type& val = *itWhat;
 207                     from.base_container().erase( itWhat );
 208                     insert( val, []( value_type& ) {} );
 209                 }
 210             };
 211
 212         public:
 213             typedef adapted_container   type;  ///< Result of the metafunction
 214         };
 215     } // namespace details
 216
 217 #if CDS_COMPILER == CDS_COMPILER_INTEL && CDS_COMPILER_VERSION <= 1500
 218     template <typename T,
 219         typename O1, typename O2, typename O3, typename O4, typename O5,
 220         typename O6, typename O7, typename O8, typename O9, typename O10,
 221         typename... Options
 222     >
 223     class adapt < boost::intrusive::unordered_set< T, O1, O2, O3, O4, O5, O6, O7, O8, O9, O10 >, Options... >
 224         : public details::adapt_boost_unordered_set < boost::intrusive::unordered_set< T, O1, O2, O3, O4, O5, O6, O7, O8, O9, O10 >, Options... >
 225     {};
 226 #else
 227     template <typename T, typename... BIOptons, typename... Options>
 228     class adapt < boost::intrusive::unordered_set< T, BIOptons... >, Options... >
 229         : public details::adapt_boost_unordered_set < boost::intrusive::unordered_set< T, BIOptons... >, Options... >
 230     {};
 231 #endif
 232
 233 }}} // namespace cds::intrusive::striped_set
 234 //@endcond
 235
 236 #endif // #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_BOOST_UNORDERED_SET_ADAPTER_H