1/*
2 *  @copyright
3 *  Copyright (C) 2009-2013, Intel Corporation
4 *  All rights reserved.
5 *
6 *  @copyright
7 *  Redistribution and use in source and binary forms, with or without
8 *  modification, are permitted provided that the following conditions
9 *  are met:
10 *
11 *    * Redistributions of source code must retain the above copyright
12 *      notice, this list of conditions and the following disclaimer.
13 *    * Redistributions in binary form must reproduce the above copyright
14 *      notice, this list of conditions and the following disclaimer in
15 *      the documentation and/or other materials provided with the
16 *      distribution.
17 *    * Neither the name of Intel Corporation nor the names of its
18 *      contributors may be used to endorse or promote products derived
19 *      from this software without specific prior written permission.
20 *
21 *  @copyright
22 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
25 *  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
26 *  HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
28 *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
29 *  OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
30 *  AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
32 *  WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 *  POSSIBILITY OF SUCH DAMAGE.
34 *
35 */
36
37/*
38 * reducer_ostream.h
39 *
40 * Purpose: Hyper-object to write to 'std::ostream's
41 *
42 * Classes: reducer_ostream
43 *
44 * Description:
45 * ============
46 * Output streams ('std::ostream's) are a convenient means of writing text to
47 * files, the user console, or sockets.  In a serial program, text is written
48 * to an ostream in a specific, logical order.  For example, computing while
49 * traversing a data structure and printing them to an 'ostream' will result
50 * in the values being printed in the order of traversal.  In a parallel
51 * version of the same program, however, different parts of the data structure
52 * may be traversed in a different order, resulting in a non-deterministic
53 * ordering of the stream.  Worse, multiple strands may write to the same
54 * stream simultaneously, resulting in a data race.  Replacing the
55 * 'std::ostream' with a 'cilk::reducer_ostream' will solve both problems: Data
56 * will appeaer in the stream in the same order as it would for the serial
57 * program, and there will be no races (no locks) on the common stream.
58 *
59 * Usage Example:
60 * ==============
61 * Assume we wish to traverse an array of objects, performing an operation on
62 * each object and writing the result to a file.  Without a reducer_ostream,
63 * we have a race on the 'output' file stream:
64 *..
65 *  void compute(std::ostream& os, double x)
66 *  {
67 *      // Perform some significant computation and print the result:
68 *      os << std::asin(x);
69 *  }
70 *
71 *  int test()
72 *  {
73 *      const std::size_t ARRAY_SIZE = 1000000;
74 *      extern double myArray[ARRAY_SIZE];
75 *
76 *      std::ofstream output("output.txt");
77 *      cilk_for (std::size_t i = 0; i < ARRAY_SIZE; ++i)
78 *      {
79 *          compute(output, myArray[i]);
80 *      }
81 *
82 *      return 0;
83 *  }
84 *..
85 * The race is solved by using a reducer_ostream to proxy the 'output' file:
86 *..
87 *  void compute(cilk::reducer_ostream& os, double x)
88 *  {
89 *      // Perform some significant computation and print the result:
90 *      *os << std::asin(x);
91 *  }
92 *
93 *  int test()
94 *  {
95 *      const std::size_t ARRAY_SIZE = 1000000;
96 *      extern double myArray[ARRAY_SIZE];
97 *
98 *      std::ofstream output("output.txt");
99 *      cilk::reducer_ostream hyper_output(output);
100 *      cilk_for (std::size_t i = 0; i < ARRAY_SIZE; ++i)
101 *      {
102 *          compute(hyper_output, myArray[i]);
103 *      }
104 *
105 *      return 0;
106 *  }
107 *..
108 *
109 * Limitations:
110 * ============
111 * There are two possible values for the formatting flags immediately after a
112 * 'cilk_spawn' statement: they may either have the value that was set by the
113 * spawn function, or they may have default values.  Because of
114 * non-determinism in the processor scheduling, there is no way to determine
115 * which it will be.  Similarly, the formatting flags after a 'cilk_sync' may
116 * or may not have the same value as before the sync.  Therefore, one must use
117 * a disciplined coding style to avoid formatting errors.  There are two
118 * approaches to mitigating the problem: The first is to eliminate the
119 * difference between the two possible outcomes by ensuring that the spawned
120 * function always returns the flags to their initial state:
121 *..
122 *  void compute(cilk::reducer_ostream& os, double x)
123 *  {
124 *      // Perform some significant computation and print the result:
125 *      int saveprec = os.precision(5);
126 *      os << std::asin(x);
127 *      os.precision(saveprec);
128 *  }
129 *..
130 * The second approach is to write your streaming operations such that they
131 * don't depend on the previous state of the formatting flags by setting any
132 * important flags before every block of output:
133 *..
134 *      cilk_spawn compute(hyper_output, value);
135 *
136 *      hyper_output->precision(2);  // Don't depend on previous precision
137 *      *hyper_output << f();
138 *      *hyper_output << g();
139 *..
140 * Another concern is memory usage.  A reducer_ostream will buffer as much text
141 * as necessary to ensure that the order of output matches that of the serial
142 * version of the program.  If all spawn branches perform an equal amount of
143 * output, then one can expect that half of the output before a sync will be
144 * buffered in memory.  This hyperobject is therefore not well suited for
145 * serializing very large quantities of text output.
146 */
147
148#ifndef REDUCER_OSTREAM_H_INCLUDED
149#define REDUCER_OSTREAM_H_INCLUDED
150
151#include <cilk/reducer.h>
152#include <iostream>
153#include <sstream>
154
155namespace cilk {
156
157/**
158 * @brief Class 'reducer_ostream' is the representation of a hyperobject for
159 * output text streaming.
160 */
161class reducer_ostream
162{
163public:
164    /// Internal representation of the per-strand view of the data for reducer_ostream
165    class View: public std::ostream
166    {
167    public:
168        /// Type of the std::stream reducer_ostream is based on
169        typedef std::ostream Base;
170
171        friend class reducer_ostream;
172
173        View():
174            std::ostream(0)
175        {
176            Base::rdbuf(&strbuf_);
177        };
178
179    private:
180        void use_ostream (const std::ostream &os)
181        {
182            Base::rdbuf(os.rdbuf());
183            Base::flags(os.flags());       // Copy formatting flags
184            Base::setstate(os.rdstate());  // Copy error state
185        }
186
187    private:
188        std::stringbuf  strbuf_;
189    };
190
191public:
192    /// Definition of data view, operation, and identity for reducer_ostream
193    struct Monoid: monoid_base< View >
194    {
195        static void reduce (View *left, View *right);
196    };
197
198private:
199    // Hyperobject to serve up views
200    reducer<Monoid> imp_;
201
202    // Methods that provide the API for the reducer
203public:
204
205    // Construct an initial 'reducer_ostream' from an 'std::ostream'.  The
206    // specified 'os' stream is used as the eventual destination for all
207    // text streamed to this hyperobject.
208    explicit reducer_ostream(const std::ostream &os);
209
210    // Return a modifiable reference to the underlying 'ostream' object.
211    std::ostream& get_reference();
212
213    /**
214     * Append data from some type to the reducer_ostream
215     *
216     * @param v Value to be appended to the reducer_ostream
217     */
218    template<typename T>
219    std::ostream &
220    operator<< (const T &v)
221    {
222        return imp_.view() << v;
223    }
224
225    /**
226     * Append data from a std::ostream to the reducer_ostream
227     *
228     * @param _Pfn std::ostream to copy from
229     */
230    std::ostream &
231    operator<< (std::ostream &(*_Pfn)(std::ostream &))
232    {
233        View &v = imp_.view();
234
235        return ((*_Pfn)(v));
236    }
237
238    reducer_ostream&       operator*()       { return *this; }
239    reducer_ostream const& operator*() const { return *this; }
240
241    reducer_ostream*       operator->()       { return this; }
242    reducer_ostream const* operator->() const { return this; }
243};
244
245
246// -------------------------------------------
247// class reducer_ostream::Monoid
248// -------------------------------------------
249
250/**
251 * Appends string from "right" reducer_basic_string onto the end of
252 * the "left". When done, the "right" reducer_basic_string is empty.
253 */
254void
255reducer_ostream::Monoid::reduce(View *left, View *right)
256{
257    left->operator<< (&right->strbuf_);
258}
259
260// --------------------------
261// class reducer_ostream
262// --------------------------
263
264/**
265 * Construct a reducer_ostream which will write to the specified std::ostream
266 *
267 * @param os std::ostream to write to
268 */
269inline
270reducer_ostream::reducer_ostream(const std::ostream &os) :
271    imp_()
272{
273    View &v = imp_.view();
274
275    v.use_ostream(os);
276}
277
278/**
279 * Get a reference to the std::ostream
280 */
281inline
282std::ostream &
283reducer_ostream::get_reference()
284{
285    View &v = imp_.view();
286
287    return v;
288}
289
290} // namespace cilk
291
292#endif //  REDUCER_OSTREAM_H_INCLUDED
293
294