Глава 14 Динамический массив xarray

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

Том 3 начинается с самого употребимого контейнера. xarray хранит байты элементов непрерывно и напрямую — дружелюбно к кэшу, ноль пообъектных распределений; с публичным полем Count и совместимым с qsort интерфейсом сортировки он закрывает высочастотный путь «загрузить пачку записей, отсортировать, обойти». Глава разбирает и его брата-близнеца xptrarray (хранит указатели, держит полиморфные объекты), пришпиливая уже в первой главе вопрос выбора «семантика значения против семантики указателя», пронизывающий том 3. Общие соглашения семейства контейнеров (жизненный цикл Init/Unit, отказ без побочных эффектов, граница заимствования и владения) также устанавливаются отсюда.

14.1引入

Фоновый сервис ведёт список «сейчас онлайн»: тысячи на пике, десятки вставок и удалений в секунду плюс периодический вывод, отсортированный по приоритету. На языке контейнеров это три фразы: добавление амортизируется O(1), сортировка на месте с нулём распределений, обход дружелюбен кэшу. Голый массив заставляет самого управлять ростом и копированием; связный список теряет непрерывность, сортировка деградирует; собственное колесо встречает отказные пути главы 6. Ответ xarray прост: непрерывное хранение + удвоение роста + пакетные операции — добавить три записи — один memcpy, сортировка — qsort на месте, обход — самый кэш-дружелюбный последовательный доступ. Простые схемы выигрывают на константах, а споры о производительности контейнеров — по большей части споры о константах.

Когда простого недостаточно? Крупные элементы с частыми вставками-удалениями в середине — цена пересылки непрерывного хранения растёт линейно: это территория AVL-дерева главы 20 и отображения главы 18; элементам нужна полиморфность (разные конкретные типы вперемешку) — семантика значения их не вместит: территория xptrarray и указательных контейнеров. Одна менее очевидная граница: когда «по индексу» самого мало и внешнему миру нужен устойчивый идентификатор объекта, индексы массива дрейфуют при удалении — территория поколенческих дескрипторов slot_map главы 17. В мире контейнеров нет панацеи, есть лишь всё более точная карта выбора; эта глава — её первый кусочек мозаики.

14.2概念

Семантика значения: элемент — это просто байты

xrtArrayInit(&arr, sizeof(元素类型)) (тип элемента — дословный токен ниже) берёт только размер элемента — массив полностью генеричен по типу. Элементы встроены напрямую в собственную память массива: нет пообъектных распределений (добавление 100 элементов может не выделить ни одного), нет прыжков по указателям (предзагрузчик работает в полную силу), адреса элементов стабильны до роста, после — переезжают целиком. Прямое следствие семантики значения: указатели на элементы, взятые при удержании массива, после роста недействительны — главный герой ловушки 1 этой главы.

Жизненный цикл и публичные поля

tRecords.Count — публичное поле: обходу и проверке ёмкости не нужны вызовы функций. Всеобщее соглашение контейнеров XRT: состояние только для чтения — публичные поля; операции, способные отказать, — функции (возвращая bool в паре со слотом ошибки главы 4). Это даёт чтению на горячих путях нулевые накладные расходы при полной диагностике путей отказа.

Стратегия роста и Reserve

Ёмкость динамического массива растёт удвоением: при нехватке расширяется кратно и переселяется целиком. Это гарантирует амортизационную оценку «добавление N элементов стоит O(N) пересылок» — но одиночный Append всё же может запустить большое распределение. Когда порядок известен, Reserve(N) приходит одним шагом, превращая амортизацию в определённость: перед загрузкой ста тысяч записей Reserve(100000) делает весь прогон одним распределением. Парная Resize явно задаёт число элементов (новоприбывшие нули), Trim поджимает ёмкость к текущему числу — по завершении загрузки и переходе в фазу только чтения один Trim — и долговременно живущая память немедленно опрятна. Тройка ёмкости (Reserve/Resize/Trim) — стандарт всех динамических контейнеров тома 3, семантика на xarray, xbuffer, xmap одинакова.

Сортировка и поиск

xrtArraySort принимает совместимую с qsort функцию сравнения — годится любой компаратор, написанный по трёхзначному </>. Форма (a>b)-(a<b) из примера заслуживает изучения: она избегает переполнения вычитания a-b (две большие отрицательные разности переворачивают знак, тихо расстраивая сортировку). Отсортированный массив можно бинарно искать по индексу семейством поиска; функции поиска принимают обе формы — «по элементу» и «по ключу» (компаратор-колбэк).

Массив указателей: вход в полиморфизм

Массив значений закрывает «плотное хранение однотипных элементов», но два класса требований он естественно не принимает: элементы разных конкретных типов (семейство фигур рендерера, семейство узлов интерпретатора) или владение элементами в другом месте (кэш не владеет объектами, только ссылается). xptrarray хранит указатели — элементы могут быть разных конкретных типов (полиморфизм через общий заголовок), могут принадлежать другому контейнеру, могут быть стековыми объектами. Цена: лишний косвенный прыжок на операцию и пообъектным жизненным циклом ведаете вы (Unit массива не освобождает то, на что указывают указатели). Мнемоника выбора: элементы однотипны и частый цельный обход → массив значений; элементы полиморфны или владение в другом месте → массив указателей. Есть скрытый, но частый третий вариант — смешанный: массив значений хранит «ключи и дескрипторы» как плотный индекс, тела объектов разбросаны по пулу или slot_map (глава 17). Упражнение этой главы с таблицей сессий репетирует именно архитектуру «массив + дескриптор», а таблица соединений главы 67 — её полный цвет.

Кроме Init, стоят знания ещё двух стартовых поз: Create напрямую возвращает объект массива в куче (сам дескриптор в куче — удобно для долгого удержания внутри других структур), InitAligned задаёт выравнивание элементов (сценарии SIMD или атомарных полей). Clear обнуляет число элементов, сохраняя ёмкость — при переиспользовании пачки массивов в цикле Clear куда быстрее пары Unit/Init и не трогает аллокатор.

14.3示例

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

Из примера репозитория examples/containers/array/main.c:

 */

#include <stdio.h>

#include <xrt.h>



/* 示例记录：整条记录（而非指针）会直接放进数组内存。 */
typedef struct examplerecord {
	int ID;
	int Priority;
} examplerecord;






 */
static int exampleCompareRecord(const void* pLeft, const void* pRight)
{
	const examplerecord* pLeftRecord = (const examplerecord*)pLeft;
	const examplerecord* pRightRecord = (const examplerecord*)pRight;

	return (pLeftRecord->Priority > pRightRecord->Priority) -
		(pLeftRecord->Priority < pRightRecord->Priority);
}



int main(void)
{
	xarray tRecords;         /* 栈上句柄；缓冲由数组自己管理 */
	examplerecord pInput[] = {
		{ 101, 30 },
		{ 102, 10 },
		{ 103, 20 }
	};

	/* 初始化只需要元素大小——数组对元素类型完全泛型。 */
	if ( !xrtArrayInit(&tRecords, sizeof(examplerecord)) ) {
		return 1;
	}

	/* 一次追加 3 条（单次 memcpy + 可能的扩容），再原地排序。 */
	if (
		!xrtArrayAppend(&tRecords, pInput, 3) ||
		!xrtArraySort(&tRecords, exampleCompareRecord)
	) {
		xrtArrayUnit(&tRecords);
		return 2;
	}

	


	 */
	for ( size_t i = 0; i < tRecords.Count; i++ ) {
		examplerecord* pRecord = (examplerecord*)xrtArrayGet(&tRecords, i);

		printf("id=%d priority=%d\n", pRecord->ID, pRecord->Priority);
	}
	xrtArrayUnit(&tRecords);
	return 0;
}

Что только что произошло. (1) xrtArrayInit берёт только размер элемента — генеричность без макросов и шаблонов, «переправкой байтов». (2) xrtArrayAppend(&tRecords, pInput, 3) добавляет три записи за раз (один memcpy плюс возможный рост); пакетный интерфейс экономит два вызова функций и две проверки ёмкости против поштучного Append. (3) xrtArraySort сортирует перемешанный вход на месте по возрастанию приоритета — порядок вывода 10/20/30 подтверждает. (4) Обход — публичное поле Count и Get; Get возвращает прямой указатель в память массива (чтение и запись), за границей NULL. (5) Unit возвращает буфер — дескриптор массива сам на стеке, возвращается только кучный буфер.

Полная программа: обход массива указателей

Из examples/containers/ptr_array/main.c, демонстрация хранения и обхода в семантике указателя:

 */

#include <stdio.h>
#include <xrt.h>



int main(void)
{
	xptrarray tArray;
	int iFirst = 10;
	int iSecond = 20;
	int iThird = 30;

	if ( !xrtPtrArrayInit(&tArray) ) {
		return 1;
	}

	


	 */
	if (
		!xrtPtrArrayPush(&tArray, &iFirst) ||
		!xrtPtrArrayPush(&tArray, &iSecond) ||
		!xrtPtrArrayInsert(&tArray, 1, &iThird)
	) {
		xrtPtrArrayUnit(&tArray);
		return 2;
	}

	/* 解引用打印：Get 返回 ptr，转回 int* 后取值。 */
	for ( size_t i = 0; i < tArray.Count; i++ ) {
		printf("[%zu] %d\n", i, *(int*)xrtPtrArrayGet(&tArray, i));
	}

	/* 释放的是指针槽位本身；栈上的目标对象不受影响。 */
	xrtPtrArrayUnit(&tArray);
	return 0;
}

Что только что произошло. Массив хранит ptr — ссылки на объекты, живущие в другом месте. Извлечённый при обходе элемент — «значение указателя», тела объектов не в памяти массива. Законны все три типичных источника: стековые объекты (этот пример), объекты, принадлежащие другим контейнерам, объекты, выделенные вами поштучно и освобождаемые поштучно. Заметьте: Unit массива указателей возвращает только хранилище слотов — ни один указуемый объект не будет освобождён; дисциплина владения целиком на вызывающем — ровно тема ловушки 2.

Прочтя оба примера рядом, компромисс «значение против указателя» становится объёмным: массив значений грузит три записи одним memcpy, сортирует перестановкой целых блоков, обходит с нулевой косвенностью; массив указателей добавляет разыменование на операцию, сортирует перестановкой 8-байтовых указателей (тела элементов неподвижны — для крупных объектов это преимущество!) и поддерживает полиморфное смешивание. Правило большого пальца: элементы меньше кэш-строки и однотипны — массив значений почти всегда выигрывает; элементы огромны, из разных источников распределения или требуют полиморфизма — массив указателей.

Общие соглашения семейства контейнеров (действуют с этой главы)

Три соглашения, установленные здесь, проходят через весь том 3; заложим их сейчас, дальше главы ссылаются напрямую. Соглашение первое: дескриптор на стеке, память в куче — Init открывается стековым дескриптором, контейнер ведает буферами, Unit возвращает точно; самому объекту контейнера в куче — пара Create/Destroy. Соглашение второе: чтение полями, запись функциями — состояние только для чтения (Count, Size, Data) публично, чтение без накладных расходов; операции, способные отказать, все через возвращаемые значения функций со слотом ошибки главы 4. Соглашение третье: отказ без побочных эффектов — любое редактирование при неудаче оставляет контейнер в состоянии до вызова, и код секции Cleanup пишется без тревоги. Выгода трёх соглашений капает сложным процентом в каждой следующей главе: читая любой новый контейнер, вы уже знаете форму его жизненного цикла, стиль полей и семантику отказа — новым остаётся один вопрос: «в чём этот контейнер хорош».

14.4契约

• Жизненный цикл: Init/Unit точно в паре; пути отказа тоже Unit (отказ без побочных эффектов делает строку очистки всегда безопасной).
• Публичные поля: Count и прочее чтение напрямую; способное отказать — через возвращаемые значения.
• Время жизни указателей: рост обнуляет действительность указателей на элементы — нужны устойчивые адреса, готовьте ёмкость заранее или берите массив указателей/список.
• Поведение за границей: Get за границей NULL; редактирование за границей отказывает с ошибкой — никогда запись за границей.
• Владение массива указателей: Unit не освобождает указуемые элементы; кто выделил, тот освобождает.
• Компараторы: трёхзначный стиль (a>b)-(a<b); a-b запрещено (переполнение).
• Тройка ёмкости: Reserve прерасширяет, Resize фиксирует длину, Trim поджимает; Clear обнуляет с сохранением ёмкости; семантика едина во всех динамических контейнерах тома 3.

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

examplerecord* pRecord = (examplerecord*)xrtArrayGet(&tRecords, 0);
xrtArrayAppend(&tRecords, pMore, 100);   /* может запустить рост + переселение */
pRecord->ID = 42;                         /* pRecord смотрит в освобождённый старый буфер */

examplerecord* pRecord;
xrtArrayAppend(&tRecords, pMore, 100);   /* сперва операция, возможно растущая */
pRecord = (examplerecord*)xrtArrayGet(&tRecords, 0);   /* потом указатель */
pRecord->ID = 42;

xptrarray tObjects;
/* ... загрузить пачку объектов из xrtMalloc ... */
xrtPtrArrayUnit(&tObjects);   /* возвращает только слоты — утекают все элементы */

for ( size_t i = 0; i < tObjects.Count; i++ ) {
	xrtFree(xrtPtrArrayGet(&tObjects, i));   /* сперва элементы по одному */
}
xrtPtrArrayUnit(&tObjects);                  /* потом сам массив */

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

Итоги