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
15 #ifdef CDS_DOXYGEN_INVOKED
16 /// Lock striping concurrent access policy. This is typedef for intrusive::cuckoo::striping template
20 using intrusive::cuckoo::striping;
23 #ifdef CDS_DOXYGEN_INVOKED
24 /// Refinable concurrent access policy. This is typedef for intrusive::cuckoo::refinable template
28 using intrusive::cuckoo::refinable;
31 #ifdef CDS_DOXYGEN_INVOKED
32 /// Striping internal statistics. This is typedef for intrusive::cuckoo::striping_stat
36 using intrusive::cuckoo::striping_stat;
39 #ifdef CDS_DOXYGEN_INVOKED
40 /// Empty striping internal statistics. This is typedef for intrusive::cuckoo::empty_striping_stat
41 class empty_striping_stat
44 using intrusive::cuckoo::empty_striping_stat;
47 #ifdef CDS_DOXYGEN_INVOKED
48 /// Refinable internal statistics. This is typedef for intrusive::cuckoo::refinable_stat
52 using intrusive::cuckoo::refinable_stat;
55 #ifdef CDS_DOXYGEN_INVOKED
56 /// Empty refinable internal statistics. This is typedef for intrusive::cuckoo::empty_refinable_stat
57 class empty_refinable_stat
60 using intrusive::cuckoo::empty_refinable_stat;
63 #ifdef CDS_DOXYGEN_INVOKED
64 /// Cuckoo statistics. This is typedef for intrusive::cuckoo::stat
68 using intrusive::cuckoo::stat;
71 #ifdef CDS_DOXYGEN_INVOKED
72 /// Cuckoo empty statistics.This is typedef for intrusive::cuckoo::empty_stat
76 using intrusive::cuckoo::empty_stat;
79 /// Option specifying whether to store hash values in the node
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
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
90 template <bool Enable>
94 template <typename Base>
95 struct pack: public Base {
96 static bool const store_hash = Enable;
101 #ifdef CDS_DOXYGEN_INVOKED
102 /// Probe set type option
104 The option specifies probe set type for the CuckooSet and CuckooMap.
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.
110 template <typename Type>
114 using intrusive::cuckoo::probeset_type;
117 using intrusive::cuckoo::list;
118 using intrusive::cuckoo::vector;
120 /// Type traits for CuckooSet and CuckooMap classes
123 /// Hash functors tuple
125 This is mandatory type and has no predefined one.
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.
133 To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
135 struct my_traits: public cds::container::cuckoo::traits {
136 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
140 typedef cds::opt::none hash;
142 /// Concurrent access policy
144 Available opt::mutex_policy types:
145 - cuckoo::striping - simple, but the lock array is not resizable
146 - cuckoo::refinable - resizable lock array, but more complex access to set data.
148 Default is cuckoo::striping.
150 typedef cuckoo::striping<> mutex_policy;
152 /// Key equality functor
154 Default is <tt>std::equal_to<T></tt>
156 typedef opt::none equal_to;
158 /// Key comparison functor
160 No default functor is provided. If the option is not specified, the \p less is used.
162 typedef opt::none compare;
164 /// specifies binary predicate used for key comparison.
166 Default is \p std::less<T>.
168 typedef opt::none less;
172 The type for item counting feature.
173 Default is cds::atomicity::item_counter
175 Only atomic item counter type is allowed.
177 typedef cds::intrusive::cuckoo::traits::item_counter item_counter;
181 The allocator type for allocating bucket tables.
182 Default is \p CDS_DEFAULT_ALLOCATOR that is \p std::allocator
184 typedef CDS_DEFAULT_ALLOCATOR allocator;
186 /// Node allocator type
188 If this type is not set explicitly, the \ref allocator type is used.
190 typedef opt::none node_allocator;
192 /// Store hash value into items. See cuckoo::store_hash for explanation
193 static bool const store_hash = false;
195 /// Probe-set type. See \ref probeset_type option for explanation
196 typedef cuckoo::list probeset_type;
198 /// Internal statistics
199 typedef empty_stat stat;
202 /// Metafunction converting option list to CuckooSet/CuckooMap traits
204 Template argument list \p Options... are:
205 - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
206 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
207 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
208 the number \p k - the count of hash tables in cuckoo hashing.
209 - \p opt::mutex_policy - concurrent access policy.
210 Available policies: \p cuckoo::striping, \p cuckoo::refinable.
211 Default is \p %cuckoo::striping.
212 - \p opt::equal_to - key equality functor like \p std::equal_to.
213 If this functor is defined then the probe-set will be unordered.
214 If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered
215 and \p %opt::equal_to will be ignored.
216 - \p opt::compare - key comparison functor. No default functor is provided.
217 If the option is not specified, the \p %opt::less is used.
218 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
219 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
220 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
221 - \p opt::item_counter - the type of item counting feature. Default is \p opt::v::sequential_item_counter.
222 - \p opt::allocator - the allocator type using for allocating bucket tables.
223 Default is \ref CDS_DEFAULT_ALLOCATOR
224 - \p opt::node_allocator - the allocator type using for allocating set's items. If this option
225 is not specified then the type defined in \p %opt::allocator option is used.
226 - \p cuckoo::store_hash - this option reserves additional space in the node to store the hash value
227 of the object once it's introduced in the container. When this option is used,
228 the unordered container will store the calculated hash value in the node and rehashing operations won't need
229 to recalculate the hash of the value. This option will improve the performance of unordered containers
230 when rehashing is frequent or hashing the value is a slow operation. Default value is \p false.
231 - \ref intrusive::cuckoo::probeset_type "cuckoo::probeset_type" - type of probe set, may be \p cuckoo::list or <tt>cuckoo::vector<Capacity></tt>,
232 Default is \p cuckoo::list.
233 - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat.
234 Default is \p %cuckoo::empty_stat
236 template <typename... Options>
238 typedef typename cds::opt::make_options<
239 typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type
241 >::type type ; ///< Result of metafunction
243 } // namespace cuckoo
244 }} // namespace cds::container
246 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_CUCKOO_BASE_H