| <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> |
| <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> |
| <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> |
| <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> |
| <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> |
| <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-2010 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> |
