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