Глава 19 Множества: xset

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

xset — контейнер, который «спрашивает только, есть ли оно тут»: добавления дедуплицируют, проверка принадлежности O(1), объединение/пересечение/разность/симметрическая разность вычисляются за один шаг. Он делит с xmap хеш-фундамент и итерацию по вставке, но смысловой центр тяжести иной — отображение заботится «на что отображается ключ», множество — «принадлежит ли ключ». Белые списки портов межсетевого экрана, группы тегов пользователей, разности прав, кодирование, дедуплицированный подсчёт — всё это задачи множеств. Главба вдавливает различие двух форм API — Unit для стековых дескрипторов против Destroy для результатов операций — дисциплина, которую стоит установить первой в главе о множествах.

19.1引入

Шлюз решает, какие порты пропускать: администратор включил {80, 443, 8080}, приложение запрашивает {3000, 443, 8080} — допущенное множество есть пересечение {443, 8080}, и главный образец главы — полная реализация именно этой сцены. На массивах: два вложенных цикла с дедупликацией, полтора десятка строк, квадратичная сложность, и «дедупликация» сама по себе магнит багов. На множествах: Add для загрузки, Intersection за шаг, итерация с печатью — три порции по две-три строки. Главное — семантика явная: в коде стоит само слово «пересечение», рецензенту не нужно реверс-инжинирить намерение из вложенных циклов.

Форма возврата операций множеств заслуживает отдельного внимания: Intersection / Union / Difference / SymmetricDifference возвращают выделенный в куче новый множество (указатель xset*) — результат живёт независимо от операндов, его можно продолжать обрабатывать или итерировать; цена — обязательный xrtSetDestroy по завершении. А множества «для загрузки» — стековые дескрипторы, уборка xrtSetUnit. Два вида объектов — две уборки; перепутать — утечка или висячий указатель; ловушка 1 занимается именно этим, а cleanup-сегмент образца, где обе уборки стоят рядом, — каноническая форма, которую стоит целиком унести в копилку.

19.2概念

Сперва рамка: все понятия главы разворачиваются вокруг трёх вопросов — как элементы входят (Add и значимая семантика), как судится принадлежность (Has и побайтовое равенство), как они комбинируются (алгебра и две уборки). Раздел Понятия идёт по этим трём вопросам, раздел Примеры даёт по одному полному ответу, раздел Ловушек исполняет две самые аварийные дисциплины. Оглянувшись после чтения, вы обнаружите: половина знаний главы на деле пришла из главы 18 — в этом сложный процент общих соглашений семейства контейнеров.

Изоморфизм с отображением

Фундамент множества — та же основа, что у xmap: хеш-локация, цепь порядка вставки, трёхчастная итерация (Begin/Next/End) — всё совпадает. Различий два: нет значения (элемент и есть ключ) и есть семейство операций алгебры множеств. Придя из главы 18, вам нужен только инкрементальный блок «алгебры» — две главы делят большую часть ловушек и контрактов (срок действия указателей итерации, запрет правок в середине).

Алгебра множеств

Общий контракт всех четырёх: возвращают новые выделенные в куче множества, порядок итерации результата наследует порядок вставки левого операнда. Результаты могут цепочкой входить в следующую операцию — многошаговая политика «сперва объединить, потом пересечь» пишется по одной операции на строку естественно.

Поток данных операций множеств

Одно вычисление политики — обычно несколько алгебр подряд; нарисованный поток данных нагляднее чтения кода:

Заметьте: продукт каждого шага — независимое кучевое множество; промежуточные результаты Destroy-ятся сразу по использовании, итоговый получает свой Destroy после итерации. Уборку цепочечных операций лучше писать рядом с операциями (вычислил — убрал), избегая списка «сперва всё посчитать, потом единообразно убрать» — последний на ошибочных путях пропускает Destroy чаще.

Значимая семантика и сравнение

Элементы — значения: Add копирует байты элемента в слот, sizeof(元素类型) объявляется при Init. Равенство элементов — побайтовое равенство; структуры с набивкой сперва обнуляются (иначе одинаковое значение с разной набивкой судится неравным). Хранить указатели можно, но множество сравнивает значения указателей, а не объекты по адресу — «множество тождеств объектов» и «множество значений объектов» — разные вещи; нужно второе — берите бизнесовый ключ (скажем, ID) элементом.

Итерация и запросы

Has судит принадлежность, Remove удаляет элемент, Count — публичное поле — три соглашения контейнера (глава 14) действуют дословно. Итерация выводит в порядке вставки и точно воспроизводится; образец set_tour дополнительно показывает обратную итерацию и обход в стиле посетителя (callback-форма) — обе того же корня, что и прямая трёхчастная.

19.3示例

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

Из репозиторного образца examples/containers/set/main.c:

 */

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



int main(void)
{
	xset tEnabled;           /* 栈句柄集合 A：已启用端口 */
	xset tRequested;         /* 栈句柄集合 B：请求端口 */
	xset* pAllowed = NULL;   /* 堆分配结果：A ∩ B */
	xsetiter tIterator;
	const int* pPort;
	int arrEnabled[] = { 80, 443, 8080 };
	int arrRequested[] = { 443, 3000, 8080 };
	int iResult = 0;

	if ( !xrtSetInit(&tEnabled, sizeof(int)) ) {
		return 1;
	}
	if ( !xrtSetInit(&tRequested, sizeof(int)) ) {
		xrtSetUnit(&tEnabled);
		return 1;
	}

	/* 装载两个集合；Add 天然去重（重复元素不增加数量）。 */
	for ( size_t i = 0; i < 3; i++ ) {
		if ( !xrtSetAdd(&tEnabled, &arrEnabled[i]) ||
			!xrtSetAdd(&tRequested, &arrRequested[i]) ) {
			iResult = 2;
			goto cleanup;
		}
	}

	/* 交集：请求 ∩ 启用 = {443, 8080}；结果是新分配的堆集合。 */
	pAllowed = xrtSetIntersection(&tRequested, &tEnabled);
	if ( pAllowed == NULL ) {
		iResult = 3;
		goto cleanup;
	}

	/* 按插入顺序（即请求集合中的出现顺序）打印放行端口。 */
	if ( !xrtSetIterBegin(pAllowed, &tIterator) ) {
		iResult = 4;
		goto cleanup;
	}
	while ( (pPort = (const int*)xrtSetIterNext(&tIterator)) != NULL ) {
		printf("allowed port: %d\n", *pPort);
	}
	xrtSetIterEnd(&tIterator);

cleanup:
	/* 两类句柄两类收尾：堆结果 Destroy，栈句柄 Unit。 */
	if ( pAllowed != NULL ) {
		xrtSetDestroy(pAllowed);
	}
	xrtSetUnit(&tRequested);
	xrtSetUnit(&tEnabled);
	return iResult;
}

Что только что произошло. (1) Два множества со стековыми дескрипторами, каждое Init(sizeof(int)), загружаются циклами Add — 3000 есть в запрошенном, но не во включённом; его судьба решена уже на пересечении. (2) Intersection(&tRequested, &tEnabled) возвращает кучевое множество pAllowed — заметьте, это указатель, другой вид объекта, нежели стековый дескриптор tRequested. (3) Итерация выводит 443, 8080 в порядке вставки левого операнда (запрошенного множества) — порядок результата воспроизводим и годится в тестовые утверждения. (4) Уборка — дисциплинарная сцена главы: pAllowed — результат операции, Destroy; tRequested/tEnabled — стековые дескрипторы, Unit — ни одну из двух уборок нельзя перепутать, и обе на месте в goto cleanup ошибочного пути.

Вторая полная программа: полный тур по интерфейсу множества

Из examples/containers/set_tour/main.c, покрывая жизненный цикл, запросы, алгебру и два стиля обхода:

 */

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

static bool exampleVisitCount(const void* pItem, ptr pUserData)
{
	size_t* pSeen = (size_t*)pUserData;

	(void)pItem;
	*pSeen = *pSeen + 1u;
	return *pSeen < 2u;  /* 第二个元素停止 */
}

int main(void)
{
	xset* pA = NULL;
	xset* pB = NULL;
	xset* pMerged = NULL;
	xset* pUnion = NULL;
	xset* pDiff = NULL;
	xset* pSym = NULL;
	xset tAligned;
	xsetiter Iter;
	const void* pSlot = NULL;
	bool bNew = false;
	size_t iSeen = 0;
	int i;
	int iResult = 1;
	int Values[5];

	for ( i = 0; i < 5; ++i ) {
		Values[i] = i + 1;
	}

	/* ---- 生命周期：堆/内嵌对齐 + 容量族 ---- */
	pA = xrtSetCreate(sizeof(int));
	if ( (pA == NULL) ||
		!xrtSetAdd(pA, &Values[0]) ||
		!xrtSetAdd(pA, &Values[1]) ||
		(xrtSetCount(pA) != 2u) ||
		(xrtSetCapacity(pA) < 2u) ||
		!xrtSetReserve(pA, 16u) ||
		!xrtSetTrim(pA) ||
		(xrtSetCount(pA) != 2u) ) {
		goto Cleanup;
	}
	{
		xset* pAligned = xrtSetCreateAligned(sizeof(int),
			sizeof(int));

		if ( (pAligned == NULL) ||
			!xrtSetAdd(pAligned, &Values[0]) ) {
			goto Cleanup;
		}
		xrtSetDestroy(pAligned);
	}
	if ( !xrtSetInitAligned(&tAligned, sizeof(int),
			sizeof(int)) ||
		!xrtSetAdd(&tAligned, &Values[2]) ||
		(xrtSetCount(&tAligned) != 1u) ) {
		goto Cleanup;
	}
	xrtSetClear(&tAligned);
	if ( (xrtSetCount(&tAligned) != 0u) ||
		!xrtSetHas(pA, &Values[0]) ) {
		goto Cleanup;  /* Clear 只影响内嵌集合 */
	}
	xrtSetUnit(&tAligned);
	printf("set: lifecycle count=2 cap>=2 trim=1 clear=0\n");

	/* ---- 查询族：GetOrAdd 双路径 / Has / Remove / Visit ---- */
	pSlot = xrtSetGetOrAdd(pA, &Values[0], &bNew);
	if ( (pSlot == NULL) || bNew ||
		(*(const int*)pSlot != Values[0]) ) {
		goto Cleanup;  /* 已存在：不新增 */
	}
	pSlot = xrtSetGetOrAdd(pA, &Values[2], &bNew);
	if ( (pSlot == NULL) || !bNew ||
		(xrtSetCount(pA) != 3u) ) {
		goto Cleanup;  /* 不存在：插入并报告新 */
	}
	if ( !xrtSetHas(pA, &Values[1]) ||
		xrtSetHas(pA, &Values[3]) ||
		!xrtSetRemove(pA, &Values[2]) ||
		(xrtSetCount(pA) != 2u) ||
		xrtSetRemove(pA, &Values[2]) ) {
		goto Cleanup;
	}
	iSeen = 0;
	if ( (xrtSetVisit(pA, exampleVisitCount, &iSeen) != 2u) ||
		(iSeen != 2u) ) {
		goto Cleanup;
	}
	printf("set: queries get-or-add new=0/1 has=1/0 remove=1\n");

	/* ---- 代数运算：A={1,2} B={3,4} ---- */
	pB = xrtSetCreate(sizeof(int));
	if ( (pB == NULL) ||
		!xrtSetAdd(pB, &Values[2]) ||
		!xrtSetAdd(pB, &Values[3]) ||
		!xrtSetIsDisjoint(pA, pB) ) {
		goto Cleanup;
	}
	/* Merge：B 并入 A → {1,2,3,4}。 */
	pMerged = xrtSetCreate(sizeof(int));
	if ( (pMerged == NULL) ||
		!xrtSetAdd(pMerged, &Values[0]) ||
		!xrtSetMerge(pMerged, pB) ||
		(xrtSetCount(pMerged) != 3u) ) {
		goto Cleanup;
	}
	/* Union：{1,2}∪{3,4} = {1,2,3,4}。 */
	pUnion = xrtSetUnion(pA, pB);
	if ( (pUnion == NULL) || (xrtSetCount(pUnion) != 4u) ||
		!xrtSetHas(pUnion, &Values[3]) ) {
		goto Cleanup;
	}
	/* Difference：{1,2,3,4}-{2,3} 场景：用 Union-{3,4} → {1,2}。 */
	pDiff = xrtSetDifference(pUnion, pB);
	if ( (pDiff == NULL) || (xrtSetCount(pDiff) != 2u) ||
		xrtSetHas(pDiff, &Values[2]) ) {
		goto Cleanup;
	}
	/* SymmetricDifference：{1,2,3}△{3,4} = {1,2,4}。 */
	{
		xset* pThree = xrtSetCreate(sizeof(int));

		if ( (pThree == NULL) ||
			!xrtSetAdd(pThree, &Values[0]) ||
			!xrtSetAdd(pThree, &Values[1]) ||
			!xrtSetAdd(pThree, &Values[2]) ) {
			goto Cleanup;
		}
		pSym = xrtSetSymmetricDifference(pThree, pB);
		if ( (pSym == NULL) || (xrtSetCount(pSym) != 3u) ||
			xrtSetHas(pSym, &Values[2]) ||
			!xrtSetHas(pSym, &Values[3]) ) {
			goto Cleanup;
		}
		
		 * {1,2,3} 不是 {1,2} 的子集；超集方向相反。 */
		if ( xrtSetIsSubset(pThree, pA, false) ||
			!xrtSetIsSubset(pA, pThree, false) ||
			!xrtSetIsSubset(pA, pThree, true) ||
			!xrtSetIsSuperset(pThree, pA, false) ||
			!xrtSetIsSuperset(pThree, pA, true) ||
			xrtSetIsSuperset(pA, pThree, false) ||
			xrtSetIsDisjoint(pA, pThree) ) {
			goto Cleanup;
		}
		/* Equal：A 与其克隆相等。 */
		{
			xset* pClone = xrtSetClone(pA);

			if ( (pClone == NULL) ||
				!xrtSetEqual(pA, pClone) ) {
				goto Cleanup;
			}
			xrtSetDestroy(pClone);
		}
		xrtSetDestroy(pThree);
	}
	printf("set: algebra union=4 diff=2 sym=2 subset/super/disjoint"
		"\n");

	/* ---- 逆序迭代：补回 3 后集合为 {1,2,3} ---- */
	{
		int iExpect = 3;

		if ( !xrtSetAdd(pA, &Values[2]) ||
			(xrtSetCount(pA) != 3u) ) {
			goto Cleanup;
		}

		if ( !xrtSetIterRBegin(pA, &Iter) ) {
			goto Cleanup;
		}
		while ( (pSlot = xrtSetIterNext(&Iter)) != NULL ) {
			/* 哈希集合无序约束：只统计个数与内容集合。 */
			int iValue = *(const int*)pSlot;

			if ( (iValue < 1) || (iValue > 3) ) {
				goto Cleanup;
			}
			--iExpect;
		}
		xrtSetIterEnd(&Iter);
		if ( iExpect != 0 ) {
			goto Cleanup;
		}
	}
	printf("set: rbegin order=3..1 visit=stopped\n");
	iResult = 0;

Cleanup:
	xrtSetDestroy(pUnion);
	xrtSetDestroy(pDiff);
	xrtSetDestroy(pSym);
	xrtSetDestroy(pMerged);
	xrtSetDestroy(pB);
	xrtSetDestroy(pA);
	return iResult;
}

Что только что произошло. (1) Строка жизненного цикла: публичное поле Count, ёмкость Reserve/Trim (трёхчастный набор ёмкости главы 14 на множествах — те же имена и смыслы), Clear в ноль. (2) Строка запросов: у множеств тоже есть форма GetOrAdd (подтвердить существование и различить старое с новым), Has и Remove проверены парами успех/неудача. (3) Строка алгебры: счёт результатов объединения, разности и симметрической разности утверждается по одному, плюс суждения подмножество/надмножество/непересечение — проверка отношений не выделяет новое множество и возвращает булевы значения напрямую. (4) Строка обхода: обратная итерация (3..1) и посещение в callback-стиле (с возможной остановкой — visit=stopped доказывает семантику прерывания возвратом false) — два варианта трёхчастной, берите по сцене.

От образцов к инженерии: три точки приземления множества

Белый список портов — «безопасность»; ещё две точки не менее часты. Теги и группировки: группа пользователей несёт несколько тегов, один тег покрывает нескольких пользователей — «пользователи с тегами A и B одновременно» — пересечение, «A без B» — разность; система тегов по существу — комбинаторика операций множеств. Таблицы законных переходов автомата состояний: пары «текущее состояние × вход → законно» делаются множеством, и проверка законности перед переходом — один Has — незаконные переходы табулируются на этапе проектирования, а не рассыпаны по цепочкам if. Три точки делят API главы; различие лишь в типе элемента и комбинациях операций — множество самый «бизнесовый по вкусу» контейнер тома 3, и выбирают его часто не ради производительности, а чтобы в коде стояли сами бизнесовые слова — пересечение, объединение, разность.

19.4契约

• Две уборки: стековые дескрипторы Unit; результаты операций и продукты Create Destroy — какая уборка у множества, зависит от того, как оно родилось.
• Независимость результата: пересечение и родня не зависят от выживания операндов; результат остаётся действительным и после уничтожения операндов.
• Порядок результата: результаты алгебры наследуют порядок вставки левого операнда; весь вывод итераций воспроизводим.
• Равенство значений: побайтовое равенство — равенство элементов; набивку структур обнулять сперва; элементы-указатели сравниваются по значениям указателей.
• Дисциплина итерации: та же, что у xmap — три части, указатели итерационного периода не покидают итерацию, запрет правок в середине.
• Инженерные точки: белые списки/группировки тегов/таблицы переходов — в коде множеств стоят сами бизнесовые слова.

Привычка чтения кода множеств

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

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

xset* pAllowed = xrtSetIntersection(&tRequested, &tEnabled);
/* ... используем pAllowed ... */
xrtSetUnit(pAllowed);            /* Unit не освобождает кучевое множество - утечка */

xset* pAllowed = xrtSetIntersection(&tRequested, &tEnabled);
/* ... используем pAllowed ... */
xrtSetDestroy(pAllowed);          /* результат операции: Destroy */
xrtSetUnit(&tRequested);          /* стековый дескриптор: Unit */
xrtSetUnit(&tEnabled);

typedef struct portspec { short Port; int Enabled; } portspec;   /* с набивкой */
portspec A; A.Port = 443; A.Enabled = 1;                          /* набивка не тронута */
xrtSetAdd(&tSet, &A);                                             /* входит во множество со случайной набивкой */

portspec A;
memset(&A, 0, sizeof(A));          /* сперва обнулить, потом присвоить - набивка детерминирована */
A.Port = 443; A.Enabled = 1;
xrtSetAdd(&tSet, &A);

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

Итоги