tests/unit/map2/map_type_cuckoo.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_MAP_TYPE_CUCKOO_H
  32 #define CDSUNIT_MAP_TYPE_CUCKOO_H
  33
  34 #include "map2/map_type.h"
  35 #include <cds/container/cuckoo_map.h>
  36 #include "print_cuckoo_stat.h"
  37
  38 namespace map2 {
  39
  40     template <typename K, typename V, typename Traits>
  41     class CuckooMap: public cc::CuckooMap< K, V, Traits >
  42     {
  43     public:
  44         typedef cc::CuckooMap< K, V, Traits > base_class;
  45
  46     public:
  47         template <typename Config>
  48         CuckooMap( Config const& cfg )
  49             : base_class(
  50
  51                 cfg.c_nCuckooInitialSize,
  52                 static_cast<unsigned int>( cfg.c_nCuckooProbesetSize ),
  53                 static_cast<unsigned int>( cfg.c_nCuckooProbesetThreshold )
  54             )
  55         {}
  56
  57         template <typename Q, typename Pred>
  58         bool erase_with( Q const& key, Pred /*pred*/ )
  59         {
  60             return base_class::erase_with( key, typename std::conditional< base_class::c_isSorted, Pred, typename Pred::equal_to>::type() );
  61         }
  62
  63         // for testing
  64         static CDS_CONSTEXPR bool const c_bExtractSupported = false;
  65         static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
  66         static CDS_CONSTEXPR bool const c_bEraseExactKey = false;
  67     };
  68
  69     struct tag_CuckooMap;
  70
  71     template <typename Key, typename Value>
  72     struct map_type< tag_CuckooMap, Key, Value >: public map_type_base< Key, Value >
  73     {
  74         typedef map_type_base< Key, Value > base_class;
  75         typedef typename base_class::compare    compare;
  76         typedef typename base_class::less       less;
  77         typedef typename base_class::equal_to   equal_to;
  78         typedef typename base_class::key_hash   key_hash;
  79         typedef typename base_class::hash       hash;
  80         typedef typename base_class::hash2      hash2;
  81
  82         template <typename Traits>
  83         struct traits_CuckooStripedMap: public Traits
  84         {
  85             typedef cc::cuckoo::striping<> mutex_policy;
  86         };
  87         template <typename Traits>
  88         struct traits_CuckooRefinableMap : public Traits
  89         {
  90             typedef cc::cuckoo::refinable<> mutex_policy;
  91         };
  92
  93         struct traits_CuckooMap_list_unord :
  94             public cc::cuckoo::make_traits <
  95                 cc::cuckoo::probeset_type< cc::cuckoo::list >
  96                 , co::equal_to< equal_to >
  97                 , co::hash< std::tuple< hash, hash2 > >
  98             > ::type
  99         {};
 100         typedef CuckooMap< Key, Value, traits_CuckooStripedMap<traits_CuckooMap_list_unord>> CuckooStripedMap_list_unord;
 101         typedef CuckooMap< Key, Value, traits_CuckooRefinableMap<traits_CuckooMap_list_unord>> CuckooRefinableMap_list_unord;
 102
 103         struct traits_CuckooMap_list_unord_stat : public traits_CuckooMap_list_unord
 104         {
 105             typedef cc::cuckoo::stat stat;
 106         };
 107         typedef CuckooMap< Key, Value, traits_CuckooStripedMap<traits_CuckooMap_list_unord_stat>> CuckooStripedMap_list_unord_stat;
 108         typedef CuckooMap< Key, Value, traits_CuckooRefinableMap<traits_CuckooMap_list_unord_stat>> CuckooRefinableMap_list_unord_stat;
 109
 110         struct traits_CuckooMap_list_unord_storehash : public traits_CuckooMap_list_unord
 111         {
 112             static CDS_CONSTEXPR const bool store_hash = true;
 113         };
 114         typedef CuckooMap< Key, Value, traits_CuckooStripedMap<traits_CuckooMap_list_unord_storehash>> CuckooStripedMap_list_unord_storehash;
 115         typedef CuckooMap< Key, Value, traits_CuckooRefinableMap<traits_CuckooMap_list_unord_storehash>> CuckooRefinableMap_list_unord_storehash;
 116
 117         struct traits_CuckooMap_list_ord :
 118             public cc::cuckoo::make_traits <
 119                 cc::cuckoo::probeset_type< cc::cuckoo::list >
 120                 , co::compare< compare >
 121                 , co::hash< std::tuple< hash, hash2 > >
 122             >::type
 123         {};
 124         typedef CuckooMap< Key, Value, traits_CuckooStripedMap<traits_CuckooMap_list_ord>> CuckooStripedMap_list_ord;
 125         typedef CuckooMap< Key, Value, traits_CuckooRefinableMap<traits_CuckooMap_list_ord>> CuckooRefinableMap_list_ord;
 126
 127         struct traits_CuckooMap_list_ord_stat : public traits_CuckooMap_list_ord
 128         {
 129             typedef cc::cuckoo::stat stat;
 130         };
 131         typedef CuckooMap< Key, Value, traits_CuckooStripedMap<traits_CuckooMap_list_ord_stat>> CuckooStripedMap_list_ord_stat;
 132         typedef CuckooMap< Key, Value, traits_CuckooRefinableMap<traits_CuckooMap_list_ord_stat>> CuckooRefinableMap_list_ord_stat;
 133
 134         struct traits_CuckooMap_list_ord_storehash : public traits_CuckooMap_list_ord
 135         {
 136             static CDS_CONSTEXPR const bool store_hash = true;
 137         };
 138         typedef CuckooMap< Key, Value, traits_CuckooStripedMap<traits_CuckooMap_list_ord_storehash>> CuckooStripedMap_list_ord_storehash;
 139         typedef CuckooMap< Key, Value, traits_CuckooRefinableMap<traits_CuckooMap_list_ord_storehash>> CuckooRefinableMap_list_ord_storehash;
 140
 141         struct traits_CuckooMap_vector_unord :
 142             public cc::cuckoo::make_traits <
 143                 cc::cuckoo::probeset_type< cc::cuckoo::vector<4> >
 144                 , co::equal_to< equal_to >
 145                 , co::hash< std::tuple< hash, hash2 > >
 146             >::type
 147         {};
 148         typedef CuckooMap< Key, Value, traits_CuckooStripedMap<traits_CuckooMap_vector_unord>> CuckooStripedMap_vector_unord;
 149         typedef CuckooMap< Key, Value, traits_CuckooRefinableMap<traits_CuckooMap_vector_unord>> CuckooRefinableMap_vector_unord;
 150
 151         struct traits_CuckooMap_vector_unord_stat : public traits_CuckooMap_vector_unord
 152         {
 153             typedef cc::cuckoo::stat stat;
 154         };
 155         typedef CuckooMap< Key, Value, traits_CuckooStripedMap<traits_CuckooMap_vector_unord_stat>> CuckooStripedMap_vector_unord_stat;
 156         typedef CuckooMap< Key, Value, traits_CuckooRefinableMap<traits_CuckooMap_vector_unord_stat>> CuckooRefinableMap_vector_unord_stat;
 157
 158         struct traits_CuckooMap_vector_unord_storehash : public traits_CuckooMap_vector_unord
 159         {
 160             static CDS_CONSTEXPR const bool store_hash = true;
 161         };
 162         typedef CuckooMap< Key, Value, traits_CuckooStripedMap<traits_CuckooMap_vector_unord_storehash>> CuckooStripedMap_vector_unord_storehash;
 163         typedef CuckooMap< Key, Value, traits_CuckooRefinableMap<traits_CuckooMap_vector_unord_storehash>> CuckooRefinableMap_vector_unord_storehash;
 164
 165         struct traits_CuckooMap_vector_ord :
 166             public cc::cuckoo::make_traits <
 167                 cc::cuckoo::probeset_type< cc::cuckoo::vector<4> >
 168                 , co::compare< compare >
 169                 , co::hash< std::tuple< hash, hash2 > >
 170             >::type
 171         {};
 172         typedef CuckooMap< Key, Value, traits_CuckooStripedMap<traits_CuckooMap_vector_ord>> CuckooStripedMap_vector_ord;
 173         typedef CuckooMap< Key, Value, traits_CuckooRefinableMap<traits_CuckooMap_vector_ord>> CuckooRefinableMap_vector_ord;
 174
 175         struct traits_CuckooMap_vector_ord_stat : public traits_CuckooMap_vector_ord
 176         {
 177             typedef cc::cuckoo::stat stat;
 178         };
 179         typedef CuckooMap< Key, Value, traits_CuckooStripedMap<traits_CuckooMap_vector_ord_stat>> CuckooStripedMap_vector_ord_stat;
 180         typedef CuckooMap< Key, Value, traits_CuckooRefinableMap<traits_CuckooMap_vector_ord_stat>> CuckooRefinableMap_vector_ord_stat;
 181
 182         struct traits_CuckooMap_vector_ord_storehash : public traits_CuckooMap_vector_ord
 183         {
 184             static CDS_CONSTEXPR const bool store_hash = true;
 185         };
 186         typedef CuckooMap< Key, Value, traits_CuckooStripedMap<traits_CuckooMap_vector_ord_storehash>> CuckooStripedMap_vector_ord_storehash;
 187         typedef CuckooMap< Key, Value, traits_CuckooRefinableMap<traits_CuckooMap_vector_ord_storehash>> CuckooRefinableMap_vector_ord_storehash;
 188
 189     };
 190
 191     template <typename K, typename T, typename Traits >
 192     static inline void print_stat( cc::CuckooMap< K, T, Traits > const& m )
 193     {
 194         CPPUNIT_MSG( m.statistics() << m.mutex_policy_statistics() );
 195     }
 196
 197     template <typename K, typename V, typename Traits>
 198     static inline void print_stat( CuckooMap< K, V, Traits > const& m )
 199     {
 200         typedef CuckooMap< K, V, Traits > map_type;
 201         print_stat( static_cast<typename map_type::base_class const&>(m) );
 202     }
 203
 204 }   // namespace map2
 205
 206 #endif // ifndef CDSUNIT_MAP_TYPE_CUCKOO_H