Jump to content
  • Advertisement
Sign in to follow this  
Nitage

C++ equivilent to memmove?

This topic is 4331 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Is there a C++ alternative to memmove that works on non-Pod types? std::copy won't do as it requires non-overlapping ranges (at least according to the draft standard, which is the only one I have available right now).

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
Does the begining of the ouput overlap the range or the end of the ouput?
if end use std::copy
if begining use std::copy_backward

or just use memmove.

Share this post


Link to post
Share on other sites
Ie:


#include <algorithm>

namespace my_std {
template <class InputIterator, class OutputIterator>
OutputIterator safer_copy(
InputIterator first, InputIterator last,
OutputIterator result)
{
if ( (result < last) && (result >= first) ) {
return std::copy_backwards( first, last, result );
}
return std::copy( first, last, result );
}
};



Note the above isn't perfectly safe.


char buffer[1000];
char const* first = &buffer[100];
char const* last = first+100;
char *const buff_start = buffer;
int* output = reinterprit_cast<int*>(buff_start);


There is no way to safely copy from [first, last] into "output" without doing some really strange gymnastics. (basically, you'd copy from the "outside in").

A similar strategy could be required for copying from larger-to-smaller overlapping data.

A truely safe copy would be interesting to write. :)

Share this post


Link to post
Share on other sites
It would be pretty trivial to write one if you took an internal copy of the data:

template <class InIter, class OutIter>
OutIter copy(InIter inBegin ,InIter inEnd, OutIter outBegin)
{
std::vector<typename std::iterator_traits<InIter>::value_type> data_copy(inBegin,inEnd);
return std::copy(data_copy.begin(),data_copy.end(),outBegin);
}



But an in-place one would be pretty tough.

Anyway, thanks for the help. The solution you posted is fine, seeing as I'm not doing anything weird with the types of the input/output ranges.

Share this post


Link to post
Share on other sites
In practice, there is no notion of overlapping available for generic iterators.

Even when the iterators are random-access iterators, determining any overlaps would require a full traversal of the iterator range before the copy would even start (although that's the case for a handmade memmove as well, I believe).

In the end, I believe a specialized self_blit approach, designed for overlapping random iterator sequences, would be able to skip the lengthy checking requirements and move data around without requiring a copy.

Share this post


Link to post
Share on other sites
That's strange, because the STL reference on SGIs website also says the ranges are not allowed to overlap, but this is from the GCC STL, just above the copy implementation:

// All of these auxiliary structs serve two purposes.  (1) Replace
// calls to copy with memmove whenever possible. (Memmove, not memcpy,
// because the input and output ranges are permitted to overlap.)
// (2) If we're using random access iterators, then write the loop as
// a for loop with an explicit count.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Original post by ZQJ
That's strange, because the STL reference on SGIs website also says the ranges are not allowed to overlap..


No it doesn't.

http://www.sgi.com/tech/stl/copy.html
Quote:
[2] The order of assignments matters in the case where the input and output ranges overlap: copy may not be used if result is in the range [first, last). That is, it may not be used if the beginning of the output range overlaps with the input range, but it may be used if the end of the output range overlaps with the input range; copy_backward has opposite restrictions. If the two ranges are completely nonoverlapping, of course, then either algorithm may be used. The order of assignments also matters if result is an ostream_iterator, or some other iterator whose semantics depends on the order of assignments.

Share this post


Link to post
Share on other sites
Quote:
Original post by NotAYakk
Ie:

*** Source Snippet Removed ***

Note the above isn't perfectly safe.


char buffer[1000];
char const* first = &buffer[100];
char const* last = first+100;
char *const buff_start = buffer;
int* output = reinterprit_cast<int*>(buff_start);


There is no way to safely copy from [first, last] into "output" without doing some really strange gymnastics. (basically, you'd copy from the "outside in").

A similar strategy could be required for copying from larger-to-smaller overlapping data.

A truely safe copy would be interesting to write. :)


Sure, if you're copying one char to one int, you have a problem, but then you're no longer playing the same game as memmove().

In other words, copying from larger-to-smaller with memmove() usually results in a buffer overflow.

EDIT: Being a pedant, I'll also point out that one char to one int wouldn't be a problem if (sizeof(char) == sizeof(int)) returns true.

EDIT: Perhaps slightly less pedantically, unless C++ changed it, I don't think you're guaranteed to be able to compare pointers that aren't from the same data-block (or C's concept of "object").

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Even when the iterators are random-access iterators, determining any overlaps would require a full traversal of the iterator range before the copy would even start (although that's the case for a handmade memmove as well, I believe).
No it doesn't. Every memmove I've seen simply checks which way they overlap by looking at the input pointers & length and then either copies in the same way as memcpy (if dest < source), or copies backwards (if source > dest). Basically similiar to what NotAYakk posted.
There is nothing unsafe about it - it just works. For vectors, which are guaranteed to be contiguous in memory, we can obviously do the same (copying whole objects at once), without any worries.

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
No it doesn't. Every memmove I've seen simply checks which way they overlap by looking at the input pointers & length


Therein lie my worries. A library writer for a given platform may know which comparisons are possible between pointers, and give up portability to ensure speed. However, I am not certain that the behaviour of pointer comparison is defined for every single pair of pointers (in particular, for pointers which do not lie within the same memory area at all, as Way Walker has already mentioned). Three possibilities are available here:
  1. The C (or C++) standard provides sound guarantees about the linearity of memory, and says that such comparison will always work, so the program works. As far as I know, this is not the case.

  2. The C (or C++) standard classifies such a comparison as yielding an undefined value. This is not really problematic, since the two data blocks are not in the same memory area and can thus be expected not to overlap at all, so the program would still work regardless of the result, even if non-deterministic.

  3. The C (or C++) standard classifies such a comparison as undefined behaviour, which means that performing such a comparison may lead to the program doing unexpected things outside the expected semantics of the language. In this situation, the program cannot be expected to work.


I'm moderately confident that option 2 is the correct one (so the program would work), but I'm too overworked right now to wade through the standards and try to back it up, so I'll leave this to someone more knowledgeable that me.

However, in the case of iterators, aside from the very special case of a vector (which can indeed be a good specialization of the algorithm), nothing can be done to safely and reliably determine if an iterator is inside a sequence except for traversing the sequence.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!