cds/intrusive/striped_set/adapter.h

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