Как работает реализация strchr

Question

Я попытался написать свою собственную реализацию метода strchr().

Теперь это выглядит так:

char *mystrchr(const char *s, int c) {
    while (*s != (char) c) {
        if (!*s++) {
            return NULL;
        }
    }
    return (char *)s;
}

Последняя строка изначально была

return s;

Но это не сработало, потому что s является постоянным. Я узнал, что должен быть этот состав (char *), но я, честно говоря, не знаю, что я там делаю:(Кто-то может объяснить?

Answer 1

Я считаю, что это на самом деле недостаток в определении стандарта С strchr() функция. (Я буду счастлив, что окажусь неправым.) (Отвечая на комментарии, можно поспорить, действительно ли это недостаток; ИМХО, это все еще плохой дизайн. Его можно использовать безопасно, но слишком небезопасно использовать его.)

Вот что говорит стандарт C:

char *strchr(const char *s, int c);

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

Что означает, что эта программа:

#include <stdio.h>
#include <string.h>

int main(void) {
    const char *s = "hello";
    char *p = strchr(s, 'l');
    *p = 'L';
    return 0;
}

хотя он тщательно определяет указатель на строковый литерал как указатель на constchar, имеет неопределенное поведение, так как он изменяет строковый литерал. GCC, по крайней мере, не предупреждает об этом, и программа умирает с ошибкой сегментации.

Проблема в том, что strchr() занимает const char* аргумент, который означает, что он обещает не изменять данные, которые s указывает на - но это возвращает равнину char*, что позволяет вызывающей стороне изменять те же данные.

Вот еще один пример; у него нет неопределенного поведения, но он спокойно изменяет const квалифицированный объект без каких-либо приведений (который, как мне кажется, при дальнейшем рассмотрении имеет неопределенное поведение):

#include <stdio.h>
#include <string.h>

int main(void) {
    const char s[] = "hello";
    char *p = strchr(s, 'l');
    *p = 'L';
    printf("s = \"%s\"\n", s);
    return 0;
}

Это означает, я думаю, (чтобы ответить на ваш вопрос), что реализация C strchr() должен привести свой результат, чтобы преобразовать его из const char* в char* или сделать что-то эквивалентное.

Вот почему C++, в одном из немногих изменений, которые он вносит в стандартную библиотеку C, заменяет strchr() с двумя перегруженными функциями с одинаковым именем:

const char * strchr ( const char * str, int character );
      char * strchr (       char * str, int character );

Конечно, С не может этого сделать.

Альтернативой было бы заменить strchr двумя функциями, один берет const char* и возвращая const char* и еще один брал char* и возвращая char*, В отличие от C++, две функции должны иметь разные имена, возможно strchr а также strcchr,

(Исторически, const был добавлен в C после strchr() уже был определен. Это был, вероятно, единственный способ сохранить strchr() не нарушая существующий код.)

strchr() это не единственная стандартная библиотечная функция C, которая имеет эту проблему. Список затронутой функции (я думаю, что этот список полон, но я не гарантирую это):

void *memchr(const void *s, int c, size_t n);
char *strchr(const char *s, int c);
char *strpbrk(const char *s1, const char *s2);
char *strrchr(const char *s, int c);
char *strstr(const char *s1, const char *s2);

(все заявлено в <string.h>) а также:

void *bsearch(const void *key, const void *base,
    size_t nmemb, size_t size,
    int (*compar)(const void *, const void *));

(объявлено в <stdlib.h>). Все эти функции принимают указатель на const данные, которые указывают на начальный элемент массива, и возвращают не const указатель на элемент этого массива.

Answer 2

Практика возврата неконстантных указателей на константные данные из немодифицирующих функций на самом деле является идиомой, довольно широко используемой в языке Си. Это не всегда красиво, но довольно устоялось.

Обоснование здесь простое: strchr сама по себе является немодифицирующей операцией. Все же нам нужно strchr функциональность как для константных, так и для неконстантных строк, которая также будет распространять постоянство ввода на постоянство вывода. Ни C, ни C++ не предоставляют какой-либо элегантной поддержки этой концепции, а это означает, что на обоих языках вам придется написать две практически идентичные функции, чтобы избежать рисков с константностью.

В C++ вы можете использовать перегрузку функций, объявив две функции с одинаковым именем

const char *strchr(const char *s, int c);
char *strchr(char *s, int c);

В C у вас нет перегрузки функций, поэтому для полного обеспечения const-корректности в этом случае вам придется предоставить две функции с разными именами, что-то вроде

const char *strchr_c(const char *s, int c);
char *strchr(char *s, int c);

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

char *strchr(const char *s, int c);

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

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

Теперь, что касается вашей реализации strchrМне это кажется странным с точки зрения стилистики. Я бы использовал заголовок цикла для перебора всего диапазона, над которым мы работаем (полная строка), и использовал бы внутренний if поймать условие досрочного прекращения

for (; *s != '\0'; ++s)
  if (*s == c)
    return (char *) s;

return NULL;

Но такие вещи всегда являются предметом личных предпочтений. Кто-то может предпочесть просто

for (; *s != '\0' && *s != c; ++s)
  ;

return *s == c ? (char *) s : NULL;

Кто-то может сказать, что изменение параметра функции (s) внутри функции это плохая практика.

Answer 3

const Ключевое слово означает, что параметр не может быть изменен.

Вы не могли вернуться s прямо потому что s объявлен как const char *s и тип возвращаемого значения функции char *, Если бы компилятор позволил вам это сделать, можно было бы переопределить const ограничение.

Добавление явного приведения к char* говорит компилятору, что вы знаете, что делаете (хотя, как объяснил Эрик, было бы лучше, если бы вы этого не делали).

ОБНОВЛЕНИЕ: Ради контекста я цитирую ответ Эрика, так как он, кажется, удалил его:

Вы не должны изменять s, так как это const char *.

Вместо этого определите локальную переменную, которая представляет результат типа char *, и используйте его вместо s в теле метода.

Answer 4

Возвращаемое значение функции должно быть постоянным указателем на символ:

strchr принимает const char* и должен вернуться const char* также. Вы возвращаете непостоянную переменную, которая потенциально опасна, поскольку возвращаемое значение указывает на входной массив символов (вызывающий объект может ожидать, что постоянный аргумент останется постоянным, но его можно изменить, если какая-либо его часть будет возвращена как char * указатель).

Возвращаемое значение функции должно быть NULL, если не найдено ни одного соответствующего символа:

Также strchr должен вернуться NULL если искомый персонаж не найден. Если он возвращает не NULL, когда символ не найден, или s в этом случае, вызывающая сторона (если он думает, что поведение совпадает с strchr) может предположить, что первый символ в результате фактически совпадает (без возвращаемого значения NULL нет никакого способа узнать, был ли матч или нет).

(Я не уверен, что это то, что вы намеревались сделать.)

Вот пример функции, которая делает это:

Я написал и провел несколько тестов на эту функцию; Я добавил несколько действительно очевидных проверок работоспособности, чтобы избежать возможных сбоев:

const char *mystrchr1(const char *s, int c) {
    if (s == NULL) {
        return NULL;
    }
    if ((c > 255) || (c < 0)) {
        return NULL;
    }
    int s_len;
    int i;
    s_len = strlen(s);
    for (i = 0; i < s_len; i++) {
        if ((char) c == s[i]) {
            return (const char*) &s[i];
        }
    }
    return NULL;
}

Answer 5

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

Изменение строковых литералов является недопустимым с точки зрения безопасности, поскольку оно может привести к аварийному завершению программы и, возможно, атакам типа «отказ в обслуживании». Компиляторы могут предупреждать вас, когда вы передаете строковый литерал функции, принимающей char*, но они не обязательны.

Как правильно использовать strchr? Давайте посмотрим на пример.

Это пример того, чего нельзя делать:

      #include <stdio.h>
#include <string.h>

/** Truncate a null-terminated string $str starting at the first occurence 
 *  of a character $c. Return the string after truncating it.
 */
const char* trunc(const char* str, char c){
  char* pc = strchr(str, c);
  if(pc && *pc && *(pc+1)) *(pc+1)=0;
  return str;
}

Посмотрите, как он изменяет строковый литерал str через указатель pc? Это не буэно.

Вот как это сделать:

      #include <stdio.h>
#include <string.h>

/** Truncate a null-terminated string $str of $sz bytes starting at the first 
 *  occurrence of a character $c. Write the truncated string to the output buffer 
 *  $out.
 */
char* trunc(size_t sz, const char* str, char c, char* out){
  char* c_pos = strchr(str, c);
  if(c_pos){
    ptrdiff_t c_idx = c_pos - str;
    if((size_t)n < sz){
      memcpy(out, str, c_idx); // copy out all chars before c
      out[c_idx]=0; // terminate with null byte
    }
  }
   return 0; // strchr couldn't find c, or had serious problems
}

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

Вы можете подумать: «Ой, это глупо! Я не хочу использовать strchr, если он просто сделает меня memcpy». Если вы так считаете, я никогда не сталкивался с вариантом использования strchr, strrchrи т. д., что я не мог избежать использования цикла while и isspace, isalnumи т.д. Иногда это на самом деле чище, чем правильное использование strchr.