Before Asking an AI Agent for a Red-Black Tree: Define the Operating Conditions

Suppose you ask an AI agent to implement a red-black tree in C. The result supports lookup, insertion and deletion, and its tests pass. Will it also work appropriately inside shared memory used by several processes?

If that requirement was absent, allocating each new node with malloc() would be a reasonable implementation. Checking an algorithm’s behavior and checking its suitability for a particular environment are separate tasks.

An earlier C transaction-system project on HP-UX combined array-backed slots, a red-black tree and a free list. Revisiting that design highlights three things to make explicit when coding with an AI agent: environmental constraints, conditions that must remain true, and evidence that those conditions hold.

What a data-structure name leaves unspecified

Several processes needed to read and update the same transaction state. We kept it in shared memory. An ordinary malloc() call allocates from the calling process’s heap; it does not find an empty location inside an attached shared-memory segment.

Dynamic allocation within shared memory is possible with a suitable allocator. Our approach was to reserve a region, divide it into fixed-size slots, and link empty slots into a free list. An insertion took a slot; deletion returned storage for reuse.

The toolchain was constrained too. GCC was unavailable to the project: the code had to build with the HP-UX C compiler. Any reused implementation or library needed validation in that environment.

“Implement a red-black tree” communicates none of this. An agent may discover some constraints in the repository and build configuration, but that does not establish that it has found every relevant condition. Confirmed constraints and unresolved assumptions need to be distinguished before implementation proceeds.

Choose storage and lookup separately

Once storage was available, entries still needed to be found by key. The original implementation used a red-black tree for that job.

Component	Role	Still to decide
Shared array slots	Provide fixed-size storage	Capacity and address representation
Free list	Acquire and return empty slots	Exhaustion and synchronization
Red-black tree	Look up, insert and erase keys	Node storage and reference lifetime

The array was not sorted by key. Key 40 could occupy slot 0, while key 20 occupied slot 3. Tree links represented key relationships; slot indices represented storage locations.

A red-black tree maintains balance to support lookup, insertion and deletion in O(log n). Taking or returning the head of a free list is O(1). Adding a pool does not change tree-search complexity. String comparison, synchronization and data copying still contribute costs.

I do not remember the exact comparison that led to choosing a red-black tree. The code shows primarily keyed state lookup and updates, with shared slots reused for storage. Keeping search costs from becoming badly skewed as entries change is a plausible rationale, but there is no evidence here that it outperformed a hash table.

That distinction matters when reviewing alternatives with an agent. Keep the constraints explicit while allowing the solution to change. Shared-memory allocation does not require red-black-tree indexing. Exact-key lookup may suit a hash table and pool; dense integer keys may suit direct indexing; infrequent updates may make a sorted array worth comparing.

Add invariants to the implementation request

“Build a free list” leaves important behavior unspecified. More useful requirements include:

• A slot linked into the tree must not also belong to the free list.
• A failed insertion must not leave a reserved slot behind.
• Deletion must return the slot physically unlinked by the tree implementation.
• A slot must not be reused while another operation still uses it.
• Exhaustion must follow an agreed failure or waiting policy.

A condition that must remain true, such as tree membership and free-list membership never overlapping, is an invariant. These conditions and the failure policy can guide the implementation request, tests and review.

Consider this release function from a slot-pool example written for this article. The used flag records occupancy; next_free holds the index of the next empty slot.

static bool pool_release(Pool *p, size_t i)
{
    if (i >= CAPACITY || !p->slots[i].used) return false;
    Slot *s = &p->slots[i];
    s->used = false;
    s->links.next_free = p->free_head;
    p->free_head = i;
    --p->used_count;
    return true;
}

It checks the index and rejects an already released slot. But it does not check whether the slot has been unlinked from the tree or whether another operation still holds a reference. The caller must establish those conditions. Local checks alone do not establish that release is safe.

Download the complete C example, including initialization, acquisition, release and checks, and run:

cc -std=c11 -Wall -Wextra -Werror -O2 slot_pool.c -o slot_pool
./slot_pool

full pool rejected; slot 1 reused
slot ownership checks passed

The example targets a current C11 compiler and runs in one process and one thread. It checks four-slot exhaustion and reuse, invalid indices, immediate double release, and slot ownership during repeated operations. Its test scope ends at slot management. It does not implement the tree or attach shared memory.

Follow references beyond the function boundary

The node containing the requested key may differ from the node physically removed by tree deletion. An implementation that copies a successor’s data when deleting a node with two children is one example. The pool must receive the slot that the particular erase implementation actually unlinks.

Outstanding references may still remain. Suppose operation A keeps a pointer to slot 3 while operation B releases and reuses it. A can now read a different transaction at the same address. The access is incorrect even though the memory was never deallocated.

The example’s used flag cannot prevent this: it becomes true again after reuse. Review needs to cover lock scope, deferred return until references end, or handles that combine a slot index with a generation number. Generation numbers alone do not eliminate a race between validation and access.

An agent review can trace where returned pointers are retained, when locks are released, and which paths can reuse the storage.

Derive tests from the operating conditions

A fresh version of this design would need the following checks in addition to slot-pool unit tests:

Condition	Behavior to verify
Different attachment addresses	Processes resolve the same entry from their own segment base
Concurrent lookup, deletion and reuse	Storage is not reused while a reference remains valid
Exhaustion or partial failure	Agreed failure behavior occurs without leaking reservations
Unexpected process exit	Interrupted setup or mutation follows the recovery policy
Target compiler	Syntax, alignment and types build and run in the supported environment

The first check matters because attachment addresses can differ between processes. Sharing raw pointers requires address assumptions; offsets or slot indices can instead be resolved against each process’s segment base. The original implementation used pointers and the teaching example uses indices, so their address handling should not be treated as equivalent.

Interprocess synchronization requires appropriate settings, such as the distinction between process-private POSIX mutexes and the shared attribute PTHREAD_PROCESS_SHARED. That setting alone does not provide recovery from an interrupted update.

Performance needs a separate comparison of throughput, latency distributions and memory under equivalent inputs, occupancy and synchronization. Array storage does not make tree traversal contiguous, and reuse does not shrink reserved capacity. Passing the slot-pool checks cannot establish a performance gain.

Turn the lesson into a task brief

For a new task based on this example, a brief for the agent could look like this:

Goal
Several processes look up and update shared state by key.

Known constraints
- Manage storage inside a preallocated shared region.
- Account for process-specific attachment addresses.
- Use only features supported by the designated compiler.

Decisions still needed
- Capacity, key characteristics, and lookup/update ratio
- Whether ordering or range queries are required
- Duplicate-key, exhaustion, and process-exit policies

Review request
- Compare indexing and storage-management choices separately.
- Define ownership, synchronization scope, and invariants.
- Map each condition to a check; identify unresolved assumptions.
- Implement the agreed scope and report evidence against it.

Some entries can start empty. Fill them in through repository inspection with the agent, and narrow alternatives through small experiments.

Keep the reasons alongside the code

Revisiting the old code meant reconstructing part of the reason for choosing a red-black tree. The implementation survived, but the alternatives considered and the reasons for rejecting them were not fully recorded.

When working with an AI agent, keep a short record of constraints → decisions → rationale → verification → unresolved assumptions alongside the code. Someone later replacing the free list with a general-purpose allocator, or narrowing a lock, can then see what must be checked again.

Agent-assisted changes still need evidence that they preserve the original conditions. Keeping that evidence alongside the implementation carries the design intent into the next change and review.

References

• Linux: Red-black Trees - node layout, lookup, erasure and caller-owned locking.
• Linux man-pages: shmat - attachment addresses and references within a shared segment.
• Slot-pool C example - initialization, acquisition, release and ownership checks.

Further Reading

• Why Turn Immutable YAML Logs into Full Objects? - checks access patterns and allocation needs before selecting a familiar implementation.
• When Logging Becomes the Bottleneck: Keeping Heavy Appender Work Off the Request Path - connects functional behavior to execution context and capacity limits.