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