Skip to content

LayerKeySort v3.0.0

Choose a tag to compare

View all tags
@RXY712200 RXY712200 released this 03 Oct 07:10
v3.0.0
8ebf688

LayerKeySort v3.0.0

LayerKeySort 3.0.0 is the first stable release of the V3 C17 architecture. It retains the production implementation validated in v3.0.0-rc.1; the final release preparation changes version metadata, documentation, and presentation, without changing production ordering code.

What is V3?

V3 separates two ways to manage ordering coordinates:

  • LksTree is the manual-coordinate Tree. The application chooses Paths and may insert, remove, or rekey by exact Path.
  • LksOrderedTree binds a comparator and borrowed context at creation. The library maintains stable comparator order, assigns Paths, and may relabel existing Paths when space becomes congested.

Both Tree models borrow caller-owned items. A Path is a mutable ordering coordinate, not a permanent item ID. The physical AVL index is not a Path-prefix hierarchy or a logical navigation contract.

Highlights

  • Managed ordering uses logical Path relabeling while retaining physical Tree nodes, replacing V2's managed full-Tree replacement fallback.
  • Comparator ownership, item lifetime, borrowed node and Path invalidation, and safe remove/update/reinsert behavior are documented in the 3.x API contract.
  • A small ordered-Tree Quick Start, public examples, CMake integration guidance, and a V3-first README make first use easier to verify.
  • The V3 visualizer replays recorded Path snapshots from the exact RC.1 production C implementation. It does not implement Path allocation in JavaScript. The historical V1 visualizer remains available separately.
  • V2 Path comparison, canonical display parsing, LK1 v1 external-key bytes, immutable Group/Batch behavior, and stable pointer-array sort semantics remain intact.

Migration from V2

The two V2 per-operation-comparator LksTree insert/locate functions are removed from the V3 public API. Use LksOrderedTree for comparator-managed ordering and LksTree for application-selected coordinates. See the V2 to V3 migration guide and the active 3.x compatibility contract. Historical stable v2.0.0 remains available.

Validation

The exact RC.1 production commit passed five GitHub CI configurations, each with CTest 8/8: Windows MSVC, Ubuntu GCC, Ubuntu Clang, Ubuntu Clang with sanitizers, and macOS AppleClang. The final V3.0.0 release-state commit passed the same five-job matrix with CTest 8/8 in each job.

Local RC validation included strict GCC C17, MSVC Debug/Release and AddressSanitizer, examples, source and CMake consumers, deterministic mutation/property/stress tests, parser and LK1 tests, and allocation-failure tests. A separate post-RC local simulated-user campaign exercised clean C/C++ consumers, long deterministic Tree mutation sequences, adversarial insertion, parser/LK1 inputs, OOM paths, and repeated lifecycle cycles. Those extended local outputs were not reproduced in GitHub CI and are not raw artifacts in this repository.

Known limitations

  • A managed insertion can relabel a large region or the full logical range. This can cause significant synchronous tail latency.
  • Path depth, resident Path memory, and LK1 storage depend on the workload.
  • Complete managed insertion has no proven worst-case O(log n) guarantee and no formal amortized bound.
  • Generated Path coordinates and private relabel heuristics are not 3.x compatibility promises. Persisted LK1 keys preserve coordinates, not item identity or whole Trees.
  • The library does not provide distributed/CRDT convergence, whole-Tree serialization, or a public custom allocator.

Measure relabel latency and storage against your application workload. The documented benchmarks are workload and machine evidence, not universal performance rankings.

Documentation and visualizer

Release commit: 8ebf68820295b3849a6c8d99c00c95b7de70cc3d

Assets 2
Loading