2
Copyright 2005-2007 Adobe Systems Incorporated
3
Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
4
or a copy at http://stlab.adobe.com/licenses.html)
7
/*************************************************************************************************/
10
#define ADOBE_MOVE_HPP
16
#include <boost/iterator/iterator_adaptor.hpp>
17
#include <boost/mpl/bool.hpp>
18
#include <boost/mpl/and.hpp>
19
#include <boost/mpl/or.hpp>
20
#include <boost/mpl/not.hpp>
21
#include <boost/mpl/assert.hpp>
22
#include <boost/range/begin.hpp>
23
#include <boost/range/end.hpp>
24
#include <boost/type_traits/is_convertible.hpp>
25
#include <boost/type_traits/is_same.hpp>
26
#include <boost/type_traits/is_class.hpp>
27
#include <boost/utility/enable_if.hpp>
30
\defgroup move_related Move Library
33
The move library is a collection of utilities for creating and using types that leverage
34
return value optimization (RVO) to avoid unnecessary copies.
36
\section move_tutorial Tutorial
37
User defined types often have remote parts either because they are implemented using a
38
pointer-to-implementation or are variable sized. Such objects can be expensive to copy
39
and are often copied unnecessarily when they are returned from functions or stored in other
40
objects or containers. The \ref move_related is a collection of utilities to implement types which
41
can be moved to elide copying in such situations as well as utilities to assist in moving value.
43
\par Implementing a Movable Type
45
A movable type models \ref concept_movable. There are three components of a movable type:
46
- Satisfy the requirements of concept \ref concept_regular_type.
47
- Implement a move-ctor using move_from<>.
48
- Modify the assignment operator to take the operand by value and consume it.
50
A typical implementation of the move-ctor will simply extract the remote part, leaving the
51
source in a destructible state.
53
The assignment operator takes the operand parameter by value. Typically the simplest way
54
to destory the local remote part and consume the remote part of the operand is to swap
55
contents with the operand. This is similar to the copy-ctor and swap idiom for implementing
58
Listing 1 shows an example movable class that implements a typical pointer-to-implementation
59
(PiPl) idiom and shows that it can be used as any regular type.
65
#include <boost/operators.hpp>
67
#include <adobe/move.hpp>
71
struct implementation : boost::equality_comparable<implementation>
73
explicit implementation(int x = 0) : member(x) { }
75
implementation(const implementation& x) : member(x.member)
76
{ std::cout << "copy remote part: " << member << std::endl; }
78
implementation& operator=(const implementation& x)
81
std::cout << "assign remote part: " << member << std::endl;
85
friend bool operator==(const implementation& x, const implementation& y)
86
{ return x.member == y.member; }
91
class movable : public boost::equality_comparable<movable>
94
// model concept Regular
96
explicit movable(int x = 0) : member(new implementation(x)) { }
97
~movable() { delete member; }
98
movable(const movable& x) : member(new implementation(*x.member)) { }
99
// operator=() implemented below
101
friend bool operator==(const movable& x, const movable &y)
102
{ return *x.member == *y.member; }
104
friend void swap(movable& x, movable& y)
105
{ swap(x.member, y.member); }
107
// model concept Movable
109
// move-ctor assumes ownership of remote part
110
movable(adobe::move_from<movable> x) : member(x.source.member)
111
{ x.source.member = 0; }
113
// operator=() on a movable type takes parameter by value and consumes it
114
movable& operator=(movable x)
115
{ swap(*this, x); return *this; }
118
implementation* member;
129
<center>Listing 1</center>
134
<center>Output of Listing 1</center>
136
\par Returning a Movable Type
138
We can return a movable type from a function by value and unnessary copies will be avoided as
139
Listing 2 illustrates:
143
movable f(int x, int y)
144
{ return movable(x * y); }
148
movable x = f(10, 5);
155
<center>Listing 2</center>
160
<center>Ouput of Listing 2</center>
162
In this example it is not necessary to make any copies. The result of f() is constructed directly
163
in place for x through a compiler optimization known as return value optimization or RVO. In the
164
case of assigning to y, the same optimization allows the compiler to construct the operand for
165
assignment as the result of f() which is them moved into y.
167
\par Implementing a Sink Function
169
A <em>sink</em> is any function that copies it's argument, usually for the purpose of storing it.
170
A sink is often a constructor or an insert function on a container. The \c operator=() on a movable
171
type is a form of a sink function. To implement a sink function pass the argument by value and then
172
use \c adobe::move() to move the argument into place. Note that this technique cannot be used to
173
implement \c operator=() on because it relies on assignment. Listing 3 implements an example sink
181
explicit sink(movable x) : member(adobe::move(x)) { }
188
movable x = f(10, 5);
189
sink y(x); // must copy.
190
sink z(f(20, 2)); // no copy.
195
<center>Listing 3</center>
200
<center>Output of Listing 3</center>
202
Here again unnessary copies are eliminated. Although adobe::move() can be used anytime to force the
203
move of an object, it should only be used as part of an explicit sink function otherwise it hinders
204
the understanding of code.
208
There are many utilities as part of the move library which can be used to move elements instead of
209
copying them. These are useful when building containers or dealing with sink operations which must
210
manage a collection of movable objects. Generally these operations parallel the associated copying
211
algorithms from STL. Examples:
214
<tr><td><b>Move</b></td><td><b>Copy</b></td><td><b>Comment</b></td></tr>
215
<tr><td>adobe::move()</td><td>std::copy</td><td>Not to be confused with the single argument adobe::move()</td></tr>
216
<tr><td>adobe::move_backward()</td><td>std::copy_backward</td></tr>
217
<tr><td>adobe::back_move_iterator()</td><td>std::back_insert_iterator</td></tr>
218
<tr><td>adobe::back_mover()</td><td>std::back_inserter</td></tr>
219
<tr><td>adobe::move_construct()</td><td>std::construct</td></tr>
220
<tr><td>adobe::uninitialized_move()</td><td>std::uninitialized_copy</td></tr>
225
The \c adobe::move() function is a NOP if the argument is not movable, however, when a non-movable
226
item is passed to a sink this may still result in an unnecessary copy - one to the sink and one to
227
copy the argument of the sink into place. To avoid the additional copy, two forms of a sink function
228
can be provided, one for movable types and one for copyable types. The \c adobe::move_sink<> and
229
\c adobe::copy_sink<> tags can be used to select between the two functions. See the
230
implementation of \c adobe::move_construct() as an example.
232
If a sink function is a member of a template class, the same issue with regard to unnecessary copies
233
can occur. In this case, it is desirable to distinguish between the a copy and move sink as above
234
but also to allow implicit conversions to the type stored in the container. To allow this use the
235
two argument form of \c adobe::move_sink<> and \c adobe::copy_sink<>. See the implementation of
236
\c adobe::vector::push_back() as an example.
238
\par Theory of Operation
240
<em>to be written</em>
242
\par Acknowledgments:
243
The move library was inspired by the move library written by Dave Abrahams and the work on move
244
done by Dave Abrahams and Howard Hinnant.
247
/*************************************************************************************************/
251
/*************************************************************************************************/
253
namespace implementation {
255
/*************************************************************************************************/
257
template <typename T>
258
struct class_has_move_assign {
260
typedef T& (T::*E)(T t);
261
typedef char (&no_type)[1];
262
typedef char (&yes_type)[2];
263
template <E e> struct sfinae { typedef yes_type type; };
265
static typename sfinae<&U::operator=>::type test(int);
267
static no_type test(...);
269
enum {value = sizeof(test<T>(1)) == sizeof(yes_type)};
273
/*************************************************************************************************/
276
struct has_move_assign : boost::mpl::and_<boost::is_class<T>, class_has_move_assign<T> > {};
278
/*************************************************************************************************/
280
class test_can_convert_anything { };
282
/*************************************************************************************************/
284
} //namespace implementation
287
/*************************************************************************************************/
290
REVISIT (sparent@adobe.com): This is a work around for Boost 1.34.1 and VC++ 2008 where
291
boost::is_convertible<T, T> fails to compile.
294
template <typename T, typename U>
295
struct is_convertible : boost::mpl::or_<
296
boost::is_same<T, U>,
297
boost::is_convertible<T, U>
301
\ingroup move_related
302
\brief move_from is used for move_ctors.
305
template <typename T>
308
explicit move_from(T& x) : source(x) { }
313
\ingroup move_related
314
\brief The is_movable trait can be used to identify movable types.
316
template <typename T>
317
struct is_movable : boost::mpl::and_<
318
boost::is_convertible<move_from<T>, T>,
319
implementation::has_move_assign<T>,
320
boost::mpl::not_<boost::is_convertible<implementation::test_can_convert_anything, T> >
323
/*************************************************************************************************/
326
\ingroup move_related
327
\brief copy_sink and move_sink are used to select between overloaded operations according to
328
whether type T is movable and convertible to type U.
332
template <typename T,
335
struct copy_sink : boost::enable_if<
337
adobe::is_convertible<T, U>,
338
boost::mpl::not_<is_movable<T> >
344
/*************************************************************************************************/
347
\ingroup move_related
348
\brief move_sink and copy_sink are used to select between overloaded operations according to
349
whether type T is movable and convertible to type U.
353
template <typename T,
356
struct move_sink : boost::enable_if<
358
adobe::is_convertible<T, U>,
365
/*************************************************************************************************/
368
\ingroup move_related
369
\brief This version of move is selected when T is_movable . It in turn calls the move
370
constructor. This call, with the help of the return value optimization, will cause x to be moved
371
instead of copied to its destination. See adobe/test/move/main.cpp for examples.
374
template <typename T>
375
T move(T& x, typename move_sink<T>::type = 0) { return T(move_from<T>(x)); }
377
/*************************************************************************************************/
380
\ingroup move_related
381
\brief This version of move is selected when T is not movable . The net result will be that
384
template <typename T>
385
T& move(T& x, typename copy_sink<T>::type = 0) { return x; }
387
/*************************************************************************************************/
390
\ingroup move_related
391
\brief Iterator pair version of move. Similar to std::copy but with move semantics,
392
for movable types, otherwise with copy semantics.
394
template <typename I, // I models InputIterator
395
typename O> // O models OutputIterator
396
O move(I f, I l, O result)
405
/*************************************************************************************************/
408
\ingroup move_related
409
\brief \ref concept_convertible_to_range version of move. Similar to copy but with move semantics,
410
for movable types, otherwise with copy semantics.
412
template <typename I, // I models InputRange
413
typename O> // O models OutputIterator
414
inline O move(I& in, O out) { return move(boost::begin(in), boost::end(in), out); }
416
/*************************************************************************************************/
419
\ingroup move_related
420
\brief Iterator pair version of move_backwards. Similar to std::copy_backwards but with move semantics,
421
for movable types, otherwise with copy semantics.
423
template <typename I, // I models BidirectionalIterator
424
typename O> // O models BidirectionalIterator
425
O move_backward(I f, I l, O result)
434
/*************************************************************************************************/
437
\ingroup move_related
438
\brief \ref concept_convertible_to_range version of move_backwards. Similar to std::copy_backwards but
439
with move semantics, for movable types, otherwise with copy semantics.
441
template <typename I, // I models BidirectionalRange
442
typename O> // O models BidirectionalIterator
443
inline O move_backward(I& in, O out)
444
{ return move_backward(boost::begin(in), boost::end(in), out); }
446
/*************************************************************************************************/
449
\ingroup move_related
450
\brief Similar to std::back_insert_iterator but
451
with move semantics, for movable types, otherwise with copy semantics.
454
template <typename C> // C models Container
455
class back_move_iterator : public std::iterator<std::output_iterator_tag, void, void, void, void>
460
typedef C container_type;
462
explicit back_move_iterator(C& x) : container_m(&x) { }
464
back_move_iterator& operator=(typename C::value_type x)
465
{ container_m->push_back(move(x)); return *this; }
467
back_move_iterator& operator*() { return *this; }
468
back_move_iterator& operator++() { return *this; }
469
back_move_iterator& operator++(int) { return *this; }
472
/*************************************************************************************************/
475
\ingroup move_related
476
\brief Similar to std::back_inserter but
477
with move semantics, for movable types, otherwise with copy semantics.
480
template <typename C> // C models Container
481
inline back_move_iterator<C> back_mover(C& x) { return back_move_iterator<C>(x); }
483
/*************************************************************************************************/
486
\ingroup move_related
487
\brief Placement move construction, selected when T is_movable is true
490
template <typename T, typename U> // T models Regular
491
inline void move_construct(T* p, U& x, typename move_sink<U, T>::type = 0)
493
::new(static_cast<void*>(p)) T(move(x));
496
/*************************************************************************************************/
500
\ingroup move_related
501
\brief Placement copy construction, selected when T is_movable is false
503
template <typename T, typename U> // T models Regular
504
inline void move_construct(T* p, const U& x, typename copy_sink<U, T>::type = 0)
506
::new(static_cast<void*>(p)) T(x);
509
/*************************************************************************************************/
512
\ingroup move_related
513
\brief Similar to std::uninitialized_copy but
514
with move semantics, for movable types.
516
template <typename I, // I models InputIterator
517
typename F> // F models ForwardIterator
518
F uninitialized_move(I f, I l, F r,
519
typename move_sink<typename std::iterator_traits<I>::value_type>::type = 0)
522
move_construct(&*r, *f);
528
/*************************************************************************************************/
531
\ingroup move_related
532
\brief Behaves as to std::uninitialized_copy , invoked when I's value_type is not movable.
534
template <typename I, // I models InputIterator
535
typename F> // F models ForwardIterator
536
F uninitialized_move(I f, I l, F r,
537
typename copy_sink<typename std::iterator_traits<I>::value_type>::type = 0)
539
return std::uninitialized_copy(f, l, r);
542
/*************************************************************************************************/
546
/*************************************************************************************************/
550
/*************************************************************************************************/
added
removed
src/mlib/adobe/move.hpp
