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