cds/intrusive/striped_set/adapter.h

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