Module list 

Linked list — public xmlList API (§85 Phase 1).

Implements the libxml2 linked list.

UPSTREAM-PARITY

The linked list supports:

• Create/delete with custom deallocator
• Push front/back, pop front/back
• Insert/append at arbitrary positions
• Search with custom comparator
• Walk with callback
• Remove first/last/all matching entries
• Clear
• Empty/front/back/size queries
• Sort, reverse, reverse splice, merge

Phase 1 status

Complete — all list operations are implemented.

Upstream contract

Mirrors upstream list.c / list.h (SRC-LIBXML2-2.15.0-LIST-C, parity target libxml2 2.15.3 oracle): the xmlList* API with deallocator, comparator and walker callbacks.

Conceptual behavior

Implements a doubly-linked list whose nodes are owned by the list and whose data pointers are owned by the caller unless a deallocator is registered. xmlListAppend does a plain push_back when no comparator is set but a SORTED insert once a comparator is present (upstream list.c); xmlListWalk / xmlListReverseWalk stop when the walker returns 0.

Ownership & safety invariants

The list owns its ListNode storage (freed by xmlListDelete / clear paths); payload data is freed through the registered deallocator only. Walkers receive borrowed data pointers valid for the walk duration.

Historical quirks & epochs

The sorted-append and 0-stops-walk semantics were misimplemented in the candidate and corrected to upstream behavior in the 11.1-L callback audit (R-000162) — both are long-standing list.c contracts, stable since the 2.6 validation era through the 2.15.3 oracle.

Deliberate oddities

xmlListAppend becoming a sorted insert under a comparator is the upstream oddity that a naive push_back implementation misses; the walk stop convention (0 = stop, non-zero = continue) is the inverse of the intuitive C convention and is reproduced deliberately.

Proving courts

CALLBACK-001 (courts/suites/data-abi/callback-family-probe.c) exercises xmlListAppend ordering and both walks against the oracle DSO and requires byte-identical output (R-000162 evidence); cargo test runs the list unit suites.

Tempting simplifications that would break parity

Do not make xmlListAppend always push_back: with a comparator set, consumers rely on sorted order. Do not invert the walk stop condition back to non-zero-stops: the 11.1-L audit proved the oracle stops on 0.

Structs

List

The linked list struct.

Functions

link_get_data^⚠

Return the data stored in a link (upstream list.c xmlLinkGetData).

list_append^⚠

Append data to the end of the list (alias for push_back).

list_back

Get the data at the back of the list.

list_clear^⚠

Clear the list (remove all elements).

list_copy^⚠

Copy the contents of old into the existing list cur (upstream list.c xmlListCopy): walks old’s links and inserts each data pointer into cur using cur’s comparator. Returns 0 on success, 1 on error; on insertion failure the target list is deleted (upstream behavior).

list_create

Create a new linked list.

list_delete^⚠

Delete a linked list and all its nodes.

list_dup^⚠

Duplicate a list (upstream list.c xmlListDup): a shallow copy using the same deallocator/comparator; node data pointers are copied as-is. Returns the new list or NULL on allocation failure.

list_empty

Check if the list is empty.

list_end^⚠

Return the last element of a list (upstream list.c xmlListEnd): the data of the last node, or NULL.

list_front

Get the data at the front of the list.

list_insert^⚠

Insert data into the sorted position.

list_merge^⚠

Merge two sorted lists into one.

list_pop_back^⚠

Pop data from the back of the list.

list_pop_front^⚠

Pop data from the front of the list.

list_push_back^⚠

Push data to the back of the list.

list_push_front^⚠

Push data to the front of the list.

list_remove_all^⚠

Remove all matching elements.

list_remove_first^⚠

Remove the first matching element.

list_remove_last^⚠

Remove the last matching element.

list_reverse^⚠

Reverse the list in-place.

list_reverse_search^⚠

Reverse-search a list with the comparator (upstream list.c xmlListReverseSearch): scans from the back, returns the first (from the end) matching node’s data, or NULL.

list_reverse_splice^⚠

Reverse splice: move all elements from l2 to the front of l1 in reverse order.

list_reverse_walk^⚠

Walk a list in reverse with a walker callback (upstream list.c xmlListReverseWalk).

list_search^⚠

Search the list for data matching the given key.

list_size

Get the number of elements in the list.

list_sort^⚠

Sort the list in-place using the comparator.

list_walk^⚠

Walk the list, calling the walker function for each element.

Type Aliases

xmlListDataCompare

Data comparator function. Returns 0 if equal, non-zero if different.

xmlListDeallocator

Deallocator function for list data.

xmlListWalker

Walker function for xmlListWalk.