Преамбула

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

Описываемые строки носят название "ограниченные нулём" (более точно следовало бы сказать "ограниченные нулевым символом"), в английском принят термин "NUL-terminated", иногда не совсем корректно "null-terminated". NUL - это ASCII обозначение символа с кодом 0, не имеющего никакого графического или управляющего смысла в ASCII (хотя имеющего графический вид, например, в cp437 - кодировке текстовой консоли PC). В дальнейшем изложении будем говорить "nt-строки" или просто "строки".

Мы предполагаем, что читающий это описание имеет первичное представление о том, что такое указатель в языке Си; при отсутствии такого представления освоение понятия строк становится проблематичным.

Основные понятия

В мире nt-строк существуют следующие основные понятия:

Символ
Символ в Си - элемент строки, занимающий фиксированный размер в памяти; в большинстве случаев это char для ASCII и совместимого с ASCII транспорта (например, utf-8) и wchar_t для UTF-16 и других представлений Unicode, во многих случаях (например в Microsoft Windows) называемых просто Unicode. Это понятие символа может не совпадать с понятием символа в целевой кодировке для "многобайтных" кодировок (которое может быть названо, например, "code point"); за более детальной расшифровкой проблем см. стандарт Unicode.
Константная строка
Константная строка представляет собой последовательность символов (см. выше) ограниченная символом NUL (с кодом 0); получивший такую строку не имеет права производить запись в неё, а должен ограничиться только чтением её содержимого начиная с указанной указателем позиции и до символа NUL (с кодом 0), но не далее.
Строковый буфер
Строковый буфер представляет собой массив символов, для которого определены адрес начала и длина (или как варианты, адрес начала и конца, или адрес начала и адрес-ограничитель - адрес следующего за концом символа). Функция имеет право работать со строковым буфером, получив или аллоцировав его как буфер и зная пределы в памяти, в которых она имеет право работать. Буфер может содержать в себе как полные строки, так и произвольные данные, не соответствующие определению строки.

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

Константная строка

Константная строка служит для передачи строки как неизменяемой последовательности символов. Тип передаваемых данных - указатель на константный символ; это может быть const char*, в наиболее типичном случае, const TCHAR*, для программирования независимого от типа символа под Microsoft Windows, const wchar_t*, для широких символов таких как Unicode; возможны непринципиальные добавки signed или unsigned.

Разрешённые действия с константной строкой - чтение содержимого строки посимвольно с помощью указателя; продвижение указателя вперёд, но не дальше позиции следующей за финальным NUL; продвижение указателя назад, но не дальше позиции начала этой строки. Если функция не знает где начало строки, началом строки считается позиция по переданному указателю.

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

Константная строка возникает в следующих случаях:

  1. Запись текстовой константы в кавычках во всех случаях кроме присвоения начального значения массиву;
  2. Явная конверсия указателя в строковый буфер (на элемент строкового буфера) к типу указателя на константный символ.

Например, в следующем случае происходит присвоение указателю адреса константной строки:


const char* message = "Hello world!";

В следующем случае происходит не присвоение адреса константной строки, а инициализация буфера:


const char message[] = "Hello world!";

В следующем случае константная строка передаётся в функцию:


printf("Hello world!\n");

Если формальный параметр функции - указатель на константный символ, она принимает константную строку. Фактическим параметром может быть как константная строка, так и указатель в строковый буфер (далее об этом детальнее). Наоборот, формальный параметр - указатель на неконстантный символ (например, char*) означает передачу указателя в строковый буфер; конверсия в такой указатель из указателя на константную строку должна вызвать предупреждение компилятора или даже ошибку компиляции, потому что потеря квалификатора константности указателя является ошибкой.

Строковый буфер

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

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

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


  char* p = "A";
  strcat(p, "B");

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

Использование константных строк

Константные строки могут читаться целиком, по частям или отдельными символами, например:


  const char* s = "Do you see me?";
  size_t len;
  len = strlen(s);

Стандартная функция strlen() возвращает количество символов в строке, не считая завершающего NUL.


  const char* s = "Do you see me?";
  const char* sp;
  size_t len;
  for (len = 0, sp = s; *sp != '\0'; ++sp)
    ++len;

В данном примере мы повторяем "вручную" (и, вероятно, менее оптимально чем это делает стандартная библиотека) функцию strlen().


const char*
basename(const char* path)
{
  const char* rslash = strrchr(path, '/');
  if (!rslash)
    return path;
  return rslash + 1;
}

В этом примере упрощённая реализация стандартной функции basename() воспринимает входную строку как путь к файлу, в котором компоненты разделены символами '/' ("слэш", "косая черта"), и возвращает последний из них. Стандартная функция strrchr() возвращает адрес самого правого вхождения символа (2-й аргумент) в константную строку (1-й аргумент), или NULL, если нет такого символа в строке. Это упрощённая версия, потому что от полной версии требуется исключить из рассмотрения все финальные слэши. Полная версия требует или сканирования по строке назад, или замены слэшей на NUL; приведём одну из возможных реализаций полной версии basename (но ещё без модификации строки), не оптимизированную, но максимально понятную алгоритмически:


const char*
basename(const char* path)
{
  const char* p = path + strlen(path);
  // Пропуск финальных слэшей
  while (p > path && p[-1] == '/')
    --p;
  // Если p[-1] допустим, то там не слэш. Если p == path, в строке
  // были только слэши и вернуть мы ничего осмысленного не можем.
  if (p == path)
    return NULL;
  // Отсчитывая от p[-1], сканируем до следующего слэша,
  // если он есть. Если доходим до начала строки - путь из одного
  // компонента и его надо вернуть неизменным.
  --p;
  while (p > path && p[-1] != '/')
    --p;
  return p;
}

Более сложные примеры будут в следующей главе, когда нам разрешат использовать строковые буфера и тем самым модифицировать содержимое строк.

Работа со строковыми буферами

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

Мы рассмотрим действия с одной строкой и как их возможно реализовать на nt-строках. Более-менее усреднённый базис действий над строкой, допустимый в пределах одного буфера, следующий:

Мы будем приводить примеры на трёх комплектах функций реализации: стандартному, но практически непригодному к применению; функциям strlcpy, strlcat, нестандартным, но обеспечивающим невыход за границы буфера; функциям ISO/IEC TR 24731 - предложению ISO по защите от переполнений буферов.

Присвоение строке значения другой строки (т.е. копирование строки):

Вариант strcpy:


  char buffer[BUFSIZE];
  strcpy(buffer, line);

Вариант strlcpy:


  char buffer[BUFSIZE];
  if (strlcpy(buffer, line, sizeof(buffer)) >= sizeof(buffer))
    обработать_переполнение;

Вариант TR 24731:


  char buffer[BUFSIZE];
  strcpy_s(buffer, sizeof(buffer), line);

(Здесь не упоминалась strncpy(); ниже будет рассказано, почему.)

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

Часто кажется, что можно избавляться от переполнений следующей логикой: "мы знаем, что модуль A вернёт строку не более 30 символов; B - не более 50; отведя таким образом 81 байт на буфер, у нас не будет переполнения". Сколько проживёт такая логика до первого изменения семантики, при котором длины увеличатся, и кто сделает своевременную и полную реакцию в одном модуле на изменения другого? Даже в пределах одного файла не всегда получается уследить за изменениями, а если они расположены в глубоких подкаталогах разных каталогов и модифицируются разными людьми или даже разными отделами? Давно известно что этот подход неработоспособен: работоспособен в конечном итоге только подход когда модуль (неважно насколько широко он понимается) проверяет корректность входных данных, включая - в существенной степени - и данные из используемых им функций других модулей. Качественные характеристики работы используемых средств могут быть постоянными длительное время, но количественные значительно легче меняются, а максимальная возможная длина строки - один из самых изменчивых количественных признаков. Поэтому мы категорически возражаем против любых вариантов контроля когда размер буфера не находится в пределах доступности (как sizeof или как отдельный переданный параметр) и когда он не применяется напрямую к операциям работы с буфером.

Оставшиеся две функции различаются возвращаемым значением и методом реакции на опознание переполнения. Исходная strcpy() возвращает указатель на исходный буфер для добавления; strcpy_s() повторяет это, в то время как strlcpy() возвращает пригодное для немедленной проверки количество байт которое она хотела поместить в буфер. Размер буфера передаётся в обе функции, но strlcpy() требует проверочной оболочки вокруг, а strcpy_s() вызывает constraint handler в случае переполнения. Таким образом strcpy_s() больше подходит для быстрой модификации приложения с целью исключения переполнений в нём и грубых действий в случае нарушения целостности данных, в то время как strlcpy() с надлежащей проверкой даёт возможность отреагировать на переполнение, например, увеличением буфера или отказом работы на период до восстановления.

В примерах выше не использовалась strncpy(). Эта функция не совсем относится к строковым из-за специфики семантики: она предназначается для заполнения строковых буферов фиксированного размера, для которых не обязательно завершение нулём; такие буфера активно используются в интерфейсах Unix (например, имя файла классической файловой системы, имя пользователя или хоста в структуре utmp). Кроме возможности заполнения без завершения нулём, strncpy() согласно Posix и C99 обязана заполнить всё оставшееся после строки место нулевыми символами (это делается для того, чтобы содержимое буферов потом можно было сравнивать через memcmp() или аналог с фиксированным размером); таким образом, strncpy(dest,src,size) заполняет size байт независимо от реальной длины строки src. Но, если использовать комбинацию из strncpy() с последующей проверкой последнего байта буфера (если он не NUL, то произошло переполнение) - это будет хоть и более затратным чем strcpy_s() или strlcpy(), но достаточным средством копирования с защитой от переполнения:


  char buffer[BUFSIZE];
  strncpy(buffer, line, sizeof(buffer));
  if (buffer[sizeof(buffer)-1] != '\0')
    обработать_переполнение;

Присвоение строке значения из одного символа

делается без использования строковых функций:


  buf[0] = c;
  buf[1] = '\0';

Этот метод может быть расширен на любое количество символов; проверка допустимости записи в буфер по указанному смещению остаётся на программисте.

Дописывание к концу строки другой строки (конкатенация):

Средствами TR 24731:


  char buf[BUFSIZE];
  if (strcat_s(buf, sizeof(buf), line) != 0)
    обработать_переполнение;

Средствами strlcat:


  char buf[BUFSIZE];
  if (strlcat(buf, line, sizeof(buf)) >= sizeof(buf))
    обработать_переполнение;

В обоих случаях отсутствием переполнения считается результат когда вторая строка дописалась в буфер и осталось места на завершение буфера нулевым символом. strlcat гарантирует корректность nt-строки (наличие нулевого символа в буфере) независимо от факта переполнения, а также отдачу желаемого объёма буфера (но из второй строки считается не больше символов чем объём буфера). strcat_s проверяет большее количество условий (например, если указатель второй строки NULL, то strlcat приведёт к ошибке выполнения (SIGSEGV в Unix-системах, GPF в Windows), а strcat_s отработает эту ситуацию выдачей ненулевого кода возврата без нарушения выполнения программы.

Следует сделать принципиальное замечание об эффективности добавления строк в большой буфер. Так как все функции этой группы вынуждены вначале проверять строку от начала буфера, при большом буфере и последовательном добавлении строк зависимость времени работы от объёма буфера становится квадратичной. Джоэл Спольский назвал этот подход "алгоритмом маляра Шлемиэля". Но если мы уже добавили строку в буфер, то в процессе этого добавления знаем, где она кончается, и можно добавлять с этого места? Исходя из этих соображений появились функции stpcpy, stpncpy; как таковые функции strcat, strncat, strlcat, strcat_s при наличии stpcpy и stpncpy имеют смысл только при однократных добавлениях.

stpcpy() мы исключим из рассмотрения по причине отсутствия у неё ограничений на размер буфера; stpncpy() в версии GNU libc выглядит так:

char *stpncpy(char *dest, const char *src, size_t n);

К сожалению, она не терминирует буфер нулевым символом если строка src имеет не менее n символов; можно воспользоваться собственной функцией следующего вида:


char *stpnlcpy(char *dest, const char *src, size_t n)
{
  size_t r;
  assert(n > 0);
  r = strlcpy(dest, src, n);
  if (r >= n) {
    dest[n-1] = '\0';
    return &dest[n-1];
  }
  return dest + r;
}

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


  char buf[BUFSIZE];
  char *buflim = buf + sizeof(buf);
  char *pos = buf;
  pos = stpnlcpy(pos, part1, buflim - pos);
  pos = stpnlcpy(pos, part2, buflim - pos);
  pos = stpnlcpy(pos, part3, buflim - pos);
  if (pos >= buflim - 1)
    обработать_переполнение;

(Оборотная сторона отсутствия прямой проверки: полностью заполненный буфер, в последнем байте которого терминирующий NUL, для нас эквивалентен переполнению - потому что сам факт переполнения нигде не сообщается. Это спорное решение; можно было бы заполнять до последней позиции, и переполнением считать ситуацию когда pos == buflim, а NUL в буфере нет, потому что ему не хватило места. Этот вариант тоже допустим, но его расписывать не будем.)

Обратите внимание на приём с buflim. Чтобы вычислить сколько ещё есть места в буфере, зная начало буфера и его размер, надо выполнить арифметические действия: вычесть из размера буфера разность между текущей позицией и началом; если bufsize-(pos-buf) переписать в виде (buf+bufsize)-pos, buf+bufsize может быть вычислено только один раз, так как оно не меняется всё время работы с буфером. Кроме того, психологически проще представить себе фиксированный ограничитель, за который нельзя выходить, чем пересчитывать каждый раз сколько можно максимально заполнить.

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


int lbcat(char **curpos, char *buflim, const char *src)
{
  size_t r, a;
  if (curpos >= buflim - 1)
    return 1; // даже не проверяем входную строку
  a = buflim - *curpos;
  r = strlcpy(*curpos, src, a);
  if (r >= a) {
    *curpos = buflim - 1;
    **curpos = '\0';
    return 1;
  }
  *curpos += r;
  return 0;
}

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


  char buf[BUFSIZE];
  char *buflim = buf + sizeof(buf);
  char *p = pos;
  if (lbcat(&pos, buflim, part1) ||
      lbcat(&pos, buflim, part2) ||
      lbcat(&pos, buflim, part3))
  {
    обработать_переполнение;
  }

Здесь мы намеренно ушли от "простых" strcat() и strncat(). Причина этому - их диверсионность, причём если strcat() тут ничем не отличается от strcpy(), то strncat() даёт ложную защищённость ограничением количества добавляемых символов. Почему ложную? Потому что если мы знаем только размер буфера, нам это ничего не даст. А если мы знаем сколько осталось в буфере, то мы тем самым знаем текущую позицию NUL (ограничителя строки) и нам никакие функции конкатенации не нужны в принципе, нужно только копирование. Подробнее см. выше про подход с stpcpy() и аналогами.

Наконец, если программисту доступно stdio (да, это бывает не во всех случаях - например, под Windows может вводиться принципиальное ограничение использовать только WinAPI; может быть вариант freestanding environment с урезанным или отсутствующим stdio для встроенных приложений, для ядер ОС, загрузчиков и т.д.) - конкатенации подобного рода замечательно упрощаются через snprintf():


  char buf[BUFSIZE];
  if (snprintf(buf, sizeof(buf), "%s%s%s", part1, part2, part3) >= sizeof(buf))
    обработать_переполнение;

И опять-таки - snprintf(), а не sprintf()! Потому что бороться с переполнениями надо не учётом того что происходит в коде за тридевять земель, а с тем, что известно здесь и сейчас.

Замена символа в строке

Это делается тривиальным присвоением символа по указателю или как элементу массива:


  buf[4] = 'x';
  *(buf+16) = 'y';

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


  memcpy(где_заменять, чем_заменять, длина_заменяемого);

(я даже не расписываю определения переменных - они должны быть понятны и так). Почему memcpy? Потому что длина данных уже известна, подсчёта длины которой занимаются функции группы str* не требуется; и не требуется добавления NUL в конце, он и так есть где надо. Более общий случай произвольной замены будет рассмотрен далее.

Усечение строки

Для усечения строки надо записать NUL в позицию, следующую за концом оставляемых данных. Код не приводим за тривиальностью:)

Замена части строки

Самый общий случай замены части строки (аналогичный функциям substr() в perl или ряде версий Basic) задаётся входной строкой (хранящейся в буфере который мы и будем изменять), указанием заменяемой части (начало, длина) и заменяющей строкой. В общем случае это включает в себя все возможные основные типы модификации строки, включая присвоение, конкатенацию, усечение и не только. Можно использовать несколько разных стилей реализации, например с жёстким контролем (длина больше чем доступно считается ошибкой) и с мягким контролем. ****


int lbreplace(char *buf, char *buflim, int roff, int rlen, const char *snew)
{
  char *p;
  // Исключить случай переполненного буфера
  p = memchr(buf, 0, buflim - buf);
  if (p == NULL)
    return 1;
  curlen = p - buf;
  if (roff > curlen)
    roff = curlen;
  if (roff < 0) {
    roff += curlen;
    if (roff < curlen)
      roff = 0;
  }
}

(C) 2005 Valentin Nechayev. All rights reserved.

$Id: cstr.html,v 1.2 2006/04/05 20:39:42 netch Exp $