1 /////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2007-2013
4 //
5 // Distributed under the Boost Software License, Version 1.0.
6 // (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //
9 // See http://www.boost.org/libs/intrusive for documentation.
10 //
11 /////////////////////////////////////////////////////////////////////////////
12
13 #ifndef BOOST_INTRUSIVE_GENERIC_HOOK_HPP
14 #define BOOST_INTRUSIVE_GENERIC_HOOK_HPP
15
16 #ifndef BOOST_CONFIG_HPP
17 # include <boost/config.hpp>
18 #endif
19
20 #if defined(BOOST_HAS_PRAGMA_ONCE)
21 # pragma once
22 #endif
23
24 #include <boost/intrusive/pointer_traits.hpp>
25 #include <boost/intrusive/link_mode.hpp>
26 #include <boost/intrusive/detail/mpl.hpp>
27 #include <boost/intrusive/detail/assert.hpp>
28 #include <boost/intrusive/detail/node_holder.hpp>
29 #include <boost/intrusive/detail/algo_type.hpp>
30 #include <boost/static_assert.hpp>
31
32 namespace boost {
33 namespace intrusive {
34
35 /// @cond
36
37 namespace detail {
38
39 template <link_mode_type LinkMode>
40 struct link_dispatch
41 {};
42
43 template<class Hook>
destructor_impl(Hook & hook,detail::link_dispatch<safe_link>)44 void destructor_impl(Hook &hook, detail::link_dispatch<safe_link>)
45 { //If this assertion raises, you might have destroyed an object
46 //while it was still inserted in a container that is alive.
47 //If so, remove the object from the container before destroying it.
48 (void)hook; BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT(!hook.is_linked());
49 }
50
51 template<class Hook>
destructor_impl(Hook & hook,detail::link_dispatch<auto_unlink>)52 void destructor_impl(Hook &hook, detail::link_dispatch<auto_unlink>)
53 { hook.unlink(); }
54
55 template<class Hook>
destructor_impl(Hook &,detail::link_dispatch<normal_link>)56 void destructor_impl(Hook &, detail::link_dispatch<normal_link>)
57 {}
58
59 } //namespace detail {
60
61 enum base_hook_type
62 { NoBaseHookId
63 , ListBaseHookId
64 , SlistBaseHookId
65 , RbTreeBaseHookId
66 , HashBaseHookId
67 , AvlTreeBaseHookId
68 , BsTreeBaseHookId
69 , TreapTreeBaseHookId
70 , AnyBaseHookId
71 };
72
73
74 template <class HookTags, unsigned int>
75 struct hook_tags_definer{};
76
77 template <class HookTags>
78 struct hook_tags_definer<HookTags, ListBaseHookId>
79 { typedef HookTags default_list_hook; };
80
81 template <class HookTags>
82 struct hook_tags_definer<HookTags, SlistBaseHookId>
83 { typedef HookTags default_slist_hook; };
84
85 template <class HookTags>
86 struct hook_tags_definer<HookTags, RbTreeBaseHookId>
87 { typedef HookTags default_rbtree_hook; };
88
89 template <class HookTags>
90 struct hook_tags_definer<HookTags, HashBaseHookId>
91 { typedef HookTags default_hashtable_hook; };
92
93 template <class HookTags>
94 struct hook_tags_definer<HookTags, AvlTreeBaseHookId>
95 { typedef HookTags default_avltree_hook; };
96
97 template <class HookTags>
98 struct hook_tags_definer<HookTags, BsTreeBaseHookId>
99 { typedef HookTags default_bstree_hook; };
100
101 template <class HookTags>
102 struct hook_tags_definer<HookTags, AnyBaseHookId>
103 { typedef HookTags default_any_hook; };
104
105 template
106 < class NodeTraits
107 , class Tag
108 , link_mode_type LinkMode
109 , base_hook_type BaseHookType
110 >
111 struct hooktags_impl
112 {
113 static const link_mode_type link_mode = LinkMode;
114 typedef Tag tag;
115 typedef NodeTraits node_traits;
116 static const bool is_base_hook = !detail::is_same<Tag, member_tag>::value;
117 static const bool safemode_or_autounlink = is_safe_autounlink<link_mode>::value;
118 static const unsigned int type = BaseHookType;
119 };
120
121 /// @endcond
122
123 template
124 < boost::intrusive::algo_types Algo
125 , class NodeTraits
126 , class Tag
127 , link_mode_type LinkMode
128 , base_hook_type BaseHookType
129 >
130 class generic_hook
131 /// @cond
132 //If the hook is a base hook, derive generic hook from node_holder
133 //so that a unique base class is created to convert from the node
134 //to the type. This mechanism will be used by bhtraits.
135 //
136 //If the hook is a member hook, generic hook will directly derive
137 //from the hook.
138 : public detail::if_c
139 < detail::is_same<Tag, member_tag>::value
140 , typename NodeTraits::node
141 , node_holder<typename NodeTraits::node, Tag, BaseHookType>
142 >::type
143 //If this is the a default-tagged base hook derive from a class that
144 //will define an special internal typedef. Containers will be able to detect this
145 //special typedef and obtain generic_hook's internal types in order to deduce
146 //value_traits for this hook.
147 , public hook_tags_definer
148 < generic_hook<Algo, NodeTraits, Tag, LinkMode, BaseHookType>
149 , detail::is_same<Tag, dft_tag>::value ? BaseHookType : NoBaseHookId>
150 /// @endcond
151 {
152 /// @cond
153 typedef typename get_algo<Algo, NodeTraits>::type node_algorithms;
154 typedef typename node_algorithms::node node;
155 typedef typename node_algorithms::node_ptr node_ptr;
156 typedef typename node_algorithms::const_node_ptr const_node_ptr;
157
158 public:
159
160 typedef hooktags_impl
161 < NodeTraits
162 , Tag, LinkMode, BaseHookType> hooktags;
163
this_ptr()164 node_ptr this_ptr()
165 { return pointer_traits<node_ptr>::pointer_to(static_cast<node&>(*this)); }
166
this_ptr() const167 const_node_ptr this_ptr() const
168 { return pointer_traits<const_node_ptr>::pointer_to(static_cast<const node&>(*this)); }
169
170 public:
171 /// @endcond
172
generic_hook()173 generic_hook()
174 {
175 if(hooktags::safemode_or_autounlink){
176 node_algorithms::init(this->this_ptr());
177 }
178 }
179
generic_hook(const generic_hook &)180 generic_hook(const generic_hook& )
181 {
182 if(hooktags::safemode_or_autounlink){
183 node_algorithms::init(this->this_ptr());
184 }
185 }
186
operator =(const generic_hook &)187 generic_hook& operator=(const generic_hook& )
188 { return *this; }
189
~generic_hook()190 ~generic_hook()
191 {
192 destructor_impl
193 (*this, detail::link_dispatch<hooktags::link_mode>());
194 }
195
swap_nodes(generic_hook & other)196 void swap_nodes(generic_hook &other)
197 {
198 node_algorithms::swap_nodes
199 (this->this_ptr(), other.this_ptr());
200 }
201
is_linked() const202 bool is_linked() const
203 {
204 //is_linked() can be only used in safe-mode or auto-unlink
205 BOOST_STATIC_ASSERT(( hooktags::safemode_or_autounlink ));
206 return !node_algorithms::unique(this->this_ptr());
207 }
208
unlink()209 void unlink()
210 {
211 BOOST_STATIC_ASSERT(( (int)hooktags::link_mode == (int)auto_unlink ));
212 node_ptr n(this->this_ptr());
213 if(!node_algorithms::inited(n)){
214 node_algorithms::unlink(n);
215 node_algorithms::init(n);
216 }
217 }
218 };
219
220 } //namespace intrusive
221 } //namespace boost
222
223 #endif //BOOST_INTRUSIVE_GENERIC_HOOK_HPP
224