test/stress/map/map_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_MAP_TYPE_H
  32 #define CDSUNIT_MAP_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 #include <cds/urcu/signal_threaded.h>
  39
  40 #include <cds/sync/spinlock.h>
  41 #include <cds/opt/hash.h>
  42 #include <boost/functional/hash/hash.hpp>
  43
  44 #include <cds_test/stress_test.h>
  45 #include <cds_test/check_size.h>
  46 #include "framework/michael_alloc.h"
  47
  48 namespace map {
  49     namespace cc = cds::container;
  50     namespace co = cds::opt;
  51
  52     typedef cds::urcu::gc< cds::urcu::general_instant_stripped >   rcu_gpi;
  53     typedef cds::urcu::gc< cds::urcu::general_buffered_stripped >  rcu_gpb;
  54     typedef cds::urcu::gc< cds::urcu::general_threaded_stripped >  rcu_gpt;
  55 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
  56     typedef cds::urcu::gc< cds::urcu::signal_buffered_stripped >  rcu_shb;
  57     typedef cds::urcu::gc< cds::urcu::signal_threaded_stripped >  rcu_sht;
  58 #endif
  59
  60     template <typename Key>
  61     struct less;
  62
  63     template <typename Key>
  64     struct cmp {
  65         int operator ()(Key const& k1, Key const& k2) const
  66         {
  67             if ( less<Key>( k1, k2 ))
  68                 return -1;
  69             return less<Key>( k2, k1 ) ? 1 : 0;
  70         }
  71     };
  72
  73     template <typename Key>
  74     struct hash;
  75
  76 #define CDSUNIT_INT_COMPARE(t)  template <> struct cmp<t> { int operator()( t k1, t k2 ) const { return (int)(k1 - k2); } }
  77     CDSUNIT_INT_COMPARE(char);
  78     CDSUNIT_INT_COMPARE(unsigned char);
  79     CDSUNIT_INT_COMPARE(int);
  80     CDSUNIT_INT_COMPARE(unsigned int);
  81     CDSUNIT_INT_COMPARE(long);
  82     CDSUNIT_INT_COMPARE(unsigned long);
  83     CDSUNIT_INT_COMPARE(long long);
  84     CDSUNIT_INT_COMPARE(unsigned long long);
  85 #undef CDSUNIT_INT_COMPARE
  86
  87 #define CDSUNIT_INT_LESS(t)  template <> struct less<t> { bool operator()( t k1, t k2 ) const { return k1 < k2; } }
  88     CDSUNIT_INT_LESS( char );
  89     CDSUNIT_INT_LESS( unsigned char );
  90     CDSUNIT_INT_LESS( int );
  91     CDSUNIT_INT_LESS( unsigned int );
  92     CDSUNIT_INT_LESS( long );
  93     CDSUNIT_INT_LESS( unsigned long );
  94     CDSUNIT_INT_LESS( long long );
  95     CDSUNIT_INT_LESS( unsigned long long );
  96 #undef CDSUNIT_INT_LESS
  97
  98     template <>
  99     struct cmp<std::string>
 100     {
 101         int operator()(std::string const& s1, std::string const& s2)
 102         {
 103             return s1.compare( s2 );
 104         }
 105         int operator()(std::string const& s1, char const * s2)
 106         {
 107             return s1.compare( s2 );
 108         }
 109         int operator()(char const * s1, std::string const& s2)
 110         {
 111             return -s2.compare( s1 );
 112         }
 113     };
 114
 115     template <>
 116     struct less<std::string>
 117     {
 118         bool operator ()( std::string const& k1, std::string const& k2 ) const
 119         {
 120             return cmp<std::string>()(k1, k2) < 0;
 121         }
 122         bool operator ()( std::string const& k1, char const* k2 ) const
 123         {
 124             return cmp<std::string>()(k1, k2) < 0;
 125         }
 126         bool operator ()( char const* k1, std::string const& k2 ) const
 127         {
 128             return cmp<std::string>()(k1, k2) < 0;
 129         }
 130     };
 131
 132     template <typename T>
 133     struct hash
 134     {
 135         typedef size_t result_type;
 136         typedef T      argument_type;
 137
 138         size_t operator()( T const& k ) const
 139         {
 140             return std::hash<size_t>()(k.nKey);
 141         }
 142
 143         size_t operator()( size_t k ) const
 144         {
 145             return std::hash<size_t>()(k);
 146         }
 147     };
 148
 149     template <>
 150     struct hash<size_t>
 151     {
 152         typedef size_t result_type;
 153         typedef size_t argument_type;
 154
 155         size_t operator()( size_t k ) const
 156         {
 157             return std::hash<size_t>()(k);
 158         }
 159     };
 160
 161     template <>
 162     struct hash<std::string>
 163     {
 164         typedef size_t result_type;
 165         typedef std::string argument_type;
 166
 167         size_t operator()( std::string const& k ) const
 168         {
 169             return std::hash<std::string>()(k);
 170         }
 171     };
 172
 173     // forward
 174     template <typename ImplSelector, typename Key, typename Value>
 175     struct map_type;
 176
 177     template <typename Key, typename Value>
 178     struct map_type_base
 179     {
 180         typedef map::hash<Key>    key_hash;
 181         typedef map::less<Key>    key_less;
 182         typedef cmp<Key>          key_compare;
 183
 184         struct equal_to {
 185             bool operator()( Key const& k1, Key const& k2 ) const
 186             {
 187                 return key_compare()( k1, k2 ) == 0;
 188             }
 189         };
 190
 191         struct hash2: public key_hash
 192         {
 193             size_t operator()( Key const& k ) const
 194             {
 195                 size_t h = key_hash::operator ()( k );
 196                 size_t seed = ~h;
 197                 seed ^= h + 0x9e3779b9 + (seed << 6) + (seed >> 2);
 198                 return seed;
 199             }
 200             template <typename Q>
 201             size_t operator()( Q const& k ) const
 202             {
 203                 size_t h = key_hash::operator ()( k );
 204                 size_t seed = ~h;
 205                 seed ^= h + 0x9e3779b9 + (seed << 6) + (seed >> 2);
 206                 return seed;
 207             }
 208         };
 209     };
 210
 211     struct empty_stat {};
 212     static inline cds_test::property_stream& operator <<( cds_test::property_stream& o, empty_stat const& )
 213     {
 214         return o;
 215     }
 216
 217     template <typename Map>
 218     static inline void print_stat( cds_test::property_stream& o, Map const& m )
 219     {
 220         o << m.statistics();
 221     }
 222
 223
 224     template <typename Map>
 225     static inline void check_before_cleanup( Map& /*m*/ )
 226     {}
 227
 228     template <typename Map>
 229     static inline void additional_cleanup( Map& /*m*/ )
 230     {}
 231
 232     template <typename Map>
 233     static inline void additional_check( Map& /*m*/ )
 234     {}
 235
 236 } // namespace map
 237
 238 #endif // ifndef CDSUNIT_MAP_TYPE_H