<html> <head> <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> <title>Concepts explained</title> <link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> <meta name="generator" content="DocBook XSL Stylesheets V1.75.2"> <link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> <link rel="up" href="../intrusive.html" title="Chapter 10. Boost.Intrusive"> <link rel="prev" href="any_hooks.html" title="Any Hooks: A single hook for any Intrusive container"> <link rel="next" href="node_algorithms.html" title="Node algorithms with custom NodeTraits"> </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="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> </div> <div class="section"> <div class="titlepage"><div><div><h2 class="title" style="clear: both"> <a name="intrusive.concepts"></a><a class="link" href="concepts.html" title="Concepts explained"> Concepts explained</a> </h2></div></div></div> <p> This section will expand the explanation of previously presented basic concepts before explaining the customization options of <span class="bold"><strong>Boost.Intrusive</strong></span>. </p> <div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"> <span class="bold"><strong>Node Algorithms</strong></span>: A set of static functions that implement basic operations on a group of nodes: initialize a node, link_mode_type a node to a group of nodes, unlink a node from another group of nodes, etc. For example, a circular singly linked list is a group of nodes, where each node has a pointer to the next node. <span class="bold"><strong>Node Algorithms</strong></span> just require a <span class="bold"><strong>NodeTraits</strong></span> template parameter and they can work with any <span class="bold"><strong>NodeTraits</strong></span> class that fulfills the needed interface. As an example, here is a class that implements operations7' to manage a group of nodes forming a circular singly linked list: </li></ul></div> <p> </p> <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> <span class="keyword">struct</span> <span class="identifier">my_slist_algorithms</span> <span class="special">{</span> <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> <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> <span class="comment">//Get the previous node of "this_node" </span> <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> <span class="special">{</span> <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> <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> <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> <span class="keyword">return</span> <span class="identifier">p</span><span class="special">;</span> <span class="special">}</span> <span class="comment">// number of elements in the group of nodes containing "this_node" </span> <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> <span class="special">{</span> <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> <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> <span class="keyword">do</span><span class="special">{</span> <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> <span class="special">++</span><span class="identifier">result</span><span class="special">;</span> <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> <span class="keyword">return</span> <span class="identifier">result</span><span class="special">;</span> <span class="special">}</span> <span class="comment">// More operations </span> <span class="comment">// ... </span><span class="special">};</span> </pre> <div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"> <span class="bold"><strong>Node Traits</strong></span>: A class that encapsulates the basic information and operations on a node within a group of nodes: the type of the node, a function to obtain the pointer to the next node, etc. <span class="bold"><strong>Node Traits</strong></span> specify the configuration information <span class="bold"><strong>Node Algorithms</strong></span> need. Each type of <span class="bold"><strong>Node Algorithm</strong></span> expects an interface that compatible <span class="bold"><strong>Node Traits</strong></span> classes must implement. As an example, this is the definition of a <span class="bold"><strong>Node Traits</strong></span> class that is compatible with the previously presented <code class="computeroutput"><span class="identifier">my_slist_algorithms</span></code>: </li></ul></div> <p> </p> <pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">my_slist_node_traits</span> <span class="special">{</span> <span class="comment">//The type of the node </span> <span class="keyword">struct</span> <span class="identifier">node</span> <span class="special">{</span> <span class="identifier">node</span> <span class="special">*</span><span class="identifier">next_</span><span class="special">;</span> <span class="special">};</span> <span class="keyword">typedef</span> <span class="identifier">node</span> <span class="special">*</span> <span class="identifier">node_ptr</span><span class="special">;</span> <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> <span class="comment">//A function to obtain a pointer to the next node </span> <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> <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> <span class="comment">//A function to set the pointer to the next node </span> <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> <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> <span class="special">};</span> </pre> <div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"> <span class="bold"><strong>Hook</strong></span>: A class that the user must add as a base class or as a member to his own class to make that class insertable in an intrusive container. Usually the hook contains a node object that will be used to form the group of nodes: For example, the following class is a <span class="bold"><strong>Hook</strong></span> that the user can add as a base class, to make the user class compatible with a singly linked list container: </li></ul></div> <p> </p> <pre class="programlisting"><span class="keyword">class</span> <span class="identifier">my_slist_base_hook</span> <span class="comment">//This hook contains a node, that will be used </span> <span class="comment">//to link the user object in the group of nodes </span> <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> <span class="special">{</span> <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> <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> <span class="comment">//Converts the generic node to the hook </span> <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> <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> <span class="comment">//Returns the generic node stored by this hook </span> <span class="identifier">node_ptr</span> <span class="identifier">to_node_ptr</span><span class="special">()</span> <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> <span class="comment">// More operations </span> <span class="comment">// ... </span><span class="special">};</span> <span class="comment">//To make MyClass compatible with an intrusive singly linked list </span><span class="comment">//derive our class from the hook. </span><span class="keyword">class</span> <span class="identifier">MyClass</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">my_slist_base_hook</span> <span class="special">{</span> <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> <span class="keyword">int</span> <span class="identifier">get</span><span class="special">()</span> <span class="keyword">const</span><span class="special">;</span> <span class="keyword">private</span><span class="special">:</span> <span class="keyword">int</span> <span class="identifier">value_</span><span class="special">;</span> <span class="special">};</span> </pre> <div class="itemizedlist"><ul class="itemizedlist" type="disc"><li class="listitem"> <span class="bold"><strong>Intrusive Container</strong></span>: A container that offers a STL-like interface to store user objects. An intrusive container can be templatized to store different value types that use different hooks. An intrusive container is also more elaborate than a group of nodes: it can store the number of elements to achieve constant-time size information, 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> container (intrusive singly linked list) should be able to hold <code class="computeroutput"><span class="identifier">MyClass</span></code> objects that might have decided to store the hook as a base class or as a member. Internally, the container will use <span class="bold"><strong>Node Algorithms</strong></span> to implement its operations, and an intrusive container is configured using a template parameter called <span class="bold"><strong>ValueTraits</strong></span>. <span class="bold"><strong>ValueTraits</strong></span> will contain the information to convert user classes in nodes compatible with <span class="bold"><strong>Node Algorithms</strong></span>. For example, this a possible <code class="computeroutput"><a class="link" href="../boost/intrusive/slist.html" title="Class template slist">slist</a></code> implementation: </li></ul></div> <p> </p> <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> <span class="keyword">class</span> <span class="identifier">slist</span> <span class="special">{</span> <span class="keyword">public</span><span class="special">:</span> <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> <span class="comment">//More typedefs and functions </span> <span class="comment">// ... </span> <span class="comment">//Insert the value as the first element of the list </span> <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> <span class="special">{</span> <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> <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> <span class="special">}</span> <span class="comment">// More operations </span> <span class="comment">// ... </span><span class="special">};</span> </pre> <div class="itemizedlist"><ul class="itemizedlist" type="disc"> <li class="listitem"> <span class="bold"><strong>Semi-Intrusive Container</strong></span>: A semi-intrusive container is similar to an intrusive container, but apart from the values to be inserted in the container, it needs additional memory (for example, auxiliary arrays or indexes). </li> <li class="listitem"> <span class="bold"><strong>Value Traits</strong></span>: As we can see, to make our classes intrusive-friendly we add a simple hook as a member or base class. The hook contains a generic node that will be inserted in a group of nodes. <span class="bold"><strong>Node Algorithms</strong></span> just work with nodes and don't know anything about user classes. On the other hand, an intrusive container needs to know how to obtain a node from a user class, and also the inverse operation. So we can define <span class="bold"><strong>ValueTraits</strong></span> as the glue between user classes and nodes required by <span class="bold"><strong>Node Algorithms</strong></span>. Let's see a possible implementation of a value traits class that glues MyClass and the node stored in the hook: </li> </ul></div> <p> </p> <pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">my_slist_derivation_value_traits</span> <span class="special">{</span> <span class="keyword">public</span><span class="special">:</span> <span class="keyword">typedef</span> <span class="identifier">slist_node_traits</span> <span class="identifier">node_traits</span><span class="special">;</span> <span class="keyword">typedef</span> <span class="identifier">MyClass</span> <span class="identifier">value_type</span><span class="special">;</span> <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> <span class="keyword">typedef</span> <span class="identifier">value_type</span><span class="special">*</span> <span class="identifier">pointer</span><span class="special">;</span> <span class="comment">//... </span> <span class="comment">//Converts user's value to a generic node </span> <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> <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> <span class="comment">//Converts a generic node into user's value </span> <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> <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> <span class="comment">// More operations </span> <span class="comment">// ... </span><span class="special">};</span> </pre> </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, 2006-2009 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="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> </div> </body> </html>