1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
|
<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.76.1">
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
<link rel="up" href="../intrusive.html" title="Chapter 13. 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<br>Copyright © 2006-2011 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>
|
