LayerKeySort v3.0.0-preview.1

LayerKeySort v3.0.0-preview.1

This is an experimental prerelease. For normal use, prefer stable v2.0.0. V3 Preview.1 is an architecture snapshot, not a stable V3 API or a claim of universal performance improvement.

Architecture

V2 used one LksTree for both caller-selected Path coordinates and insertion using a comparator supplied per operation. V3 separates those models:

• LksTree is the manual coordinate container. It retains explicit Path insertion, removal, and arbitrary rekey.
• LksOrderedTree is the comparator-bound managed-order container. It copies the LksComparator descriptor when created, borrows its context and caller items, and inserts comparator-equal items stably. Its public API does not permit arbitrary rekey.

The context and comparator-relevant item fields must remain valid and ordering-compatible. Remove and reinsert an item before changing fields that affect comparison.

The Path-keyed AVL index remains. V3 managed online insertion no longer replaces the physical Tree as its full-rebuild fallback.

API migration

The V3 Preview.1 header has 59 public functions; stable V2 has 52. This Preview intentionally breaks source compatibility for V2 Tree comparator operations: lks_tree_insert_item() and lks_tree_locate_item() were removed from the V3 public API. Use the new lks_ordered_tree_* API for comparator-managed ordering. The migration guide maps the APIs.

Path comparison, canonical display text, and LK1 v1 bytes and semantics remain unchanged. Exact automatically generated Path coordinates are still implementation details. Stable V2 remains available through its v2.0.0 tag; migration is optional.

Adaptive relabeling and complexity

Managed insertion first seeks a direct Path. When coordinates become congested, it prepares replacement Paths for a contiguous logical range, expanding the range geometrically and, if needed, relabeling the full logical range. It validates the prepared Paths before an allocation-free commit. A full-range relabel changes up to n existing Paths and remains a real cost.

AVL search follows balanced-index height behavior. Direct insertion also generates a coordinate and links/rebalances the AVL node. An adaptive relabel touches k existing logical nodes, where k may equal n. Preview.1 claims neither worst-case O(log n) time for complete insertion nor a formal amortized relabel bound. Removing physical replacement-Tree rebuilding did not eliminate all expensive individual insertions.

Validation

The release-state commit passed strict local GCC C17 build and CTest 7/7, both examples, and a clean public-header LksOrderedTree consumer. Its GitHub Actions run passed CTest 7/7 in each of five configurations: Windows MSVC, Ubuntu GCC, Ubuntu Clang, Ubuntu Clang with sanitizers, and macOS AppleClang. The suite includes manual and managed Tree tests, Path/display/LK1 vectors, mutation soak, parser torture, OOM checks, and three benchmark smoke tests.

Release-state CI · Benchmark method and limitations

Performance evidence

Stable V2 versus V3 Preview.1 on the documented Windows 11 / Ryzen 9 9955HX machine, in milliseconds (one warmup, three measured runs, median):

Managed insertion workload	Stable V2	V3 Preview.1
Ascending, 100k	327.913	421.662
All equal, 100k	331.146	419.852
32-value duplicates, 100k	477.263	126.797
Alternating, 10k	216.716	85.698
Random unique, 100k	112.053	112.892

Ascending and all-equal regress; duplicate-heavy and alternating improve substantially; random 100k is close in this measurement. These are one-machine workload measurements, not universal rankings or complexity proofs. Raw captured rows remain available.

Known limits and stable release

This experimental Preview does not freeze the V3 API, guarantee that every workload is faster, provide a formal amortized insertion bound, or make a Path a permanent item identity. Full-range relabeling may still be expensive. For normal applications, use stable LayerKeySort v2.0.0.

Release-state commit: 6fd34ca709ded89e0784e7c33cf08a6603ac9df1.