]>
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_SET_HOOK_HPP | |
15 | #define BOOST_INTRUSIVE_SET_HOOK_HPP | |
16 | ||
17 | #include <boost/intrusive/detail/config_begin.hpp> | |
18 | #include <boost/intrusive/intrusive_fwd.hpp> | |
19 | ||
20 | #include <boost/intrusive/detail/rbtree_node.hpp> | |
21 | #include <boost/intrusive/rbtree_algorithms.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 | //! Helper metafunction to define a \c set_base_hook that yields to the same | |
33 | //! type when the same options (either explicitly or implicitly) are used. | |
34 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
35 | template<class ...Options> | |
36 | #else | |
37 | template<class O1 = void, class O2 = void, class O3 = void, class O4 = void> | |
38 | #endif | |
39 | struct make_set_base_hook | |
40 | { | |
41 | /// @cond | |
42 | typedef typename pack_options | |
43 | < hook_defaults, | |
44 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
45 | O1, O2, O3, O4 | |
46 | #else | |
47 | Options... | |
48 | #endif | |
49 | >::type packed_options; | |
50 | ||
51 | typedef generic_hook | |
52 | < RbTreeAlgorithms | |
53 | , rbtree_node_traits<typename packed_options::void_pointer, packed_options::optimize_size> | |
54 | , typename packed_options::tag | |
55 | , packed_options::link_mode | |
56 | , RbTreeBaseHookId | |
57 | > implementation_defined; | |
58 | /// @endcond | |
59 | typedef implementation_defined type; | |
60 | }; | |
61 | ||
62 | //! Derive a class from set_base_hook in order to store objects in | |
63 | //! in a set/multiset. set_base_hook holds the data necessary to maintain | |
64 | //! the set/multiset and provides an appropriate value_traits class for set/multiset. | |
65 | //! | |
66 | //! The hook admits the following options: \c tag<>, \c void_pointer<>, | |
67 | //! \c link_mode<> and \c optimize_size<>. | |
68 | //! | |
69 | //! \c tag<> defines a tag to identify the node. | |
70 | //! The same tag value can be used in different classes, but if a class is | |
71 | //! derived from more than one \c list_base_hook, then each \c list_base_hook needs its | |
72 | //! unique tag. | |
73 | //! | |
74 | //! \c void_pointer<> is the pointer type that will be used internally in the hook | |
75 | //! and the container configured to use this hook. | |
76 | //! | |
77 | //! \c link_mode<> will specify the linking mode of the hook (\c normal_link, | |
78 | //! \c auto_unlink or \c safe_link). | |
79 | //! | |
80 | //! \c optimize_size<> will tell the hook to optimize the hook for size instead | |
81 | //! of speed. | |
82 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
83 | template<class ...Options> | |
84 | #else | |
85 | template<class O1, class O2, class O3, class O4> | |
86 | #endif | |
87 | class set_base_hook | |
88 | : public make_set_base_hook< | |
89 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
90 | O1, O2, O3, O4 | |
91 | #else | |
92 | Options... | |
93 | #endif | |
94 | >::type | |
95 | { | |
96 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
97 | public: | |
98 | //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link | |
99 | //! initializes the node to an unlinked state. | |
100 | //! | |
101 | //! <b>Throws</b>: Nothing. | |
102 | set_base_hook(); | |
103 | ||
104 | //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link | |
105 | //! initializes the node to an unlinked state. The argument is ignored. | |
106 | //! | |
107 | //! <b>Throws</b>: Nothing. | |
108 | //! | |
109 | //! <b>Rationale</b>: Providing a copy-constructor | |
110 | //! makes classes using the hook STL-compliant without forcing the | |
111 | //! user to do some additional work. \c swap can be used to emulate | |
112 | //! move-semantics. | |
113 | set_base_hook(const set_base_hook& ); | |
114 | ||
115 | //! <b>Effects</b>: Empty function. The argument is ignored. | |
116 | //! | |
117 | //! <b>Throws</b>: Nothing. | |
118 | //! | |
119 | //! <b>Rationale</b>: Providing an assignment operator | |
120 | //! makes classes using the hook STL-compliant without forcing the | |
121 | //! user to do some additional work. \c swap can be used to emulate | |
122 | //! move-semantics. | |
123 | set_base_hook& operator=(const set_base_hook& ); | |
124 | ||
125 | //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does | |
126 | //! nothing (ie. no code is generated). If link_mode is \c safe_link and the | |
127 | //! object is stored in a set an assertion is raised. If link_mode is | |
128 | //! \c auto_unlink and \c is_linked() is true, the node is unlinked. | |
129 | //! | |
130 | //! <b>Throws</b>: Nothing. | |
131 | ~set_base_hook(); | |
132 | ||
133 | //! <b>Effects</b>: Swapping two nodes swaps the position of the elements | |
134 | //! related to those nodes in one or two containers. That is, if the node | |
135 | //! this is part of the element e1, the node x is part of the element e2 | |
136 | //! and both elements are included in the containers s1 and s2, then after | |
137 | //! the swap-operation e1 is in s2 at the position of e2 and e2 is in s1 | |
138 | //! at the position of e1. If one element is not in a container, then | |
139 | //! after the swap-operation the other element is not in a container. | |
140 | //! Iterators to e1 and e2 related to those nodes are invalidated. | |
141 | //! | |
142 | //! <b>Complexity</b>: Constant | |
143 | //! | |
144 | //! <b>Throws</b>: Nothing. | |
145 | void swap_nodes(set_base_hook &other); | |
146 | ||
147 | //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink. | |
148 | //! | |
149 | //! <b>Returns</b>: true, if the node belongs to a container, false | |
150 | //! otherwise. This function can be used to test whether \c set::iterator_to | |
151 | //! will return a valid iterator. | |
152 | //! | |
153 | //! <b>Complexity</b>: Constant | |
154 | bool is_linked() const; | |
155 | ||
156 | //! <b>Effects</b>: Removes the node if it's inserted in a container. | |
157 | //! This function is only allowed if link_mode is \c auto_unlink. | |
158 | //! | |
159 | //! <b>Throws</b>: Nothing. | |
160 | void unlink(); | |
161 | #endif | |
162 | }; | |
163 | ||
164 | //! Helper metafunction to define a \c set_member_hook that yields to the same | |
165 | //! type when the same options (either explicitly or implicitly) are used. | |
166 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
167 | template<class ...Options> | |
168 | #else | |
169 | template<class O1 = void, class O2 = void, class O3 = void, class O4 = void> | |
170 | #endif | |
171 | struct make_set_member_hook | |
172 | { | |
173 | /// @cond | |
174 | typedef typename pack_options | |
175 | < hook_defaults, | |
176 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
177 | O1, O2, O3, O4 | |
178 | #else | |
179 | Options... | |
180 | #endif | |
181 | >::type packed_options; | |
182 | ||
183 | typedef generic_hook | |
184 | < RbTreeAlgorithms | |
185 | , rbtree_node_traits<typename packed_options::void_pointer, packed_options::optimize_size> | |
186 | , member_tag | |
187 | , packed_options::link_mode | |
188 | , NoBaseHookId | |
189 | > implementation_defined; | |
190 | /// @endcond | |
191 | typedef implementation_defined type; | |
192 | }; | |
193 | ||
194 | //! Put a public data member set_member_hook in order to store objects of this class in | |
195 | //! a set/multiset. set_member_hook holds the data necessary for maintaining the | |
196 | //! set/multiset and provides an appropriate value_traits class for set/multiset. | |
197 | //! | |
198 | //! The hook admits the following options: \c void_pointer<>, | |
199 | //! \c link_mode<> and \c optimize_size<>. | |
200 | //! | |
201 | //! \c void_pointer<> is the pointer type that will be used internally in the hook | |
202 | //! and the container configured to use this hook. | |
203 | //! | |
204 | //! \c link_mode<> will specify the linking mode of the hook (\c normal_link, | |
205 | //! \c auto_unlink or \c safe_link). | |
206 | //! | |
207 | //! \c optimize_size<> will tell the hook to optimize the hook for size instead | |
208 | //! of speed. | |
209 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
210 | template<class ...Options> | |
211 | #else | |
212 | template<class O1, class O2, class O3, class O4> | |
213 | #endif | |
214 | class set_member_hook | |
215 | : public make_set_member_hook< | |
216 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
217 | O1, O2, O3, O4 | |
218 | #else | |
219 | Options... | |
220 | #endif | |
221 | >::type | |
222 | { | |
223 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
224 | public: | |
225 | //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link | |
226 | //! initializes the node to an unlinked state. | |
227 | //! | |
228 | //! <b>Throws</b>: Nothing. | |
229 | set_member_hook(); | |
230 | ||
231 | //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link | |
232 | //! initializes the node to an unlinked state. The argument is ignored. | |
233 | //! | |
234 | //! <b>Throws</b>: Nothing. | |
235 | //! | |
236 | //! <b>Rationale</b>: Providing a copy-constructor | |
237 | //! makes classes using the hook STL-compliant without forcing the | |
238 | //! user to do some additional work. \c swap can be used to emulate | |
239 | //! move-semantics. | |
240 | set_member_hook(const set_member_hook& ); | |
241 | ||
242 | //! <b>Effects</b>: Empty function. The argument is ignored. | |
243 | //! | |
244 | //! <b>Throws</b>: Nothing. | |
245 | //! | |
246 | //! <b>Rationale</b>: Providing an assignment operator | |
247 | //! makes classes using the hook STL-compliant without forcing the | |
248 | //! user to do some additional work. \c swap can be used to emulate | |
249 | //! move-semantics. | |
250 | set_member_hook& operator=(const set_member_hook& ); | |
251 | ||
252 | //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does | |
253 | //! nothing (ie. no code is generated). If link_mode is \c safe_link and the | |
254 | //! object is stored in a set an assertion is raised. If link_mode is | |
255 | //! \c auto_unlink and \c is_linked() is true, the node is unlinked. | |
256 | //! | |
257 | //! <b>Throws</b>: Nothing. | |
258 | ~set_member_hook(); | |
259 | ||
260 | //! <b>Effects</b>: Swapping two nodes swaps the position of the elements | |
261 | //! related to those nodes in one or two containers. That is, if the node | |
262 | //! this is part of the element e1, the node x is part of the element e2 | |
263 | //! and both elements are included in the containers s1 and s2, then after | |
264 | //! the swap-operation e1 is in s2 at the position of e2 and e2 is in s1 | |
265 | //! at the position of e1. If one element is not in a container, then | |
266 | //! after the swap-operation the other element is not in a container. | |
267 | //! Iterators to e1 and e2 related to those nodes are invalidated. | |
268 | //! | |
269 | //! <b>Complexity</b>: Constant | |
270 | //! | |
271 | //! <b>Throws</b>: Nothing. | |
272 | void swap_nodes(set_member_hook &other); | |
273 | ||
274 | //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink. | |
275 | //! | |
276 | //! <b>Returns</b>: true, if the node belongs to a container, false | |
277 | //! otherwise. This function can be used to test whether \c set::iterator_to | |
278 | //! will return a valid iterator. | |
279 | //! | |
280 | //! <b>Complexity</b>: Constant | |
281 | bool is_linked() const; | |
282 | ||
283 | //! <b>Effects</b>: Removes the node if it's inserted in a container. | |
284 | //! This function is only allowed if link_mode is \c auto_unlink. | |
285 | //! | |
286 | //! <b>Throws</b>: Nothing. | |
287 | void unlink(); | |
288 | #endif | |
289 | }; | |
290 | ||
291 | } //namespace intrusive | |
292 | } //namespace boost | |
293 | ||
294 | #include <boost/intrusive/detail/config_end.hpp> | |
295 | ||
296 | #endif //BOOST_INTRUSIVE_SET_HOOK_HPP |