Глава 25 Полный набор операций со строками

Ориентация главы

Том 4 начинается со строк. Текстовая философия XRT — полное воплощение конвенции представлений главы 3: где можно обойтись без выделения памяти — обходимся — Trim, Cut, сравнение без учёта регистра лишь переносят пары (指针, 长度) (указатель, длина), а распределение откладывается до момента, когда новая память действительно нужна; когда распределение назрело — используем построитель — цепочка дописываний даёт суммарное копирование O(n), а не O(n²) у Concat; продукты всегда владеющие — возвращается str, освобождение через xrtFree, бесшовно согласовано с конвенцией главы 5. Глава выстраивает три слоя в прогрессию «конвейер представлений → построитель → шпаргалка по полному семейству»: поиск, редактирование, разрезание и форматирование собраны в шпаргалке за один проход.

25.1引入

Функция обработки URL должна сделать пять вещей: срезать краевые пробелы, разрезать путь и запрос по ?, сравнить путь в нижнем регистре, удалить из запроса некоторые символы и наконец приклеить префикс. Учебниковый подход делает strdup на каждом шаге — пять шагов, пять распределений, пять освобождений и пять цепочек очистки на пути отказа. Но всмотритесь: первые четыре шага вообще не требуют новой памяти — обрезка пробелов лишь сдвигает указатели к середине, разрез лишь делит одно представление на два, для сравнения без учёта регистра есть специализированный вариант IgnoreCase, удаление символов может писаться в стековый буфер вызывающего. И только последний шаг — приклейка префикса — действительно требует распределения.

В этом отправная точка конвейера представлений: отделить «оперировать над текстом» от «порождать новый текст» — первое стоит нескольких сложений и вычитаний указателей, второе ужато до минимума. На горячих путях (код, исполняющийся на каждый запрос) это быстрее «копии на каждом шаге» на порядок — не потому, что алгоритм умнее, а потому, что лишних распределений просто нет.

25.2概念

Слой 1: конвейер представлений (без распределений)

Дисциплина дизайна конвейера: чем позже распределение, тем лучше. Каждый нераспределяющий шаг сохраняет выбор для последующих шагов (вырезанное представление можно резать снова, фильтровать снова, сравнивать снова); как только распределение произошло, все дальнейшие операции идут по копии. Критерий, нужно ли распределение на шаге, прост: является ли множество выходных байтов собственным подотрезком входа (Trim, Cut, срез подстроки — решается без распределений) или требуется пересборка (склейка, замена, фильтрация — распределять или пользоваться буфером вызывающего)?

Слой 2: построитель (склейка за O(n))

Не собирайте цепочку Concat из трёх и более сегментов — каждый Concat порождает новый промежуточный буфер, n сегментов дают суммарное копирование O(n²). Построитель xstrbuf наращивает внутренний буфер удвоением (та же стратегия, что у контейнеров главы 15), поэтому цепочка дописываний копирует суммарно O(n). Семантика передачи у Take изоморфна контейнеру buffer (глава 15): владение буфером переходит напрямую, построитель обнуляется и переиспользуется. Построитель умеет и AppendRepeat (повторное дописывание — генератор разделителей и отступов), и форматированное дописывание.

Слой 3: шпаргалка по полному семейству

Два столбца заслуживают отдельного упоминания: семейство Case (CaseFind, CaseEqual, CaseStarts и другие) выполняет сравнение без учёта регистра за один вызов — на два распределения меньше, чем «сперва ToLower обе копии, потом сравнить»; расстояние/сходство (xrtUtf8Distance/xrtUtf8Similarity семейства наборов символов, счёт по скалярам Unicode) дают нечёткому сопоставлению готовый ответ — пример distance демонстрирует чтение «расстояние редактирования 2, сходство 0.6».

Разделение труда со стандартной библиотекой C

Почему бы просто не взять strstr/strdup? Три жёстких довода: стандартные функции предполагают нулевое завершение (двоично-безопасные сценарии выбывают сразу), пути отказа не сообщаются (strdup при OOM возвращает лишь NULL без диагностики), владение продуктом не оговорено (кто распределил, тот освобождает — чистая договорённость). Строковое семейство XRT полностью ходит на (视图, 长度) (представление, длина) как на валюту, на bool плюс слот ошибки, на владеющие продукты с xrtFree — все три пункта суть конвенции тома 1, воплощённые в текстовом слое.

25.3示例

Полная программа: конвейер из четырёх шагов одним духом

Из образца репозитория examples/string/basic/main.c:

 */

#include <stdio.h>

#include <xrt.h>



int main(void)
{
	/* Trim 返回原字符串的子视图：不改字节、不分配。 */
	xstrview Text = xrtStrTrim(XRT_STR_LITERAL("  alpha/beta  "));
	xstrview Name;
	char arrName[32];
	size_t iNameSize;
	str sResult;

	




	 */
	if ( !xrtStrCut(Text, XRT_STR_LITERAL("/"), &Name, NULL) ||
		 !xrtStrFilterTo(Name, XRT_STR_LITERAL("_-"), arrName,
			sizeof(arrName), &iNameSize) ) {
		return 1;
	}

	/* 第一次分配发生在拼接：产物拥有式，xrtFree 释放。 */
	sResult = xrtStrConcat((xstrview){ arrName, iNameSize },
		XRT_STR_LITERAL(".txt"));
	if ( sResult == NULL ) {
		return 2;
	}
	printf("%s\n", sResult);
	xrtFree(sResult);
	return 0;
}

Что только что произошло. (1) xrtStrTrim возвращает подпредставление исходной строки — два указателя сходятся к середине, ни один исходный байт не тронут, распределений нет. (2) xrtStrCut режет по первому /: Name получает передний сегмент alpha, задний не нужен, поэтому второй выходной параметр принимает NULL — ненужные продукты просто не принимаются, удобная конвенция Cut. (3) FilterTo вычищает - и _ из представления, остальное пишет в стековый буфер вызывающего — даже на шаге «нужна перезаписываемая память» право распределения остаётся у вызывающего (при нехватке ёмкости — отказ, а не тихое распределение за спиной). (4) Первое и единственное распределение в куче происходит в Concat при приклейке .txt — продукт владеющий, освобождение через xrtFree. Три шага из четырёх без распределений — полная демонстрация принципа «распределять как можно позже».

Полная программа: построитель и передача владения

Из examples/string/builder/main.c:

 */

#include <stdio.h>

#include <xrt.h>



int main(void)
{
	xstrbuf tBuffer;
	str sResult;

	xrtStrBufInit(&tBuffer);

	/* 前缀 + 模式重复三次："ab" × 3 = ababab。 */
	if ( !xrtStrBufAppend(&tBuffer, XRT_STR_LITERAL("items=")) ||
		 !xrtStrBufAppendRepeat(&tBuffer, XRT_STR_LITERAL("ab"), 3) ) {
		xrtStrBufFree(&tBuffer);
		return 1;
	}

	/* 移交：产物由 xrtFree 释放，构建器可继续复用。 */
	sResult = xrtStrBufTake(&tBuffer);
	if ( sResult == NULL ) {
		return 2;
	}
	printf("%s\n", sResult);
	xrtFree(sResult);
	return 0;
}

Что только что произошло. (1) xrtStrBufInit открывает дело со стековым дескриптором — внутренний буфер построителя растёт по потребности (стратегия удвоения); между двумя дописываниями items= и ab×3 нет промежуточных продуктов. (2) AppendRepeat — специализированный вход для повторного дописывания: потребности вида «один сегмент n раз» (разделители, отступы, заполнение) не требуют цикла от вас. (3) Take передаёт владение буфером вызывающему: без копии, без разделения; построитель возвращается в пустое состояние и готов к переиспользованию — семантика, полностью изоморфная xrtBufferTake главы 15; ритм «накопить — собрать — взять» главы 15 дословно действует и в мире строк. (4) На пути отказа xrtStrBufFree возвращает построитель — три конвенции контейнеров работают здесь как обычно.

25.4契约

• Представления в приоритете: обрезка, разрезание, проверки префикса/суффикса — без распределений; выходы-собственные-подотрезки — всегда представления.
• Владеющие продукты: Concat/Join/Dup/Replace/Format возвращают str, ровно одно освобождение xrtFree.
• Дисциплина построителя: три сегмента и больше — xstrbuf; после передачи Take построитель обнулён и переиспользуется; на пути отказа — Free.
• Семейство Case: без учёта регистра — специализированные CaseFind/CaseEqual, без «сперва преобразовать, потом сравнить».
• Семантика промаха: поиск возвращает XRT_NPOS, проверка — == XRT_NPOS (дисциплина сигнальных значений главы 3).
• Двоичная безопасность: все функции ходят на валюте (视图, 长度) (представление, длина); содержимое может содержать нулевые байты.

От примеров к инженерии: три хозяина строк

Параллельно трём хозяевам контейнеров (глава 23) у строк в инженерии три типовых хозяина. Запросный временный текст: конвейер представлений плюс стековый буфер, ноль распределений на всём пути — набор для обработки URL и разбора заголовков, кода, исполняющегося на каждый запрос. Накапливаемый вывод: построитель висит на контексте обработки, дописывает через множество обратных вызовов и один раз забирает в конце — стандартная форма строк журнала, строк отчётов, вывода сериализации. Долгоживущие поля: разобранные поля, обязанные пережить запрос (элементы конфигурации, ключи кеша), уходят в контейнеры владеющими продуктами Dup/Join — владение с этого момента принадлежит той структуре, которой управляет контейнер. Три хозяина отвечают трём ступеням «ноль распределений, позднее распределение, владение» и сверяются с языком памяти главы 5 с одного взгляда.

Одна привычка: сперва спросите, не подстрока ли выход

Перед любой текстовой функцией спросите: выход — собственный подотрезок входа? Да — возвращайте представление, ноль распределений (мир Trim/Cut/Slice); нет, но содержимое ограничено — пишите в буфер вызывающего (FilterTo/семейство To); нужна открытая длина — владеющий продукт или построитель. Эта привычка трёх вопросов отсекает большую часть расточительства «Dup на всякий случай» и большую часть аварий «возврат висячего представления» — самая ценная фраза, которую стоит унести из главы.

Типичные ошибки

str s = xrtStrDupView(Prefix);
s = xrtStrConcat((xstrview){ s, strlen(s) }, Host);   /* копирует всё накопленное */
s = xrtStrConcat((xstrview){ s, strlen(s) }, Path);   /* и ещё раз всё */
s = xrtStrConcat((xstrview){ s, strlen(s) }, Query);  /* и снова - O(n²) уже предрешено */

xstrbuf tBuf;
xrtStrBufInit(&tBuf);
xrtStrBufAppend(&tBuf, Prefix);
xrtStrBufAppend(&tBuf, Host);
xrtStrBufAppend(&tBuf, Path);
xrtStrBufAppend(&tBuf, Query);
str s = xrtStrBufTake(&tBuf);     /* одна передача владения, суммарное копирование O(n) */

xstrview getName(const char* sRaw)
{
	xstrview Text = xrtStrTrim((xstrview){ sRaw, strlen(sRaw) });
	xstrview Name;
	xrtStrCut(Text, XRT_STR_LITERAL("/"), &Name, NULL);
	return Name;   /* Name указывает внутрь sRaw - висячий, как только вызывающий сменит sRaw */
}

str getName(const char* sRaw)
{
	xstrview Text = xrtStrTrim((xstrview){ sRaw, strlen(sRaw) });
	xstrview Name;
	xrtStrCut(Text, XRT_STR_LITERAL("/"), &Name, NULL);
	return xrtStrDupView(Name);   /* чтобы жить долго - владейте собственной копией */
}

Практические задания

Итоги