如何实现在标准C的memmove不需要复制？ [英] How to implement memmove in standard C without an intermediate copy?

问题描述

从我的系统上的手册页：

From the man page on my system:

无效的memmove *（无效* DST，常量无效* SRC，为size_t的len）;

void *memmove(void *dst, const void *src, size_t len);

描述结果
          该memmove与（）函数将len个自的字符串src字节串DST。结果
          两个字符串可以重叠;副本总是以非破坏性的结果，完成
          方式。

DESCRIPTION
The memmove() function copies len bytes from string src to string dst.
The two strings may overlap; the copy is always done in a non-destructive
manner.

从C99标准：

6.5.8.5当两个指针进行比较，则结果取决于
  在地址相对位置
  物体的空间指向。如果
  两个指针对象或不完整
  类型都指向同一个对象，
  或者两者一点一点过去的最后一个
  相同的数组对象的元素，
  theycompare相等。如果对象
  尖的都是同成员
  聚集对象，指针
  结构成员后宣布
  比较比指针更大
  成员在早些时候宣布
  结构，和指针数组
  较大的下标值的元素
  比较比指针更大
  较低的相同数组的元素
  标值。所有指针
  相同工会对象的成员
  比较平等的。如果EX pression P
  指向一个数组的元素
  对象和前pression Q点
  同一阵列的最后一个元素
  对象，指针前pression Q + 1
  比较比 P 更大。在所有
  其他情况下，该行为是
  未定义

6.5.8.5 When two pointers are compared, the result depends on the relative locations in the address space of the objects pointed to. If two pointers to object or incomplete types both point to the same object, or both point one past the last element of the same array object, theycompare equal. If the objects pointed to are members of the same aggregate object, pointers to structure members declared later compare greater than pointers to members declared earlier in the structure, and pointers to array elements with larger subscript values compare greater than pointers to elements of the same array with lower subscript values. All pointers to members of the same union object compare equal. If the expression P points to an element of an array object and the expression Q points to the last element of the same array object, the pointer expression Q+1 compares greater than P. In all other cases, the behavior is undefined.

重点是我的。

的参数 DST 和的src 可转换为指针字符，以减轻严格走样的问题，但是它可以比较两个指针可能指向内部不同块，这样才能做正确的顺序副本，以防它们指向同一个块中？

The arguments dst and src can be converted to pointers to char so as to alleviate strict aliasing problems, but is it possible to compare two pointers that may point inside different blocks, so as to do the copy in the correct order in case they point inside the same block?

显而易见的解决方案是如果（SRC＆LT; D​​ST），但未定义如果的src 和 DST 点不同的块。 未定义意味着你应该甚至不应该假设条件返回0或1（这将被称为标准的词汇未指定）。

The obvious solution is if (src < dst), but that is undefined if src and dst point to different blocks. "Undefined" means you should not even assume that the condition returns 0 or 1 (this would have been called "unspecified" in the standard's vocabulary).

另一种方法是 IF（（uintptr_t形式）SRC≤（uintptr_t形式）DST），这至少是不确定的，但我不知道该标准保证了当 SRC＆LT; DST 的定义，它相当于（uintptr_t形式）SRC＆LT; （uintptr_t形式）DST）。指针比较从指针运算来定义。例如，当我在阅读除了6.5.6节，但在我看来，指针运算在相反方向可以去 uintptr_t形式算术，就是一个兼容的编译器可能有，当 p 的类型的char * 的：

An alternative is if ((uintptr_t)src < (uintptr_t)dst), which is at least unspecified, but I am not sure that the standard guarantees that when src < dst is defined, it is equivalent to (uintptr_t)src < (uintptr_t)dst). Pointer comparison is defined from pointer arithmetic. For instance, when I read section 6.5.6 on addition, it seems to me that pointer arithmetic could go in the direction opposite to uintptr_t arithmetic, that is, that a compliant compiler might have, when p is of type char*:

((uintptr_t)p)+1==((uintptr_t)(p-1)

这仅仅是一个例子。一般来说很少似乎转换指向整数时要保证的。

This is only an example. Generally speaking very little seems to be guaranteed when converting pointers to integers.

这是一个纯粹的学术问题，因为 memmove与与编译器一起提供。在实践中，编译器作者可以直接促进不确定的指针比较不确定的行为，或者使用相关的编译，迫使他们的编译器编译它们的 memmove与正确。例如，此实现有这个片断：

This is a purely academic question, because memmove is provided together with the compiler. In practice, the compiler authors can simply promote undefined pointer comparison to unspecified behavior, or use the relevant pragma to force their compiler to compile their memmove correctly. For instance, this implementation has this snippet:

if ((uintptr_t)dst < (uintptr_t)src) {
            /*
             * As author/maintainer of libc, take advantage of the
             * fact that we know memcpy copies forwards.
             */
            return memcpy(dst, src, len);
    }

我还是想用这个例子来证明标准走得太远未定义行为，如果这是真的， memmove与不能有效地在标准C语言实现例如，没有人打勾时回答这太问题。

I would still like to use this example as proof that the standard goes too far with undefined behaviors, if it is true that memmove cannot be implemented efficiently in standard C. For instance, no-one ticked when answering this SO question.

推荐答案

我想你是对的，这是不可能实现 memmove与高效标准C。

I think you're right, it's not possible to implement memmove efficiently in standard C.

测试区是否重叠，我想，只有真正便携的方法是这样的：

The only truly portable way to test whether the regions overlap, I think, is something like this:

for (size_t l = 0; l < len; ++l) {
    if (src + l == dst) || (src + l == dst + len) {
      // they overlap, so now we can use comparison,
      // and copy forwards or backwards as appropriate.
      ...
      return dst;
    }
}
// No overlap, doesn't matter which direction we copy
return memcpy(dst, src, len);

您不能执行或者的memcpy 或 memmove与所有的是的高效便携code，因为特定于平台的实现是可能踢你的屁股不管你做什么。但是便携的memcpy 至少看起来有道理的。

You can't implement either memcpy or memmove all that efficiently in portable code, because the platform-specific implementation is likely to kick your butt whatever you do. But a portable memcpy at least looks plausible.

C ++引入的指针专业化的std ::少，其被定义为相同类型的任何两个指针工作。它可能在理论上会比＆LT慢; ，但显然在非分段架构事实并非如此。

C++ introduced a pointer specialization of std::less, which is defined to work for any two pointers of the same type. It might in theory be slower than <, but obviously on a non-segmented architecture it isn't.

C有没有这样的事情，所以从某种意义上讲，C ++标准与您同意C没有足够的定义的行为。但随后，C ++需要它的std ::地图等。它更可能是你想要实施的std ::地图（或类似的东西）未经执行方面的知识比你要实施 memmove与（或类似的东西）未经执行的知识。

C has no such thing, so in a sense, the C++ standard agrees with you that C doesn't have enough defined behaviour. But then, C++ needs it for std::map and so on. It's much more likely that you'd want to implement std::map (or something like it) without knowledge of the implementation than that you'd want to implement memmove (or something like it) without knowledge of the implementation.

这篇关于如何实现在标准C的memmove不需要复制？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！