LayerKeySort v2.0.0-preview.4

LayerKeySort v2.0.0-preview.4

v2.0.0-preview.4 is the fourth public development snapshot of the
LayerKeySort 2.0 architecture.

This Preview is the largest V2 core-architecture update so far. It separates
mutable Tree indexing from hierarchical Path topology, completes the basic
Tree mutation lifecycle with remove/rekey, adds canonical Path parsing and a
versioned sortable external key, and introduces reproducible performance
evidence for the current design.

Warning

This is a Preview release, not a production-ready release.

Algorithms, heuristics, generated Path coordinates, performance
characteristics, and some Preview-level contracts may still change before
stable 2.0.

Path-keyed AVL Tree

The mutable Tree is now indexed by Path order using an AVL tree.

Physical Tree topology is no longer the same thing as Path-prefix hierarchy.

This means:

• explicit deep Paths no longer require all proper Path prefixes to exist;
• physical parents/children are implementation-defined index structure;
• physical Tree height depends on item count rather than caller-supplied Path
  depth;
• the former mutable ChildBlock/sibling-array representation is no longer the
  current Tree core.

Use lks_path_compare() for logical Path ordering rather than physical Tree
navigation.

Comparator-equal insertion

Comparator-driven insertion now locates the upper bound of an equal run through
the balanced index instead of linearly walking successors to the end of the
run.

On the documented test machine, 4,000 all-equal online insertions changed from:

Preview.3:
4,129,960 comparator calls
937.480 ms

Preview.4:
43,905 comparator calls
1.354 ms

These measurements describe this workload and machine. They are not a general
complexity proof or universal speed claim.

Tree remove and rekey

Preview.4 adds:

lks_tree_remove_path()
lks_tree_rekey()

Removal destroys the Tree-owned node and Path but never the caller-owned item.
It performs no allocation and does not compact unrelated Paths.

Rekey keeps the same borrowed item pointer while changing its ordering
coordinate. Allocation failure leaves the original association unchanged.
Rekeying to the same Path is a successful no-op.

Higher-level helpers such as move_before() / move_after() are not part of
this Preview.

Canonical Path parsing

Preview.4 adds:

lks_path_parse()

It accepts the canonical display syntax generated by lks_path_format() and
rejects malformed, noncanonical, or overflowing input.

The display representation remains intended for readable Path representation.
It is not the database lexical ordering key.

Durable sortable Path key: LK1

Preview.4 adds a separate versioned external ordering representation:

lks_path_order_key_length()
lks_path_order_key_format()
lks_path_order_key_parse()

Canonical LK1: keys are reversible and designed so that, for keys of this
format under bytewise ASCII ordering:

sign(strcmp(keyA, keyB))
==
sign(lks_path_compare(pathA, pathB))

This gives applications a sortable persisted ordering coordinate without
turning a Path into permanent item identity.

LK1: prioritizes canonical, portable, reversible ordering semantics rather
than minimum string size.

It does not serialize:

• the Tree;
• caller-owned item data;
• permanent object identity;
• distributed/CRDT conflict state.

Local repair and full rebuild

Local repair now works over bounded contiguous logical-order windows rather
than requiring a physical Path-prefix subtree.

Existing items keep their logical in-order ranks while replacement Paths are
prepared and validated before commit.

A full Tree rebuild remains the failure-atomic fallback when the current
coordinate space cannot be repaired within policy limits.

The fallback is still a real cost. Preview.4 does not claim that complete
comparator-driven insertion has worst-case O(log n) time, and no formal
amortized bound is claimed.

Performance convergence and benchmark harness

Preview.4 adds a reproducible public-API benchmark harness and captured
Preview.3 / Stage 4 / Preview.4 measurements.

The report includes:

• ascending;
• descending;
• random;
• all-equal;
• duplicate-heavy;
• alternating;
• Group/Batch operations;
• Tree remove/rekey;
• Path display/parser;
• LK1 format/parser;
• allocation diagnostics;
• AVL height/rotations;
• Path depth distributions;
• repair and rebuild diagnostics.

The data intentionally includes regressions.

For example:

Tree insert / alternating / N=4000

Preview.3: 65.951 ms
Preview.4: 77.934 ms

and:

Tree insert / random / N=1000

Preview.3: 0.607 ms
Preview.4: 1.343 ms

The new AVL representation is therefore not claimed to be faster at every
scale or distribution.

See:

• docs/BENCHMARKS.md
• benchmarks/README.md
• benchmarks/results/

for methodology, raw captured rows, limitations, and interpretation.

Large open-end insertion improvement

Preview.4 avoids repeatedly attempting local repair at an open end while the
candidate Path is still within the hard depth allowance.

On the documented 100,000-item ascending workload:

Stage 4:
2,120.870 ms
64,262 repair attempts

Preview.4:
319.905 ms
90 repair attempts

Both runs still performed nine full rebuilds.

This change reduces repeated repair work; it does not change the comparator
search complexity.

Validation

The final Preview.4 main commit passed:

• Windows MSVC;
• Ubuntu GCC;
• Ubuntu Clang;
• Ubuntu Clang with AddressSanitizer/UndefinedBehaviorSanitizer configuration;
• public API and core regression tests;
• mutation differential tests;
• deep-Path tests;
• Path parser tests;
• LK1: golden vectors and ordering equivalence tests;
• allocation-failure/OOM tests;
• benchmark smoke tests.

Each GitHub Actions configuration ran CTest 4/4 successfully.

GitHub Pages deployment for the final release-state commit also succeeded.

Current limits

Preview.4 still intentionally does not claim:

• production readiness;
• a formal amortized bound for online insertion;
• worst-case O(log n) complete insertion;
• a fixed Path-depth or memory ceiling;
• whole-Tree serialization;
• distributed/CRDT ordering;
• a public custom allocator;
• high-level move_before / move_after convenience APIs.

Comparator-driven Tree operations also require the existing item order to be
compatible with the supplied comparator/context. The Tree does not currently
bind one comparator as permanent Tree state.

Release commit

61a9ff91a16c9a3a2cbef5bf21a4d157e48631db

Tag:

v2.0.0-preview.4