test/stress/set/set_type.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-2017
   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_TYPE_H
  32 #define CDSUNIT_SET_TYPE_H
  33
  34 #include <cds/urcu/general_instant.h>
  35 #include <cds/urcu/general_buffered.h>
  36 #include <cds/urcu/general_threaded.h>
  37 #include <cds/urcu/signal_buffered.h>
  38
  39 #include <cds/opt/hash.h>
  40 #include <cds/sync/spinlock.h>
  41
  42 #include <cds_test/stress_test.h>
  43
  44 namespace set {
  45     namespace cc = cds::container;
  46     namespace co = cds::opt;
  47
  48     typedef cds::urcu::gc< cds::urcu::general_instant_stripped >   rcu_gpi;
  49     typedef cds::urcu::gc< cds::urcu::general_buffered_stripped >  rcu_gpb;
  50     typedef cds::urcu::gc< cds::urcu::general_threaded_stripped >  rcu_gpt;
  51 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
  52     typedef cds::urcu::gc< cds::urcu::signal_buffered_stripped >  rcu_shb;
  53 #endif
  54
  55     template <typename Key>
  56     struct less;
  57
  58     template <typename Key>
  59     struct cmp
  60     {
  61         int operator ()(Key const& k1, Key const& k2) const
  62         {
  63             if ( less<Key>( k1, k2 ))
  64                 return -1;
  65             return less<Key>( k2, k1 ) ? 1 : 0;
  66         }
  67     };
  68
  69     template <typename Key>
  70     struct hash;
  71
  72 #define CDSUNIT_INT_COMPARE(t)  template <> struct cmp<t> { int operator()( t k1, t k2 ){ return (int)(k1 - k2); } }
  73     CDSUNIT_INT_COMPARE(char);
  74     CDSUNIT_INT_COMPARE(unsigned char);
  75     CDSUNIT_INT_COMPARE(int);
  76     CDSUNIT_INT_COMPARE(unsigned int);
  77     CDSUNIT_INT_COMPARE(long);
  78     CDSUNIT_INT_COMPARE(unsigned long);
  79     CDSUNIT_INT_COMPARE(long long);
  80     CDSUNIT_INT_COMPARE(unsigned long long);
  81 #undef CDSUNIT_INT_COMPARE
  82
  83 #define CDSUNIT_INT_LESS(t)  template <> struct less<t> { bool operator()( t k1, t k2 ){ return k1 < k2; } }
  84     CDSUNIT_INT_LESS( char );
  85     CDSUNIT_INT_LESS( unsigned char );
  86     CDSUNIT_INT_LESS( int );
  87     CDSUNIT_INT_LESS( unsigned int );
  88     CDSUNIT_INT_LESS( long );
  89     CDSUNIT_INT_LESS( unsigned long );
  90     CDSUNIT_INT_LESS( long long );
  91     CDSUNIT_INT_LESS( unsigned long long );
  92 #undef CDSUNIT_INT_LESS
  93
  94     template <>
  95     struct cmp<std::string>
  96     {
  97         int operator()(std::string const& s1, std::string const& s2)
  98         {
  99             return s1.compare( s2 );
 100         }
 101         int operator()(std::string const& s1, char const * s2)
 102         {
 103             return s1.compare( s2 );
 104         }
 105         int operator()(char const * s1, std::string const& s2)
 106         {
 107             return -s2.compare( s1 );
 108         }
 109     };
 110
 111     template <>
 112     struct less<std::string>
 113     {
 114         bool operator ()( std::string const& k1, std::string const& k2 ) const
 115         {
 116             return cmp<std::string>()( k1, k2 ) < 0;
 117         }
 118         bool operator ()( std::string const& k1, char const* k2 ) const
 119         {
 120             return cmp<std::string>()( k1, k2 ) < 0;
 121         }
 122         bool operator ()( char const* k1, std::string const& k2 ) const
 123         {
 124             return cmp<std::string>()( k1, k2 ) < 0;
 125         }
 126     };
 127
 128     template <typename T>
 129     struct hash
 130     {
 131         typedef size_t result_type;
 132         typedef T      argument_type;
 133
 134         size_t operator()( T const& k ) const
 135         {
 136             return std::hash<size_t>()(k.nKey);
 137         }
 138
 139         size_t operator()( size_t k ) const
 140         {
 141             return std::hash<size_t>()(k);
 142         }
 143     };
 144
 145     template <>
 146     struct hash<size_t>
 147     {
 148         typedef size_t result_type;
 149         typedef size_t argument_type;
 150
 151         size_t operator()( size_t k ) const
 152         {
 153             return std::hash<size_t>()(k);
 154         }
 155     };
 156
 157     template <>
 158     struct hash<std::string>
 159     {
 160         typedef size_t result_type;
 161         typedef std::string argument_type;
 162
 163         size_t operator()( std::string const& k ) const
 164         {
 165             return std::hash<std::string>()(k);
 166         }
 167     };
 168
 169     // forward
 170     template <typename ImplSelector, typename Key, typename Value>
 171     struct set_type;
 172
 173     template <typename Key, typename Value>
 174     struct set_type_base
 175     {
 176         typedef Key     key_type;
 177         typedef Value   value_type;
 178
 179         struct key_val {
 180             key_type    key;
 181             value_type  val;
 182
 183             explicit key_val( key_type const& k ): key(k), val() {}
 184             key_val( key_type const& k, value_type const& v ): key(k), val(v) {}
 185
 186             template <typename K>
 187             explicit key_val( K const& k ): key(k) {}
 188
 189             template <typename K, typename T>
 190             key_val( K const& k, T const& v ): key(k), val(v) {}
 191         };
 192
 193         typedef set::hash<key_type>   key_hash;
 194         typedef set::less<key_type>   key_less;
 195         typedef set::cmp<key_type>    key_compare;
 196
 197         struct less {
 198             bool operator()( key_val const& k1, key_val const& k2 ) const
 199             {
 200                 return key_less()( k1.key, k2.key );
 201             }
 202             bool operator()( key_type const& k1, key_val const& k2 ) const
 203             {
 204                 return key_less()( k1, k2.key );
 205             }
 206             bool operator()( key_val const& k1, key_type const& k2 ) const
 207             {
 208                 return key_less()( k1.key, k2 );
 209             }
 210         };
 211
 212         struct compare {
 213             int operator()( key_val const& k1, key_val const& k2 ) const
 214             {
 215                 return key_compare()( k1.key, k2.key );
 216             }
 217             int operator()( key_type const& k1, key_val const& k2 ) const
 218             {
 219                 return key_compare()( k1, k2.key );
 220             }
 221             int operator()( key_val const& k1, key_type const& k2 ) const
 222             {
 223                 return key_compare()( k1.key, k2 );
 224             }
 225         };
 226
 227         struct equal_to {
 228             bool operator()( key_val const& k1, key_val const& k2 ) const
 229             {
 230                 return key_compare()( k1.key, k2.key ) == 0;
 231             }
 232             bool operator()( key_type const& k1, key_val const& k2 ) const
 233             {
 234                 return key_compare()( k1, k2.key ) == 0;
 235             }
 236             bool operator()( key_val const& k1, key_type const& k2 ) const
 237             {
 238                 return key_compare()( k1.key, k2 ) == 0;
 239             }
 240         };
 241
 242
 243         struct hash: public key_hash
 244         {
 245             size_t operator()( key_val const& v ) const
 246             {
 247                 return key_hash::operator()( v.key );
 248             }
 249             size_t operator()( key_type const& key ) const
 250             {
 251                 return key_hash::operator()( key );
 252             }
 253             template <typename Q>
 254             size_t operator()( Q const& k ) const
 255             {
 256                 return key_hash::operator()( k );
 257             }
 258         };
 259
 260         struct hash2: public hash
 261         {
 262             size_t operator()( key_val const& k ) const
 263             {
 264                 size_t h = hash::operator ()( k.key );
 265                 size_t seed = ~h;
 266                 seed ^= h + 0x9e3779b9 + (seed << 6) + (seed >> 2);
 267                 return seed;
 268             }
 269             size_t operator()( key_type const& k ) const
 270             {
 271                 size_t h = hash::operator ()( k );
 272                 size_t seed = ~h;
 273                 seed ^= h + 0x9e3779b9 + (seed << 6) + (seed >> 2);
 274                 return seed;
 275             }
 276             template <typename Q>
 277             size_t operator()( Q const& k ) const
 278             {
 279                 return key_hash::operator()( k );
 280             }
 281         };
 282     };
 283
 284
 285     // *************************************************
 286     // print_stat
 287     // *************************************************
 288
 289     struct empty_stat {};
 290     static inline cds_test::property_stream& operator <<( cds_test::property_stream& o, empty_stat const& )
 291     {
 292         return o;
 293     }
 294
 295     template <typename Set>
 296     static inline void print_stat( cds_test::property_stream& o, Set const& s )
 297     {
 298         o << s.statistics();
 299     }
 300
 301
 302     //*******************************************************
 303     // additional_check
 304     //*******************************************************
 305
 306     template <typename Set>
 307     static inline void additional_check( Set& /*set*/ )
 308     {}
 309
 310     template <typename Set>
 311     static inline void additional_cleanup( Set& /*set*/ )
 312     {}
 313
 314     //*******************************************************
 315     // check_before_clear
 316     //*******************************************************
 317
 318     template <typename Set>
 319     static inline void check_before_clear( Set& /*s*/ )
 320     {}
 321
 322 } // namespace set
 323
 324
 325 #endif // ifndef CDSUNIT_SET_TYPE_H