Chapter 14 The Dynamic Array: xarray

Chapter Orientation

Volume 3 begins with the most used container. xarray stores elements' bytes contiguously and directly — cache-friendly, zero per-element allocation, paired with the public Count field and a qsort-compatible sort interface, covering the highest-frequency path of "hold a batch of records, sort, iterate". The chapter also covers its twin xptrarray (storing pointers, holding polymorphic objects), pinning down in the very first chapter the "value semantics versus pointer semantics" selection question that runs through Volume 3. The container family's shared conventions (Init/Unit lifecycle, no side effects on failure, the borrowing-versus-owning boundary) are also established starting here.

14.1引入

A backend service maintains the "currently online sessions" list: thousands at peak, tens of inserts and removals per second, plus periodic priority-ordered output. Translated into container language: append must amortize O(1), sort must be in-place with zero allocation, iteration must be cache-friendly. A bare array makes you manage growth and copying yourself; a linked list loses contiguity and degrades sorting; rolling your own faces the failure paths Chapter 6 documents. xarray's answer is plain: contiguous storage + doubling growth + batch operations — appending three elements is one memcpy, sorting is in-place qsort semantics, iteration is the most cache-friendly sequential access. Plain schemes win on constant factors, and container performance debates are mostly debates of constant factors.

When is the plain scheme not enough? With large elements and frequent mid-sequence inserts/deletes, the shifting cost of contiguous storage grows linearly — that is the territory of Chapter 20's AVL tree and Chapter 18's map; when elements need polymorphism (mixed concrete types), value semantics cannot hold them — that is the territory of xptrarray and the pointer containers. One less obvious boundary: when "by index" itself is not enough and the outside needs stable object identity, array indices drift on removal — that is the territory of Chapter 17's slot_map generation handles. The container world has no panacea, only an ever more precise selection map; this chapter is its first puzzle piece.

14.2概念

Value semantics: an element is just bytes

xrtArrayInit(&arr, sizeof(元素类型)) (element type verbatim below) takes only the element size — the array is fully generic over the element type. Elements are embedded directly in the array's own memory: no per-element allocation (appending 100 elements may allocate not even once), no pointer hopping (the prefetcher works at full strength during iteration), and element addresses stay stable until a growth, after which everything relocates wholesale. The direct corollary of value semantics: element pointers taken while holding the array become invalid after growth — the protagonist of this chapter's Pitfall 1.

Lifecycle and public fields

tRecords.Count is a public field — iteration and capacity checks need no function call. XRT containers' universal convention: read-only state goes through public fields; fallible operations go through functions (returning bool with Chapter 4's error slot). This gives hot-path reads zero overhead while failure paths keep full diagnostics.

Growth strategy and Reserve

The dynamic array's capacity grows by doubling: on insufficiency it expands by a factor and relocates wholesale. This guarantees the amortized bound "appending N elements costs O(N) total relocation" — but a single Append may still trigger one big allocation. When the magnitude is known, Reserve(N) arrives in one step, turning amortization into certainty: before loading a hundred thousand records, Reserve(100000) makes the whole run a single allocation. The companion Resize explicitly sets the element count (newly grown elements zero-valued) and Trim shrinks capacity to the current count — after loading completes and the read-only phase begins, one Trim cut and the long-resident memory is immediately tidy. This capacity trio (Reserve/Resize/Trim) is standard across all of Volume 3's dynamic containers, with semantics identical on xarray, xbuffer, and xmap.

Sorting and searching

xrtArraySort accepts a qsort-compatible comparison function — any comparator written as three-state </> works. The example's (a>b)-(a<b) form is worth learning: it avoids the a-b subtraction overflow (two large negatives subtracted flip the sign, silently scrambling the sort). A sorted array can be binary-searched by index with the find family; the find functions accept both "search by element" and "search by key" (comparator callback) forms.

The pointer array: the gateway to polymorphism

The value array handles "dense storage of same-typed elements", but two requirement classes it naturally cannot: elements of different concrete types (a renderer's shape family, an interpreter's node family), or element ownership belonging elsewhere (a cache does not own its objects, only references them). xptrarray stores pointers — elements may be of different concrete types (polymorphic through a common header), may be owned by another container, may be stack objects. The price: one extra indirection per access, and per-element lifecycle management is yours (the array's Unit does not free what the pointers point to). The selection mnemonic: same-typed elements with heavy whole-array traversal → value array; polymorphic elements or ownership elsewhere → pointer array. There is also a hidden but common third option: mix the two — a value array storing "keys and handles" as the dense index, with object bodies scattered in a pool or slot_map (Chapter 17). This chapter's session-table exercise rehearses exactly this "array + handle" architecture, and Chapter 67's network connection table is its full bloom.

Besides Init, two other starting postures are worth knowing: Create directly returns a heap-allocated array object (the handle itself on the heap, suited to long-term holding inside other structures), and InitAligned specifies element alignment (SIMD or atomic-field scenarios). Clear zeroes the element count but retains capacity — when reusing a batch of arrays in a loop, Clear is far faster than a paired Unit/Init and never touches the allocator.

14.3示例

Complete program: batch append and in-place sort

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

What just happened. (1) xrtArrayInit takes only the element size — genericity without macros or templates, by "moving bytes". (2) xrtArrayAppend(&tRecords, pInput, 3) appends three records at once (a single memcpy plus possible growth); the batch interface saves two function calls and two capacity checks over per-item Append. (3) xrtArraySort in-place sorts the shuffled input into ascending priority — the output order 10/20/30 verifies. (4) Iteration uses the public field Count and Get; Get returns a direct pointer into the array's memory (readable and writable), NULL when out of range. (5) Unit returns the buffer — the array handle itself is on the stack; only the heap buffer is returned.

Complete program: pointer-array traversal

From examples/containers/ptr_array/main.c, demonstrating pointer-semantics storage and traversal:

 */

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

What just happened. The array stores ptr — references to objects living elsewhere. The element taken out during traversal is "the pointer's value"; the object bodies are not in the array's memory. All three typical sources are legal: stack objects (this example), objects owned by other containers, objects you allocated one by one and will free one by one. Note that the pointer array's Unit returns only the pointer-slot storage — not one pointed-to object is freed; the ownership discipline lies entirely with the caller, which is exactly Pitfall 2's theme.

Read the two examples side by side and the "value versus pointer" trade-off becomes three-dimensional: the value array loads three records in one memcpy, sorts by moving whole blocks, iterates with zero indirection; the pointer array adds one dereference per operation, sorts by moving 8-byte pointers (the element bodies stay put — an advantage for large objects!), and supports polymorphic mixing. Rule of thumb: elements smaller than a cache line and same-typed — the value array almost always wins; elements huge, from mixed allocation sources, or needing polymorphism — the pointer array.

The container family's shared conventions (effective from this chapter)

The three conventions established here run through all of Volume 3; set them up now, later chapters reference directly. Convention one: handle on the stack, memory on the heap — Init opens with a stack handle, the container manages its buffers, Unit returns exactly; when the container object itself must live on the heap, use the Create/Destroy pair. Convention two: read via fields, write via functions — read-only state (Count, Size, Data) is public fields, zero-overhead direct reads; fallible operations all go through function return values with Chapter 4's error slot. Convention three: no side effects on failure — any edit failing leaves the container in its pre-call state, so Cleanup-section code can be written with zero anxiety. The three conventions compound in every later chapter: reading any new container, you already know its lifecycle shape, field style, and failure semantics — only "what is this container good at" remains new.

14.4契约

• Lifecycle: Init/Unit paired exactly; failure paths also Unit (no-side-effect-on-failure makes this cleanup line always safe).
• Public fields: read-only state like Count directly as fields; fallible operations via function return values.
• Pointer validity: growth invalidates existing element pointers — need stable addresses? Reserve capacity first, or switch to the pointer array/linked list.
• Out-of-range behavior: Get returns NULL when out of range; edit operations fail and set an error on out-of-range — never an out-of-bounds write.
• Pointer-array ownership: Unit does not free the pointed-to elements; whoever allocated frees.
• Comparators: three-state (a>b)-(a<b) style; a-b forbidden (overflow).
• The capacity trio: Reserve pre-grows, Resize sets length, Trim tightens; Clear zeroes retaining capacity; semantics identical across Volume 3's dynamic containers.

Common Mistakes

examplerecord* pRecord = (examplerecord*)xrtArrayGet(&tRecords, 0);
xrtArrayAppend(&tRecords, pMore, 100);   /* may trigger growth + relocation */
pRecord->ID = 42;                         /* pRecord points into the freed old buffer */

examplerecord* pRecord;
xrtArrayAppend(&tRecords, pMore, 100);   /* do the possibly-growing operation first */
pRecord = (examplerecord*)xrtArrayGet(&tRecords, 0);   /* then take the pointer */
pRecord->ID = 42;

xptrarray tObjects;
/* ... load a batch of xrtMalloc'ed objects ... */
xrtPtrArrayUnit(&tObjects);   /* returns only the pointer slots — every element leaks */

for ( size_t i = 0; i < tObjects.Count; i++ ) {
	xrtFree(xrtPtrArrayGet(&tObjects, i));   /* return the elements one by one first */
}
xrtPtrArrayUnit(&tObjects);                  /* then return the array itself */

Programming Exercises

Summary