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>Concepts explained</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="any_hooks.html" title="Any Hooks: A single hook for any Intrusive container"> 11<link rel="next" href="node_algorithms.html" title="Node algorithms with custom NodeTraits"> 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="any_hooks.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="node_algorithms.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.concepts"></a><a class="link" href="concepts.html" title="Concepts explained">Concepts explained</a> 29</h2></div></div></div> 30<p> 31 This section will expand the explanation of previously presented basic concepts 32 before explaining the customization options of <span class="bold"><strong>Boost.Intrusive</strong></span>. 33 </p> 34<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"> 35 <span class="bold"><strong>Node Algorithms</strong></span>: A set of static functions 36 that implement basic operations on a group of nodes: initialize a node, 37 link a node to a group of nodes, unlink a node from another group of nodes, 38 etc. For example, a circular singly linked list is a group of nodes, where 39 each node has a pointer to the next node. <span class="bold"><strong>Node Algorithms</strong></span> 40 just require a <span class="bold"><strong>NodeTraits</strong></span> template parameter 41 and they can work with any <span class="bold"><strong>NodeTraits</strong></span> 42 class that fulfills the needed interface. As an example, here is a class 43 that implements operations to manage a group of nodes forming a circular 44 singly linked list: 45 </li></ul></div> 46<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">NodeTraits</span><span class="special">></span> 47<span class="keyword">struct</span> <span class="identifier">my_slist_algorithms</span> 48<span class="special">{</span> 49 <span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">NodeTraits</span><span class="special">::</span><span class="identifier">node_ptr</span> <span class="identifier">node_ptr</span><span class="special">;</span> 50 <span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">NodeTraits</span><span class="special">::</span><span class="identifier">const_node_ptr</span> <span class="identifier">const_node_ptr</span><span class="special">;</span> 51 52 <span class="comment">//Get the previous node of "this_node"</span> 53 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_prev_node</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">this_node</span><span class="special">)</span> 54 <span class="special">{</span> 55 <span class="identifier">node_ptr</span> <span class="identifier">p</span> <span class="special">=</span> <span class="identifier">this_node</span><span class="special">;</span> 56 <span class="keyword">while</span> <span class="special">(</span><span class="identifier">this_node</span> <span class="special">!=</span> <span class="identifier">NodeTraits</span><span class="special">::</span><span class="identifier">get_next</span><span class="special">(</span><span class="identifier">p</span><span class="special">))</span> 57 <span class="identifier">p</span> <span class="special">=</span> <span class="identifier">NodeTraits</span><span class="special">::</span><span class="identifier">get_next</span><span class="special">(</span><span class="identifier">p</span><span class="special">);</span> 58 <span class="keyword">return</span> <span class="identifier">p</span><span class="special">;</span> 59 <span class="special">}</span> 60 61 <span class="comment">// number of elements in the group of nodes containing "this_node"</span> 62 <span class="keyword">static</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span> <span class="identifier">count</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">this_node</span><span class="special">)</span> 63 <span class="special">{</span> 64 <span class="identifier">std</span><span class="special">::</span><span class="identifier">size_t</span> <span class="identifier">result</span> <span class="special">=</span> <span class="number">0</span><span class="special">;</span> 65 <span class="identifier">const_node_ptr</span> <span class="identifier">p</span> <span class="special">=</span> <span class="identifier">this_node</span><span class="special">;</span> 66 <span class="keyword">do</span><span class="special">{</span> 67 <span class="identifier">p</span> <span class="special">=</span> <span class="identifier">NodeTraits</span><span class="special">::</span><span class="identifier">get_next</span><span class="special">(</span><span class="identifier">p</span><span class="special">);</span> 68 <span class="special">++</span><span class="identifier">result</span><span class="special">;</span> 69 <span class="special">}</span> <span class="keyword">while</span> <span class="special">(</span><span class="identifier">p</span> <span class="special">!=</span> <span class="identifier">this_node</span><span class="special">);</span> 70 <span class="keyword">return</span> <span class="identifier">result</span><span class="special">;</span> 71 <span class="special">}</span> 72 73 <span class="comment">// More operations</span> 74 <span class="comment">// ...</span> 75<span class="special">};</span> 76</pre> 77<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"> 78 <span class="bold"><strong>Node Traits</strong></span>: A class that encapsulates 79 the basic information and operations on a node within a group of nodes: 80 the type of the node, a function to obtain the pointer to the next node, 81 etc. <span class="bold"><strong>Node Traits</strong></span> specify the configuration 82 information <span class="bold"><strong>Node Algorithms</strong></span> need. Each 83 type of <span class="bold"><strong>Node Algorithm</strong></span> expects an interface 84 that compatible <span class="bold"><strong>Node Traits</strong></span> classes must 85 implement. As an example, this is the definition of a <span class="bold"><strong>Node 86 Traits</strong></span> class that is compatible with the previously presented 87 <code class="computeroutput"><span class="identifier">my_slist_algorithms</span></code>: 88 </li></ul></div> 89<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">my_slist_node_traits</span> 90<span class="special">{</span> 91 <span class="comment">//The type of the node</span> 92 <span class="keyword">struct</span> <span class="identifier">node</span> 93 <span class="special">{</span> 94 <span class="identifier">node</span> <span class="special">*</span><span class="identifier">next_</span><span class="special">;</span> 95 <span class="special">};</span> 96 97 <span class="keyword">typedef</span> <span class="identifier">node</span> <span class="special">*</span> <span class="identifier">node_ptr</span><span class="special">;</span> 98 <span class="keyword">typedef</span> <span class="keyword">const</span> <span class="identifier">node</span> <span class="special">*</span> <span class="identifier">const_node_ptr</span><span class="special">;</span> 99 100 <span class="comment">//A function to obtain a pointer to the next node</span> 101 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">get_next</span><span class="special">(</span><span class="identifier">const_node_ptr</span> <span class="identifier">n</span><span class="special">)</span> 102 <span class="special">{</span> <span class="keyword">return</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">next_</span><span class="special">;</span> <span class="special">}</span> 103 104 <span class="comment">//A function to set the pointer to the next node</span> 105 <span class="keyword">static</span> <span class="keyword">void</span> <span class="identifier">set_next</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">n</span><span class="special">,</span> <span class="identifier">node_ptr</span> <span class="identifier">next</span><span class="special">)</span> 106 <span class="special">{</span> <span class="identifier">n</span><span class="special">-></span><span class="identifier">next_</span> <span class="special">=</span> <span class="identifier">next</span><span class="special">;</span> <span class="special">}</span> 107<span class="special">};</span> 108</pre> 109<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"> 110 <span class="bold"><strong>Hook</strong></span>: A class that the user must add as 111 a base class or as a member to his own class to make that class insertable 112 in an intrusive container. Usually the hook contains a node object that 113 will be used to form the group of nodes: For example, the following class 114 is a <span class="bold"><strong>Hook</strong></span> that the user can add as a base 115 class, to make the user class compatible with a singly linked list container: 116 </li></ul></div> 117<pre class="programlisting"><span class="keyword">class</span> <span class="identifier">my_slist_base_hook</span> 118 <span class="comment">//This hook contains a node, that will be used</span> 119 <span class="comment">//to link the user object in the group of nodes</span> 120 <span class="special">:</span> <span class="keyword">private</span> <span class="identifier">my_slist_node_traits</span><span class="special">::</span><span class="identifier">node</span> 121<span class="special">{</span> 122 <span class="keyword">typedef</span> <span class="identifier">my_slist_node_traits</span><span class="special">::</span><span class="identifier">node_ptr</span> <span class="identifier">node_ptr</span><span class="special">;</span> 123 <span class="keyword">typedef</span> <span class="identifier">my_slist_node_traits</span><span class="special">::</span><span class="identifier">const_node_ptr</span> <span class="identifier">const_node_ptr</span><span class="special">;</span> 124 125 <span class="comment">//Converts the generic node to the hook</span> 126 <span class="keyword">static</span> <span class="identifier">my_slist_base_hook</span> <span class="special">*</span><span class="identifier">to_hook_ptr</span><span class="special">(</span><span class="identifier">node_ptr</span> <span class="identifier">p</span><span class="special">)</span> 127 <span class="special">{</span> <span class="keyword">return</span> <span class="keyword">static_cast</span><span class="special"><</span><span class="identifier">my_slist_base_hook</span><span class="special">*>(</span><span class="identifier">p</span><span class="special">);</span> <span class="special">}</span> 128 129 <span class="comment">//Returns the generic node stored by this hook</span> 130 <span class="identifier">node_ptr</span> <span class="identifier">to_node_ptr</span><span class="special">()</span> 131 <span class="special">{</span> <span class="keyword">return</span> <span class="keyword">static_cast</span><span class="special"><</span><span class="identifier">node</span> <span class="special">*</span><span class="keyword">const</span><span class="special">>(</span><span class="keyword">this</span><span class="special">);</span> <span class="special">}</span> 132 133 <span class="comment">// More operations</span> 134 <span class="comment">// ...</span> 135<span class="special">};</span> 136 137<span class="comment">//To make MyClass compatible with an intrusive singly linked list</span> 138<span class="comment">//derive our class from the hook.</span> 139<span class="keyword">class</span> <span class="identifier">MyClass</span> 140 <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">my_slist_base_hook</span> 141<span class="special">{</span> 142 <span class="keyword">void</span> <span class="identifier">set</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">value</span><span class="special">);</span> 143 <span class="keyword">int</span> <span class="identifier">get</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span> 144 145 <span class="keyword">private</span><span class="special">:</span> 146 <span class="keyword">int</span> <span class="identifier">value_</span><span class="special">;</span> 147<span class="special">};</span> 148</pre> 149<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"> 150 <span class="bold"><strong>Intrusive Container</strong></span>: A container that 151 offers a STL-like interface to store user objects. An intrusive container 152 can be templatized to store different value types that use different hooks. 153 An intrusive container is also more elaborate than a group of nodes: it 154 can store the number of elements to achieve constant-time size information, 155 it can offer debugging facilities, etc. For example, an <code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code> 156 container (intrusive singly linked list) should be able to hold <code class="computeroutput"><span class="identifier">MyClass</span></code> objects that might have decided 157 to store the hook as a base class or as a member. Internally, the container 158 will use <span class="bold"><strong>Node Algorithms</strong></span> to implement 159 its operations, and an intrusive container is configured using a template 160 parameter called <span class="bold"><strong>ValueTraits</strong></span>. <span class="bold"><strong>ValueTraits</strong></span> will contain the information to convert 161 user classes in nodes compatible with <span class="bold"><strong>Node Algorithms</strong></span>. 162 For example, this a possible <code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code> 163 implementation: 164 </li></ul></div> 165<pre class="programlisting"><span class="keyword">template</span><span class="special"><</span><span class="keyword">class</span> <span class="identifier">ValueTraits</span><span class="special">,</span> <span class="special">...></span> 166<span class="keyword">class</span> <span class="identifier">slist</span> 167<span class="special">{</span> 168 <span class="keyword">public</span><span class="special">:</span> 169 <span class="keyword">typedef</span> <span class="keyword">typename</span> <span class="identifier">ValueTraits</span><span class="special">::</span><span class="identifier">value_type</span> <span class="identifier">value_type</span><span class="special">;</span> 170 171 <span class="comment">//More typedefs and functions</span> 172 <span class="comment">// ...</span> 173 174 <span class="comment">//Insert the value as the first element of the list</span> 175 <span class="keyword">void</span> <span class="identifier">push_front</span> <span class="special">(</span><span class="identifier">reference</span> <span class="identifier">value</span><span class="special">)</span> 176 <span class="special">{</span> 177 <span class="identifier">node_ptr</span> <span class="identifier">to_insert</span><span class="special">(</span><span class="identifier">ValueTraits</span><span class="special">::</span><span class="identifier">to_node_ptr</span><span class="special">(</span><span class="identifier">value</span><span class="special">));</span> 178 <span class="identifier">circular_list_algorithms</span><span class="special">::</span><span class="identifier">link_after</span><span class="special">(</span><span class="identifier">to_insert</span><span class="special">,</span> <span class="identifier">get_root_node</span><span class="special">());</span> 179 <span class="special">}</span> 180 181 <span class="comment">// More operations</span> 182 <span class="comment">// ...</span> 183<span class="special">};</span> 184</pre> 185<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 186<li class="listitem"> 187 <span class="bold"><strong>Semi-Intrusive Container</strong></span>: A semi-intrusive 188 container is similar to an intrusive container, but apart from the values 189 to be inserted in the container, it needs additional memory (for example, 190 auxiliary arrays or indexes). 191 </li> 192<li class="listitem"> 193 <span class="bold"><strong>Value Traits</strong></span>: As we can see, to make our 194 classes intrusive-friendly we add a simple hook as a member or base class. 195 The hook contains a generic node that will be inserted in a group of nodes. 196 <span class="bold"><strong>Node Algorithms</strong></span> just work with nodes and 197 don't know anything about user classes. On the other hand, an intrusive 198 container needs to know how to obtain a node from a user class, and also 199 the inverse operation. So we can define <span class="bold"><strong>ValueTraits</strong></span> 200 as the glue between user classes and nodes required by <span class="bold"><strong>Node 201 Algorithms</strong></span>. Let's see a possible implementation of a value traits 202 class that glues MyClass and the node stored in the hook: 203 </li> 204</ul></div> 205<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">my_slist_derivation_value_traits</span> 206<span class="special">{</span> 207 <span class="keyword">public</span><span class="special">:</span> 208 <span class="keyword">typedef</span> <span class="identifier">slist_node_traits</span> <span class="identifier">node_traits</span><span class="special">;</span> 209 <span class="keyword">typedef</span> <span class="identifier">MyClass</span> <span class="identifier">value_type</span><span class="special">;</span> 210 <span class="keyword">typedef</span> <span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node_ptr</span> <span class="identifier">node_ptr</span><span class="special">;</span> 211 <span class="keyword">typedef</span> <span class="identifier">value_type</span><span class="special">*</span> <span class="identifier">pointer</span><span class="special">;</span> 212 <span class="comment">//...</span> 213 214 <span class="comment">//Converts user's value to a generic node</span> 215 <span class="keyword">static</span> <span class="identifier">node_ptr</span> <span class="identifier">to_node_ptr</span><span class="special">(</span><span class="identifier">reference</span> <span class="identifier">value</span><span class="special">)</span> 216 <span class="special">{</span> <span class="keyword">return</span> <span class="keyword">static_cast</span><span class="special"><</span><span class="identifier">slist_base_hook</span> <span class="special">&>(</span><span class="identifier">value</span><span class="special">).</span><span class="identifier">to_node_ptr</span><span class="special">();</span> <span class="special">}</span> 217 218 <span class="comment">//Converts a generic node into user's value</span> 219 <span class="keyword">static</span> <span class="identifier">value_type</span> <span class="special">*</span><span class="identifier">to_value_ptr</span><span class="special">(</span><span class="identifier">node_traits</span><span class="special">::</span><span class="identifier">node</span> <span class="special">*</span><span class="identifier">n</span><span class="special">)</span> 220 <span class="special">{</span> <span class="keyword">static_cast</span><span class="special"><</span><span class="identifier">value_type</span><span class="special">*>(</span><span class="identifier">slist_base_hook</span><span class="special">::</span><span class="identifier">to_hook_ptr</span><span class="special">(</span><span class="identifier">n</span><span class="special">));</span> <span class="special">}</span> 221 222 <span class="comment">// More operations</span> 223 <span class="comment">// ...</span> 224<span class="special">};</span> 225</pre> 226</div> 227<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 228<td align="left"></td> 229<td align="right"><div class="copyright-footer">Copyright © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<p> 230 Distributed under the Boost Software License, Version 1.0. (See accompanying 231 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>) 232 </p> 233</div></td> 234</tr></table> 235<hr> 236<div class="spirit-nav"> 237<a accesskey="p" href="any_hooks.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="node_algorithms.html"><img src="../../../doc/src/images/next.png" alt="Next"></a> 238</div> 239</body> 240</html> 241
