Как исправить 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;
}

---

EDIT:

Итак, одна из возможных реализаций, основанная на @ Secure's ответ:

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).

EDIT:

Как отметил Стив Джессоп в комментариях, на самом деле существует портативный, но медленный способ обнаружения перекрытия в этом случае. Сравните каждый адрес в пределах b с первым и последним адресом a на равенство. Сравнение равенства с == всегда четко определено.

Итак, у вас есть что-то вроде этого:

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

Если вы хотите, чтобы это было немного более хакерским, вы можете сжать его дальше, но я не рекомендую это:

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

Answer 2

Примечание. Здесь b - это адрес исходной строки, а a - адрес получателя.

С a > b вы не обязательно будете иметь перекрытие.Если

(a <= b && a+strlen(a) >= b) || (b <= a && b+strlen(b) >= a)

, то у вас есть перекрытие.

Однако, помимо обнаружения перекрытия ради интервью, a > b должно подойти для strcpy.Идея такова:

Если b помещен дальше в память (b > a), то вы обычно можете скопировать b в a.Части b будут перезаписаны, но вы уже прошли эту часть.

Если a помещается дальше в память (a > b), это означает, что возможно записывая в первое местоположение a, вы уже переписали местоположение в b с более высоким индексом.В таком случае вы должны скопировать в обратном направлении.Таким образом, вместо копирования из индекса 0 в strlen(b)-1, вам следует скопировать из strlen(b)-1 в 0.

Если вы не уверены, как это помогает, нарисуйте два перекрывающихся массива на бумаге и попробуйте скопироватьодин раз с начала массива и один раз с конца.Попробуйте сделать это с перекрывающимися массивами в случаях a > b и a < b.

Обратите внимание, что если a == b, вам не нужно ничего копировать, и вы можете просто вернуть.

Изменить: я не уверен, но читая другие решения, кажется, что этот ответ может быть не полностью переносимым.Остерегайтесь этого.

Answer 3

Возможно, вы могли бы использовать memmove (), если ожидаете, что строки перекрываются.

char* my_strcpy(char *a, char *b)
{
    memmove(a, b, strlen(b) + 1);
    return a;
}

Answer 4

if a > b; then
    copy a from the beginning
else if a < b; then
    copy a from the ending
else // a == b
    do nothing

Вы можете сослаться на реализацию из memmove, это очень похоже на то, что я сказал.

Answer 5

Даже без использования сравнения реляционных указателей, memmove или эквивалентного, можно кодировать версию strcpy, которая будет выполняться как strlen и memcpy в неперекрывающемся случае и какнисходящая копия в перекрывающемся кейсе.Ключ заключается в том, чтобы использовать тот факт, что, если первый байт места назначения считывается, а затем заменяется на ноль, вызывая strlen в источнике и добавляя к указателю источника возвращаемое значение, получим законный указатель, который будет равенначало пункта назначения в случае "проблемного перекрытия".Если источником и назначением являются разные объекты, указатель «источник плюс strlen» может быть безопасно вычислен и может быть замечен как неравный по отношению к месту назначения.

В том случае, если добавление длины строки к указателю источника дает место назначенияуказатель, заменив нулевой байт на ранее прочитанное значение и вызвав strlen в месте назначения, позволит коду определить конечный адрес строк источника и назначения.Кроме того, длина исходной строки будет указывать расстояние между указателями.Если это значение велико (вероятно, больше 16 или около того), код может эффективно подразделить операцию «перемещение» на нисходящую последовательность операций memcpy.В противном случае строка может быть скопирована с помощью цикла сверху вниз с однобайтовыми операциями копирования или с последовательностью операций «memcpy для источника в буфер» / «memcpy для буфера до места назначения» [если стоимость одного байта большой memcpyменьше, чем половина цикла копирования отдельных символов, использование буфера ~ 256 байт может быть полезной оптимизацией].

Answer 6

Если эти две строки перекрываются, то при копировании вы будете использовать исходные указатели a или b.

Предполагая, что strcpy (a, b) примерно означает a <- b,т. е. первым параметром является место назначения копии, затем вы только проверяете, достигает ли указатель копии позиции <code>b.

Вам нужно только сохранить исходную позицию b, а во время копированияпроверьте, что вы не достигли этого.Кроме того, не пишите конечный ноль, если вы достигли этой позиции.

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

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

    char *n = a;
    const char * oldB = b;

    while( *b != '\0'
       &&  a != oldB )
    {
        *a = *b;
        a++;
        b++;
    }

    if ( a != oldB ) {
        *a = '\0';
    }

    return n;
 }

Этот алгоритм просто останавливает копирование.Может быть, вы хотите сделать что-то еще, например, пометить условие ошибки или добавить метку конца строки в предыдущую позицию (хотя молчаливый сбой (как в настоящий момент делает алгоритм) - не лучший вариант).

Надеюсь, это поможет.

Answer 7

Меня спросили об этом в недавнем интервью. Нам не нужно «обнаруживать» перекрытие. Мы можем написать strcpy таким образом, чтобы позаботились о перекрывающихся адресах. Ключ должен копировать с конца исходной строки, а не с начала.

Вот быстрый код.

void str_copy(const char *src, char *dst) 
{
    /* error checks */

    int i = strlen(a); /* may have to account for null character */

    while(i >= 0) 
    {
        dst[i] = src[i];  
        i--; 
    }
}

РЕДАКТИРОВАТЬ: Это работает, только когда a b скопируйте с самого начала.

Answer 8

if (a>= b && a <= b+strlen(b))) || (b+strlen(b) >= a && b+strlen(b) <= a + strlen(b))

(*) вам следует кэшировать strlen (b) для повышения производительности

Что он делает:
проверяет, находится ли a+len [адрес + дополнительные байты len] внутри строки или a [адрес a] находится внутри строки, это единственные возможности перекрытия строк.