如何修复strcpy以便检测重叠的字符串

Question

在一次采访中,我被要求编写一个实现,strcpy然后修复它,以便它正确处理重叠的字符串.我的实现如下,非常天真.如何修复它以便:

1. 它检测重叠的字符串和
2. 检测后,我们如何处理重叠并继续？

---

char* my_strcpy(char *a, char *b) {

     if (a == NULL || b == NULL) {
         return NULL;
     }
     if (a > b) {
         //we have an overlap?
         return NULL;
     }
     char *n = a;

     while (*b != '\0') {
         *a = *b;
         a++;
         b++;
     }
     *a = '\0';
     return n;
}

int main(int argc, char *argv[])
{
    char str1[] = "wazzupdude";
    char *after_cpy = my_strcpy(str1 + 2, str1);
    return 0;
}

---

编辑:

因此,基于@ Secure的答案的一种可能的实现是:

char* my_strcpy(char *a, char *b) {

    if (a == NULL || b == NULL) {
        return NULL;
    }

    memmove(a, b, strlen(b) + 1);
    return a;
}

如果我们不依赖memmove,那么

char* my_strcpy(char *a, char *b) {

    if (a == NULL || b == NULL) {
        return NULL;
    }

    if (a == b) {
        return a;
    }

    // case1: b is placed further in the memory
    if ( a <= b && a + strlen(a) > b ) {
        char *n = a;

        while(*b != '\0') {
            *a = *b;
            a++; b++;
        }
        *a = '\0';
        return n;
    }

    // case 2: a is further in memory
    else if ( b <= a && b + strlen(b) > a ) { 
        char *src = b + strlen(b) - 1; // src points to end of b
        char *dest = a;

        while(src != b) {
            *dest = *src;
            dest--; src--;  // not sure about this..
        }
        *a = '\0';
        return a;
    }
}

Answer 1

没有可移植的方法来检测这一点.您必须进行指针比较,这些仅在同一对象中定义.即如果两个字符串不重叠并且实际上是不同的对象,则指针比较会给出未定义的行为.

我会让标准库通过使用来处理它memmove(a, b, strlen(b) + 1).

编辑:

正如Steve Jessop在评论中指出的那样,在这种情况下实际上存在一种便携但缓慢的方法来检测重叠.将b中的每个地址与for的第一个和最后一个地址进行比较.与...的平等比较==总是很明确.

所以你有这样的事情:

l = strlen(b);
isoverlap = 0;
for (i = 0; i <= l; i++)
{
    if ((b + i == a) || (b + i == a + l))        
    {
        isoverlap = 1;
        break;
    }
}

编辑2:案例2的可视化

你有类似下面的数组和指针:

S t r i n g 0 _ _ _ _ _ _ _
^       ^
|       |
b       a

请注意,b + strlen(b)结果是指向终止\ 0的指针.开始一个,否则你需要额外处理边缘情况.在那里设置指针是有效的,你不能取消引用它们.

src = b + strlen(b) + 1;
dst = a + strlen(b) + 1;

S t r i n g 0 _ _ _ _ _ _ _
^       ^     ^       ^  
|       |     |       |
b       a     src     dst

现在复制循环也复制了\ 0.

while (src > b)
{
    src--; dst--;
    *dst = *src;
}

第一步给出了这个:

src--; dst--;

S t r i n g 0 _ _ _ _ _ _ _
^       ^   ^       ^  
|       |   |       |
b       a   src     dst

*dst = *src;

S t r i n g 0 _ _ _ 0 _ _ _
^       ^   ^       ^  
|       |   |       |
b       a   src     dst

依此类推,直到src最终等于b:

S t r i S t r i n g 0 _ _ _
^       ^              
|       |            
b       a          
src     dst

如果你想要它更加hackish,你可以进一步压缩它,但我不建议这样:

while (src > b)
    *(--dst) = *(--src);