]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 init_header(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_traits | |
156 | { | |
157 | typedef typename detail::if_c | |
158 | < (StoreHash || OptimizeMultiKey) | |
159 | , unordered_node_traits<VoidPointer, StoreHash, OptimizeMultiKey> | |
160 | , slist_node_traits<VoidPointer> | |
161 | >::type type; | |
162 | }; | |
163 | ||
164 | template<bool OptimizeMultiKey> | |
165 | struct get_uset_algo_type | |
166 | { | |
167 | static const algo_types value = OptimizeMultiKey ? UnorderedAlgorithms : UnorderedCircularSlistAlgorithms; | |
168 | }; | |
169 | ||
170 | template<class NodeTraits> | |
171 | struct get_algo<UnorderedAlgorithms, NodeTraits> | |
172 | { | |
173 | typedef unordered_algorithms<NodeTraits> type; | |
174 | }; | |
175 | ||
176 | template<class NodeTraits> | |
177 | struct get_algo<UnorderedCircularSlistAlgorithms, NodeTraits> | |
178 | { | |
179 | typedef uset_algo_wrapper< circular_slist_algorithms<NodeTraits> > type; | |
180 | }; | |
181 | ||
182 | /// @endcond | |
183 | ||
184 | //! Helper metafunction to define a \c unordered_set_base_hook that yields to the same | |
185 | //! type when the same options (either explicitly or implicitly) are used. | |
186 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
187 | template<class ...Options> | |
188 | #else | |
189 | template<class O1 = void, class O2 = void, class O3 = void, class O4 = void> | |
190 | #endif | |
191 | struct make_unordered_set_base_hook | |
192 | { | |
193 | /// @cond | |
194 | typedef typename pack_options | |
195 | < hook_defaults, | |
196 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
197 | O1, O2, O3, O4 | |
198 | #else | |
199 | Options... | |
200 | #endif | |
201 | >::type packed_options; | |
202 | ||
203 | typedef generic_hook | |
204 | < get_uset_algo_type <packed_options::optimize_multikey>::value | |
205 | , typename get_uset_node_traits < typename packed_options::void_pointer | |
206 | , packed_options::store_hash | |
207 | , packed_options::optimize_multikey | |
208 | >::type | |
209 | , typename packed_options::tag | |
210 | , packed_options::link_mode | |
211 | , HashBaseHookId | |
212 | > implementation_defined; | |
213 | /// @endcond | |
214 | typedef implementation_defined type; | |
215 | }; | |
216 | ||
217 | //! Derive a class from unordered_set_base_hook in order to store objects in | |
218 | //! in an unordered_set/unordered_multi_set. unordered_set_base_hook holds the data necessary to maintain | |
219 | //! the unordered_set/unordered_multi_set and provides an appropriate value_traits class for unordered_set/unordered_multi_set. | |
220 | //! | |
221 | //! The hook admits the following options: \c tag<>, \c void_pointer<>, | |
222 | //! \c link_mode<>, \c store_hash<> and \c optimize_multikey<>. | |
223 | //! | |
224 | //! \c tag<> defines a tag to identify the node. | |
225 | //! The same tag value can be used in different classes, but if a class is | |
226 | //! derived from more than one \c list_base_hook, then each \c list_base_hook needs its | |
227 | //! unique tag. | |
228 | //! | |
229 | //! \c void_pointer<> is the pointer type that will be used internally in the hook | |
230 | //! and the container configured to use this hook. | |
231 | //! | |
232 | //! \c link_mode<> will specify the linking mode of the hook (\c normal_link, | |
233 | //! \c auto_unlink or \c safe_link). | |
234 | //! | |
235 | //! \c store_hash<> will tell the hook to store the hash of the value | |
236 | //! to speed up rehashings. | |
237 | //! | |
238 | //! \c optimize_multikey<> will tell the hook to store a link to form a group | |
239 | //! with other value with the same value to speed up searches and insertions | |
240 | //! in unordered_multisets with a great number of with equivalent keys. | |
241 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
242 | template<class ...Options> | |
243 | #else | |
244 | template<class O1, class O2, class O3, class O4> | |
245 | #endif | |
246 | class unordered_set_base_hook | |
247 | : public make_unordered_set_base_hook< | |
248 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
249 | O1, O2, O3, O4 | |
250 | #else | |
251 | Options... | |
252 | #endif | |
253 | >::type | |
254 | { | |
255 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
256 | public: | |
257 | //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link | |
258 | //! initializes the node to an unlinked state. | |
259 | //! | |
260 | //! <b>Throws</b>: Nothing. | |
261 | unordered_set_base_hook(); | |
262 | ||
263 | //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link | |
264 | //! initializes the node to an unlinked state. The argument is ignored. | |
265 | //! | |
266 | //! <b>Throws</b>: Nothing. | |
267 | //! | |
268 | //! <b>Rationale</b>: Providing a copy-constructor | |
269 | //! makes classes using the hook STL-compliant without forcing the | |
270 | //! user to do some additional work. \c swap can be used to emulate | |
271 | //! move-semantics. | |
272 | unordered_set_base_hook(const unordered_set_base_hook& ); | |
273 | ||
274 | //! <b>Effects</b>: Empty function. The argument is ignored. | |
275 | //! | |
276 | //! <b>Throws</b>: Nothing. | |
277 | //! | |
278 | //! <b>Rationale</b>: Providing an assignment operator | |
279 | //! makes classes using the hook STL-compliant without forcing the | |
280 | //! user to do some additional work. \c swap can be used to emulate | |
281 | //! move-semantics. | |
282 | unordered_set_base_hook& operator=(const unordered_set_base_hook& ); | |
283 | ||
284 | //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does | |
285 | //! nothing (ie. no code is generated). If link_mode is \c safe_link and the | |
286 | //! object is stored in an unordered_set an assertion is raised. If link_mode is | |
287 | //! \c auto_unlink and \c is_linked() is true, the node is unlinked. | |
288 | //! | |
289 | //! <b>Throws</b>: Nothing. | |
290 | ~unordered_set_base_hook(); | |
291 | ||
292 | //! <b>Effects</b>: Swapping two nodes swaps the position of the elements | |
293 | //! related to those nodes in one or two containers. That is, if the node | |
294 | //! this is part of the element e1, the node x is part of the element e2 | |
295 | //! and both elements are included in the containers s1 and s2, then after | |
296 | //! the swap-operation e1 is in s2 at the position of e2 and e2 is in s1 | |
297 | //! at the position of e1. If one element is not in a container, then | |
298 | //! after the swap-operation the other element is not in a container. | |
299 | //! Iterators to e1 and e2 related to those nodes are invalidated. | |
300 | //! | |
301 | //! <b>Complexity</b>: Constant | |
302 | //! | |
303 | //! <b>Throws</b>: Nothing. | |
304 | void swap_nodes(unordered_set_base_hook &other); | |
305 | ||
306 | //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink. | |
307 | //! | |
308 | //! <b>Returns</b>: true, if the node belongs to a container, false | |
309 | //! otherwise. This function can be used to test whether \c unordered_set::iterator_to | |
310 | //! will return a valid iterator. | |
311 | //! | |
312 | //! <b>Complexity</b>: Constant | |
313 | bool is_linked() const; | |
314 | ||
315 | //! <b>Effects</b>: Removes the node if it's inserted in a container. | |
316 | //! This function is only allowed if link_mode is \c auto_unlink. | |
317 | //! | |
318 | //! <b>Throws</b>: Nothing. | |
319 | void unlink(); | |
320 | #endif | |
321 | }; | |
322 | ||
323 | ||
324 | //! Helper metafunction to define a \c unordered_set_member_hook that yields to the same | |
325 | //! type when the same options (either explicitly or implicitly) are used. | |
326 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
327 | template<class ...Options> | |
328 | #else | |
329 | template<class O1 = void, class O2 = void, class O3 = void, class O4 = void> | |
330 | #endif | |
331 | struct make_unordered_set_member_hook | |
332 | { | |
333 | /// @cond | |
334 | typedef typename pack_options | |
335 | < hook_defaults, | |
336 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
337 | O1, O2, O3, O4 | |
338 | #else | |
339 | Options... | |
340 | #endif | |
341 | >::type packed_options; | |
342 | ||
343 | typedef generic_hook | |
344 | < get_uset_algo_type <packed_options::optimize_multikey>::value | |
345 | , typename get_uset_node_traits < typename packed_options::void_pointer | |
346 | , packed_options::store_hash | |
347 | , packed_options::optimize_multikey | |
348 | >::type | |
349 | , member_tag | |
350 | , packed_options::link_mode | |
351 | , NoBaseHookId | |
352 | > implementation_defined; | |
353 | /// @endcond | |
354 | typedef implementation_defined type; | |
355 | }; | |
356 | ||
357 | //! Put a public data member unordered_set_member_hook in order to store objects of this class in | |
358 | //! an unordered_set/unordered_multi_set. unordered_set_member_hook holds the data necessary for maintaining the | |
359 | //! unordered_set/unordered_multi_set and provides an appropriate value_traits class for unordered_set/unordered_multi_set. | |
360 | //! | |
361 | //! The hook admits the following options: \c void_pointer<>, | |
362 | //! \c link_mode<> and \c store_hash<>. | |
363 | //! | |
364 | //! \c void_pointer<> is the pointer type that will be used internally in the hook | |
365 | //! and the container configured to use this hook. | |
366 | //! | |
367 | //! \c link_mode<> will specify the linking mode of the hook (\c normal_link, | |
368 | //! \c auto_unlink or \c safe_link). | |
369 | //! | |
370 | //! \c store_hash<> will tell the hook to store the hash of the value | |
371 | //! to speed up rehashings. | |
372 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
373 | template<class ...Options> | |
374 | #else | |
375 | template<class O1, class O2, class O3, class O4> | |
376 | #endif | |
377 | class unordered_set_member_hook | |
378 | : public make_unordered_set_member_hook< | |
379 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
380 | O1, O2, O3, O4 | |
381 | #else | |
382 | Options... | |
383 | #endif | |
384 | >::type | |
385 | { | |
386 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
387 | public: | |
388 | //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link | |
389 | //! initializes the node to an unlinked state. | |
390 | //! | |
391 | //! <b>Throws</b>: Nothing. | |
392 | unordered_set_member_hook(); | |
393 | ||
394 | //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link | |
395 | //! initializes the node to an unlinked state. The argument is ignored. | |
396 | //! | |
397 | //! <b>Throws</b>: Nothing. | |
398 | //! | |
399 | //! <b>Rationale</b>: Providing a copy-constructor | |
400 | //! makes classes using the hook STL-compliant without forcing the | |
401 | //! user to do some additional work. \c swap can be used to emulate | |
402 | //! move-semantics. | |
403 | unordered_set_member_hook(const unordered_set_member_hook& ); | |
404 | ||
405 | //! <b>Effects</b>: Empty function. The argument is ignored. | |
406 | //! | |
407 | //! <b>Throws</b>: Nothing. | |
408 | //! | |
409 | //! <b>Rationale</b>: Providing an assignment operator | |
410 | //! makes classes using the hook STL-compliant without forcing the | |
411 | //! user to do some additional work. \c swap can be used to emulate | |
412 | //! move-semantics. | |
413 | unordered_set_member_hook& operator=(const unordered_set_member_hook& ); | |
414 | ||
415 | //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does | |
416 | //! nothing (ie. no code is generated). If link_mode is \c safe_link and the | |
417 | //! object is stored in an unordered_set an assertion is raised. If link_mode is | |
418 | //! \c auto_unlink and \c is_linked() is true, the node is unlinked. | |
419 | //! | |
420 | //! <b>Throws</b>: Nothing. | |
421 | ~unordered_set_member_hook(); | |
422 | ||
423 | //! <b>Effects</b>: Swapping two nodes swaps the position of the elements | |
424 | //! related to those nodes in one or two containers. That is, if the node | |
425 | //! this is part of the element e1, the node x is part of the element e2 | |
426 | //! and both elements are included in the containers s1 and s2, then after | |
427 | //! the swap-operation e1 is in s2 at the position of e2 and e2 is in s1 | |
428 | //! at the position of e1. If one element is not in a container, then | |
429 | //! after the swap-operation the other element is not in a container. | |
430 | //! Iterators to e1 and e2 related to those nodes are invalidated. | |
431 | //! | |
432 | //! <b>Complexity</b>: Constant | |
433 | //! | |
434 | //! <b>Throws</b>: Nothing. | |
435 | void swap_nodes(unordered_set_member_hook &other); | |
436 | ||
437 | //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink. | |
438 | //! | |
439 | //! <b>Returns</b>: true, if the node belongs to a container, false | |
440 | //! otherwise. This function can be used to test whether \c unordered_set::iterator_to | |
441 | //! will return a valid iterator. | |
442 | //! | |
443 | //! <b>Complexity</b>: Constant | |
444 | bool is_linked() const; | |
445 | ||
446 | //! <b>Effects</b>: Removes the node if it's inserted in a container. | |
447 | //! This function is only allowed if link_mode is \c auto_unlink. | |
448 | //! | |
449 | //! <b>Throws</b>: Nothing. | |
450 | void unlink(); | |
451 | #endif | |
452 | }; | |
453 | ||
454 | } //namespace intrusive | |
455 | } //namespace boost | |
456 | ||
457 | #include <boost/intrusive/detail/config_end.hpp> | |
458 | ||
459 | #endif //BOOST_INTRUSIVE_UNORDERED_SET_HOOK_HPP |