cds/container/cuckoo_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_CUCKOO_BASE_H
   4 #define __CDS_CONTAINER_CUCKOO_BASE_H
   5
   6 #include <cds/intrusive/cuckoo_set.h>
   7
   8 namespace cds { namespace container {
   9
  10     /// CuckooSet and CuckooMap related definitions
  11     /** @ingroup cds_nonintrusive_helper
  12     */
  13     namespace cuckoo {
  14
  15 #ifdef CDS_DOXYGEN_INVOKED
  16         /// Lock striping concurrent access policy. This is typedef for intrusive::cuckoo::striping template
  17         class striping
  18         {};
  19 #else
  20         using intrusive::cuckoo::striping;
  21 #endif
  22
  23 #ifdef CDS_DOXYGEN_INVOKED
  24         /// Refinable concurrent access policy. This is typedef for intrusive::cuckoo::refinable template
  25         class refinable
  26         {};
  27 #else
  28         using intrusive::cuckoo::refinable;
  29 #endif
  30
  31 #ifdef CDS_DOXYGEN_INVOKED
  32         /// Striping internal statistics. This is typedef for intrusive::cuckoo::striping_stat
  33         class striping_stat
  34         {};
  35 #else
  36         using intrusive::cuckoo::striping_stat;
  37 #endif
  38
  39 #ifdef CDS_DOXYGEN_INVOKED
  40         /// Empty striping internal statistics. This is typedef for intrusive::cuckoo::empty_striping_stat
  41         class empty_striping_stat
  42         {};
  43 #else
  44         using intrusive::cuckoo::empty_striping_stat;
  45 #endif
  46
  47 #ifdef CDS_DOXYGEN_INVOKED
  48         /// Refinable internal statistics. This is typedef for intrusive::cuckoo::refinable_stat
  49         class refinable_stat
  50         {};
  51 #else
  52         using intrusive::cuckoo::refinable_stat;
  53 #endif
  54
  55 #ifdef CDS_DOXYGEN_INVOKED
  56         /// Empty refinable internal statistics. This is typedef for intrusive::cuckoo::empty_refinable_stat
  57         class empty_refinable_stat
  58         {};
  59 #else
  60         using intrusive::cuckoo::empty_refinable_stat;
  61 #endif
  62
  63 #ifdef CDS_DOXYGEN_INVOKED
  64         /// Cuckoo statistics. This is typedef for intrusive::cuckoo::stat
  65         class stat
  66         {};
  67 #else
  68         using intrusive::cuckoo::stat;
  69 #endif
  70
  71 #ifdef CDS_DOXYGEN_INVOKED
  72         /// Cuckoo empty statistics.This is typedef for intrusive::cuckoo::empty_stat
  73         class empty_stat
  74         {};
  75 #else
  76         using intrusive::cuckoo::empty_stat;
  77 #endif
  78
  79         /// Option specifying whether to store hash values in the node
  80         /**
  81              This option reserves additional space in the hook to store the hash value of the object once it's introduced in the container.
  82              When this option is used, the unordered container will store the calculated hash value in the hook and rehashing operations won't need
  83              to recalculate the hash of the value. This option will improve the performance of unordered containers
  84              when rehashing is frequent or hashing the value is a slow operation
  85
  86              The \p Enable template parameter toggles the feature:
  87              - the value \p true enables storing the hash values
  88              - the value \p false disables storing the hash values
  89         */
  90         template <bool Enable>
  91         struct store_hash
  92         {
  93             //@cond
  94             template <typename Base>
  95             struct pack: public Base {
  96                 static bool const store_hash = Enable;
  97             };
  98             //@endcond
  99         };
 100
 101 #ifdef CDS_DOXYGEN_INVOKED
 102         /// Probe set type option
 103         /**
 104             The option specifies probe set type for the CuckooSet and CuckooMap.
 105             Available \p Type:
 106             - \p cuckoo::list - the probe-set is a single-linked list.
 107             - \p cuckoo::vector<Capacity> - the probe-set is a vector
 108                 with constant-size \p Capacity where \p Capacity is an <tt>unsigned int</tt> constant.
 109         */
 110         template <typename Type>
 111         struct probeset_type
 112         {};
 113 #else
 114         using intrusive::cuckoo::probeset_type;
 115 #endif
 116
 117         using intrusive::cuckoo::list;
 118         using intrusive::cuckoo::vector;
 119
 120         /// Type traits for CuckooSet and CuckooMap classes
 121         struct type_traits
 122         {
 123             /// Hash functors tuple
 124             /**
 125                 This is mandatory type and has no predefined one.
 126
 127                 At least, two hash functors should be provided. All hash functor
 128                 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
 129                 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
 130                 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
 131                 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
 132                 Up to 10 different hash functors are supported.
 133             */
 134             typedef cds::opt::none      hash;
 135
 136             /// Concurrent access policy
 137             /**
 138                 Available opt::mutex_policy types:
 139                 - cuckoo::striping - simple, but the lock array is not resizable
 140                 - cuckoo::refinable - resizable lock array, but more complex access to set data.
 141
 142                 Default is cuckoo::striping.
 143             */
 144             typedef cuckoo::striping<>               mutex_policy;
 145
 146             /// Key equality functor
 147             /**
 148                 Default is <tt>std::equal_to<T></tt>
 149             */
 150             typedef opt::none                       equal_to;
 151
 152             /// Key comparison functor
 153             /**
 154                 No default functor is provided. If the option is not specified, the \p less is used.
 155             */
 156             typedef opt::none                       compare;
 157
 158             /// specifies binary predicate used for key comparison.
 159             /**
 160                 Default is \p std::less<T>.
 161             */
 162             typedef opt::none                       less;
 163
 164             /// Item counter
 165             /**
 166                 The type for item counting feature.
 167                 Default is cds::atomicity::item_counter
 168
 169                 Only atomic item counter type is allowed.
 170             */
 171             typedef cds::intrusive::cuckoo::type_traits::item_counter   item_counter;
 172
 173             /// Allocator type
 174             /**
 175                 The allocator type for allocating bucket tables.
 176                 Default is \p CDS_DEFAULT_ALLOCATOR that is \p std::allocator
 177             */
 178             typedef CDS_DEFAULT_ALLOCATOR       allocator;
 179
 180             /// Node allocator type
 181             /**
 182                 If this type is not set explicitly, the \ref allocator type is used.
 183             */
 184             typedef opt::none                   node_allocator;
 185
 186             /// Store hash value into items. See cuckoo::store_hash for explanation
 187             static bool const store_hash = false;
 188
 189             /// Probe-set type. See \ref probeset_type option for explanation
 190             typedef cuckoo::list                probeset_type;
 191
 192             /// Internal statistics
 193             typedef empty_stat                  stat;
 194         };
 195
 196         /// Metafunction converting option list to CuckooSet/CuckooMap traits
 197         /**
 198             This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
 199             \p Options list see CuckooSet and CuckooMap
 200         */
 201         template <CDS_DECL_OPTIONS12>
 202         struct make_traits {
 203             typedef typename cds::opt::make_options<
 204                 typename cds::opt::find_type_traits< cuckoo::type_traits, CDS_OPTIONS12 >::type
 205                 ,CDS_OPTIONS12
 206             >::type   type ;    ///< Result of metafunction
 207         };
 208     }   // namespace cuckoo
 209 }} // namespace cds::container
 210
 211 #endif  // #ifndef __CDS_CONTAINER_CUCKOO_BASE_H