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
29namespace boost {
30namespace intrusive {
31
32/// @cond
33
34template<class VoidPointer, bool StoreHash, bool OptimizeMultiKey>
35struct 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
46template<class VoidPointer>
47struct 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
57template<class VoidPointer>
58struct 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
68template<class VoidPointer, bool StoreHash, bool OptimizeMultiKey>
69struct 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
104template<class NodeTraits>
105struct 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
118template<class NodeTraits>
119struct 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
150template<class Algo>
151struct uset_algo_wrapper : public Algo
152{};
153
154template<class VoidPointer, bool StoreHash, bool OptimizeMultiKey>
155struct 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
164template<bool OptimizeMultiKey>
165struct get_uset_algo_type
166{
167 static const algo_types value = OptimizeMultiKey ? UnorderedAlgorithms : UnorderedCircularSlistAlgorithms;
168};
169
170template<class NodeTraits>
171struct get_algo<UnorderedAlgorithms, NodeTraits>
172{
173 typedef unordered_algorithms<NodeTraits> type;
174};
175
176template<class NodeTraits>
177struct 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)
187template<class ...Options>
188#else
189template<class O1 = void, class O2 = void, class O3 = void, class O4 = void>
190#endif
191struct 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)
242template<class ...Options>
243#else
244template<class O1, class O2, class O3, class O4>
245#endif
246class 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)
327template<class ...Options>
328#else
329template<class O1 = void, class O2 = void, class O3 = void, class O4 = void>
330#endif
331struct 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)
373template<class ...Options>
374#else
375template<class O1, class O2, class O3, class O4>
376#endif
377class 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
460