1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Auto-unlink hooks</title>
<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
<link rel="up" href="../intrusive.html" title="Chapter 19. Boost.Intrusive">
<link rel="prev" href="safe_hook.html" title="Safe hooks">
<link rel="next" href="slist.html" title="Intrusive singly linked list: slist">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td>
<td align="center"><a href="../../../index.html">Home</a></td>
<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="safe_hook.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="slist.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="intrusive.auto_unlink_hooks"></a><a class="link" href="auto_unlink_hooks.html" title="Auto-unlink hooks">Auto-unlink hooks</a>
</h2></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="auto_unlink_hooks.html#intrusive.auto_unlink_hooks.auto_unlink_hooks_what">What's
an auto-unlink hook?</a></span></dt>
<dt><span class="section"><a href="auto_unlink_hooks.html#intrusive.auto_unlink_hooks.auto_unlink_hooks_example">Auto-unlink
hook example</a></span></dt>
<dt><span class="section"><a href="auto_unlink_hooks.html#intrusive.auto_unlink_hooks.auto_unlink_and_constant_time">Auto-unlink
hooks and containers with constant-time <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code></a></span></dt>
</dl></div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.auto_unlink_hooks.auto_unlink_hooks_what"></a><a class="link" href="auto_unlink_hooks.html#intrusive.auto_unlink_hooks.auto_unlink_hooks_what" title="What's an auto-unlink hook?">What's
an auto-unlink hook?</a>
</h3></div></div></div>
<p>
<span class="bold"><strong>Boost.Intrusive</strong></span> offers additional hooks
with unique features:
</p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
When the destructor of the hook is called, the hook checks if the node
is inserted in a container. If so, the hook removes the node from the
container.
</li>
<li class="listitem">
The hook has a member function called <code class="computeroutput"><span class="identifier">unlink</span><span class="special">()</span></code> that can be used to unlink the node
from the container at any time, without having any reference to the container,
if the user wants to do so.
</li>
</ul></div>
<p>
These hooks have exactly the same size overhead as their analog non auto-unlinking
hooks, but they have a restriction: they can only be used with <a class="link" href="presenting_containers.html" title="Presenting Boost.Intrusive containers">non-constant
time size containers</a>. There is a reason for this:
</p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
Auto-unlink hooks don't store any reference to the container where they
are inserted.
</li>
<li class="listitem">
Only containers with non constant-time <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code> allow removing an object from the container
without referring to the container.
</li>
</ul></div>
<p>
This auto-unlink feature is useful in certain applications but it must be
used <span class="bold"><strong>very carefully</strong></span>:
</p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
If several threads are using the same container the destructor of the
auto-unlink hook will be called without any thread synchronization so
removing the object is thread-unsafe.
</li>
<li class="listitem">
Container contents change silently without modifying the container directly.
This can lead to surprising effects.
</li>
</ul></div>
<p>
These auto-unlink hooks have also safe-mode properties:
</p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
Hooks' constructors put the hook in a well-known default state.
</li>
<li class="listitem">
Every time an object is inserted in the intrusive container, the container
checks if the hook is in the well-known default state. If not, an assertion
is raised.
</li>
<li class="listitem">
Every time an object is erased from an intrusive container, the container
puts the erased object in the well-known default state.
</li>
</ul></div>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.auto_unlink_hooks.auto_unlink_hooks_example"></a><a class="link" href="auto_unlink_hooks.html#intrusive.auto_unlink_hooks.auto_unlink_hooks_example" title="Auto-unlink hook example">Auto-unlink
hook example</a>
</h3></div></div></div>
<p>
Let's see an example of an auto-unlink hook:
</p>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">intrusive</span><span class="special">/</span><span class="identifier">list</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">cassert</span><span class="special">></span>
<span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">;</span>
<span class="keyword">typedef</span> <span class="identifier">list_base_hook</span><span class="special"><</span><span class="identifier">link_mode</span><span class="special"><</span><span class="identifier">auto_unlink</span><span class="special">></span> <span class="special">></span> <span class="identifier">auto_unlink_hook</span><span class="special">;</span>
<span class="keyword">class</span> <span class="identifier">MyClass</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">auto_unlink_hook</span>
<span class="comment">//This hook removes the node in the destructor</span>
<span class="special">{</span>
<span class="keyword">int</span> <span class="identifier">int_</span><span class="special">;</span>
<span class="keyword">public</span><span class="special">:</span>
<span class="identifier">MyClass</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span> <span class="special">=</span> <span class="number">0</span><span class="special">)</span> <span class="special">:</span> <span class="identifier">int_</span><span class="special">(</span><span class="identifier">i</span><span class="special">)</span> <span class="special">{}</span>
<span class="keyword">int</span> <span class="identifier">get_int</span><span class="special">()</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">int_</span><span class="special">;</span> <span class="special">}</span>
<span class="keyword">void</span> <span class="identifier">unlink</span><span class="special">()</span> <span class="special">{</span> <span class="identifier">auto_unlink_hook</span><span class="special">::</span><span class="identifier">unlink</span><span class="special">();</span> <span class="special">}</span>
<span class="keyword">bool</span> <span class="identifier">is_linked</span><span class="special">()</span> <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">auto_unlink_hook</span><span class="special">::</span><span class="identifier">is_linked</span><span class="special">();</span> <span class="special">}</span>
<span class="special">};</span>
<span class="comment">//Define a list that will store values using the base hook</span>
<span class="comment">//The list can't have constant-time size!</span>
<span class="keyword">typedef</span> <span class="identifier">list</span><span class="special"><</span> <span class="identifier">MyClass</span><span class="special">,</span> <span class="identifier">constant_time_size</span><span class="special"><</span><span class="keyword">false</span><span class="special">></span> <span class="special">></span> <span class="identifier">List</span><span class="special">;</span>
<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span>
<span class="special">{</span>
<span class="comment">//Create the list</span>
<span class="identifier">List</span> <span class="identifier">l</span><span class="special">;</span>
<span class="special">{</span>
<span class="comment">//Create myclass and check it's linked</span>
<span class="identifier">MyClass</span> <span class="identifier">myclass</span><span class="special">;</span>
<span class="identifier">assert</span><span class="special">(</span><span class="identifier">myclass</span><span class="special">.</span><span class="identifier">is_linked</span><span class="special">()</span> <span class="special">==</span> <span class="keyword">false</span><span class="special">);</span>
<span class="comment">//Insert the object</span>
<span class="identifier">l</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">myclass</span><span class="special">);</span>
<span class="comment">//Check that we have inserted the object</span>
<span class="identifier">assert</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">empty</span><span class="special">()</span> <span class="special">==</span> <span class="keyword">false</span><span class="special">);</span>
<span class="identifier">assert</span><span class="special">(&</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">front</span><span class="special">()</span> <span class="special">==</span> <span class="special">&</span><span class="identifier">myclass</span><span class="special">);</span>
<span class="identifier">assert</span><span class="special">(</span><span class="identifier">myclass</span><span class="special">.</span><span class="identifier">is_linked</span><span class="special">()</span> <span class="special">==</span> <span class="keyword">true</span><span class="special">);</span>
<span class="comment">//Now myclass' destructor will unlink it</span>
<span class="comment">//automatically</span>
<span class="special">}</span>
<span class="comment">//Check auto-unlink has been executed</span>
<span class="identifier">assert</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">empty</span><span class="special">()</span> <span class="special">==</span> <span class="keyword">true</span><span class="special">);</span>
<span class="special">{</span>
<span class="comment">//Now test the unlink() function</span>
<span class="comment">//Create myclass and check it's linked</span>
<span class="identifier">MyClass</span> <span class="identifier">myclass</span><span class="special">;</span>
<span class="identifier">assert</span><span class="special">(</span><span class="identifier">myclass</span><span class="special">.</span><span class="identifier">is_linked</span><span class="special">()</span> <span class="special">==</span> <span class="keyword">false</span><span class="special">);</span>
<span class="comment">//Insert the object</span>
<span class="identifier">l</span><span class="special">.</span><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">myclass</span><span class="special">);</span>
<span class="comment">//Check that we have inserted the object</span>
<span class="identifier">assert</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">empty</span><span class="special">()</span> <span class="special">==</span> <span class="keyword">false</span><span class="special">);</span>
<span class="identifier">assert</span><span class="special">(&</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">front</span><span class="special">()</span> <span class="special">==</span> <span class="special">&</span><span class="identifier">myclass</span><span class="special">);</span>
<span class="identifier">assert</span><span class="special">(</span><span class="identifier">myclass</span><span class="special">.</span><span class="identifier">is_linked</span><span class="special">()</span> <span class="special">==</span> <span class="keyword">true</span><span class="special">);</span>
<span class="comment">//Now unlink the node</span>
<span class="identifier">myclass</span><span class="special">.</span><span class="identifier">unlink</span><span class="special">();</span>
<span class="comment">//Check auto-unlink has been executed</span>
<span class="identifier">assert</span><span class="special">(</span><span class="identifier">l</span><span class="special">.</span><span class="identifier">empty</span><span class="special">()</span> <span class="special">==</span> <span class="keyword">true</span><span class="special">);</span>
<span class="special">}</span>
<span class="keyword">return</span> <span class="number">0</span><span class="special">;</span>
<span class="special">}</span>
</pre>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.auto_unlink_hooks.auto_unlink_and_constant_time"></a><a class="link" href="auto_unlink_hooks.html#intrusive.auto_unlink_hooks.auto_unlink_and_constant_time" title="Auto-unlink hooks and containers with constant-time size()">Auto-unlink
hooks and containers with constant-time <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code></a>
</h3></div></div></div>
<p>
As explained, <span class="bold"><strong>Boost.Intrusive</strong></span> auto-unlink
hooks are incompatible with containers that have constant-time <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>,
so if you try to define such container with an auto-unlink hook's value_traits,
you will get a static assertion:
</p>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">intrusive</span><span class="special">/</span><span class="identifier">list</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
<span class="keyword">using</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">intrusive</span><span class="special">;</span>
<span class="keyword">struct</span> <span class="identifier">MyTag</span><span class="special">;</span>
<span class="keyword">class</span> <span class="identifier">MyClass</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">list_base_hook</span><span class="special"><</span> <span class="identifier">link_mode</span><span class="special"><</span><span class="identifier">auto_unlink</span><span class="special">></span> <span class="special">></span>
<span class="special">{/**/};</span>
<span class="identifier">list</span> <span class="special"><</span><span class="identifier">MyClass</span><span class="special">,</span> <span class="identifier">constant_time_size</span><span class="special"><</span><span class="keyword">true</span><span class="special">></span> <span class="special">></span> <span class="identifier">bad_list</span><span class="special">;</span>
<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span>
<span class="special">{</span>
<span class="identifier">bad_list</span> <span class="identifier">list</span><span class="special">;</span>
<span class="keyword">return</span> <span class="number">0</span><span class="special">;</span>
<span class="special">}</span>
</pre>
<p>
leads to an error similar to:
</p>
<pre class="programlisting"> error : use of undefined type 'boost::STATIC_ASSERTION_FAILURE<false>'
</pre>
<p>
Pointing to code like this:
</p>
<pre class="programlisting"><span class="comment">//Constant-time size is incompatible with auto-unlink hooks!</span>
<span class="identifier">BOOST_STATIC_ASSERT</span><span class="special">(!(</span><span class="identifier">constant_time_size</span> <span class="special">&&</span> <span class="special">((</span><span class="keyword">int</span><span class="special">)</span><span class="identifier">value_traits</span><span class="special">::</span><span class="identifier">link_mode</span> <span class="special">==</span> <span class="special">(</span><span class="keyword">int</span><span class="special">)</span><span class="identifier">auto_unlink</span><span class="special">)));</span>
</pre>
<p>
This way, there is no way to compile a program if you try to use auto-unlink
hooks in constant-time size containers.
</p>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<p>
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
</p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="safe_hook.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="slist.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
|
