241 lines
23 KiB
HTML
241 lines
23 KiB
HTML
<!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=UTF-8">
|
||
<title>Concepts explained</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="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" style="list-style-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 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 operations 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" style="list-style-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" style="list-style-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" style="list-style-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" style="list-style-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<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="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>
|