Chapter 19 Sets: xset

Chapter Orientation

xset is the container that "only asks whether it's in there": adds deduplicate, membership checks are O(1), and union/intersection/difference/symmetric difference compute in one step. It shares the hash foundation and insertion-order iteration with xmap, but the semantic center of gravity differs — the map cares about "what the key maps to", the set cares about "whether the key belongs". Firewall port whitelists, user tag groups, permission differences, deduplicated counting of encodings — all set problems. This chapter nails the difference between two API shapes — Unit for stack handles versus Destroy for operation results — the discipline most worth establishing first in a set chapter.

19.1引入

A gateway must decide which ports to allow: the administrator enabled {80, 443, 8080}, the application requests {3000, 443, 8080} — the allowed set is the intersection {443, 8080}, and this chapter's main example implements exactly this scene. With arrays: two nested loops deduplicating, a dozen-plus lines, quadratic complexity, and "deduplication" itself a bug magnet. With sets: Add to load, Intersection in one step, iterate and print — three segments of two or three lines each. More importantly the semantics are explicit: what appears in the code is the word "intersection" itself; a reviewer need not reverse-engineer intent out of nested loops.

The return shape of set operations deserves particular attention: Intersection / Union / Difference / SymmetricDifference return a heap-allocated new set (an xset* pointer) — the result lives independently of its operands; you can keep operating on it or iterating it; the price is that it must be xrtSetDestroy-ed when done. Sets used "for loading" are stack handles finished with xrtSetUnit. Two object kinds, two finishes — mixing them up is a leak or a dangling reference; pitfall 1 polices exactly this, and the example's cleanup segment — both finishes side by side — is the canonical form worth copying wholesale.

19.2概念

First a framing: all of the set's concepts unfold around three questions — how elements enter (Add and value semantics), how membership is judged (Has and byte equality), how they combine (the algebra and the two finishes). The Concepts section unfolds along these three questions, the Examples section gives one complete answer each, and the Pitfalls section enforces the two most crash-prone disciplines. Looking back after reading you will find: half of this chapter's knowledge actually came from Chapter 18 — precisely the compound interest of the container family's shared conventions.

Isomorphism with the map

The set's foundation is the same stock as xmap: hash location, insertion-order chain, three-part iteration (Begin/Next/End) all identical. Only two differences: there is no value (the element is the key), and there is a family of set-algebra operations. Coming from Chapter 18, you only need the incremental "algebra" block — the two chapters share most of their pitfalls and contracts (iteration-pointer validity, no edits mid-iteration).

Set algebra

The shared contract of all four: they return newly allocated heap sets, and the iteration order follows the left operand's insertion order. Results can chain into the next operation — a "union first, then intersect" multi-step policy writes naturally as one operation per line.

The data flow of set operations

One policy computation is usually several algebras in series; drawing the data flow is more intuitive than reading code:

Note that every step's product is an independent heap set: intermediate results get Destroy-ed as soon as they're used, the final result after iteration gets its Destroy. Cleanup for chained operations is best written alongside the operations (evaluate-and-clean), avoiding the "compute everything first, clean up in one batch" long list — the latter leaks more easily on error paths.

Value semantics and comparison

Elements are values: Add copies the element bytes into the slot, sizeof(元素类型) (element type) declared at Init. Element equality is byte equality — structs with padding must be zeroed before entering the set (otherwise the same value with different padding is judged unequal). Storing pointers works, but the set compares pointer values, not the objects pointed to — an "object-identity set" and an "object-value set" are different things; when you need the latter, use the business key (say an ID) as the element.

Iteration and queries

Has judges membership, Remove deletes an element, Count is a public field — the container's three conventions (Chapter 14) apply verbatim. Iteration outputs in insertion order, exactly reproducible; the set_tour sample also demonstrates reverse iteration and visitor-style traversal (callback form), both of the same stock as the forward three-parter.

19.3示例

Complete program: port-whitelist intersection

From the repository example 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;
}

What just happened. (1) Two stack-handle sets each Init(sizeof(int)), loaded by Add loops — 3000 is in the requested set but not in the enabled set; its fate was sealed at the intersection. (2) Intersection(&tRequested, &tEnabled) returns the heap set pAllowed — note it is a pointer, a different object kind from the stack handle tRequested. (3) The iteration outputs 443, 8080, ordered along the left operand's (requested set's) insertion order — the result order reproduces and can go into test assertions. (4) The cleanup is this chapter's discipline scene: pAllowed is an operation result, Destroy; tRequested/tEnabled are stack handles, Unit — neither of the two finishes may be misplaced, and the failure-path goto cleanup carries both.

Complete program: a full-interface tour of the set

From examples/containers/set_tour/main.c, covering lifecycle, queries, algebra, and two traversal styles:

 */

#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;
}

What just happened. (1) The lifecycle line: the public Count field, capacity Reserve/Trim (Chapter 14's capacity three-piece set, same names and meanings on sets), Clear back to zero. (2) The queries line: sets also have a GetOrAdd shape (confirm existence and distinguish old from new), with Has and Remove verified as success/failure pairs. (3) The algebra line: result counts of union, difference, and symmetric difference asserted one by one, plus subset/superset/disjoint judgments — relation checks allocate no new set and return booleans directly. (4) The traversal line: reverse iteration (3..1) and callback-style visiting (stoppable midway — visit=stopped proves the abort semantics of the callback returning false) — two variants of the three-parter, take as the scene demands.

From examples to engineering: the set's three landing points

The port whitelist is the set's "security" landing point; the other two are equally frequent. Tags and groupings: a group of users carries several tags, one tag covers several users — "users with both tag A and tag B" is an intersection, "A without B" is a difference; a tag system is at heart a combination punch of set operations. State-machine legal-transition tables: make "current state × input → legal" pairs into a set, and the pre-transition legality check is one Has — illegal transitions are tabulated at design time instead of scattered through if chains. The three landing points share this chapter's API; they differ only in element type and operation combinations — the set is Volume 3's most "business-flavored" container, and choosing it is often not for performance but so that the business vocabulary itself — intersection, union, difference — appears in the code.

19.4契约

• Two finishes: stack handles Unit; operation results and Create products Destroy — which finish a set takes depends on how it was born.
• Result independence: intersection and friends do not depend on their operands' survival; the result stays valid after the operands are destroyed.
• Result order: algebra results follow the left operand's insertion order; all iteration outputs reproduce.
• Value equality: byte equality is element equality; zero-pad structs first; pointer elements compare pointer values.
• Iteration discipline: same as xmap — three parts, iteration-period pointers stay in the iteration, no edits mid-iteration.
• Engineering landing points: whitelists/tag groupings/transition tables — set code contains the business vocabulary itself.

A habit for reading set code

Set operations shorten code but make "intermediate products" invisible — three operations chained on one line mean three temporary sets alive on the heap at once. Build the habit of reading set code: on seeing Intersection silently say "one heap set"; on seeing a chain, count the intermediates. Pair it with Chapter 6's stats for a checkup: run set-dense logic and watch whether the live-bytes curve is a "sawtooth" (allocation-release pairs) rather than a "staircase" (up only) — sawtooth is healthy, staircase leaks; this reading is far faster than line-by-line review.

Common Mistakes

xset* pAllowed = xrtSetIntersection(&tRequested, &tEnabled);
/* ... use pAllowed ... */
xrtSetUnit(pAllowed);            /* Unit does not free a heap set - leak */

xset* pAllowed = xrtSetIntersection(&tRequested, &tEnabled);
/* ... use pAllowed ... */
xrtSetDestroy(pAllowed);          /* operation result: Destroy */
xrtSetUnit(&tRequested);          /* stack handle: Unit */
xrtSetUnit(&tEnabled);

typedef struct portspec { short Port; int Enabled; } portspec;   /* has padding */
portspec A; A.Port = 443; A.Enabled = 1;                          /* padding untouched */
xrtSetAdd(&tSet, &A);                                             /* enters the set with random padding */

portspec A;
memset(&A, 0, sizeof(A));          /* zero first, then assign - padding is deterministic */
A.Port = 443; A.Enabled = 1;
xrtSetAdd(&tSet, &A);

Programming Exercises

Summary