1 <!DOCTYPE html PUBLIC
"-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><title>The multi_pass
</title>
3 <meta http-equiv=
"Content-Type" content=
"text/html; charset=iso-8859-1">
4 <link rel=
"stylesheet" href=
"theme/style.css" type=
"text/css"></head>
6 <table width=
"100%" border=
"0" background=
"theme/bkd2.gif" cellspacing=
"2">
11 <td width=
"85%"> <font size=
"6" face=
"Verdana, Arial, Helvetica, sans-serif"><b>The
12 multi_pass
</b></font> </td>
13 <td width=
"112"><a href=
"http://spirit.sf.net"><img src=
"theme/spirit.gif" width=
"112" height=
"48" align=
"right" border=
"0"></a></td>
21 <td width=
"30"><a href=
"../index.html"><img src=
"theme/u_arr.gif" border=
"0"></a></td>
22 <td width=
"30"><a href=
"trees.html"><img src=
"theme/l_arr.gif" border=
"0"></a></td>
23 <td width=
"30"><a href=
"file_iterator.html"><img src=
"theme/r_arr.gif" border=
"0"></a></td>
26 <p>Backtracking in Spirit requires the use of the following types of iterator:
27 forward, bidirectional, or random access. Because of backtracking, input iterators
28 cannot be used. Therefore, the standard library classes istreambuf_iterator
29 and istream_iterator, that fall under the category of input iterators, cannot
30 be used. Another input iterator that is of interest is one that wraps a lexer,
32 <table width=
"80%" border=
"0" align=
"center">
34 <td class=
"note_box"> <img src=
"theme/note.gif" width=
"16" height=
"16"> <b>Input
37 In general, Spirit is a backtracking parser. This is not an absolute requirement
38 though. In the future, we shall see more deterministic parsers that require
39 no more than
1 character (token) of lookahead. Such parsers allow us to
40 use input iterators such as the istream_iterator as is.
</td>
43 <p> Unfortunately, with an input iterator, there is no way to save an iterator
44 position, and thus input iterators will not work with backtracking in Spirit.
45 One solution to this problem is to simply load all the data to be parsed into
46 a container, such as a vector or deque, and then pass the begin and end of the
47 container to Spirit. This method can be too memory intensive for certain applications,
48 which is why the multi_pass iterator was created.
</p>
49 <p> The multi_pass iterator will convert any input iterator into a forward iterator
50 suitable for use with Spirit. multi_pass will buffer data when needed and will
51 discard the buffer when only one copy of the iterator exists.
</p>
52 <p> A grammar must be designed with care if the multi_pass iterator is used. Any rule that may
53 need to backtrack, such as one that contains an alternative, will cause data to be buffered. The rules that are optimal to
54 use are sequence and repetition. Sequences of the form
<tt>a
>> b
</tt>
55 will not buffer data at all. Any rule that repeats, such as kleene_star (
<tt>*a
</tt>)
56 or positive such as (
<tt>+a
</tt>), will only buffer the data for the current
58 <p> In typical grammars, ambiguity and therefore lookahead is often localized.
59 In fact, many well designed languages are fully deterministic and require no
60 lookahead at all. Peeking at the first character from the input will immediately
61 determine the alternative branch to take. Yet, even with highly ambiguous grammars,
62 alternatives are often of the form
<tt>*(a | b | c | d)
</tt>. The input iterator
63 moves on and is never stuck at the beginning. Let's look at a Pascal snippet
65 <pre> <code><span class=
"identifier">program
</span><span class=
"special">=
<br> </span><span class=
"identifier"> programHeading
</span><span class=
"special">>> </span><span class=
"identifier">block
</span><span class=
"special">>> </span><span class=
"literal">'.'
<br> </span><span class=
"special"> ;
<br><br> </span><span class=
"identifier">block
</span><span class=
"special">=
<br> *(
</span><span class=
"identifier">labelDeclarationPart
<br> </span><span class=
"special">|
</span><span class=
"identifier">constantDefinitionPart
<br> </span><span class=
"special">|
</span><span class=
"identifier">typeDefinitionPart
<br> </span><span class=
"special"> |
</span><span class=
"identifier">variableDeclarationPart
<br> </span><span class=
"special">|
</span><span class=
"identifier"> procedureAndFunctionDeclarationPart
<br> </span><span class=
"special"> )
<br> >> </span><span class=
"identifier">statementPart
<br> </span><span class=
"special">;
<br></span></code></pre>
66 <p> Notice the alternatives inside the Kleene star in the rule block . The rule
67 gobbles the input in a linear manner and throws away the past history with each
68 iteration. As this is fully deterministic LL(
1) grammar, each failed alternative
69 only has to peek
1 character (token). The alternative that consumes more than
70 1 character (token) is definitely a winner. After which, the Kleene star moves
72 <p>Be mindful if you use the free parse functions.
73 All of these make a copy of the iterator passed to them.
<br>
75 <p>Now, after the lecture on the features to be careful with when using multi_pass,
76 you may think that multi_pass is way too restrictive to use.
That's
77 not the case.
If your grammar is deterministic, you can make use of flush_multi_pass in your grammar to ensure that data is not buffered when unnecessary.
<br>
80 <p> Again, following up the example we started to use in the section on the scanner
81 . Here's an example using the multi_pass: This time around we are extracting
82 our input from the input stream using an istreambuf_iterator.
</p>
83 <pre> <span class=
"preprocessor">#include
</span> <span class=
"special"><</span><span class=
"identifier">boost
</span><span class=
"special">/
</span><span class=
"identifier">spirit
</span><span class=
"special">/
</span><span class=
"identifier">core
</span><span class=
"special">.
</span><span class=
"identifier">hpp
</span><span class=
"special">></span>
84 <code><span class=
"preprocessor"> #include
</span><span class=
"special"><</span><span class=
"identifier">boost
</span><span class=
"special">/
</span><span class=
"identifier">spirit
</span><span class=
"special">/
</span><span class=
"identifier">iterator
</span><span class=
"special">/
</span><span class=
"identifier">multi_pass
</span><span class=
"special">.
</span><span class=
"identifier">hpp
</span><span class=
"special">></span><span class=
"comment">
86 </span><span class=
"keyword">using namespace
</span> <span class=
"identifier">boost
</span><span class=
"special">::
</span><span class=
"identifier">spirit
</span><span class=
"special">;
87 </span><span class=
"keyword">using namespace
</span> <span class=
"identifier">std
</span><span class=
"special">;
</span>
89 <span class=
"identifier">ifstream in
</span><span class=
"special">(
</span><span class=
"string">"input_file.txt"</span><span class=
"special">);
</span><span class=
"comment">// we get our input from this file
<br><br> </span><span class=
"keyword">typedef char
</span><span class=
"identifier">char_type
</span><span class=
"special">;
</span>
90 <span class=
"keyword">typedef
</span><span class=
"identifier">multi_pass
</span><span class=
"special"><</span><span class=
"identifier">istreambuf_iterator
</span><span class=
"special"><</span><span class=
"identifier">char_type
</span><span class=
"special">> > </span><span class=
"identifier">iterator_type
</span><span class=
"special">;
</span>
92 <span class=
"keyword">typedef
</span> <span class=
"identifier">skip_parser_iteration_policy
</span><span class=
"special"><</span><span class=
"identifier">space_parser
</span><span class=
"special">></span> <span class=
"identifier">iter_policy_type
</span><span class=
"special">;
</span>
93 <span class=
"keyword">typedef
</span> <span class=
"identifier">scanner_policies
</span><span class=
"special"><</span>iter_policy_type
<span class=
"special">></span> <span class=
"identifier">scanner_policies_type
</span><span class=
"special">;
</span>
94 <span class=
"keyword">typedef
</span> <span class=
"identifier">scanner
</span><span class=
"special"><</span>iterator_type, scanner_policies_type
<span class=
"special">></span> <span class=
"identifier">scanner_type
</span><span class=
"special">;
</span>
96 <span class=
"keyword">typedef
</span> rule
<span class=
"special"><</span>scanner_type
<span class=
"special">></span> <span class=
"identifier">rule_type
</span><span class=
"special">;
</span>
98 <span class=
"identifier">iter_policy_type
</span> <span class=
"identifier">iter_policy
</span><span class=
"special">(
</span><span class=
"identifier">space_p
</span><span class=
"special">);
</span>
99 <span class=
"identifier">scanner_policies_type
</span> <span class=
"identifier">policies
</span><span class=
"special">(
</span><span class=
"identifier">iter_policy
</span><span class=
"special">);
</span>
101 make_multi_pass(std::istreambuf_iterator
<char_type
>(in)));
103 scanner_type
<span class=
"identifier">scan
</span><span class=
"special">(
</span>
104 first
<span class=
"special">,
</span> make_multi_pass(std::istreambuf_iterator
<span class=
"special"><</span><span class=
"identifier">char_type
</span><span class=
"special">>()),
</span>
105 <span class=
"identifier">policies
</span><span class=
"special">)
</span>;
106 <span class=
"special"><br> </span><span class=
"identifier">rule_type n_list
</span><span class=
"special">=
</span><span class=
"identifier">real_p
</span><span class=
"special">>> *(
</span><span class=
"literal">','
</span><span class=
"special">>> </span><span class=
"identifier">real_p
</span><span class=
"special">);
<br> </span><span class=
"identifier">match
</span><span class=
"special"><></span><span class=
"identifier"> m
</span><span class=
"special">=
</span><span class=
"identifier">n_list
</span><span class=
"special">.
</span><span class=
"identifier">parse
</span><span class=
"special">(
</span><span class=
"identifier">scan
</span><span class=
"special">);
<br></span></code></pre>
107 <a name=
"flush_multi_pass"></a>
108 <h2>flush_multi_pass
</h2>
109 <p> There is a predefined pseudo-parser called flush_multi_pass. When this parser
110 is used with multi_pass, it will call multi_pass::clear_queue(). This will cause
111 any buffered data to be erased. This also will invalidate all other copies of
112 multi_pass and they should not be used. If they are, an boost::illegal_backtracking
113 exception will be thrown.
</p>
114 <a name=
"multi_pass_policies"></a>
115 <h2>multi_pass Policies
</h2>
116 <p> multi_pass is a templated policy driven class. The description of multi_pass
117 above is how it was originally implemented (before it used policies), and is
118 the default configuration now. But, multi_pass is capable of much more. Because
119 of the open-ended nature of policies, you can write your own policy to make
120 multi_pass behave in a way that we never before imagined.
</p>
121 <p> The multi_pass class has five template parameters:
</p>
123 <li>InputT - The type multi_pass uses to acquire it's input. This is typically
124 an input iterator, or functor.
</li>
125 <li>InputPolicy - A class that defines how multi_pass acquires it's input. The
126 InputPolicy is parameterized by InputT.
</li>
127 <li>OwnershipPolicy - This policy determines how multi_pass deals with it's
128 shared components.
</li>
129 <li>CheckingPolicy - This policy determines how checking for invalid iterators
131 <li>StoragePolicy - The buffering scheme used by multi_pass is determined and
132 managed by the StoragePolicy.
</li>
134 <a name=
"predefined_policies"></a>
135 <h2>Predefined policies
</h2>
136 <p> All predefined multi_pass policies are in the namespace boost::spirit::multi_pass_policies.
</p>
137 <a name=
"predefined_inputpolicy_classes"></a>
138 <h3>Predefined InputPolicy classes
</h3>
139 <a name=
"input_iterator"></a>
140 <h4>input_iterator
</h4>
141 <p> This policy directs multi_pass to read from an input iterator of type InputT.
</p>
142 <a name=
"lex_input"></a>
144 <p> This policy obtains it's input by calling yylex(), which would typically be
145 provided by a scanner generated by LEX. If you use this policy your code must
146 link against a LEX generated scanner.
</p>
147 <a name=
"functor_input"></a>
148 <h4>functor_input
</h4>
149 <p> This input policy obtains it's data by calling a functor of type InputT. The
150 functor must meet certain requirements. It must have a typedef called result_type
151 which should be the type returned from operator(). Also, since an input policy
152 needs a way to determine when the end of input has been reached, the functor
153 must contain a static variable named eof which is comparable to a variable of
155 <a name=
"predefined_ownershippolicy_classes"></a>
156 <h3>Predefined OwnershipPolicy classes
</h3>
157 <a name=
"ref_counted"></a>
159 <p> This class uses a reference counting scheme. multi_pass will delete it's shared
160 components when the count reaches zero.
</p>
161 <a name=
"first_owner"></a>
163 <p> When this policy is used, the first multi_pass created will be the one that
164 deletes the shared data. Each copy will not take ownership of the shared data.
165 This works well for spirit, since no dynamic allocation of iterators is done.
166 All copies are made on the stack, so the original iterator has the longest lifespan.
</p>
167 <a name=
"predefined_checkingpolicy_classes"></a>
168 <h3>Predefined CheckingPolicy classes
</h3>
169 <a name=
"no_check"></a>
171 <p> This policy does no checking at all.
</p>
172 <a name=
"buf_id_check"></a>
173 <h4>buf_id_check
</h4>
174 <p> buf_id_check keeps around a buffer id, or a buffer age. Every time clear_queue()
175 is called on a multi_pass iterator, it is possible that all other iterators
176 become invalid. When clear_queue() is called, buf_id_check increments the buffer
177 id. When an iterator is dereferenced, this policy checks that the buffer id
178 of the iterator matches the shared buffer id. This policy is most effective
179 when used together with the std_deque StoragePolicy. It should not be used with
180 the fixed_size_queue StoragePolicy, because it will not detect iterator dereferences
181 that are out of range.
</p>
182 <a name=
"full_check"></a>
184 <p> This policy has not been implemented yet. When it is, it will keep track of
185 all iterators and make sure that they are all valid.
</p>
186 <a name=
"predefined_storagepolicy_classes"></a>
187 <h3>Predefined StoragePolicy classes
</h3>
188 <a name=
"std_deque"></a>
190 <p> This policy keeps all buffered data in a std::deque. All data is stored as
191 long as there is more than one iterator. Once the iterator count goes down to
192 one, and the queue is no longer needed, it is cleared, freeing up memory. The
193 queue can also be forcibly cleared by calling multi_pass::clear_queue().
</p>
194 <a name=
"fixed_size_queue_lt_n_gt_"></a>
195 <h4>fixed_size_queue
<N
></h4>
196 <p> fixed_size_queue keeps a circular buffer that is size N+
1 and stores N elements.
197 fixed_size_queue is a template with a std::size_t parameter that specified the
198 queue size. It is your responsibility to ensure that N is big enough for your
199 parser. Whenever the foremost iterator is incremented, the last character of
200 the buffer is automatically erased. Currently there is no way to tell if an
201 iterator is trailing too far behind and has become invalid. No dynamic allocation
202 is done by this policy during normal iterator operation, only on initial construction.
203 The memory usage of this StoragePolicy is set at N+
1 bytes, unlike std_deque,
204 which is unbounded.
</p>
205 <a name=
"combinations__how_to_specify_your_own_custom_multi_pass"></a>
206 <h2>Combinations: How to specify your own custom multi_pass
</h2>
207 <p> The beauty of policy based designs is that you can mix and match policies
208 to create your own custom class by selecting the policies you want. Here's an
209 example of how to specify a custom multi_pass that wraps an istream_iterator
<char
>,
210 and is slightly more efficient than the default because it uses the first_owner
211 OwnershipPolicy and the no_check CheckingPolicy:
</p>
212 <pre> <code><span class=
"keyword">typedef
</span><span class=
"identifier">multi_pass
</span><span class=
"special"><<br> </span><span class=
"identifier">istream_iterator
</span><span class=
"special"><</span><span class=
"keyword">char
</span><span class=
"special">>,
<br> </span><span class=
"identifier">multi_pass_policies
</span><span class=
"special">::
</span><span class=
"identifier">input_iterator
</span><span class=
"special">,
<br> </span><span class=
"identifier">multi_pass_policies
</span><span class=
"special">::
</span><span class=
"identifier">first_owner
</span><span class=
"special">,
<br> </span><span class=
"identifier">multi_pass_policies
</span><span class=
"special">::
</span><span class=
"identifier">no_check
</span><span class=
"special">,
<br> </span><span class=
"identifier">multi_pass_policies
</span><span class=
"special">::
</span><span class=
"identifier">std_deque
<br> </span><span class=
"special">> </span><span class=
"identifier">first_owner_multi_pass_type
</span><span class=
"special">;
<br></span></code></pre>
213 <p> The default template parameters for multi_pass are: input_iterator InputPolicy,
214 ref_counted OwnershipPolicy, buf_id_check CheckingPolicy and std_deque StoragePolicy.
215 So if you use multi_pass
<istream_iterator
<char
> > you will get those
216 pre-defined behaviors while wrapping an istream_iterator
<char
>.
</p>
217 <p> There is one other pre-defined class called look_ahead. look_ahead has two
218 template parameters: InputT, the type of the input iterator to wrap, and a std::size_t
219 N, which specifies the size of the buffer to the fixed_size_queue policy. While
220 the default multi_pass configuration is designed for safey, look_ahead is designed
221 for speed. look_ahead is derived from a multi_pass with the following policies:
222 input_iterator InputPolicy, first_owner OwnershipPolicy, no_check CheckingPolicy,
223 and fixed_size_queue
<N
> StoragePolicy.
</p>
224 <a name=
"how_to_write_a_functor_for_use_with_the_functor_input_inputpolicy"></a>
225 <h3>How to write a functor for use with the functor_input InputPolicy
</h3>
226 <p> If you want to use the functor_input InputPolicy, you can write your own functor
227 that will supply the input to multi_pass. The functor must satisfy two requirements.
228 It must have a typedef result_type which specifies the return type of operator().
229 This is standard practice in the STL. Also, it must supply a static variable
230 called eof which is compared against to know whether the input has reached the
231 end. Here is an example:
</p>
232 <pre> <code><span class=
"keyword">class
</span><span class=
"identifier">my_functor
<br> </span><span class=
"special">{
<br> </span><span class=
"keyword">public
</span><span class=
"special">:
<br><br> </span><span class=
"keyword">typedef char
</span><span class=
"identifier">result_type
</span><span class=
"special">;
<br><br> </span><span class=
"identifier">my_functor
</span><span class=
"special">()
<br> :
</span><span class=
"identifier">c
</span><span class=
"special">(
</span><span class=
"literal">'A'
</span><span class=
"special">) {}
<br><br> </span><span class=
"keyword">char operator
</span><span class=
"special">()()
</span><span class=
"keyword">const
<br> </span><span class=
"special">{
<br> </span><span class=
"keyword">if
</span><span class=
"special">(
</span><span class=
"identifier">c
</span><span class=
"special">==
</span><span class=
"literal">'M'
</span><span class=
"special">)
<br> </span><span class=
"keyword">return
</span><span class=
"identifier">eof
</span><span class=
"special">;
<br> </span><span class=
"keyword">else
<br> return
</span><span class=
"identifier">c
</span><span class=
"special">++;
<br> }
<br><br> </span><span class=
"keyword">static
</span><span class=
"identifier">result_type eof
</span><span class=
"special">;
<br><br> </span><span class=
"keyword">private
</span><span class=
"special">:
<br><br> </span><span class=
"keyword">char
</span><span class=
"identifier">c
</span><span class=
"special">;
<br> };
<br><br> </span><span class=
"identifier">my_functor
</span><span class=
"special">::
</span><span class=
"identifier">result_type my_functor
</span><span class=
"special">::
</span><span class=
"identifier">eof
</span><span class=
"special">=
</span><span class=
"literal">'\
0'
</span><span class=
"special">;
<br><br> </span><span class=
"keyword">typedef
</span><span class=
"identifier">multi_pass
</span><span class=
"special"><<br> </span><span class=
"identifier">my_functor
</span><span class=
"special">,
<br> </span><span class=
"identifier">multi_pass_policies
</span><span class=
"special">::
</span><span class=
"identifier">functor_input
</span><span class=
"special">,
<br> </span><span class=
"identifier">multi_pass_policies
</span><span class=
"special">::
</span><span class=
"identifier">first_owner
</span><span class=
"special">,
<br> </span><span class=
"identifier">multi_pass_policies
</span><span class=
"special">::
</span><span class=
"identifier">no_check
</span><span class=
"special">,
<br> </span><span class=
"identifier">multi_pass_policies
</span><span class=
"special">::
</span><span class=
"identifier">std_deque
<br> </span><span class=
"special">> </span><span class=
"identifier">functor_multi_pass_type
</span><span class=
"special">;
<br><br> </span><span class=
"identifier">functor_multi_pass_type first
</span><span class=
"special">=
</span><span class=
"identifier">functor_multi_pass_type
</span><span class=
"special">(
</span><span class=
"identifier">my_functor
</span><span class=
"special">());
<br> </span><span class=
"identifier">functor_multi_pass_type last
</span><span class=
"special">;
<br></span></code></pre>
233 <a name=
"how_to_write_policies_for_use_with_multi_pass"></a>
234 <h3>How to write policies for use with multi_pass
</h3>
235 <a name=
"inputpolicy"></a>
237 <p> An InputPolicy must have the following interface:
</p>
238 <pre> <code><span class=
"keyword">class
</span><span class=
"identifier">my_input_policy
</span><span class=
"comment">// your policy name
<br> </span><span class=
"special">{
<br> </span><span class=
"keyword">public
</span><span class=
"special">:
<br><br> </span><span class=
"comment">// class inner will be instantiated with the type given
<br> // as the InputT parameter to multi_pass.
<br><br> </span><span class=
"keyword">template
</span><span class=
"special"><</span><span class=
"keyword">typename
</span><span class=
"identifier">InputT
</span><span class=
"special">><br> </span><span class=
"keyword">class
</span><span class=
"identifier">inner
<br> </span><span class=
"special">{
<br> </span><span class=
"keyword">public
</span><span class=
"special">:
<br><br> </span><span class=
"comment">// these typedefs determine the iterator_traits for multi_pass
<br> </span><span class=
"keyword">typedef
</span><span class=
"identifier">x
</span><span class=
"identifier">value_type
</span><span class=
"special">;
<br> </span><span class=
"keyword">typedef
</span><span class=
"identifier">x
</span><span class=
"identifier">difference_type
</span><span class=
"special">;
<br> </span><span class=
"keyword">typedef
</span><span class=
"identifier">x
</span><span class=
"identifier">pointer
</span><span class=
"special">;
<br> </span><span class=
"keyword">typedef
</span><span class=
"identifier">x
</span><span class=
"identifier">reference
</span><span class=
"special">;
<br><br> </span><span class=
"keyword">protected
</span><span class=
"special">:
<br><br> </span><span class=
"identifier">inner
</span><span class=
"special">();
<br> </span><span class=
"identifier">inner
</span><span class=
"special">(
</span><span class=
"identifier">InputT
</span><span class=
"identifier">x
</span><span class=
"special">);
<br> </span><span class=
"identifier">inner
</span><span class=
"special">(
</span><span class=
"identifier">inner
</span><span class=
"keyword">const
</span><span class=
"special">& </span><span class=
"identifier">x
</span><span class=
"special">);
<br> </span><span class=
"comment">// delete or clean up any state
<br> </span><span class=
"keyword">void
</span><span class=
"identifier">destroy
</span><span class=
"special">();
<br> </span><span class=
"comment">// return true if *this and x have the same input
<br> </span><span class=
"keyword">bool
</span><span class=
"identifier">same_input
</span><span class=
"special">(
</span><span class=
"identifier">inner
</span><span class=
"keyword">const
</span><span class=
"special">& </span><span class=
"identifier">x
</span><span class=
"special">)
</span><span class=
"keyword">const
</span><span class=
"special">;
<br> </span><span class=
"keyword">void
</span><span class=
"identifier">swap
</span><span class=
"special">(
</span><span class=
"identifier">inner
</span><span class=
"special">& </span><span class=
"identifier">x
</span><span class=
"special">);
<br><br> </span><span class=
"keyword">public
</span><span class=
"special">:
<br><br> </span><span class=
"comment">// get an instance from the input
<br> </span><span class=
"identifier">result_type
</span><span class=
"identifier">get_input
</span><span class=
"special">()
</span><span class=
"keyword">const
</span><span class=
"special">;
<br> </span><span class=
"comment">// advance the input
<br> </span><span class=
"keyword">void
</span><span class=
"identifier">advance_input
</span><span class=
"special">();
<br> </span><span class=
"comment">// return true if the input is at the end
<br> </span><span class=
"keyword">bool
</span><span class=
"identifier">input_at_eof
</span><span class=
"special">()
</span><span class=
"keyword">const
</span><span class=
"special">;
<br> </span><span class=
"special">};
<br> </span><span class=
"special">};
<br></span></code></pre>
239 <p> Because of the way that multi_pass shares a buffer and input among multiple
240 copies, class inner should keep a pointer to it's input. The copy constructor
241 should simply copy the pointer. destroy() should delete it. same_input should
242 compare the pointers. For more details see the various implementations of InputPolicy
244 <a name=
"ownershippolicy"></a>
245 <h4>OwnershipPolicy
</h4>
246 <p> The OwnershipPolicy must have the following interface:
</p>
247 <pre> <code><span class=
"keyword">class
</span><span class=
"identifier">my_ownership_policy
<br> </span><span class=
"special">{
<br> </span><span class=
"keyword">protected
</span><span class=
"special">:
<br><br> </span><span class=
"identifier">my_ownership_policy
</span><span class=
"special">();
<br> </span><span class=
"identifier">my_ownership_policy
</span><span class=
"special">(
</span><span class=
"identifier">my_ownership_policy
</span><span class=
"keyword">const
</span><span class=
"special">& </span><span class=
"identifier">x
</span><span class=
"special">);
<br> </span><span class=
"comment">// clone is called when a copy of the iterator is made
<br> </span><span class=
"keyword">void
</span><span class=
"identifier">clone
</span><span class=
"special">();
<br> </span><span class=
"comment">// called when a copy is deleted. Return true to indicate
<br> // resources should be released
<br> </span><span class=
"keyword">bool
</span><span class=
"identifier">release
</span><span class=
"special">();
<br> </span><span class=
"keyword">void
</span><span class=
"identifier">swap
</span><span class=
"special">(
</span><span class=
"identifier">my_ownership_policy
</span><span class=
"special">& </span><span class=
"identifier">x
</span><span class=
"special">);
<br><br> </span><span class=
"keyword">public
</span><span class=
"special">:
<br> </span><span class=
"comment">// returns true if there is only one iterator in existence.
<br> // std_dequeue StoragePolicy will free it's buffered data if this
<br> // returns true.
<br> </span><span class=
"keyword">bool
</span><span class=
"identifier">unique
</span><span class=
"special">()
</span><span class=
"keyword">const
</span><span class=
"special">;
<br> </span><span class=
"special">};
<br></span></code></pre>
248 <a name=
"checkingpolicy"></a>
249 <h4>CheckingPolicy
</h4>
250 <p> The CheckingPolicy must have the following interface:
</p>
251 <pre> <code><span class=
"keyword">class
</span><span class=
"identifier">my_check
<br> </span><span class=
"special">{
<br> </span><span class=
"keyword">protected
</span><span class=
"special">:
<br><br> </span><span class=
"identifier">my_check
</span><span class=
"special">();
<br> </span><span class=
"identifier">my_check
</span><span class=
"special">(
</span><span class=
"identifier">my_check
</span><span class=
"keyword">const
</span><span class=
"special">& </span><span class=
"identifier">x
</span><span class=
"special">);
<br> </span><span class=
"keyword">void
</span><span class=
"identifier">destroy
</span><span class=
"special">();
<br> </span><span class=
"keyword">void
</span><span class=
"identifier">swap
</span><span class=
"special">(
</span><span class=
"identifier">my_check
</span><span class=
"special">& </span><span class=
"identifier">x
</span><span class=
"special">);
<br> </span><span class=
"comment">// check should make sure that this iterator is valid
<br> </span><span class=
"keyword">void
</span><span class=
"identifier">check_if_valid
</span><span class=
"special">()
</span><span class=
"keyword">const
</span><span class=
"special">;
<br> </span><span class=
"keyword">void
</span><span class=
"identifier">clear_queue
</span><span class=
"special">();
<br> </span><span class=
"special">};
<br></span></code></pre>
252 <a name=
"storagepolicy"></a>
253 <h4>StoragePolicy
</h4>
254 <p> A StoragePolicy must have the following interface:
</p>
255 <pre> <code><span class=
"keyword">class
</span><span class=
"identifier">my_storage_policy
<br> </span><span class=
"special">{
<br> </span><span class=
"keyword">public
</span><span class=
"special">:
<br><br> </span><span class=
"comment">// class inner will be instantiated with the value_type from the InputPolicy
<br><br> </span><span class=
"keyword">template
</span><span class=
"special"><</span><span class=
"keyword">typename
</span><span class=
"identifier">ValueT
</span><span class=
"special">><br> </span><span class=
"keyword">class
</span><span class=
"identifier">inner
<br> </span><span class=
"special">{
<br> </span><span class=
"keyword">protected
</span><span class=
"special">:
<br><br> </span><span class=
"identifier">inner
</span><span class=
"special">();
<br> </span><span class=
"identifier">inner
</span><span class=
"special">(
</span><span class=
"identifier">inner
</span><span class=
"keyword">const
</span><span class=
"special">& </span><span class=
"identifier">x
</span><span class=
"special">);
<br> </span><span class=
"comment">// will be called from the destructor of the last iterator.
<br> </span><span class=
"keyword">void
</span><span class=
"identifier">destroy
</span><span class=
"special">();
<br> </span><span class=
"keyword">void
</span><span class=
"identifier">swap
</span><span class=
"special">(
</span><span class=
"identifier">inner
</span><span class=
"special">& </span><span class=
"identifier">x
</span><span class=
"special">);
<br> </span><span class=
"comment">// This is called when the iterator is dereferenced. It's a template
<br> // method so we can recover the type of the multi_pass iterator
<br> // and access it.
<br> </span><span class=
"keyword">template
</span><span class=
"special"><</span><span class=
"keyword">typename
</span><span class=
"identifier">MultiPassT
</span><span class=
"special">><br> </span><span class=
"keyword">static
</span><span class=
"identifier">ValueT
</span><span class=
"identifier">dereference
</span><span class=
"special">(
</span><span class=
"identifier">MultiPassT
</span><span class=
"keyword">const
</span><span class=
"special">& </span><span class=
"identifier">mp
</span><span class=
"special">);
<br> </span><span class=
"comment">// This is called when the iterator is incremented. It's a template
<br> // method so we can recover the type of the multi_pass iterator
<br> // and access it.
<br> </span><span class=
"keyword">template
</span><span class=
"special"><</span><span class=
"keyword">typename
</span><span class=
"identifier">MultiPassT
</span><span class=
"special">><br> </span><span class=
"keyword">static
</span><span class=
"keyword">void
</span><span class=
"identifier">increment
</span><span class=
"special">(
</span><span class=
"identifier">MultiPassT
</span><span class=
"special">& </span><span class=
"identifier">mp
</span><span class=
"special">);
<br> </span><span class=
"keyword">void
</span><span class=
"identifier">clear_queue
</span><span class=
"special">();
<br> </span><span class=
"comment">// called to determine whether the iterator is an eof iterator
<br> </span><span class=
"keyword">template
</span><span class=
"special"><</span><span class=
"keyword">typename
</span><span class=
"identifier">MultiPassT
</span><span class=
"special">><br> </span><span class=
"keyword">static
</span><span class=
"keyword">bool
</span><span class=
"identifier">is_eof
</span><span class=
"special">(
</span><span class=
"identifier">MultiPassT
</span><span class=
"keyword">const
</span><span class=
"special">& </span><span class=
"identifier">mp
</span><span class=
"special">);
<br> </span><span class=
"comment">// called by operator==
<br> </span><span class=
"keyword">bool
</span><span class=
"identifier">equal_to
</span><span class=
"special">(
</span><span class=
"identifier">inner
</span><span class=
"keyword">const
</span><span class=
"special">& </span><span class=
"identifier">x
</span><span class=
"special">)
</span><span class=
"keyword">const
</span><span class=
"special">;
<br> </span><span class=
"comment">// called by operator
<<br> </span><span class=
"keyword">bool
</span><span class=
"identifier">less_than
</span><span class=
"special">(
</span><span class=
"identifier">inner
</span><span class=
"keyword">const
</span><span class=
"special">& </span><span class=
"identifier">x
</span><span class=
"special">)
</span><span class=
"keyword">const
</span><span class=
"special">;
<br> </span><span class=
"special">};
</span><span class=
"comment"> // class inner
<br> </span><span class=
"special">};
<br></span></code></pre>
256 <p> A StoragePolicy is the trickiest policy to write. You should study and understand
257 the existing StoragePolicy classes before you try and write your own.
</p>
262 <td width=
"30"><a href=
"../index.html"><img src=
"theme/u_arr.gif" border=
"0"></a></td>
263 <td width=
"30"><a href=
"trees.html"><img src=
"theme/l_arr.gif" border=
"0"></a></td>
264 <td width=
"30"><a href=
"file_iterator.html"><img src=
"theme/r_arr.gif" border=
"0"></a></td>
269 <p class=
"copyright">Copyright
© 2001-
2002 Daniel C. Nuffer
<br>
271 <font size=
"2">Use, modification and distribution is subject to the Boost Software
272 License, Version
1.0. (See accompanying file LICENSE_1_0.txt or copy at
273 http://www.boost.org/LICENSE_1_0.txt)
</font> </p>
274 <p class=
"copyright"> </p>
projects / ceph.git / blob