3 #ifndef CDSLIB_CONTAINER_DETAILS_CUCKOO_BASE_H
4 #define CDSLIB_CONTAINER_DETAILS_CUCKOO_BASE_H
6 #include <cds/intrusive/cuckoo_set.h>
8 namespace cds { namespace container {
10 /// CuckooSet and CuckooMap related definitions
11 /** @ingroup cds_nonintrusive_helper
14 using cds::intrusive::cuckoo::implementation_tag;
16 #ifdef CDS_DOXYGEN_INVOKED
17 /// Lock striping concurrent access policy. This is typedef for intrusive::cuckoo::striping template
21 using intrusive::cuckoo::striping;
24 #ifdef CDS_DOXYGEN_INVOKED
25 /// Refinable concurrent access policy. This is typedef for intrusive::cuckoo::refinable template
29 using intrusive::cuckoo::refinable;
32 #ifdef CDS_DOXYGEN_INVOKED
33 /// Striping internal statistics. This is typedef for intrusive::cuckoo::striping_stat
37 using intrusive::cuckoo::striping_stat;
40 #ifdef CDS_DOXYGEN_INVOKED
41 /// Empty striping internal statistics. This is typedef for intrusive::cuckoo::empty_striping_stat
42 class empty_striping_stat
45 using intrusive::cuckoo::empty_striping_stat;
48 #ifdef CDS_DOXYGEN_INVOKED
49 /// Refinable internal statistics. This is typedef for intrusive::cuckoo::refinable_stat
53 using intrusive::cuckoo::refinable_stat;
56 #ifdef CDS_DOXYGEN_INVOKED
57 /// Empty refinable internal statistics. This is typedef for intrusive::cuckoo::empty_refinable_stat
58 class empty_refinable_stat
61 using intrusive::cuckoo::empty_refinable_stat;
64 #ifdef CDS_DOXYGEN_INVOKED
65 /// Cuckoo statistics. This is typedef for intrusive::cuckoo::stat
69 using intrusive::cuckoo::stat;
72 #ifdef CDS_DOXYGEN_INVOKED
73 /// Cuckoo empty statistics.This is typedef for intrusive::cuckoo::empty_stat
77 using intrusive::cuckoo::empty_stat;
80 /// Option specifying whether to store hash values in the node
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
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
91 template <bool Enable>
95 template <typename Base>
96 struct pack: public Base {
97 static bool const store_hash = Enable;
102 #ifdef CDS_DOXYGEN_INVOKED
103 /// Probe set type option
105 The option specifies probe set type for the CuckooSet and CuckooMap.
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.
111 template <typename Type>
115 using intrusive::cuckoo::probeset_type;
118 using intrusive::cuckoo::list;
119 using intrusive::cuckoo::vector;
121 /// Type traits for CuckooSet and CuckooMap classes
124 /// Hash functors tuple
126 This is mandatory type and has no predefined one.
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.
134 To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
136 struct my_traits: public cds::container::cuckoo::traits {
137 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
141 typedef cds::opt::none hash;
143 /// Concurrent access policy
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.
149 Default is cuckoo::striping.
151 typedef cuckoo::striping<> mutex_policy;
153 /// Key equality functor
155 Default is <tt>std::equal_to<T></tt>
157 typedef opt::none equal_to;
159 /// Key comparison functor
161 No default functor is provided. If the option is not specified, the \p less is used.
163 typedef opt::none compare;
165 /// specifies binary predicate used for key comparison.
167 Default is \p std::less<T>.
169 typedef opt::none less;
173 The type for item counting feature.
174 Default is cds::atomicity::item_counter
176 Only atomic item counter type is allowed.
178 typedef cds::intrusive::cuckoo::traits::item_counter item_counter;
182 The allocator type for allocating bucket tables.
183 Default is \p CDS_DEFAULT_ALLOCATOR that is \p std::allocator
185 typedef CDS_DEFAULT_ALLOCATOR allocator;
187 /// Node allocator type
189 If this type is not set explicitly, the \ref allocator type is used.
191 typedef opt::none node_allocator;
193 /// Store hash value into items. See cuckoo::store_hash for explanation
194 static bool const store_hash = false;
196 /// Probe-set type. See \ref probeset_type option for explanation
197 typedef cuckoo::list probeset_type;
199 /// Internal statistics
200 typedef empty_stat stat;
203 /// Metafunction converting option list to CuckooSet/CuckooMap traits
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
237 template <typename... Options>
239 typedef typename cds::opt::make_options<
240 typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type
242 >::type type ; ///< Result of metafunction
244 } // namespace cuckoo
245 }} // namespace cds::container
247 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_CUCKOO_BASE_H