Является ли это правильным и переносимым способом проверки, если 2 c-строки перекрываются в памяти?

Ответ 1

Да, ваш код верен. Если две строки заканчиваются на месте выборки, они по определению перекрываются - они имеют один и тот же нулевой ограничитель. Либо обе строки одинаковы, либо одна подстрока другой.

Все, что касается вашей программы, - это совершенно четкое поведение, поэтому, принимая компиляторы, совместимые со стандартами, оно должно быть совершенно портативным.

Соответствующий бит в стандарте от 6.5.9 Операторы равенства (основное внимание):

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

Ответ 2

Размышляя о комментариях zdan к моему предыдущему сообщению (который, вероятно, вскоре будет удален), я пришел к выводу, что проверка конечных точек достаточно.

Если существует какое-либо перекрытие, нулевой ограничитель сделает две строки не различными. Давайте посмотрим на некоторые возможности.

Если вы начинаете с

a 0x10000000 "Hello" and somehow add
b 0x10000004 "World",

у вас будет одно слово: HellWorld, так как W перезапишет \0. Они заканчивались бы в той же конечной точке.

Если вы каким-то образом напишите в ту же отправную точку:

a 0x10000000 "Hello" and
b 0x10000000 "Jupiter"

У вас будет слово Юпитер и будет иметь ту же конечную точку.

Есть ли случай, когда вы можете иметь одну и ту же конечную точку и не иметь перекрытия? Вид.

a = 0x1000000 "Four" and
b = 0x1000004 "".

Это также даст перекрытие.

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

Итак, короткий ответ: Да, ваш чек достаточно.

Ответ 3

Вероятно, это не относится к вашему варианту использования, так как ваш вопрос касается только C-строк, но код не будет работать в том случае, если данные имеют встроенные NUL-байты в строках.

char a[] = "abcd\0ABCD";
char *b = a + 5;

Кроме этого, ваше решение прямолинейно и правильно. Он работает, поскольку вы используете == для сравнения указателей и в соответствии со стандартом (от C11 6.5.9/6)

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

Однако реляционные операторы более строгие (из C11 6.5.8/5):

При сравнении двух указателей результат зависит от относительных местоположений в адресном пространстве объектов, на которые указывает. Если два указателя на типы объектов указывают на один и тот же объект или оба указывают один за последним элементом одного и того же объекта массива, они сравнивают равные. Если объекты, на которые указывают, являются членами одного и того же совокупного объекта, указатели на элементы структуры, объявленные позже, сравниваются больше, чем указатели на элементы, объявленные ранее в структуре, а указатели на элементы массива с большими значениями индекса сравниваются больше, чем указатели на элементы одного и того же массива с нижними значениями индекса. Все указатели на члены одного и того же объекта объединения сравниваются одинаково. Если выражение P указывает на элемент объекта массива, а выражение Q указывает на последний элемент одного и того же объекта массива, выражение указателя Q + 1 сравнивается больше P. Во всех остальных случаях поведение undefined.

Последнее предложение - это кикер.

Некоторые из них сделали исключение из того, что ваш код может дважды вычислить длину перекрытия и попытался принять меры предосторожности, чтобы избежать этого. Тем не менее, эффективность сокращения этого вычисления сравнивается с дополнительным сравнением указателя на итерацию или включает в себя undefined или поведение, определенное реализацией. Предполагая, что вам требуется портативное и совместимое решение, фактический средний коэффициент усиления, вероятно, равен нулю, и не стоит усилий.

Ответ 4

Это решение по-прежнему является одной и той же наихудшей производительностью, но оптимизировано для хитов - вам не нужно разбирать обе строки.

char * temp_a = a;
char * temp_b = b;

while (*temp_a != '\0') {

    if (temp_a++ == b) 
        return 1;

}

// check for b being an empty string
if (temp_a == b) return 1;

/* but if b was larger, we aren't done, so you have to try from b now */
while (*temp_b != '\0') {
    if (temp_b++ == a)
        return 1;
}

/* don't need the a==b check again here

return 0;

По-видимому, только единственное равенство (неравномерность) указателя переносимо в C, поэтому следующие решения не переносимы - все ниже, чем до того, как я это знал.

Ваше решение действительно, но зачем вычислять strlen на второй строке? Вы знаете начальную и конечную точку одной строки, просто посмотрите, находится ли между ними (включительно). сохраняет ваш проход через вторую строку - O (M + N) до O (M)

char * lower_addr_string = a < b ? a : b
char * higher_addr_string = a > b ? a : b
length = strlen(lower_addr_string)
return higher_addr_string >= lower_addr_string && higher_addr_string <= lower_addr_string + length;

в качестве альтернативы, выполните синтаксический анализ самостоятельно.

char * lower_addr_string = a < b ? a : b
char * higher_addr_string = a > b ? a : b
while(*lower_addr_string != '\0') {
    if (lower_addr_string == higher_addr_string)
        return 1;
    ++lower_addr_string;
}
/* check the last character */
if (lower_addr_string == higher_addr_string)
    return 1;
return 0;

Ответ 5

Да, ваш чек верен, но он, конечно, не самый эффективный (если "эффективностью" вы понимаете вычислительную эффективность). Очевидная интуитивная неэффективность в вашей реализации основана на том факте, что, когда строки фактически перекрываются, вызовы strlen будут перебирать по их общей части дважды.

Для формальной эффективности можно использовать несколько иной подход

int are_overlapping(const char *a, const char *b) 
{
  if (a > b) /* or `(uintptr_t) a > (uintptr_t) b`, see note below! */
  {
    const char *t = a; 
    a = b; 
    b = t;
  }

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

  return a == b;
}

Важное замечание об этой версии состоит в том, что он выполняет реляционное сравнение двух указателей, которые не гарантируют указание на один и тот же массив, что формально приводит к поведению undefined. Он будет работать на практике в системе с плоской моделью памяти, но может привлечь критику от рецензента педантичного кода. Чтобы формально обойти эту проблему, можно преобразовать указатели в uintptr_t перед выполнением реляционных сравнений. Таким образом, поведение undefined преобразуется в поведение, определенное реализацией, с правильной семантикой для наших целей в большинстве (если не всех) традиционных реализаций с плоской моделью памяти.

Этот подход свободен от проблемы "двойного счета": он анализирует неперекрывающуюся часть строки, которая находится "раньше" в памяти. Конечно, на практике преимущества такого подхода могут оказаться несуществующими. Это будет зависеть как от качества вашей реализации strlen, так и от свойств фактического ввода.

Например, в этой ситуации

const char *str = "Very very very long string, say 64K characters long......";

are_overlapped(str, str + 1);

моя версия будет обнаруживать перекрытие намного быстрее, чем ваша. Моя версия будет делать это в 1 итерации цикла, в то время как ваша версия будет тратить 2 * 64K итераций (предполагая наивную реализацию strlen).

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

int are_overlapping(const char *a, const char *b) 
{
  if (a > b)
  {
    const char *t = a; 
    a = b; 
    b = t;
  }

  return b <= a + strlen(a);
}

Эта реализация не выполняет дополнительное сравнение указателей на каждой итерации. Цена, которую мы платим за это, состоит в том, что она всегда выполняет итерацию до конца одной из строк, а не заканчивается раньше. Тем не менее он по-прежнему более эффективен, чем ваша реализация, поскольку он вызывает strlen только один раз.