2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
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.
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.
31 #ifndef CDSLIB_CONTAINER_DETAILS_CUCKOO_BASE_H
32 #define CDSLIB_CONTAINER_DETAILS_CUCKOO_BASE_H
34 #include <cds/intrusive/cuckoo_set.h>
36 namespace cds { namespace container {
38 /// CuckooSet and CuckooMap related definitions
39 /** @ingroup cds_nonintrusive_helper
42 #ifdef CDS_DOXYGEN_INVOKED
43 /// Lock striping concurrent access policy. This is typedef for intrusive::cuckoo::striping template
47 using intrusive::cuckoo::striping;
50 #ifdef CDS_DOXYGEN_INVOKED
51 /// Refinable concurrent access policy. This is typedef for intrusive::cuckoo::refinable template
55 using intrusive::cuckoo::refinable;
58 #ifdef CDS_DOXYGEN_INVOKED
59 /// Striping internal statistics. This is typedef for intrusive::cuckoo::striping_stat
63 using intrusive::cuckoo::striping_stat;
66 #ifdef CDS_DOXYGEN_INVOKED
67 /// Empty striping internal statistics. This is typedef for intrusive::cuckoo::empty_striping_stat
68 class empty_striping_stat
71 using intrusive::cuckoo::empty_striping_stat;
74 #ifdef CDS_DOXYGEN_INVOKED
75 /// Refinable internal statistics. This is typedef for intrusive::cuckoo::refinable_stat
79 using intrusive::cuckoo::refinable_stat;
82 #ifdef CDS_DOXYGEN_INVOKED
83 /// Empty refinable internal statistics. This is typedef for intrusive::cuckoo::empty_refinable_stat
84 class empty_refinable_stat
87 using intrusive::cuckoo::empty_refinable_stat;
90 #ifdef CDS_DOXYGEN_INVOKED
91 /// Cuckoo statistics. This is typedef for intrusive::cuckoo::stat
95 using intrusive::cuckoo::stat;
98 #ifdef CDS_DOXYGEN_INVOKED
99 /// Cuckoo empty statistics.This is typedef for intrusive::cuckoo::empty_stat
103 using intrusive::cuckoo::empty_stat;
106 /// Option specifying whether to store hash values in the node
108 This option reserves additional space in the hook to store the hash value of the object once it's introduced in the container.
109 When this option is used, the unordered container will store the calculated hash value in the hook and rehashing operations won't need
110 to recalculate the hash of the value. This option will improve the performance of unordered containers
111 when rehashing is frequent or hashing the value is a slow operation
113 The \p Enable template parameter toggles the feature:
114 - the value \p true enables storing the hash values
115 - the value \p false disables storing the hash values
117 template <bool Enable>
121 template <typename Base>
122 struct pack: public Base {
123 static bool const store_hash = Enable;
128 #ifdef CDS_DOXYGEN_INVOKED
129 /// Probe set type option
131 @copydetails cds::intrusive::cuckoo::probeset_type
133 template <typename Type>
137 using intrusive::cuckoo::probeset_type;
140 using intrusive::cuckoo::list;
141 using intrusive::cuckoo::vector;
143 /// Type traits for CuckooSet and CuckooMap classes
146 /// Hash functors tuple
148 This is mandatory type and has no predefined one.
150 At least, two hash functors should be provided. All hash functor
151 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
152 The hash functors are defined as <tt> std::tuple< H1, H2, ... Hn > </tt>:
153 \@code cds::opt::hash< std::tuple< h1, h2 > > \@endcode
154 The number of hash functors specifies the number \p k - the count of hash tables in cuckoo hashing.
156 To specify hash tuple in traits you should use \p cds::opt::hash_tuple:
158 struct my_traits: public cds::container::cuckoo::traits {
159 typedef cds::opt::hash_tuple< hash1, hash2 > hash;
163 typedef cds::opt::none hash;
165 /// Concurrent access policy
167 Available opt::mutex_policy types:
168 - cuckoo::striping - simple, but the lock array is not resizable
169 - cuckoo::refinable - resizable lock array, but more complex access to set data.
171 Default is cuckoo::striping.
173 typedef cuckoo::striping<> mutex_policy;
175 /// Key equality functor
177 Default is <tt>std::equal_to<T></tt>
179 typedef opt::none equal_to;
181 /// Key comparison functor
183 No default functor is provided. If the option is not specified, the \p less is used.
185 typedef opt::none compare;
187 /// specifies binary predicate used for key comparison.
189 Default is \p std::less<T>.
191 typedef opt::none less;
195 The type for item counting feature.
196 Default is cds::atomicity::item_counter
198 Only atomic item counter type is allowed.
200 typedef cds::intrusive::cuckoo::traits::item_counter item_counter;
204 The allocator type for allocating bucket tables.
205 Default is \p CDS_DEFAULT_ALLOCATOR that is \p std::allocator
207 typedef CDS_DEFAULT_ALLOCATOR allocator;
209 /// Node allocator type
211 If this type is not set explicitly, the \ref allocator type is used.
213 typedef opt::none node_allocator;
215 /// Store hash value into items. See cuckoo::store_hash for explanation
216 static bool const store_hash = false;
218 /// Probe-set type. See \ref probeset_type option for explanation
219 typedef cuckoo::list probeset_type;
221 /// Internal statistics
222 typedef empty_stat stat;
225 /// Metafunction converting option list to CuckooSet/CuckooMap traits
227 Template argument list \p Options... are:
228 - \p opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
229 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
230 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
231 the number \p k - the count of hash tables in cuckoo hashing.
232 - \p opt::mutex_policy - concurrent access policy.
233 Available policies: \p cuckoo::striping, \p cuckoo::refinable.
234 Default is \p %cuckoo::striping.
235 - \p opt::equal_to - key equality functor like \p std::equal_to.
236 If this functor is defined then the probe-set will be unordered.
237 If \p %opt::compare or \p %opt::less option is specified too, then the probe-set will be ordered
238 and \p %opt::equal_to will be ignored.
239 - \p opt::compare - key comparison functor. No default functor is provided.
240 If the option is not specified, the \p %opt::less is used.
241 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
242 - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
243 If \p %opt::compare or \p %opt::less option is specified, then the probe-set will be ordered.
244 - \p opt::item_counter - the type of item counting feature. Default is \p opt::v::sequential_item_counter.
245 - \p opt::allocator - the allocator type using for allocating bucket tables.
246 Default is \ref CDS_DEFAULT_ALLOCATOR
247 - \p opt::node_allocator - the allocator type using for allocating set's items. If this option
248 is not specified then the type defined in \p %opt::allocator option is used.
249 - \p cuckoo::store_hash - this option reserves additional space in the node to store the hash value
250 of the object once it's introduced in the container. When this option is used,
251 the unordered container will store the calculated hash value in the node and rehashing operations won't need
252 to recalculate the hash of the value. This option will improve the performance of unordered containers
253 when rehashing is frequent or hashing the value is a slow operation. Default value is \p false.
254 - \ref intrusive::cuckoo::probeset_type "cuckoo::probeset_type" - type of probe set, may be \p cuckoo::list or <tt>cuckoo::vector<Capacity></tt>,
255 Default is \p cuckoo::list.
256 - \p opt::stat - internal statistics. Possibly types: \p cuckoo::stat, \p cuckoo::empty_stat.
257 Default is \p %cuckoo::empty_stat
259 template <typename... Options>
261 typedef typename cds::opt::make_options<
262 typename cds::opt::find_type_traits< cuckoo::traits, Options... >::type
264 >::type type ; ///< Result of metafunction
266 } // namespace cuckoo
267 }} // namespace cds::container
269 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_CUCKOO_BASE_H