c - 如何在没有中间副本的情况下在标准 C 中实现 memmove？

Question

来 self 系统的手册页:

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

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 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可以转换为指向 char 的指针以减轻严格的别名问题，但是否可以比较可能指向不同 block 内的两个指针，以便在它们指向同一 block 内的情况下以正确的顺序进行复制？

显而易见的解决方案是 if (src < dst) , 但如果 src 则未定义和 dst指向不同的 block 。 “未定义”意味着您甚至不应该假设条件返回 0 或 1(在标准词汇表中这将被称为“未指定”)。

另一种选择是 if ((uintptr_t)src < (uintptr_t)dst) ，这至少是未指定的，但我不确定标准是否保证在 src < dst 时被定义，它相当于(uintptr_t)src < (uintptr_t)dst) .指针比较是从指针算术定义的。例如，当我阅读关于加法的 6.5.6 节时，在我看来，指针运算的方向可能与 uintptr_t 相反。算术，也就是说，一个兼容的编译器可能有，当 p类型为 char* :

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

这只是一个例子。一般来说，将指针转换为整数时，似乎几乎无法保证。

这是一个纯粹的学术问题，因为memmove与编译器一起提供。在实践中，编译器作者可以简单地将未定义的指针比较提升为未指定的行为，或者使用相关的 pragma 强制他们的编译器编译他们的 memmove正确。例如，this implementation有这个片段:

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 中有效地实现。例如，在回答 this SO question 时没有人打勾。 .

Answer 1

我认为你是对的，不可能实现memmove在标准 C 中高效。

我认为，唯一真正可移植的测试区域是否重叠的方法是这样的:

for (size_t l = 0; l < len; ++l) {
    if (src + l == dst) || (src + l == dst + len - 1) {
      // 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所有在可移植代码中都很有效，因为无论您做什么，特定于平台的实现都可能会让您大吃一惊。但是可移植memcpy至少看起来是合理的。

C++ 引入了一个指针特化 std::less ，它被定义为适用于同一类型的任何两个指针。理论上它可能比 < 慢，但显然在非分段架构上它不是。

C 没有这样的东西，所以在某种意义上，C++ 标准同意你的观点，即 C 没有足够的定义行为。但是，C++ 需要它来处理 std::map等等。您更有可能想要实现 std::map (或类似的东西)在不了解你想要实现的实现的情况下 memmove (或类似的东西)不知道实现。