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

Question

从我系统的手册页:

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

描述
memmove()函数将字符串src中的len个字节复制到字符串dst.
两个字符串可能重叠 ; 副本总是以非破坏性的
方式完成.

从C99标准:

6.5.8.5比较两个指针时,结果取决于指向的对象的地址空间中的相对位置.如果指向对象或不完整类型的两个指针都指向同一个对象,或者两个指针都指向同一个数组对象的最后一个元素,则它们相等.如果指向的对象是同一聚合对象的成员,则指向稍后声明的结构成员的指针比指向结构中先前声明的成员的指针大,指向具有较大下标值的数组元素的指针比指向同一数组的元素的指针大.具有较低的下标值.指向同一个union对象的成员的所有指针都比较相等.如果表达P 指向数组对象的元素,表达式Q指向同一数组对象的最后一个元素,指针表达式Q+1 比较大于 P.在所有其他情况下,行为 未定义.

重点是我的.

的参数dst和src可被转化为指针char以便减轻严格别名的问题,但有可能以比较两个指针可以指向内部的不同的块,以便做以正确的顺序的拷贝的情况下,它们指向相同的块内？

显而易见的解决方案是if (src < dst),但未定义如果src和dst指向不同的块."未定义"意味着您甚至不应该假设条件返回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它与编译器一起提供.在实践中,编译器作者可以简单地将未定义的指针比较提升为未指定的行为,或者使用相关的编译指示强制其编译器memmove正确编译它们.例如,此实现具有以下代码段:

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中有效实现.例如,在回答这个SO问题时没有人勾选.

Answer 1

我认为你是对的,不可能memmove在标准C中有效实施.

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

[编辑:稍后看这个,我认为它应该dst+len-1在第二行的末尾.但我不能费心去测试它,所以我现在就会离开,我可能第一次知道我在说什么.

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全部,因为特定于平台的实现很可能无论您做什么都可以实现.但便携式至少看起来似乎有道理.memcpy

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

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

Answer 2

为了使两个存储区域有效且重叠,我相信您需要处于6.5.8.5的定义情况之一.也就是说,数组的两个区域,联合,结构等.

其他情况未定义的原因是因为两个不同的对象可能甚至不在相同类型的内存中,具有相同类型的指针.在PC体系结构中,地址通常只是32位地址到虚拟内存中,但C支持各种奇怪的体系结构,其中内存不是那样的.

C保留未定义的原因是在不需要定义情况时给编译器编写者留有余地.阅读6.5.8.5的方法是一个段落,它仔细地描述了C想要支持的架构,除非它在同一个对象中,否则指针比较没有意义.

此外,编译器提供memmove和memcpy的原因是它们有时使用专门的指令写入目标CPU的调整组件中.它们并不意味着能够以相同的效率在C中实现.