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_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)
173template<class ...Options>
174#else
175template<class O1 = void, class O2 = void, class O3 = void, class O4 = void>
176#endif
177struct 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)
227template<class ...Options>
228#else
229template<class O1, class O2, class O3, class O4>
230#endif
231class 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)
312template<class ...Options>
313#else
314template<class O1 = void, class O2 = void, class O3 = void, class O4 = void>
315#endif
316struct 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)
357template<class ...Options>
358#else
359template<class O1, class O2, class O3, class O4>
360#endif
361class 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

source code of boost/boost/intrusive/unordered_set_hook.hpp