JezK
Edit File: reducer_string.h
/* reducer_string.h -*- C++ -*- * * @copyright * Copyright (C) 2009-2013, Intel Corporation * All rights reserved. * * @copyright * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * * Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * Neither the name of Intel Corporation nor the names of its * contributors may be used to endorse or promote products derived * from this software without specific prior written permission. * * @copyright * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */ /** @file reducer_string.h * * @brief Defines classes for doing parallel string creation by appending. * * @ingroup ReducersString * * @see ReducersString */ #ifndef REDUCER_STRING_H_INCLUDED #define REDUCER_STRING_H_INCLUDED #include <cilk/reducer.h> #include <string> #include <list> /** @defgroup ReducersString String Reducers * * String reducers allow the creation of a string by concatenating a set of * strings or characters in parallel. * * @ingroup Reducers * * You should be familiar with @ref pagereducers "Cilk reducers", described in * file reducers.md, and particularly with @ref reducers_using, before trying * to use the information in this file. * * @section redstring_usage Usage Example * * vector<Data> data; * void expensive_string_computation(const Data& x, string& s); * cilk::reducer<cilk::op_string> r; * cilk_for (int i = 0; i != data.size(); ++i) { * string temp; * expensive_string_computation(data[i], temp); * *r += temp; * } * string result; * r.move_out(result); * * @section redstring_monoid The Monoid * * @subsection redstring_monoid_values Value Set * * The value set of a string reducer is the set of values of the class * `std::basic_string<Char, Traits, Alloc>`, which we refer to as “the * reducer’s string type”. * * @subsection redstring_monoid_operator Operator * * The operator of a string reducer is the string concatenation operator, * defined by the “`+`” binary operator on the reducer’s string type. * * @subsection redstring_monoid_identity Identity * * The identity value of a string reducer is the empty string, which is the * value of the expression * `std::basic_string<Char, Traits, Alloc>([allocator])`. * * @section redstring_operations Operations * * In the operation descriptions below, the type name `String` refers to the * reducer’s string type, `std::basic_string<Char, Traits, Alloc>`. * * @subsection redstring_constructors Constructors * * Any argument list which is valid for a `std::basic_string` constructor is * valid for a string reducer constructor. The usual move-in constructor is * also provided: * * reducer(move_in(String& variable)) * * @subsection redstring_get_set Set and Get * * r.set_value(const String& value) * const String& = r.get_value() const * r.move_in(String& variable) * r.move_out(String& variable) * * @subsection redstring_initial Initial Values * * A string reducer with no constructor arguments, or with only an allocator * argument, will initially contain the identity value, an empty string. * * @subsection redstring_view_ops View Operations * * *r += a * r->append(a) * r->append(a, b) * r->push_back(a) * * These operations on string reducer views are the same as the corresponding * operations on strings. * * @section redstring_performance Performance Considerations * * String reducers work by creating a string for each view, collecting those * strings in a list, and then concatenating them into a single result string * at the end of the computation. This last step takes place in serial code, * and necessarily takes time proportional to the length of the result string. * Thus, a parallel string reducer cannot actually speed up the time spent * directly creating the string. This trivial example would probably be slower * (because of reducer overhead) than the corresponding serial code: * * vector<string> a; * reducer<op_string> r; * cilk_for (int i = 0; i != a.length(); ++i) { * *r += a[i]; * } * string result; * r.move_out(result); * * What a string reducer _can_ do is to allow the _remainder_ of the * computation to be done in parallel, without having to worry about managing * the string computation. * * The strings for new views are created (by the view identity constructor) * using the same allocator as the string that was created when the reducer * was constructed. Note that this allocator is determined when the reducer is * constructed. The following two examples may have very different behavior: * * string<Char, Traits, Allocator> a_string; * * reducer< op_string<Char, Traits, Allocator> reducer1(move_in(a_string)); * ... parallel computation ... * reducer1.move_out(a_string); * * reducer< op_string<Char, Traits, Allocator> reducer2; * reducer2.move_in(a_string); * ... parallel computation ... * reducer2.move_out(a_string); * * * `reducer1` will be constructed with the same allocator as `a_string`, * because the string was specified in the constructor. The `move_in` * and `move_out` can therefore be done with a `swap` in constant time. * * `reducer2` will be constructed with a _default_ allocator of type * `Allocator`, which may not be the same as the allocator of `a_string`. * Therefore, the `move_in` and `move_out` may have to be done with a copy * in _O(N)_ time. * * (All instances of an allocator type with no internal state (like * `std::allocator`) are “the same”. You only need to worry about the “same * allocator” issue when you create string reducers with custom allocator * types.) * * @section redstring_types Type and Operator Requirements * * `std::basic_string<Char, Traits, Alloc>` must be a valid type. */ namespace cilk { /** @ingroup ReducersString */ //@{ /** The string append reducer view class. * * This is the view class for reducers created with * `cilk::reducer< cilk::op_basic_string<Type, Traits, Allocator> >`. It holds * the accumulator variable for the reduction, and allows only append * operations to be performed on it. * * @note The reducer “dereference” operation (`reducer::operator *()`) * yields a reference to the view. Thus, for example, the view class’s * `append` operation would be used in an expression like * `r->append(a)`, where `r` is a string append reducer variable. * * @tparam Char The string element type (not the string type). * @tparam Traits The character traits type. * @tparam Alloc The string allocator type. * * @see ReducersString * @see op_basic_string */ template<typename Char, typename Traits, typename Alloc> class op_basic_string_view { typedef std::basic_string<Char, Traits, Alloc> string_type; typedef std::list<string_type> list_type; typedef typename string_type::size_type size_type; // The view's value is represented by a list of strings and a single // string. The value is the concatenation of the strings in the list with // the single string at the end. All string operations apply to the single // string; reduce operations cause lists of partial strings from multiple // strands to be combined. // mutable string_type m_string; mutable list_type m_list; // Before returning the value of the reducer, concatenate all the strings // in the list with the single string. // void flatten() const { if (m_list.empty()) return; typename list_type::iterator i; size_type len = m_string.size(); for (i = m_list.begin(); i != m_list.end(); ++i) len += i->size(); string_type result(get_allocator()); result.reserve(len); for (i = m_list.begin(); i != m_list.end(); ++i) result += *i; m_list.clear(); result += m_string; result.swap(m_string); } public: /** @name Monoid support. */ //@{ /// Required by @ref monoid_with_view typedef string_type value_type; /// Required by @ref op_string Alloc get_allocator() const { return m_string.get_allocator(); } /** Reduction operation. * * This function is invoked by the @ref op_basic_string monoid to combine * the views of two strands when the right strand merges with the left * one. It appends the value contained in the right-strand view to the * value contained in the left-strand view, and leaves the value in the * right-strand view undefined. * * @param right A pointer to the right-strand view. (`this` points to * the left-strand view.) * * @note Used only by the @ref op_basic_string monoid to implement the * monoid reduce operation. */ void reduce(op_basic_string_view* right) { if (!right->m_string.empty() || !right->m_list.empty()) { // (list, string) + (right_list, right_string) => // (list + {string} + right_list, right_string) if (!m_string.empty()) { // simulate m_list.push_back(std::move(m_string)) m_list.push_back(string_type(get_allocator())); m_list.back().swap(m_string); } m_list.splice(m_list.end(), right->m_list); m_string.swap(right->m_string); } } //@} /** @name Pass constructor arguments through to the string constructor. */ //@{ op_basic_string_view() : m_string() {} template <typename T1> op_basic_string_view(const T1& x1) : m_string(x1) {} template <typename T1, typename T2> op_basic_string_view(const T1& x1, const T2& x2) : m_string(x1, x2) {} template <typename T1, typename T2, typename T3> op_basic_string_view(const T1& x1, const T2& x2, const T3& x3) : m_string(x1, x2, x3) {} template <typename T1, typename T2, typename T3, typename T4> op_basic_string_view(const T1& x1, const T2& x2, const T3& x3, const T4& x4) : m_string(x1, x2, x3, x4) {} //@} /** Move-in constructor. */ explicit op_basic_string_view(move_in_wrapper<value_type> w) : m_string(w.value().get_allocator()) { m_string.swap(w.value()); } /** @name @ref reducer support. */ //@{ void view_move_in(string_type& s) { m_list.clear(); if (m_string.get_allocator() == s.get_allocator()) // Equal allocators. Do a (fast) swap. m_string.swap(s); else // Unequal allocators. Do a (slow) copy. m_string = s; s.clear(); } void view_move_out(string_type& s) { flatten(); if (m_string.get_allocator() == s.get_allocator()) // Equal allocators. Do a (fast) swap. m_string.swap(s); else // Unequal allocators. Do a (slow) copy. s = m_string; m_string.clear(); } void view_set_value(const string_type& s) { m_list.clear(); m_string = s; } string_type const& view_get_value() const { flatten(); return m_string; } string_type & view_get_reference() { flatten(); return m_string; } string_type const& view_get_reference() const { flatten(); return m_string; } //@} /** @name View modifier operations. * * @details These simply wrap the corresponding operations on the underlying string. */ //@{ template <typename T> op_basic_string_view& operator +=(const T& x) { m_string += x; return *this; } template <typename T1> op_basic_string_view& append(const T1& x1) { m_string.append(x1); return *this; } template <typename T1, typename T2> op_basic_string_view& append(const T1& x1, const T2& x2) { m_string.append(x1, x2); return *this; } template <typename T1, typename T2, typename T3> op_basic_string_view& append(const T1& x1, const T2& x2, const T3& x3) { m_string.append(x1, x2, x3); return *this; } void push_back(const Char x) { m_string.push_back(x); } //@} }; /** String append monoid class. Instantiate the cilk::reducer template class * with an op_basic_string monoid to create a string append reducer class. For * example, to concatenate a collection of standard strings: * * cilk::reducer< cilk::op_basic_string<char> > r; * * @tparam Char The string element type (not the string type). * @tparam Traits The character traits type. * @tparam Alloc The string allocator type. * @tparam Align If `false` (the default), reducers instantiated on this * monoid will be naturally aligned (the Cilk library 1.0 * behavior). If `true`, reducers instantiated on this monoid * will be cache-aligned for binary compatibility with * reducers in Cilk library version 0.9. * * @see ReducersString * @see op_basic_string_view * @see reducer_basic_string * @see op_string * @see op_wstring */ template<typename Char, typename Traits = std::char_traits<Char>, typename Alloc = std::allocator<Char>, bool Align = false> class op_basic_string : public monoid_with_view< op_basic_string_view<Char, Traits, Alloc>, Align > { typedef monoid_with_view< op_basic_string_view<Char, Traits, Alloc>, Align > base; Alloc m_allocator; public: /** View type of the monoid. */ typedef typename base::view_type view_type; /** Constructor. * * There is no default constructor for string monoids, because the * allocator must always be specified. * * @param allocator The list allocator to be used when * identity-constructing new views. */ op_basic_string(const Alloc& allocator = Alloc()) : m_allocator(allocator) {} /** Create an identity view. * * String view identity constructors take the string allocator as an * argument. * * @param v The address of the uninitialized memory in which the view * will be constructed. */ void identity(view_type *v) const { ::new((void*) v) view_type(m_allocator); } /** @name Construct functions * * A string append reduction monoid must have a copy of the allocator of * the leftmost view’s string, so that it can use it in the `identity` * operation. This, in turn, requires that string reduction monoids have a * specialized `construct()` function. * * All string reducer monoid `construct()` functions first construct the * leftmost view, using the arguments that were passed in from the reducer * constructor. They then call the view’s `get_allocator()` function to * get the string allocator from the string in the leftmost view, and pass * that to the monoid constructor. */ //@{ static void construct(op_basic_string* monoid, view_type* view) { provisional( new ((void*)view) view_type() ).confirm_if( new ((void*)monoid) op_basic_string(view->get_allocator()) ); } template <typename T1> static void construct(op_basic_string* monoid, view_type* view, const T1& x1) { provisional( new ((void*)view) view_type(x1) ).confirm_if( new ((void*)monoid) op_basic_string(view->get_allocator()) ); } template <typename T1, typename T2> static void construct(op_basic_string* monoid, view_type* view, const T1& x1, const T2& x2) { provisional( new ((void*)view) view_type(x1, x2) ).confirm_if( new ((void*)monoid) op_basic_string(view->get_allocator()) ); } template <typename T1, typename T2, typename T3> static void construct(op_basic_string* monoid, view_type* view, const T1& x1, const T2& x2, const T3& x3) { provisional( new ((void*)view) view_type(x1, x2, x3) ).confirm_if( new ((void*)monoid) op_basic_string(view->get_allocator()) ); } template <typename T1, typename T2, typename T3, typename T4> static void construct(op_basic_string* monoid, view_type* view, const T1& x1, const T2& x2, const T3& x3, const T4& x4) { provisional( new ((void*)view) view_type(x1, x2, x3, x4) ).confirm_if( new ((void*)monoid) op_basic_string(view->get_allocator()) ); } //@} }; /** Convenience typedef for 8-bit strings */ typedef op_basic_string<char> op_string; /** Convenience typedef for 16-bit strings */ typedef op_basic_string<wchar_t> op_wstring; /** Deprecated string append reducer class. * * reducer_basic_string is the same as @ref reducer<@ref op_basic_string>, * except that reducer_basic_string is a proxy for the contained view, so that * accumulator variable update operations can be applied directly to the * reducer. For example, a value is appended to a `reducer<%op_basic_string>` * with `r->push_back(a)`, but a value can be appended to a `%reducer_opand` * with `r.push_back(a)`. * * @deprecated Users are strongly encouraged to use `reducer<monoid>` * reducers rather than the old wrappers like reducer_basic_string. * The `reducer<monoid>` reducers show the reducer/monoid/view * architecture more clearly, are more consistent in their * implementation, and present a simpler model for new * user-implemented reducers. * * @note Implicit conversions are provided between `%reducer_basic_string` * and `reducer<%op_basic_string>`. This allows incremental code * conversion: old code that used `%reducer_basic_string` can pass a * `%reducer_basic_string` to a converted function that now expects a * pointer or reference to a `reducer<%op_basic_string>`, and vice * versa. * * @tparam Char The string element type (not the string type). * @tparam Traits The character traits type. * @tparam Alloc The string allocator type. * * @see op_basic_string * @see reducer * @see ReducersString */ template<typename Char, typename Traits = std::char_traits<Char>, typename Alloc = std::allocator<Char> > class reducer_basic_string : public reducer< op_basic_string<Char, Traits, Alloc, true> > { typedef reducer< op_basic_string<Char, Traits, Alloc, true> > base; using base::view; public: /// The reducer’s string type. typedef typename base::value_type string_type; /// The reducer’s primitive component type. typedef Char basic_value_type; /// The string size type. typedef typename string_type::size_type size_type; /// The view type for the reducer. typedef typename base::view_type View; /// The monoid type for the reducer. typedef typename base::monoid_type Monoid; /** @name Constructors */ //@{ /** @name Forward constructor calls to the base class. * * All basic_string constructor forms are supported. */ //@{ reducer_basic_string() {} template <typename T1> reducer_basic_string(const T1& x1) : base(x1) {} template <typename T1, typename T2> reducer_basic_string(const T1& x1, const T2& x2) : base(x1, x2) {} template <typename T1, typename T2, typename T3> reducer_basic_string(const T1& x1, const T2& x2, const T3& x3) : base(x1, x2, x3) {} template <typename T1, typename T2, typename T3, typename T4> reducer_basic_string(const T1& x1, const T2& x2, const T3& x3, const T4& x4) : base(x1, x2, x3, x4) {} //@} /** Allow mutable access to the string within the current view. * * @warning If this method is called before the parallel calculation is * complete, the string returned by this method will be a * partial result. * * @returns A mutable reference to the string within the current view. */ string_type &get_reference() { return view().view_get_reference(); } /** Allow read-only access to the string within the current view. * * @warning If this method is called before the parallel calculation is * complete, the string returned by this method will be a * partial result. * * @returns A const reference to the string within the current view. */ string_type const &get_reference() const { return view().view_get_reference(); } /** @name Append to the string. * * These operations are simply forwarded to the view. */ //@{ void append(const Char *ptr) { view().append(ptr); } void append(const Char *ptr, size_type count) { view().append(ptr, count); } void append(const string_type &str, size_type offset, size_type count) { view().append(str, offset, count); } void append(const string_type &str) { view().append(str); } void append(size_type count, Char ch) { view().append(count, ch); } // Append to the string reducer_basic_string<Char, Traits, Alloc> &operator+=(Char ch) { view() += ch; return *this; } reducer_basic_string<Char, Traits, Alloc> &operator+=(const Char *ptr) { view() += ptr; return *this; } reducer_basic_string<Char, Traits, Alloc> &operator+=(const string_type &right) { view() += right; return *this; } //@} /** @name Dereference * @details Dereferencing a wrapper is a no-op. It simply returns the * wrapper. Combined with the rule that the wrapper forwards view * operations to its contained view, this means that view operations can * be written the same way on reducers and wrappers, which is convenient * for incrementally converting old code using wrappers to use reducers * instead. That is: * * reducer<op_string> r; * r->push_back(a); // r-> returns the view * // push_back() is a view member function * * reducer_string w; * w->push_back(a); // *w returns the wrapper * // push_back() is a wrapper member function * // that calls the corresponding view function */ //@{ reducer_basic_string& operator*() { return *this; } reducer_basic_string const& operator*() const { return *this; } reducer_basic_string* operator->() { return this; } reducer_basic_string const* operator->() const { return this; } //@} /** @name Upcast * @details In Cilk library 0.9, reducers were always cache-aligned. In * library 1.0, reducer cache alignment is optional. By default, reducers * are unaligned (i.e., just naturally aligned), but legacy wrappers * inherit from cache-aligned reducers for binary compatibility. * * This means that a wrapper will automatically be upcast to its aligned * reducer base class. The following conversion operators provide * pseudo-upcasts to the corresponding unaligned reducer class. */ //@{ operator reducer< op_basic_string<Char, Traits, Alloc, false> >& () { return *reinterpret_cast< reducer< op_basic_string<Char, Traits, Alloc, false> >* >(this); } operator const reducer< op_basic_string<Char, Traits, Alloc, false> >& () const { return *reinterpret_cast< const reducer< op_basic_string<Char, Traits, Alloc, false> >* >(this); } //@} }; /** Convenience typedef for 8-bit strings */ typedef reducer_basic_string<char> reducer_string; /** Convenience typedef for 16-bit strings */ typedef reducer_basic_string<wchar_t> reducer_wstring; /// @cond internal /// @cond internal /** Metafunction specialization for reducer conversion. * * This specialization of the @ref legacy_reducer_downcast template class * defined in reducer.h causes the `reducer< op_basic_string<Char> >` class to * have an `operator reducer_basic_string<Char>& ()` conversion operator that * statically downcasts the `reducer<op_basic_string>` to the corresponding * `reducer_basic_string` type. (The reverse conversion, from * `reducer_basic_string` to `reducer<op_basic_string>`, is just an upcast, * which is provided for free by the language.) * * @ingroup ReducersString */ template<typename Char, typename Traits, typename Alloc, bool Align> struct legacy_reducer_downcast< reducer<op_basic_string<Char, Traits, Alloc, Align> > > { typedef reducer_basic_string<Char, Traits, Alloc> type; }; /// @endcond //@} } // namespace cilk #endif // REDUCER_STRING_H_INCLUDED