test/unit/set/test_intrusive_set.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSUNIT_SET_TEST_INTRUSIVE_SET_H
  32 #define CDSUNIT_SET_TEST_INTRUSIVE_SET_H
  33
  34 #include <cds_test/check_size.h>
  35 #include <cds_test/fixture.h>
  36
  37 #include <cds/opt/hash.h>
  38 #include <functional>   // ref
  39
  40 // forward declaration
  41 namespace cds { namespace intrusive {}}
  42
  43 namespace cds_test {
  44
  45     namespace ci = cds::intrusive;
  46     namespace co = cds::opt;
  47
  48     class intrusive_set: public fixture
  49     {
  50     protected:
  51         struct stat
  52         {
  53             unsigned int nDisposeCount  ;   // count of disposer calling
  54             unsigned int nFindCount     ;   // count of find-functor calling
  55             unsigned int nUpdateNewCount;
  56             unsigned int nUpdateCount;
  57             mutable unsigned int nEraseCount;
  58
  59             stat()
  60             {
  61                 memset( this, 0, sizeof(*this));
  62             }
  63         };
  64
  65         template <typename Node>
  66         struct base_int_item
  67             : public Node
  68             , public stat
  69
  70         {
  71             int nKey;
  72             int nVal;
  73
  74             base_int_item()
  75             {}
  76
  77             explicit base_int_item( int key )
  78                 : nKey( key )
  79                 , nVal( key )
  80             {}
  81
  82             base_int_item(int key, int val)
  83                 : nKey( key )
  84                 , nVal(val)
  85             {}
  86
  87             base_int_item( base_int_item const& v )
  88                 : Node()
  89                 , stat()
  90                 , nKey( v.nKey )
  91                 , nVal( v.nVal )
  92             {}
  93
  94             int key() const
  95             {
  96                 return nKey;
  97             }
  98         };
  99
 100         template <typename Node>
 101         struct member_int_item: public stat
 102         {
 103             int nKey;
 104             int nVal;
 105
 106             Node hMember;
 107
 108             stat s;
 109
 110             member_int_item()
 111             {}
 112
 113             explicit member_int_item( int key )
 114                 : nKey( key )
 115                 , nVal( key )
 116             {}
 117
 118             member_int_item(int key, int val)
 119                 : nKey( key )
 120                 , nVal(val)
 121             {}
 122
 123             member_int_item(member_int_item const& v )
 124                 : stat()
 125                 , nKey( v.nKey )
 126                 , nVal( v.nVal )
 127             {}
 128
 129             int key() const
 130             {
 131                 return nKey;
 132             }
 133         };
 134
 135         struct hash_int {
 136             size_t operator()( int i ) const
 137             {
 138                 return co::v::hash<int>()( i );
 139             }
 140             template <typename Item>
 141             size_t operator()( const Item& i ) const
 142             {
 143                 return (*this)( i.key() );
 144             }
 145         };
 146
 147         struct simple_item_counter {
 148             size_t  m_nCount;
 149
 150             simple_item_counter()
 151                 : m_nCount(0)
 152             {}
 153
 154             size_t operator ++()
 155             {
 156                 return ++m_nCount;
 157             }
 158
 159             size_t operator --()
 160             {
 161                 return --m_nCount;
 162             }
 163
 164             void reset()
 165             {
 166                 m_nCount = 0;
 167             }
 168
 169             operator size_t() const
 170             {
 171                 return m_nCount;
 172             }
 173
 174         };
 175
 176
 177         template <typename T>
 178         struct less
 179         {
 180             bool operator ()(const T& v1, const T& v2 ) const
 181             {
 182                 return v1.key() < v2.key();
 183             }
 184
 185             template <typename Q>
 186             bool operator ()(const T& v1, const Q& v2 ) const
 187             {
 188                 return v1.key() < v2;
 189             }
 190
 191             template <typename Q>
 192             bool operator ()(const Q& v1, const T& v2 ) const
 193             {
 194                 return v1 < v2.key();
 195             }
 196         };
 197
 198         template <typename T>
 199         struct cmp {
 200             int operator ()(const T& v1, const T& v2 ) const
 201             {
 202                 if ( v1.key() < v2.key() )
 203                     return -1;
 204                 return v1.key() > v2.key() ? 1 : 0;
 205             }
 206
 207             template <typename Q>
 208             int operator ()(const T& v1, const Q& v2 ) const
 209             {
 210                 if ( v1.key() < v2 )
 211                     return -1;
 212                 return v1.key() > v2 ? 1 : 0;
 213             }
 214
 215             template <typename Q>
 216             int operator ()(const Q& v1, const T& v2 ) const
 217             {
 218                 if ( v1 < v2.key() )
 219                     return -1;
 220                 return v1 > v2.key() ? 1 : 0;
 221             }
 222         };
 223
 224         struct other_item {
 225             int nKey;
 226
 227             explicit other_item( int k )
 228                 : nKey( k )
 229             {}
 230
 231             int key() const
 232             {
 233                 return nKey;
 234             }
 235         };
 236
 237         struct other_less {
 238             template <typename Q, typename T>
 239             bool operator()( Q const& lhs, T const& rhs ) const
 240             {
 241                 return lhs.key() < rhs.key();
 242             }
 243         };
 244
 245         struct mock_disposer
 246         {
 247             template <typename T>
 248             void operator ()( T * p )
 249             {
 250                 ++p->nDisposeCount;
 251             }
 252         };
 253
 254         struct find_functor
 255         {
 256             template <typename Item, typename T>
 257             void operator()( Item& item, T& /*val*/ )
 258             {
 259                 ++item.nFindCount;
 260             }
 261         };
 262
 263         struct insert_functor
 264         {
 265             template <typename Item>
 266             void operator()(Item& item )
 267             {
 268                 item.nVal = item.nKey * 100;
 269             }
 270         };
 271
 272         struct update_functor
 273         {
 274             template <typename Item>
 275             void operator()( bool bNew, Item& item, Item& /*val*/ )
 276             {
 277                 if ( bNew )
 278                     ++item.nUpdateNewCount;
 279                 else
 280                     ++item.nUpdateCount;
 281             }
 282         };
 283
 284         struct erase_functor
 285         {
 286             template <typename Item>
 287             void operator()( Item const& item )
 288             {
 289                 item.nEraseCount++;
 290             }
 291         };
 292
 293         template <class Set>
 294         void test( Set& s )
 295         {
 296             // Precondition: set is empty
 297             // Postcondition: set is empty
 298
 299             ASSERT_TRUE( s.empty() );
 300             ASSERT_CONTAINER_SIZE( s, 0 );
 301
 302             typedef typename Set::value_type value_type;
 303
 304             std::vector< value_type > data;
 305             size_t const kSize = 100;
 306             data.reserve( kSize );
 307             for ( size_t key = 0; key < kSize; ++key ) {
 308                 data.push_back( value_type( static_cast<int>( key )));
 309             }
 310             shuffle( data.begin(), data.end() );
 311
 312             // insert/find
 313             for ( auto& i : data ) {
 314                 ASSERT_FALSE( s.contains( i.nKey ));
 315                 ASSERT_FALSE( s.contains( i ));
 316                 ASSERT_FALSE( s.contains( other_item( i.key()), other_less());
 317                 ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} );
 318                 ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
 319             }
 320         }
 321     };
 322
 323 } // namespace cds_test
 324
 325 #endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_SET_H