diff options
Diffstat (limited to 'include/EASTL/internal/copy_help.h')
| -rw-r--r-- | include/EASTL/internal/copy_help.h | 215 |
1 files changed, 215 insertions, 0 deletions
diff --git a/include/EASTL/internal/copy_help.h b/include/EASTL/internal/copy_help.h new file mode 100644 index 0000000..e5fb2ab --- /dev/null +++ b/include/EASTL/internal/copy_help.h @@ -0,0 +1,215 @@ +///////////////////////////////////////////////////////////////////////////// +// Copyright (c) Electronic Arts Inc. All rights reserved. +///////////////////////////////////////////////////////////////////////////// + + +#ifndef EASTL_INTERNAL_COPY_HELP_H +#define EASTL_INTERNAL_COPY_HELP_H + + +#if defined(EA_PRAGMA_ONCE_SUPPORTED) + #pragma once +#endif + +#include <EASTL/internal/config.h> +#include <EASTL/type_traits.h> +#include <EASTL/iterator.h> +#include <string.h> // memcpy, memcmp, memmove + + +namespace eastl +{ + /// move / move_n / move_backward + /// copy / copy_n / copy_backward + /// + /// We want to optimize move, move_n, move_backward, copy, copy_backward, copy_n to do memmove operations + /// when possible. + /// + /// We could possibly use memcpy, though it has stricter overlap requirements than the move and copy + /// algorithms and would require a runtime if/else to choose it over memmove. In particular, memcpy + /// allows no range overlap at all, whereas move/copy allow output end overlap and move_backward/copy_backward + /// allow output begin overlap. Despite this it might be useful to use memcpy for any platforms where + /// memcpy is significantly faster than memmove, and since in most cases the copy/move operation in fact + /// doesn't target overlapping memory and so memcpy would be usable. + /// + /// We can use memmove/memcpy if the following hold true: + /// InputIterator and OutputIterator are of the same type. + /// InputIterator and OutputIterator are of type contiguous_iterator_tag or simply are pointers (the two are virtually synonymous). + /// is_trivially_copyable<T>::value is true. i.e. the constructor T(const T& t) (or T(T&& t) if present) can be replaced by memmove(this, &t, sizeof(T)) + /// + /// copy normally differs from move, but there is a case where copy is the same as move: when copy is + /// used with a move_iterator. We handle that case here by detecting that copy is being done with a + /// move_iterator and redirect it to move (which can take advantage of memmove/memcpy). + /// + /// The generic_iterator class is typically used for wrapping raw memory pointers so they can act like + /// formal iterators. Since pointers provide an opportunity for memmove/memcpy operations, we can + /// detect a generic iterator and use it's wrapped type as a pointer if it happens to be one. + + // Implementation moving copying both trivial and non-trivial data via a lesser iterator than random-access. + template <typename /*InputIteratorCategory*/, bool /*isMove*/, bool /*canMemmove*/> + struct move_and_copy_helper + { + template <typename InputIterator, typename OutputIterator> + static OutputIterator move_or_copy(InputIterator first, InputIterator last, OutputIterator result) + { + for(; first != last; ++result, ++first) + *result = *first; + return result; + } + }; + + // Specialization for copying non-trivial data via a random-access iterator. It's theoretically faster because the compiler can see the count when its a compile-time const. + // This specialization converts the random access InputIterator last-first to an integral type. There's simple way for us to take advantage of a random access output iterator, + // as the range is specified by the input instead of the output, and distance(first, last) for a non-random-access iterator is potentially slow. + template <> + struct move_and_copy_helper<EASTL_ITC_NS::random_access_iterator_tag, false, false> + { + template <typename InputIterator, typename OutputIterator> + static OutputIterator move_or_copy(InputIterator first, InputIterator last, OutputIterator result) + { + typedef typename eastl::iterator_traits<InputIterator>::difference_type difference_type; + + for(difference_type n = (last - first); n > 0; --n, ++first, ++result) + *result = *first; + + return result; + } + }; + + // Specialization for moving non-trivial data via a lesser iterator than random-access. + template <typename InputIteratorCategory> + struct move_and_copy_helper<InputIteratorCategory, true, false> + { + template <typename InputIterator, typename OutputIterator> + static OutputIterator move_or_copy(InputIterator first, InputIterator last, OutputIterator result) + { + for(; first != last; ++result, ++first) + *result = eastl::move(*first); + return result; + } + }; + + // Specialization for moving non-trivial data via a random-access iterator. It's theoretically faster because the compiler can see the count when its a compile-time const. + template <> + struct move_and_copy_helper<EASTL_ITC_NS::random_access_iterator_tag, true, false> + { + template <typename InputIterator, typename OutputIterator> + static OutputIterator move_or_copy(InputIterator first, InputIterator last, OutputIterator result) + { + typedef typename eastl::iterator_traits<InputIterator>::difference_type difference_type; + + for(difference_type n = (last - first); n > 0; --n, ++first, ++result) + *result = eastl::move(*first); + + return result; + } + }; + + // Specialization for when we can use memmove/memcpy. See the notes above for what conditions allow this. + template <bool isMove> + struct move_and_copy_helper<EASTL_ITC_NS::random_access_iterator_tag, isMove, true> + { + template <typename T> + static T* move_or_copy(const T* first, const T* last, T* result) + { + if (EASTL_UNLIKELY(first == last)) + return result; + + // We could use memcpy here if there's no range overlap, but memcpy is rarely much faster than memmove. + return (T*)memmove(result, first, (size_t)((uintptr_t)last - (uintptr_t)first)) + (last - first); + } + }; + + + + template <bool isMove, typename InputIterator, typename OutputIterator> + inline OutputIterator move_and_copy_chooser(InputIterator first, InputIterator last, OutputIterator result) + { + typedef typename eastl::iterator_traits<InputIterator>::iterator_category IIC; + typedef typename eastl::iterator_traits<OutputIterator>::iterator_category OIC; + typedef typename eastl::iterator_traits<InputIterator>::value_type value_type_input; + typedef typename eastl::iterator_traits<OutputIterator>::value_type value_type_output; + + const bool canBeMemmoved = eastl::is_trivially_copyable<value_type_output>::value && + eastl::is_same<value_type_input, value_type_output>::value && + (eastl::is_pointer<InputIterator>::value || eastl::is_same<IIC, eastl::contiguous_iterator_tag>::value) && + (eastl::is_pointer<OutputIterator>::value || eastl::is_same<OIC, eastl::contiguous_iterator_tag>::value); + + return eastl::move_and_copy_helper<IIC, isMove, canBeMemmoved>::move_or_copy(first, last, result); // Need to chose based on the input iterator tag and not the output iterator tag, because containers accept input ranges of iterator types different than self. + } + + + // We have a second layer of unwrap_iterator calls because the original iterator might be something like move_iterator<generic_iterator<int*> > (i.e. doubly-wrapped). + template <bool isMove, typename InputIterator, typename OutputIterator> + inline OutputIterator move_and_copy_unwrapper(InputIterator first, InputIterator last, OutputIterator result) + { + return OutputIterator(eastl::move_and_copy_chooser<isMove>(eastl::unwrap_iterator(first), eastl::unwrap_iterator(last), eastl::unwrap_iterator(result))); // Have to convert to OutputIterator because result.base() could be a T* + } + + + /// move + /// + /// After this operation the elements in the moved-from range will still contain valid values of the + /// appropriate type, but not necessarily the same values as before the move. + /// Returns the end of the result range. + /// Note: When moving between containers, the dest range must be valid; this function doesn't resize containers. + /// Note: if result is within [first, last), move_backward must be used instead of move. + /// + /// Example usage: + /// eastl::move(myArray.begin(), myArray.end(), myDestArray.begin()); + /// + /// Reference implementation: + /// template <typename InputIterator, typename OutputIterator> + /// OutputIterator move(InputIterator first, InputIterator last, OutputIterator result) + /// { + /// while(first != last) + /// *result++ = eastl::move(*first++); + /// return result; + /// } + + template <typename InputIterator, typename OutputIterator> + inline OutputIterator move(InputIterator first, InputIterator last, OutputIterator result) + { + return eastl::move_and_copy_unwrapper<true>(eastl::unwrap_iterator(first), eastl::unwrap_iterator(last), result); + } + + + /// copy + /// + /// Effects: Copies elements in the range [first, last) into the range [result, result + (last - first)) + /// starting from first and proceeding to last. For each nonnegative integer n < (last - first), + /// performs *(result + n) = *(first + n). + /// + /// Returns: result + (last - first). That is, returns the end of the result. Note that this + /// is different from how memmove/memcpy work, as they return the beginning of the result. + /// + /// Requires: result shall not be in the range [first, last). But the end of the result range + /// may in fact be within the input rante. + /// + /// Complexity: Exactly 'last - first' assignments. + /// + template <typename InputIterator, typename OutputIterator> + inline OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result) + { + const bool isMove = eastl::is_move_iterator<InputIterator>::value; EA_UNUSED(isMove); + + return eastl::move_and_copy_unwrapper<isMove>(eastl::unwrap_iterator(first), eastl::unwrap_iterator(last), result); + } +} // namespace eastl + +#endif // Header include guard + + + + + + + + + + + + + + + |