1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // |
3 | // (C) Copyright Olaf Krzikalla 2004-2006. |
4 | // (C) Copyright Ion Gaztanaga 2006-2013 |
5 | // |
6 | // Distributed under the Boost Software License, Version 1.0. |
7 | // (See accompanying file LICENSE_1_0.txt or copy at |
8 | // http://www.boost.org/LICENSE_1_0.txt) |
9 | // |
10 | // See http://www.boost.org/libs/intrusive for documentation. |
11 | // |
12 | ///////////////////////////////////////////////////////////////////////////// |
13 | |
14 | #ifndef BOOST_INTRUSIVE_UNORDERED_SET_HOOK_HPP |
15 | #define BOOST_INTRUSIVE_UNORDERED_SET_HOOK_HPP |
16 | |
17 | #include <boost/intrusive/detail/config_begin.hpp> |
18 | #include <boost/intrusive/intrusive_fwd.hpp> |
19 | |
20 | #include <boost/intrusive/pointer_traits.hpp> |
21 | #include <boost/intrusive/slist_hook.hpp> |
22 | #include <boost/intrusive/options.hpp> |
23 | #include <boost/intrusive/detail/generic_hook.hpp> |
24 | |
25 | #if defined(BOOST_HAS_PRAGMA_ONCE) |
26 | # pragma once |
27 | #endif |
28 | |
29 | namespace boost { |
30 | namespace intrusive { |
31 | |
32 | /// @cond |
33 | |
34 | template<class VoidPointer, bool StoreHash, bool OptimizeMultiKey> |
35 | struct unordered_node |
36 | : public slist_node<VoidPointer> |
37 | { |
38 | typedef typename pointer_traits |
39 | <VoidPointer>::template rebind_pointer |
40 | < unordered_node<VoidPointer, StoreHash, OptimizeMultiKey> >::type |
41 | node_ptr; |
42 | node_ptr prev_in_group_; |
43 | std::size_t hash_; |
44 | }; |
45 | |
46 | template<class VoidPointer> |
47 | struct unordered_node<VoidPointer, false, true> |
48 | : public slist_node<VoidPointer> |
49 | { |
50 | typedef typename pointer_traits |
51 | <VoidPointer>::template rebind_pointer |
52 | < unordered_node<VoidPointer, false, true> >::type |
53 | node_ptr; |
54 | node_ptr prev_in_group_; |
55 | }; |
56 | |
57 | template<class VoidPointer> |
58 | struct unordered_node<VoidPointer, true, false> |
59 | : public slist_node<VoidPointer> |
60 | { |
61 | typedef typename pointer_traits |
62 | <VoidPointer>::template rebind_pointer |
63 | < unordered_node<VoidPointer, true, false> >::type |
64 | node_ptr; |
65 | std::size_t hash_; |
66 | }; |
67 | |
68 | template<class VoidPointer, bool StoreHash, bool OptimizeMultiKey> |
69 | struct unordered_node_traits |
70 | : public slist_node_traits<VoidPointer> |
71 | { |
72 | typedef slist_node_traits<VoidPointer> reduced_slist_node_traits; |
73 | typedef unordered_node<VoidPointer, StoreHash, OptimizeMultiKey> node; |
74 | |
75 | typedef typename pointer_traits |
76 | <VoidPointer>::template rebind_pointer |
77 | < node >::type node_ptr; |
78 | typedef typename pointer_traits |
79 | <VoidPointer>::template rebind_pointer |
80 | < const node >::type const_node_ptr; |
81 | |
82 | static const bool store_hash = StoreHash; |
83 | static const bool optimize_multikey = OptimizeMultiKey; |
84 | |
85 | static node_ptr get_next(const const_node_ptr & n) |
86 | { return pointer_traits<node_ptr>::static_cast_from(n->next_); } |
87 | |
88 | static void set_next(const node_ptr & n, const node_ptr & next) |
89 | { n->next_ = next; } |
90 | |
91 | static node_ptr get_prev_in_group(const const_node_ptr & n) |
92 | { return n->prev_in_group_; } |
93 | |
94 | static void set_prev_in_group(const node_ptr & n, const node_ptr & prev) |
95 | { n->prev_in_group_ = prev; } |
96 | |
97 | static std::size_t get_hash(const const_node_ptr & n) |
98 | { return n->hash_; } |
99 | |
100 | static void set_hash(const node_ptr & n, std::size_t h) |
101 | { n->hash_ = h; } |
102 | }; |
103 | |
104 | template<class NodeTraits> |
105 | struct unordered_group_adapter |
106 | { |
107 | typedef typename NodeTraits::node node; |
108 | typedef typename NodeTraits::node_ptr node_ptr; |
109 | typedef typename NodeTraits::const_node_ptr const_node_ptr; |
110 | |
111 | static node_ptr get_next(const const_node_ptr & n) |
112 | { return NodeTraits::get_prev_in_group(n); } |
113 | |
114 | static void set_next(const node_ptr & n, const node_ptr & next) |
115 | { NodeTraits::set_prev_in_group(n, next); } |
116 | }; |
117 | |
118 | template<class NodeTraits> |
119 | struct unordered_algorithms |
120 | : public circular_slist_algorithms<NodeTraits> |
121 | { |
122 | typedef circular_slist_algorithms<NodeTraits> base_type; |
123 | typedef unordered_group_adapter<NodeTraits> group_traits; |
124 | typedef circular_slist_algorithms<group_traits> group_algorithms; |
125 | typedef NodeTraits node_traits; |
126 | typedef typename NodeTraits::node node; |
127 | typedef typename NodeTraits::node_ptr node_ptr; |
128 | typedef typename NodeTraits::const_node_ptr const_node_ptr; |
129 | |
130 | static void init(typename base_type::node_ptr n) |
131 | { |
132 | base_type::init(n); |
133 | group_algorithms::init(n); |
134 | } |
135 | |
136 | static void (typename base_type::node_ptr n) |
137 | { |
138 | base_type::init_header(n); |
139 | group_algorithms::init_header(n); |
140 | } |
141 | |
142 | static void unlink(typename base_type::node_ptr n) |
143 | { |
144 | base_type::unlink(n); |
145 | group_algorithms::unlink(n); |
146 | } |
147 | }; |
148 | |
149 | //Class to avoid defining the same algo as a circular list, as hooks would be ambiguous between them |
150 | template<class Algo> |
151 | struct uset_algo_wrapper : public Algo |
152 | {}; |
153 | |
154 | template<class VoidPointer, bool StoreHash, bool OptimizeMultiKey> |
155 | struct get_uset_node_algo |
156 | { |
157 | typedef typename detail::if_c |
158 | < (StoreHash || OptimizeMultiKey) |
159 | , unordered_node_traits<VoidPointer, StoreHash, OptimizeMultiKey> |
160 | , slist_node_traits<VoidPointer> |
161 | >::type node_traits_type; |
162 | typedef typename detail::if_c |
163 | < OptimizeMultiKey |
164 | , unordered_algorithms<node_traits_type> |
165 | , uset_algo_wrapper< circular_slist_algorithms<node_traits_type> > |
166 | >::type type; |
167 | }; |
168 | /// @endcond |
169 | |
170 | //! Helper metafunction to define a \c unordered_set_base_hook that yields to the same |
171 | //! type when the same options (either explicitly or implicitly) are used. |
172 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
173 | template<class ...Options> |
174 | #else |
175 | template<class O1 = void, class O2 = void, class O3 = void, class O4 = void> |
176 | #endif |
177 | struct make_unordered_set_base_hook |
178 | { |
179 | /// @cond |
180 | typedef typename pack_options |
181 | < hook_defaults, |
182 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
183 | O1, O2, O3, O4 |
184 | #else |
185 | Options... |
186 | #endif |
187 | >::type packed_options; |
188 | |
189 | typedef generic_hook |
190 | < typename get_uset_node_algo < typename packed_options::void_pointer |
191 | , packed_options::store_hash |
192 | , packed_options::optimize_multikey |
193 | >::type |
194 | , typename packed_options::tag |
195 | , packed_options::link_mode |
196 | , HashBaseHookId |
197 | > implementation_defined; |
198 | /// @endcond |
199 | typedef implementation_defined type; |
200 | }; |
201 | |
202 | //! Derive a class from unordered_set_base_hook in order to store objects in |
203 | //! in an unordered_set/unordered_multi_set. unordered_set_base_hook holds the data necessary to maintain |
204 | //! the unordered_set/unordered_multi_set and provides an appropriate value_traits class for unordered_set/unordered_multi_set. |
205 | //! |
206 | //! The hook admits the following options: \c tag<>, \c void_pointer<>, |
207 | //! \c link_mode<>, \c store_hash<> and \c optimize_multikey<>. |
208 | //! |
209 | //! \c tag<> defines a tag to identify the node. |
210 | //! The same tag value can be used in different classes, but if a class is |
211 | //! derived from more than one \c list_base_hook, then each \c list_base_hook needs its |
212 | //! unique tag. |
213 | //! |
214 | //! \c void_pointer<> is the pointer type that will be used internally in the hook |
215 | //! and the container configured to use this hook. |
216 | //! |
217 | //! \c link_mode<> will specify the linking mode of the hook (\c normal_link, |
218 | //! \c auto_unlink or \c safe_link). |
219 | //! |
220 | //! \c store_hash<> will tell the hook to store the hash of the value |
221 | //! to speed up rehashings. |
222 | //! |
223 | //! \c optimize_multikey<> will tell the hook to store a link to form a group |
224 | //! with other value with the same value to speed up searches and insertions |
225 | //! in unordered_multisets with a great number of with equivalent keys. |
226 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
227 | template<class ...Options> |
228 | #else |
229 | template<class O1, class O2, class O3, class O4> |
230 | #endif |
231 | class unordered_set_base_hook |
232 | : public make_unordered_set_base_hook< |
233 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
234 | O1, O2, O3, O4 |
235 | #else |
236 | Options... |
237 | #endif |
238 | >::type |
239 | { |
240 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
241 | public: |
242 | //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link |
243 | //! initializes the node to an unlinked state. |
244 | //! |
245 | //! <b>Throws</b>: Nothing. |
246 | unordered_set_base_hook(); |
247 | |
248 | //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link |
249 | //! initializes the node to an unlinked state. The argument is ignored. |
250 | //! |
251 | //! <b>Throws</b>: Nothing. |
252 | //! |
253 | //! <b>Rationale</b>: Providing a copy-constructor |
254 | //! makes classes using the hook STL-compliant without forcing the |
255 | //! user to do some additional work. \c swap can be used to emulate |
256 | //! move-semantics. |
257 | unordered_set_base_hook(const unordered_set_base_hook& ); |
258 | |
259 | //! <b>Effects</b>: Empty function. The argument is ignored. |
260 | //! |
261 | //! <b>Throws</b>: Nothing. |
262 | //! |
263 | //! <b>Rationale</b>: Providing an assignment operator |
264 | //! makes classes using the hook STL-compliant without forcing the |
265 | //! user to do some additional work. \c swap can be used to emulate |
266 | //! move-semantics. |
267 | unordered_set_base_hook& operator=(const unordered_set_base_hook& ); |
268 | |
269 | //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does |
270 | //! nothing (ie. no code is generated). If link_mode is \c safe_link and the |
271 | //! object is stored in an unordered_set an assertion is raised. If link_mode is |
272 | //! \c auto_unlink and \c is_linked() is true, the node is unlinked. |
273 | //! |
274 | //! <b>Throws</b>: Nothing. |
275 | ~unordered_set_base_hook(); |
276 | |
277 | //! <b>Effects</b>: Swapping two nodes swaps the position of the elements |
278 | //! related to those nodes in one or two containers. That is, if the node |
279 | //! this is part of the element e1, the node x is part of the element e2 |
280 | //! and both elements are included in the containers s1 and s2, then after |
281 | //! the swap-operation e1 is in s2 at the position of e2 and e2 is in s1 |
282 | //! at the position of e1. If one element is not in a container, then |
283 | //! after the swap-operation the other element is not in a container. |
284 | //! Iterators to e1 and e2 related to those nodes are invalidated. |
285 | //! |
286 | //! <b>Complexity</b>: Constant |
287 | //! |
288 | //! <b>Throws</b>: Nothing. |
289 | void swap_nodes(unordered_set_base_hook &other); |
290 | |
291 | //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink. |
292 | //! |
293 | //! <b>Returns</b>: true, if the node belongs to a container, false |
294 | //! otherwise. This function can be used to test whether \c unordered_set::iterator_to |
295 | //! will return a valid iterator. |
296 | //! |
297 | //! <b>Complexity</b>: Constant |
298 | bool is_linked() const; |
299 | |
300 | //! <b>Effects</b>: Removes the node if it's inserted in a container. |
301 | //! This function is only allowed if link_mode is \c auto_unlink. |
302 | //! |
303 | //! <b>Throws</b>: Nothing. |
304 | void unlink(); |
305 | #endif |
306 | }; |
307 | |
308 | |
309 | //! Helper metafunction to define a \c unordered_set_member_hook that yields to the same |
310 | //! type when the same options (either explicitly or implicitly) are used. |
311 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
312 | template<class ...Options> |
313 | #else |
314 | template<class O1 = void, class O2 = void, class O3 = void, class O4 = void> |
315 | #endif |
316 | struct make_unordered_set_member_hook |
317 | { |
318 | /// @cond |
319 | typedef typename pack_options |
320 | < hook_defaults, |
321 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
322 | O1, O2, O3, O4 |
323 | #else |
324 | Options... |
325 | #endif |
326 | >::type packed_options; |
327 | |
328 | typedef generic_hook |
329 | < typename get_uset_node_algo< typename packed_options::void_pointer |
330 | , packed_options::store_hash |
331 | , packed_options::optimize_multikey |
332 | >::type |
333 | , member_tag |
334 | , packed_options::link_mode |
335 | , NoBaseHookId |
336 | > implementation_defined; |
337 | /// @endcond |
338 | typedef implementation_defined type; |
339 | }; |
340 | |
341 | //! Put a public data member unordered_set_member_hook in order to store objects of this class in |
342 | //! an unordered_set/unordered_multi_set. unordered_set_member_hook holds the data necessary for maintaining the |
343 | //! unordered_set/unordered_multi_set and provides an appropriate value_traits class for unordered_set/unordered_multi_set. |
344 | //! |
345 | //! The hook admits the following options: \c void_pointer<>, |
346 | //! \c link_mode<> and \c store_hash<>. |
347 | //! |
348 | //! \c void_pointer<> is the pointer type that will be used internally in the hook |
349 | //! and the container configured to use this hook. |
350 | //! |
351 | //! \c link_mode<> will specify the linking mode of the hook (\c normal_link, |
352 | //! \c auto_unlink or \c safe_link). |
353 | //! |
354 | //! \c store_hash<> will tell the hook to store the hash of the value |
355 | //! to speed up rehashings. |
356 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
357 | template<class ...Options> |
358 | #else |
359 | template<class O1, class O2, class O3, class O4> |
360 | #endif |
361 | class unordered_set_member_hook |
362 | : public make_unordered_set_member_hook< |
363 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
364 | O1, O2, O3, O4 |
365 | #else |
366 | Options... |
367 | #endif |
368 | >::type |
369 | { |
370 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
371 | public: |
372 | //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link |
373 | //! initializes the node to an unlinked state. |
374 | //! |
375 | //! <b>Throws</b>: Nothing. |
376 | unordered_set_member_hook(); |
377 | |
378 | //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link |
379 | //! initializes the node to an unlinked state. The argument is ignored. |
380 | //! |
381 | //! <b>Throws</b>: Nothing. |
382 | //! |
383 | //! <b>Rationale</b>: Providing a copy-constructor |
384 | //! makes classes using the hook STL-compliant without forcing the |
385 | //! user to do some additional work. \c swap can be used to emulate |
386 | //! move-semantics. |
387 | unordered_set_member_hook(const unordered_set_member_hook& ); |
388 | |
389 | //! <b>Effects</b>: Empty function. The argument is ignored. |
390 | //! |
391 | //! <b>Throws</b>: Nothing. |
392 | //! |
393 | //! <b>Rationale</b>: Providing an assignment operator |
394 | //! makes classes using the hook STL-compliant without forcing the |
395 | //! user to do some additional work. \c swap can be used to emulate |
396 | //! move-semantics. |
397 | unordered_set_member_hook& operator=(const unordered_set_member_hook& ); |
398 | |
399 | //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does |
400 | //! nothing (ie. no code is generated). If link_mode is \c safe_link and the |
401 | //! object is stored in an unordered_set an assertion is raised. If link_mode is |
402 | //! \c auto_unlink and \c is_linked() is true, the node is unlinked. |
403 | //! |
404 | //! <b>Throws</b>: Nothing. |
405 | ~unordered_set_member_hook(); |
406 | |
407 | //! <b>Effects</b>: Swapping two nodes swaps the position of the elements |
408 | //! related to those nodes in one or two containers. That is, if the node |
409 | //! this is part of the element e1, the node x is part of the element e2 |
410 | //! and both elements are included in the containers s1 and s2, then after |
411 | //! the swap-operation e1 is in s2 at the position of e2 and e2 is in s1 |
412 | //! at the position of e1. If one element is not in a container, then |
413 | //! after the swap-operation the other element is not in a container. |
414 | //! Iterators to e1 and e2 related to those nodes are invalidated. |
415 | //! |
416 | //! <b>Complexity</b>: Constant |
417 | //! |
418 | //! <b>Throws</b>: Nothing. |
419 | void swap_nodes(unordered_set_member_hook &other); |
420 | |
421 | //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink. |
422 | //! |
423 | //! <b>Returns</b>: true, if the node belongs to a container, false |
424 | //! otherwise. This function can be used to test whether \c unordered_set::iterator_to |
425 | //! will return a valid iterator. |
426 | //! |
427 | //! <b>Complexity</b>: Constant |
428 | bool is_linked() const; |
429 | |
430 | //! <b>Effects</b>: Removes the node if it's inserted in a container. |
431 | //! This function is only allowed if link_mode is \c auto_unlink. |
432 | //! |
433 | //! <b>Throws</b>: Nothing. |
434 | void unlink(); |
435 | #endif |
436 | }; |
437 | |
438 | } //namespace intrusive |
439 | } //namespace boost |
440 | |
441 | #include <boost/intrusive/detail/config_end.hpp> |
442 | |
443 | #endif //BOOST_INTRUSIVE_UNORDERED_SET_HOOK_HPP |
444 | |