cds/intrusive/striped_set/adapter.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_INTRUSIVE_STRIPED_SET_ADAPTER_H
  32 #define CDSLIB_INTRUSIVE_STRIPED_SET_ADAPTER_H
  33
  34 #include <cds/opt/options.h>
  35 #include <cds/intrusive/striped_set/resizing_policy.h>
  36 #include <cds/opt/hash.h>
  37 #include <cds/opt/compare.h>    // cds::opt::details::make_comparator - for some adapt specializations
  38
  39 namespace cds { namespace intrusive {
  40
  41     /// StripedSet related definitions
  42     namespace striped_set {
  43         /// Default adapter for intrusive striped/refinable hash set
  44         /**
  45             By default, the metafunction does not make any transformation for container type \p Container.
  46             \p Container should provide interface suitable for the hash set.
  47
  48             The \p Options template argument contains option pack
  49             that will be passed to \p cds::intrusive::StripedSet.
  50
  51         <b>Bucket interface</b>
  52
  53             The result of metafunction is a container (a bucket) that should support the following interface:
  54
  55             Public typedefs that the bucket should provide:
  56                 - \p value_type - the type of the item in the bucket
  57                 - \p iterator - bucket's item iterator
  58                 - \p const_iterator - bucket's item constant iterator
  59                 - \p default_resizing_policy - default resizing policy preferable for the container.
  60                     By default, the library defines cds::container::striped_set::load_factor_resizing<4> for sequential containers like
  61                     boost::intrusive::list,  and cds::container::striped_set::no_resizing for ordered container like boost::intrusive::set.
  62
  63             <b>Insert value \p val of type \p Q</b>
  64             \code template <typename Func> bool insert( value_type& val, Func f ) ; \endcode
  65                 Inserts \p val into the container and, if inserting is successful, calls functor \p f
  66                 with \p val.
  67
  68                 The functor signature is:
  69                 \code
  70                 struct functor {
  71                     void operator()( value_type& item );
  72                 };
  73                 \endcode
  74                 where \p item is the item inserted.
  75
  76                 The user-defined functor \p f is called only if the inserting is success.
  77                 <hr>
  78
  79             <b>Updates the item in the container</b>
  80             \code template <typename Func> std::pair<bool, bool> update( value_type& val, Func f, bool bAllowInsert = true ) \endcode
  81                 The operation performs inserting or changing data.
  82
  83                 If the \p val key not found in the container, then \p val is inserted iff \p bAllowInsert is \p true.
  84                 Otherwise, the functor \p f is called with the item found.
  85
  86                 The \p Func functor has the following interface:
  87                 \code
  88                     void func( bool bNew, value_type& item, value_type& val );
  89                 \endcode
  90                 or like a functor:
  91                 \code
  92                     struct functor {
  93                         void operator()( bool bNew, value_type& item, value_type& val );
  94                     };
  95                 \endcode
  96
  97                 where arguments are:
  98                 - \p bNew - \p true if the item has been inserted, \p false otherwise
  99                 - \p item - container's item
 100                 - \p val - argument \p val passed into the \p update() function
 101
 102                 If \p val has been inserted (i.e. <tt>bNew == true</tt>) then \p item and \p val
 103                 are the same element: <tt>&item == &val</tt>. Otherwise, they are different.
 104
 105                 The functor can change non-key fields of the \p item.
 106
 107                 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
 108                 \p second is true if new item has been added or \p false if the item with \p val key
 109                 already exists.
 110                 <hr>
 111
 112             <b>Unlink an item</b>
 113             \code bool unlink( value_type& val ) \endcode
 114                 Unlink \p val from the container if \p val belongs to it.
 115                 <hr>
 116
 117             <b>Erase \p key</b>
 118             \code template <typename Q, typename Func> bool erase( Q const& key, Func f ) \endcode
 119                 The function searches an item with key \p key, calls \p f functor
 120                 and erases the item. If \p key is not found, the functor is not called.
 121
 122                 The functor \p Func interface is:
 123                 \code
 124                 struct functor {
 125                     void operator()(value_type& val);
 126                 };
 127                 \endcode
 128
 129                 The type \p Q can differ from \ref value_type of items storing in the container.
 130                 Therefore, the \p value_type should be comparable with type \p Q.
 131
 132                 Return \p true if key is found and deleted, \p false otherwise
 133                 <hr>
 134
 135
 136             <b>Find the key \p val </b>
 137             \code
 138             template <typename Q, typename Func> bool find( Q& val, Func f )
 139             template <typename Q, typename Compare, typename Func> bool find( Q& val, Compare cmp, Func f )
 140             \endcode
 141                 The function searches the item with key equal to \p val and calls the functor \p f for item found.
 142                 The interface of \p Func functor is:
 143                 \code
 144                 struct functor {
 145                     void operator()( value_type& item, Q& val );
 146                 };
 147                 \endcode
 148                 where \p item is the item found, \p val is the <tt>find</tt> function argument.
 149
 150                 The functor can change non-key fields of \p item.
 151                 The \p val argument may be non-const since it can be used as \p f functor destination i.e., the functor
 152                 can modify both arguments.
 153
 154                 The type \p Q can differ from \ref value_type of items storing in the container.
 155                 Therefore, the \p value_type should be comparable with type \p Q.
 156
 157                 The first form uses default \p compare function used for key ordering.
 158                 The second form allows to point specific \p Compare functor \p cmp
 159                 that can compare \p value_typwe and \p Q type. The interface of \p Compare is the same as \p std::less.
 160
 161                 The function returns \p true if \p val is found, \p false otherwise.
 162                 <hr>
 163
 164             <b>Clears the container</b>
 165             \code
 166             void clear()
 167             template <typename Disposer> void clear( Disposer disposer )
 168             \endcode
 169             Second form calls \p disposer for each item in the container before clearing.
 170             <hr>
 171
 172             <b>Get size of bucket</b>
 173             \code size_t size() const \endcode
 174             This function may be required by some resizing policy
 175             <hr>
 176
 177             <b>Iterators</b>
 178             \code
 179             iterator begin();
 180             const_iterator begin() const;
 181             iterator end();
 182             const_iterator end() const;
 183             \endcode
 184             <hr>
 185
 186             <b>Move item when resizing</b>
 187             \code void move_item( adapted_container& from, iterator it ) \endcode
 188                 This helper function is invented for the set resizing when the item
 189                 pointed by \p it iterator is copied from old bucket \p from to a new bucket
 190                 pointed by \p this.
 191             <hr>
 192
 193         */
 194         template < typename Container, typename... Options >
 195         class adapt
 196         {
 197         public:
 198             typedef Container   type            ;   ///< adapted container type
 199             typedef typename type::value_type value_type  ;   ///< value type stored in the container
 200         };
 201
 202         //@cond
 203         struct adapted_sequential_container
 204         {
 205             typedef striped_set::load_factor_resizing<4>   default_resizing_policy;
 206         };
 207
 208         struct adapted_container
 209         {
 210             typedef striped_set::no_resizing   default_resizing_policy;
 211         };
 212         //@endcond
 213
 214         //@cond
 215         namespace details {
 216             template <typename Set>
 217             class boost_intrusive_set_adapter: public cds::intrusive::striped_set::adapted_container
 218             {
 219             public:
 220                 typedef Set container_type;
 221
 222                 typedef typename container_type::value_type     value_type      ;   ///< value type stored in the container
 223                 typedef typename container_type::iterator       iterator        ;   ///< container iterator
 224                 typedef typename container_type::const_iterator const_iterator  ;   ///< container const iterator
 225
 226                 typedef typename container_type::key_compare  key_comparator;
 227
 228             private:
 229                 container_type  m_Set;
 230
 231             public:
 232                 boost_intrusive_set_adapter()
 233                 {}
 234
 235                 container_type& base_container()
 236                 {
 237                     return m_Set;
 238                 }
 239
 240                 template <typename Func>
 241                 bool insert( value_type& val, Func f )
 242                 {
 243                     std::pair<iterator, bool> res = m_Set.insert( val );
 244                     if ( res.second )
 245                         f( val );
 246                     return res.second;
 247                 }
 248
 249                 template <typename Func>
 250                 std::pair<bool, bool> update( value_type& val, Func f, bool bAllowInsert )
 251                 {
 252                     if ( bAllowInsert ) {
 253                         std::pair<iterator, bool> res = m_Set.insert( val );
 254                         f( res.second, *res.first, val );
 255                         return std::make_pair( true, res.second );
 256                     }
 257                     else {
 258                         auto it = m_Set.find( val, key_comparator() );
 259                         if ( it == m_Set.end() )
 260                             return std::make_pair( false, false );
 261                         f( false, *it, val );
 262                         return std::make_pair( true, false );
 263                     }
 264                 }
 265
 266                 bool unlink( value_type& val )
 267                 {
 268                     iterator it = m_Set.find( val, key_comparator() );
 269                     if ( it == m_Set.end() || &(*it) != &val )
 270                         return false;
 271                     m_Set.erase( it );
 272                     return true;
 273                 }
 274
 275                 template <typename Q, typename Func>
 276                 value_type * erase( Q const& key, Func f )
 277                 {
 278                     iterator it = m_Set.find( key, key_comparator() );
 279                     if (it == m_Set.end())
 280                         return nullptr;
 281                     value_type& val = *it;
 282                     f( val );
 283                     m_Set.erase( it );
 284                     return &val;
 285                 }
 286
 287                 template <typename Q, typename Less, typename Func>
 288                 value_type * erase( Q const& key, Less pred, Func f )
 289                 {
 290                     iterator it = m_Set.find( key, pred );
 291                     if (it == m_Set.end())
 292                         return nullptr;
 293                     value_type& val = *it;
 294                     f( val );
 295                     m_Set.erase( it );
 296                     return &val;
 297                 }
 298
 299                 template <typename Q, typename Func>
 300                 bool find( Q const& key, Func f )
 301                 {
 302                     return find( key, key_comparator(), f );
 303                 }
 304
 305                 template <typename Q, typename Compare, typename Func>
 306                 bool find( Q const& key, Compare cmp, Func f )
 307                 {
 308                     iterator it = m_Set.find( key, cmp );
 309                     if ( it == m_Set.end() )
 310                         return false;
 311                     f( *it, key );
 312                     return true;
 313                 }
 314
 315                 void clear()
 316                 {
 317                     m_Set.clear();
 318                 }
 319
 320                 template <typename Disposer>
 321                 void clear( Disposer disposer )
 322                 {
 323                     m_Set.clear_and_dispose( disposer );
 324                 }
 325
 326                 iterator begin()                { return m_Set.begin(); }
 327                 const_iterator begin() const    { return m_Set.begin(); }
 328                 iterator end()                  { return m_Set.end(); }
 329                 const_iterator end() const      { return m_Set.end(); }
 330
 331                 size_t size() const
 332                 {
 333                     return (size_t) m_Set.size();
 334                 }
 335
 336                 void move_item( boost_intrusive_set_adapter& from, iterator itWhat )
 337                 {
 338                     value_type& val = *itWhat;
 339                     from.base_container().erase( itWhat );
 340                     insert( val, []( value_type& ) {} );
 341                 }
 342             };
 343         }   // namespace details
 344         //@endcond
 345
 346     } // namespace striped_set
 347 }} // namespace cds::intrusive
 348
 349 #endif // #ifndef CDSLIB_INTRUSIVE_STRIPED_SET_ADAPTER_H