cds/container/details/cuckoo_base.h

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