STXXL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
scan.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/algo/scan.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2002-2004 Roman Dementiev <[email protected]>
7  * Copyright (C) 2008, 2009 Andreas Beckmann <[email protected]>
8  * Copyright (C) 2013 Timo Bingmann <[email protected]>
9  *
10  * Distributed under the Boost Software License, Version 1.0.
11  * (See accompanying file LICENSE_1_0.txt or copy at
12  * http://www.boost.org/LICENSE_1_0.txt)
13  **************************************************************************/
14 
15 #ifndef STXXL_ALGO_SCAN_HEADER
16 #define STXXL_ALGO_SCAN_HEADER
17 
18 #include <stxxl/bits/namespace.h>
19 #include <stxxl/bits/mng/config.h>
22 
24 
25 //! \addtogroup stlalgo
26 //! \{
27 
28 /*!
29  * External equivalent of std::for_each, see \ref design_algo_foreach.
30  *
31  * stxxl::for_each applies the function object \c functor to each element in
32  * the range [first, last); \c functor's return value, if any, is
33  * ignored. Applications are performed in forward order, i.e. from first to
34  * last. stxxl::for_each returns the function object after it has been applied
35  * to each element. To overlap I/O and computation \c nbuffers used (a value
36  * at least \a D is recommended). The size of the buffers is derived from the
37  * container that is pointed by the iterators.
38  *
39  * \remark The implementation exploits STXXL buffered streams (computation and I/O overlapped).
40  *
41  * \param begin object of model of \c ext_random_access_iterator concept
42  * \param end object of model of \c ext_random_access_iterator concept
43  * \param functor function object of model of \c std::UnaryFunction concept
44  * \param nbuffers number of buffers (blocks) for internal use (should be at least 2*D )
45  * \return function object \c functor after it has been applied to the each element of the given range
46  *
47  * \warning nested stxxl::for_each are not supported
48  */
49 template <typename ExtIterator, typename UnaryFunction>
50 UnaryFunction for_each(ExtIterator begin, ExtIterator end,
51  UnaryFunction functor, int_type nbuffers = 0)
52 {
53  if (begin == end)
54  return functor;
55 
56  typedef typename ExtIterator::value_type value_type;
57 
58  typedef buf_istream<
59  typename ExtIterator::block_type,
60  typename ExtIterator::bids_container_iterator
61  > buf_istream_type;
62 
63  begin.flush(); // flush container
64 
65  if (nbuffers == 0)
66  nbuffers = 2 * config::get_instance()->disks_number();
67 
68  // create prefetching stream,
69  buf_istream_type in(begin.bid(), end.bid() + ((end.block_offset()) ? 1 : 0), nbuffers);
70 
71  ExtIterator cur = begin - begin.block_offset();
72 
73  // leave part of the block before begin untouched (e.g. copy)
74  for ( ; cur != begin; ++cur)
75  {
76  value_type tmp;
77  in >> tmp;
78  }
79 
80  // apply functor to the range [begin,end)
81  for ( ; cur != end; ++cur)
82  {
83  value_type tmp;
84  in >> tmp;
85  functor(tmp);
86  }
87 
88  // leave part of the block after end untouched
89  if (end.block_offset())
90  {
91  ExtIterator last_block_end = end - end.block_offset() + ExtIterator::block_type::size;
92  for ( ; cur != last_block_end; ++cur)
93  {
94  value_type tmp;
95  in >> tmp;
96  }
97  }
98 
99  return functor;
100 }
101 
102 /*!
103  * External equivalent of std::for_each (mutating), see \ref design_algo_foreachm
104  *
105  * stxxl::for_each_m applies the function object \c functor to each element in
106  * the range [first, last); \c functor's return value, if any, is
107  * ignored. Applications are performed in forward order, i.e. from first to
108  * last. stxxl::for_each_m returns the function object after it has been
109  * applied to each element. To overlap I/O and computation \c nbuffers are used
110  * (a value at least \a 2D is recommended). The size of the buffers is derived
111  * from the container that is pointed by the iterators.
112  *
113  * \remark The implementation exploits STXXL buffered streams (computation and
114  * I/O overlapped)
115  *
116  * \param begin object of model of \c ext_random_access_iterator concept
117  * \param end object of model of \c ext_random_access_iterator concept
118  * \param functor object of model of \c std::UnaryFunction concept
119  * \param nbuffers number of buffers (blocks) for internal use (should be at least 2*D )
120  * \return function object \c functor after it has been applied to the each element of the given range
121  *
122  * \warning nested stxxl::for_each_m are not supported
123  */
124 template <typename ExtIterator, typename UnaryFunction>
125 UnaryFunction for_each_m(ExtIterator begin, ExtIterator end,
126  UnaryFunction functor, int_type nbuffers = 0)
127 {
128  if (begin == end)
129  return functor;
130 
131  typedef typename ExtIterator::value_type value_type;
132 
133  typedef buf_istream<
134  typename ExtIterator::block_type,
135  typename ExtIterator::bids_container_iterator
136  > buf_istream_type;
137 
138  typedef buf_ostream<
139  typename ExtIterator::block_type,
140  typename ExtIterator::bids_container_iterator
141  > buf_ostream_type;
142 
143  begin.flush(); // flush container
144 
145  if (nbuffers == 0)
146  nbuffers = 2 * config::get_instance()->disks_number();
147 
148  // create prefetching stream,
149  buf_istream_type in(begin.bid(), end.bid() + ((end.block_offset()) ? 1 : 0), nbuffers / 2);
150  // create buffered write stream for blocks
151  buf_ostream_type out(begin.bid(), nbuffers / 2);
152  // REMARK: these two streams do I/O while
153  // functor is being computed (overlapping for free)
154 
155  ExtIterator cur = begin - begin.block_offset();
156 
157  // leave part of the block before begin untouched (e.g. copy)
158  for ( ; cur != begin; ++cur)
159  {
160  value_type tmp;
161  in >> tmp;
162  out << tmp;
163  }
164 
165  // apply functor to the range [begin,end)
166  for ( ; cur != end; ++cur)
167  {
168  value_type tmp;
169  in >> tmp;
170  functor(tmp);
171  out << tmp;
172  }
173 
174  // leave part of the block after end untouched
175  if (end.block_offset())
176  {
177  ExtIterator _last_block_end = end - end.block_offset() + ExtIterator::block_type::size;
178  for ( ; cur != _last_block_end; ++cur)
179  {
180  value_type tmp;
181  in >> tmp;
182  out << tmp;
183  }
184  }
185 
186  return functor;
187 }
188 
189 /*!
190  * External equivalent of std::generate, see \ref design_algo_generate.
191  *
192  * Generate assigns the result of invoking \c generator, a function object that
193  * takes no arguments, to each element in the range [first, last). To overlap
194  * I/O and computation \c nbuffers are used (a value at least \a D is
195  * recommended). The size of the buffers is derived from the container that is
196  * pointed by the iterators.
197  *
198  * \remark The implementation exploits STXXL buffered streams (computation and
199  * I/O overlapped).
200  *
201  * \param begin object of model of \c ext_random_access_iterator concept
202  * \param end object of model of \c ext_random_access_iterator concept
203  * \param generator function object of model of \c std::generator concept
204  * \param nbuffers number of buffers (blocks) for internal use (should be at least 2*D, or zero for automaticl 2*D)
205  */
206 template <typename ExtIterator, typename Generator>
207 void generate(ExtIterator begin, ExtIterator end,
208  Generator generator, int_type nbuffers = 0)
209 {
210  typedef typename ExtIterator::block_type block_type;
211 
212  typedef buf_ostream<
213  block_type, typename ExtIterator::bids_container_iterator
214  > buf_ostream_type;
215 
216  while (begin.block_offset()) // go to the beginning of the block
217  // of the external vector
218  {
219  if (begin == end)
220  return;
221 
222  *begin = generator();
223  ++begin;
224  }
225 
226  begin.flush(); // flush container
227 
228  if (nbuffers == 0)
229  nbuffers = 2 * config::get_instance()->disks_number();
230 
231  // create buffered write stream for blocks
232  buf_ostream_type outstream(begin.bid(), nbuffers);
233 
234  assert(begin.block_offset() == 0);
235 
236  // delay calling block_externally_updated() until the block is
237  // completely filled (and written out) in outstream
238  typename ExtIterator::const_iterator prev_block = begin;
239 
240  while (end != begin)
241  {
242  if (begin.block_offset() == 0) {
243  if (prev_block != begin) {
244  prev_block.block_externally_updated();
245  prev_block = begin;
246  }
247  }
248 
249  *outstream = generator();
250  ++begin;
251  ++outstream;
252  }
253 
254  typename ExtIterator::const_iterator out = begin;
255 
256  while (out.block_offset()) // filling the rest of the block
257  {
258  *outstream = *out;
259  ++out;
260  ++outstream;
261  }
262 
263  if (prev_block != out)
264  prev_block.block_externally_updated();
265 
266  begin.flush();
267 }
268 
269 /*!
270  * External equivalent of std::find, see \ref design_algo_find.
271  *
272  * Returns the first iterator \a i in the range [first, last) such that <tt>*i
273  * == value</tt>. Returns last if no such iterator exists. To overlap I/O and
274  * computation \c nbuffers are used (a value at least \a D is recommended). The
275  * size of the buffers is derived from the container that is pointed by the
276  * iterators.
277  *
278  * \remark The implementation exploits STXXL buffered streams (computation and
279  * I/O overlapped).
280  *
281  * \param begin object of model of \c ext_random_access_iterator concept
282  * \param end object of model of \c ext_random_access_iterator concept
283  * \param value value that is equality comparable to the ExtIterator's value type
284  * \param nbuffers number of buffers (blocks) for internal use (should be at least 2*D)
285  * \return first iterator \c i in the range [begin,end) such that *( \c i ) == \c value, if no
286  * such exists then \c end
287  */
288 template <typename ExtIterator, typename EqualityComparable>
289 ExtIterator find(ExtIterator begin, ExtIterator end,
290  const EqualityComparable& value, int_type nbuffers = 0)
291 {
292  if (begin == end)
293  return end;
294 
295  typedef buf_istream<
296  typename ExtIterator::block_type,
297  typename ExtIterator::bids_container_iterator
298  > buf_istream_type;
299 
300  begin.flush(); // flush container
301 
302  if (nbuffers == 0)
303  nbuffers = 2 * config::get_instance()->disks_number();
304 
305  // create prefetching stream,
306  buf_istream_type in(begin.bid(), end.bid() + ((end.block_offset()) ? 1 : 0), nbuffers);
307 
308  ExtIterator cur = begin - begin.block_offset();
309 
310  // skip part of the block before begin untouched
311  for ( ; cur != begin; ++cur)
312  ++in;
313 
314  // search in the the range [begin,end)
315  for ( ; cur != end; ++cur)
316  {
317  typename ExtIterator::value_type tmp;
318  in >> tmp;
319  if (tmp == value)
320  return cur;
321  }
322 
323  return cur;
324 }
325 
326 //! \}
327 
329 
330 #endif // !STXXL_ALGO_SCAN_HEADER
331 // vim: et:ts=4:sw=4
Buffered output stream.
Definition: buf_ostream.h:29
self_type & flush()
Force flush of current block, for finishing writing within a block.
Definition: buf_ostream.h:109
UnaryFunction for_each(ExtIterator begin, ExtIterator end, UnaryFunction functor, int_type nbuffers=0)
External equivalent of std::for_each, see stxxl::for_each.
Definition: scan.h:50
UnaryFunction for_each_m(ExtIterator begin, ExtIterator end, UnaryFunction functor, int_type nbuffers=0)
External equivalent of std::for_each (mutating), see stxxl::for_each_m (mutating).
Definition: scan.h:125
choose_int_types< my_pointer_size >::int_type int_type
Definition: types.h:63
void generate(ExtIterator begin, ExtIterator end, Generator generator, int_type nbuffers=0)
External equivalent of std::generate, see stxxl::generate.
Definition: scan.h:207
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
Buffered input stream.
Definition: buf_istream.h:34
ExtIterator find(ExtIterator begin, ExtIterator end, const EqualityComparable &value, int_type nbuffers=0)
External equivalent of std::find, see stxxl::find.
Definition: scan.h:289
#define STXXL_END_NAMESPACE
Definition: namespace.h:17