实现memmove而不复制源数据

Question

我需要自己实现标准 c 函数 memmove。

void *memmove(void *str1, const void *str2, size_t n) 在进行实际复制之前，我是否可以避免将源（由 str2 指向）复制到临时缓冲区中？

谢谢！

Answer 1

memmove

的描述是这么说的

复制发生

就好像首先将 s2 指向的对象中的 n 个字符复制到一个包含 n 个字符的临时数组中，该数组不与 s1 和 s2 指向的对象重叠，然后将临时数组中的 n 个字符复制到被复制到 s1 指向的对象中。

现在“好像”部分告诉我们，这只是用于解释可观察的行为，而不是实现实际上必须如何做到这一点。

但有趣的事实是：在大多数情况下，如果不将整个源代码复制到临时缓冲区中，实际上“不可能”在可移植标准 C 中实现

memmove（如果 src == dest

，则可以完全避免进行复制）。 

如果您进行逐字符复制，您可以检查哪个指针在内存中最先出现，即如果

target > source

，则意味着您需要反向复制，即从

n - 1

开始向后复制。

需要注意的是，如果两个指针都指向同一数组的成员，则使用 

target > source

严格符合

。这不仅仅是理论上的 - 例如，x86 实模式分段内存模型可能会使指针比较变得困难。 考虑到这一点，您可以将两者都投射到

uintptr_t

进行比较并希望最好的结果（并担心最坏的情况）。我相信转换为

uintptr_t

在 x86 实模式下不起作用（即“640 KB 对任何人来说都足够了”模式），但无论如何谁愿意为其编程。

Answer 2

typedef unsigned char uint8_t;

typedef unsigned int uint32_t;

typedef uint32_t size_t;

void * memmove(void *dst, const void *src, size_t len){
    uint8_t *dp = (uint8_t *)dst;
    const uint8_t *sp = (const uint8_t *)src;
    
    if(sp < dp && sp + len > dp){
        sp += len;
        dp += len;
        while(len-- > 0){
            *--dp = *--sp;
        }
    }else{
        while(len-- > 0){
            *dp++ = *sp++;
        }
    }
    
    return dst;
}

Answer 3

<

和

-

等操作时说得对，在一般情况下是未定义的行为。不过，如果我没记错的话，有一种方法可以在不复制的情况下执行

memmove

：

void *memmove(void *target, const void *source, size_t length)
{
    {
        const unsigned char *cursor = source;
        for(size_t i = 0; i < length; i++) {
            if(cursor == target) {
                goto overlap;
            }
        }
    }
    // Here, we know there is not enough overlap for a simple loop to fail
    for(size_t i = 0; i < length; i++) {
        i[(unsigned char *)target] = i[(unsigned char *)source];
    }
    return target;
    
    // This case handles the overlapping situation, where we run the loop backward.
    overlap:
    if(length > 0) {
        for(size_t i = length-1; i >= 0; i--) {
            i[(unsigned char *)target] = i[(unsigned char *)source];
        }
    }
    return target;
}

这是 O(1) 空间，O(n) 时间。