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