LayerKeySort v4.0.0-preview.1

LayerKeySort v4.0.0-preview.1

This is an experimental V4 prerelease. For normal use, prefer stable v3.1.0.

V4 Preview.1 is the first production implementation of the new V4 architecture. It introduces the explicit live-order core while intentionally keeping the existing V3 APIs available alongside it.

New V4 live-order core

Preview.1 adds provisional LksOrder and LksOrderHandle APIs for:

• front/back insertion
• insert before/after a resident handle
• exact removal
• first/last/next/previous traversal
• borrowed item access
• contextual order comparison

Resident handles are stable while resident. They survive local shifts, block splits, redistribution, merges and AVL rotations. Removal or container destruction invalidates them.

Handles are not Paths, persistent IDs, serialization keys or standalone ordering coordinates.

New architecture

V4 live order no longer maintains a globally sortable Path for every resident item.

The core uses:

• bounded blocks with capacity 128
• local resident-pointer arrays
• an implicit AVL ordering the blocks
• subtree block counts
• threaded block neighbors
• stable separately allocated resident records

Global logical order is the concatenation of block order and local order.

Ordinary insertion performs bounded local maintenance and at most one block split. Removal performs bounded neighboring merge or redistribution. There is no global resident-coordinate rewrite, relabel pass, deferred maintenance backlog or cascading split.

Why V4 changes direction

V3 research found that large synchronous coordinate relabels, recurring rewrite work and Path/LK1 growth formed a significant engineering tradeoff.

V4 separates contextual live order from the future snapshot/export representation instead of requiring every live item to continuously own a standalone serialized sortable coordinate.

Preview.1 implements only the live explicit-order half of that architecture.

Validation

The exact release commit passed the repository's GitHub Actions workflow in all five configurations:

• Windows MSVC
• Ubuntu GCC
• Ubuntu Clang
• Ubuntu Clang configuration with the repository's enabled checks
• macOS AppleClang

Local validation additionally included:

• 120,000 randomized oracle operations across deterministic seeds
• 388,599 instrumented structural operations
• adversarial front/back/hotspot/alternating campaigns
• exact forward and reverse traversal verification
• handle-stability checks across structural maintenance
• deterministic allocation-failure sweeps
• MSVC AddressSanitizer
• C/C++ source, FetchContent and installed-package consumers
• reproducible amalgamation/package validation

Observed structural maxima remained bounded by the block architecture. No tested operation triggered a global resident rewrite or deferred maintenance backlog.

These results are validation evidence, not realtime guarantees or final V4 performance acceptance.

Provisional API

V4 Preview.1 adds 14 provisional lks_order_* functions while preserving the existing 59 V3 public functions.

The V4 API is not frozen.

The latest stable release remains v3.1.0.

Deferred to later V4 Previews

Not yet implemented:

• move-before / move-after
• comparator-managed V4 ordering
• snapshots and exported sortable keys
• persistence/load
• V3 LK1 migration
• V4 Group/Batch integration
• final API/wire-format freeze
• final performance acceptance

These omissions are intentional Preview.1 scope boundaries.

Documentation

• V4 Preview.1 implementation and validation
• V4 architecture
• V4 decisions
• Live-order example
• Changelog

Release-state commit:

21b2902555534d10d97e704161066197cebc13ae

LayerKeySort v3.1.0

LayerKeySort v3.1.0

LayerKeySort 3.1.0 is a compatible V3 feature release focused on installation, source distribution, and first-use experience. The production ordering implementation and public C function set are unchanged from v3.0.0.

Highlights

• A generated two-file C17 amalgamation: layerkeysort.h and layerkeysort.c.
• CMake install/export support: find_package(LayerKeySort CONFIG REQUIRED) and LayerKeySort::layerkeysort.
• Tests, examples, and install rules default OFF when used as a CMake subproject.
• Deterministic Release assets with a SHA-256 manifest, exact-membership validation, reproducibility checks, and tamper rejection.
• Clearer English and Simplified Chinese onboarding, integration guidance, API selection, and a project landing page. Current documentation is separated from historical design and benchmark records.

Download

For a small source integration, download LayerKeySort-3.1.0-amalgamation.zip. Copy layerkeysort.h and layerkeysort.c beside your application, include the header, and compile the implementation as C17. Python is not required to consume the downloaded package.

The ZIP contains exactly layerkeysort.h, layerkeysort.c, example.c, LICENSE, and README.txt. Use LayerKeySort-3.1.0-SHA256SUMS.txt to verify the ZIP. GitHub's automatic Source code ZIP/tar.gz are separate full-repository archives. No prebuilt library binaries are supplied.

Compatibility

The public API remains 59 functions. No production src/*.c ordering implementation changes from v3.0.0 are included. Path comparison, canonical display syntax, LK1 v1 bytes, ownership, comparator behavior, and relabel semantics remain unchanged. See the 3.x compatibility contract.

Validation

The exact release commit passed the five GitHub CI configurations: Windows MSVC, Ubuntu GCC, Ubuntu Clang, Ubuntu Clang with sanitizers, and macOS AppleClang. Each ran CTest 8/8, all three examples, and distribution validation.

External consumer checks cover source-tree and offline FetchContent C/C++ projects, installed C/C++ consumers, and strict-warning amalgamation consumers. The release-asset workflow checks membership, checksums, reproducibility, and rejection of tampered assets. These results describe the tested configurations rather than every possible platform.

Known limitations

Managed insertion may relabel a large region or the entire collection, producing workload-dependent synchronous tail latency. Path depth, memory use, and LK1 storage depend on the workload. Complete managed insertion has no proven worst-case O(log n) guarantee or formal amortized bound.

A Path is an ordering coordinate, not permanent item identity. LayerKeySort does not provide distributed/CRDT ordering or whole-Tree serialization. Caller-owned items and comparator context must remain valid; comparator-relevant fields must remain unchanged while items are resident.

Documentation

• English README
• 简体中文
• Integration
• Usage
• API reference
• Benchmark evidence and limitations
• Changelog
• Project homepage and visualizer

Release commit: dfa9562b9471947cfbd4ee1d1750a59434be83e2

LayerKeySort v3.0.0

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

• README and Quick Start
• API reference
• Integration guide
• Benchmark evidence and limitations
• V3 visualizer
• Historical V1 showcase

Release commit: 8ebf68820295b3849a6c8d99c00c95b7de70cc3d

LayerKeySort v3.0.0-rc.1

LayerKeySort v3.0.0-rc.1

v3.0.0-rc.1 is a public Release Candidate for the existing V3 architecture. It is a prerelease, not V3 Stable. Stable v2.0.0 remains the recommended release for normal use.

Goal

Freeze the V3 feature set and begin final release-candidate stabilization. RC.1 is intended for focused correctness, integration, and external-user validation rather than new architecture work.

Changes

• Retains the V3 separation between manual-coordinate LksTree and comparator-managed LksOrderedTree, together with the existing adaptive endpoint and relabel behavior.
• Keeps Path comparison, canonical display text, and LK1 v1 bytes unchanged.
• Adds focused regression coverage for documented invalid arguments, aliased locate outputs, duplicate and missing Paths, undersized formatting buffers, constructor allocation failures, and repeated create/destroy cycles.
• Clarifies version, prerelease status, compatibility, integration, migration, and benchmark documentation. The public API remains 59 functions.
• Does not change the production ordering algorithm or add product features.

Validation

The reviewed RC candidate passed a strict local GCC C17 build with -Wall -Wextra -Wpedantic -Werror, local MSVC x64 Debug and Release builds, and local MSVC AddressSanitizer tests. Local CTest passed 8/8 for GCC, MSVC Debug, and MSVC Release; the local MSVC AddressSanitizer configuration passed 5/5.

The reviewed candidate's GitHub Actions run passed Windows MSVC, Ubuntu GCC, Ubuntu Clang, Ubuntu Clang with sanitizers, and macOS AppleClang. Each job reported CTest 8/8. The final release-state commit was also required to pass branch CI before this tag was created.

During local RC preparation, three deterministic seeds each completed 150,000 manual-Tree and 200,000 ordered-Tree mixed-operation steps. Seven insertion distributions, including alternating extremes and a fixed interior hotspot, passed correctness checks at 100,000 items each. Three deterministic parser-torture seeds each completed 100,000 cases. Existing LK1 golden-vector, ordering-equivalence, deep-Path, and allocation-failure tests passed. These large local runs were not reproduced by every CI job.

Clean external consumers built and ran through add_subdirectory, SHA-pinned remote FetchContent, and direct documented C17 source integration. All three public examples also ran from the remote candidate source.

Known Limitations

• A comparator-managed insertion may relabel the full range of existing nodes.
• Large relabel work can cause significant synchronous tail latency.
• Path depth, memory use, and external key size depend on workload.
• No proven worst-case bound or formal amortized bound is claimed for complete managed insertion.
• Comparator-relevant fields of resident items must remain stable. To change such a field, remove the item by its exact Path, update it, then reinsert it.
• Paths and LK1 keys are ordering coordinates, not permanent item identities or distributed conflict-resolution records.

See docs/BENCHMARKS.md for measured workloads, methodology, and limitations. Its historical Preview measurements are not relabeled as RC measurements.

Feedback

Focused reports from external users are welcome, especially deterministic reproductions of correctness, integration, or latency problems. This release does not imply that a broad external testing community has already validated V3.

LayerKeySort v3.0.0-preview.5

LayerKeySort v3.0.0-preview.5

Preview.5 is an experimental release-candidate preparation snapshot. Its purpose is to check the current V3 public contract, documentation, builds, and consumer paths before considering v3.0.0-rc.1. It does not declare an RC or stable V3 release.

Purpose and changes

• Reviews the 59-function public API, ownership and borrowed-lifetime rules, comparator requirements, error behavior, examples, and test coverage. No public function signature or production behavior changes were needed.
• Aligns version and publication wording across the README, changelog, API, usage, integration, migration, development, compatibility, and benchmark guides.
• Keeps the CMake numeric project version at 3.0.0 while the public header reports 3.0.0-preview.5.
• Leaves the ordering algorithm, Path model, LK1 v1 format, and captured benchmark data unchanged.

Validation

The implementation commit 2a11d8548deb866736fd4da94277b375ef912e0e passed strict GCC C17, MSVC Debug and Release, CTest 7/7 in each, all three examples, MSVC AddressSanitizer, a 100,000-step manual mutation soak, add_subdirectory, local and real remote FetchContent, and a standalone public-header consumer. The publication-state commit 763c2b6339b28b499db244ba1362770812c8c0a6 passed all five GitHub Actions jobs: CI run.

Known limitations

• Managed insertion may relabel up to the full collection, with workload-dependent Path memory and latency costs. No worst-case O(log n) complete-insertion or formal amortized bound is claimed.
• Item objects and comparator context remain caller-owned; comparator-relevant fields must remain stable while resident.
• LK1 is a sortable representation of one coordinate, not whole-Tree persistence or permanent item identity.
• Passing tests and CI supports RC consideration but does not prove production readiness, universal platform behavior, or a theoretical complexity bound.

Tag target: 763c2b6339b28b499db244ba1362770812c8c0a6.

LayerKeySort v3.0.0-preview.4

LayerKeySort v3.0.0-preview.4

Preview.4 is an experimental V3 user-experience and integration snapshot. It builds on Preview.3 without changing the ordering algorithm. Stable v2.0.0 remains the recommended release for normal use.

Purpose and changes

• Puts a minimal managed-Tree Quick Start near the start of the README. The new public-header-only example creates a Tree, inserts caller-owned items, queries, removes, and cleans up.
• Explains when to choose comparator-managed LksOrderedTree, manual-coordinate LksTree, or an ordinary sort.
• Documents add_subdirectory, FetchContent, and direct C17 source integration, plus the V2-to-V3 API change.
• Captures the earlier one-machine Preview.3 validation matrix for 100,000 to 1,000,000 managed insertions, with raw timed rows, relabel diagnostics, methodology, and explicit measurement limits. It records slow alternating and duplicate-heavy behavior rather than claiming a universal improvement.
• Adds the managed example to CMake, Visual Studio project metadata, and cross-platform CI example runs.

The public function set remains 59; Path and LK1 v1 bytes are unchanged.

Validation

The implementation commit e5c8adbdba2ff5068304d2b298d3b98ce25f0ef3 passed strict GCC C17 and MSVC Debug testing locally, including CTest 7/7, examples, and public-header consumers. add_subdirectory, local and remote FetchContent, and standalone linkage were exercised. The publication-state commit c3376b2a437247cf8053b7707a8c6aa97cc9ac3c passed all five GitHub Actions C17 jobs: CI run.

Known limitations

• Adaptive relabel can update many Paths in one insertion. In the captured one-machine validation, the 1,000,000-item alternating pattern took about 44 seconds overall and had individual pauses above 700 ms. This is workload evidence, not a general latency prediction.
• No worst-case O(log n) complete-insertion or formal amortized guarantee is claimed. Path size and memory may grow with workload.
• LK1 persists one mutable ordering coordinate, not a Tree, item payload, or permanent item ID.
• The V3 API and private heuristics remain experimental; Preview.4 is not production-ready or stable V3.

Tag target: c3376b2a437247cf8053b7707a8c6aa97cc9ac3c.

LayerKeySort v3.0.0-preview.3

LayerKeySort v3.0.0-preview.3

Preview.3 is an experimental V3 contract and architecture stabilization snapshot. Stable v2.0.0 remains the recommended release for normal use.

Purpose and changes

• Clarifies the separation between manual-coordinate LksTree and comparator-managed LksOrderedTree.
• Documents caller ownership of items and comparator context, borrowed node/Path lifetimes, invalidation after actual mutation, and the remove–update–reinsert procedure for comparator-relevant item changes.
• Keeps physical AVL navigation an ephemeral implementation view rather than a logical Path hierarchy contract.
• Corrects the V3 complexity and relabel documentation, including the possibility of a full-range coordinate update.
• Extends private benchmark diagnostics with a fixed interior hotspot workload and final Path/LK1 footprint records. These diagnostics do not establish a timing or asymptotic guarantee.

The public V3 header has 59 functions. Preview.3 does not redesign the ordering algorithm or change Path comparison, display text, or LK1 v1 bytes.

Validation

The implementation commit 8db22a831506f70163c419bc6d931063df884631 and the publication-state commit d5b53a3875a6e527fc5490977acc2ea55afa38f5 each passed the repository's GitHub Actions C17 build/test workflow. The latter run passed Windows MSVC, Ubuntu GCC, Ubuntu Clang, Ubuntu Clang with sanitizers, and macOS AppleClang: CI run.

Known limitations

• Managed insertion may relabel a large region, potentially every resident Path; a complete insertion has no claimed worst-case O(log n) or formal amortized bound.
• Path depth, encoded size, memory use, and single-operation latency depend on workload. The new footprint diagnostics are observations, not fixed limits.
• Caller items and comparator context must remain valid, and comparator-relevant resident item fields must not change in place.
• This Preview is not a stable V3 compatibility or production-readiness declaration. Generated Path values and private policy may change.

Tag target: d5b53a3875a6e527fc5490977acc2ea55afa38f5.

LayerKeySort v3.0.0-preview.2

LayerKeySort v3.0.0-preview.2

Experimental V3 prerelease. For normal use, prefer stable v2.0.0. V3 APIs, generated coordinates, and private placement policies remain provisional.

Endpoint coordinate optimization

Preview.1 established separate manual LksTree and comparator-bound LksOrderedTree APIs, with Path-keyed AVL indexing and logical coordinate relabeling. Preview.2 improves repeated managed endpoint insertion. It carries a saturated slot into an available Path ancestor, uses a one-slot stride after a sustained endpoint run, and allows valid direct endpoint Paths through private depth 16 before attempting relabel. Interior insertion retains adaptive geometric logical-window relabeling. No physical replacement-Tree rebuild was reintroduced.

Final endpoint-policy audit

The original Preview.2 candidate used direct endpoint depth eight. At ascending insertion 261,579 it successfully generated a valid depth-nine Path, but the private threshold alone triggered a full-range relabel of 261,578 existing nodes. The final depth-16 policy removes this particular 300k cliff.

Depth 16 is a provisional engineering tradeoff, not a public contract or mathematical optimum. Depth 12 still caused repeated relabels. Removing the depth trigger entirely avoided relabels in the tested monotone range but produced substantially deeper Paths and higher peak memory. A size-dependent limit added complexity and used more memory than depth 16 at one million items.

Performance and tradeoffs

On the documented test machine, the independent final-source ascending insertion medians were 54.574 ms at 100k, 339.946 ms at 300k, 889.976 ms at 500k, and 2,580.855 ms at 1m. All-equal append medians were 55.956 ms at 100k and 355.181 ms at 300k. These are workload measurements, not universal speed claims.

The matched depth-eight/depth-16 policy audit exposes a real regression at 500k ascending: 749.108 ms versus 882.634 ms. At 1m ascending, depth eight performed four full-range relabels of 2,487,584 old nodes in total; depth 16 performed one of 523,722 old nodes. The depth-16 final mean/P95/P99/maximum Path depths were 6.173/14/15/16, with 165,980,120 peak live bytes. With no depth trigger they were 15.780/30/31/31, with 288,763,760 peak live bytes.

Detailed methodology and raw results: benchmark report, final-source timings, and matched policy audit.

Complexity and remaining limits

Comparator upper-bound search visits O(log n) AVL nodes, excluding comparator cost. Direct insertion also creates or copies a Path in work proportional to relevant Path depth and rebalances the AVL. Adaptive relabel processes and generates replacement Paths for a logical region of k old nodes; k can equal n. Geometric expansion controls cumulative region scanning relative to the final attempted region, while Path construction also depends on depth. At 1m ascending, Preview.2 still performed one full-range relabel of 523,722 old nodes. Complete managed insertion has no claimed worst-case O(log n) or formal amortized bound.

Validation

The release-state commit passed Windows MSVC, Ubuntu GCC, Ubuntu Clang, Ubuntu Clang with sanitizers, and macOS AppleClang CI. Each configuration ran CTest 7/7 and both examples. The test suite covers ordered-tree invariants, endpoint and relabel OOM rollback, mutation soak, parser torture, Path/LK1 contracts, and benchmark smoke cases. The release-state commit changes documentation only; the final candidate's larger benchmark and 20-seed soak evidence remains applicable.

Designing beyond the algorithm

V3 development is beginning to treat API clarity, integration, distribution, documentation, migration, and first-use experience as product work. Preview.2 does not complete that work; later V3 Previews may continue it.

Stable release

Stable v2.0.0 remains the recommended release for normal use. Preview.2 is experimental, is not an API freeze, and is not marked GitHub Latest.

Release-state commit: 8e4f0c6a88dbff0c5eebaf00bd24381d4a6c85f9.

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.

LayerKeySort v2.0.0

LayerKeySort v2.0.0

LayerKeySort 2.0.0 is the first stable V2 release. It retains the production implementation published in v2.0.0-rc.1, adds the completed RC observation tests, and activates the documented 2.x source/API and semantic compatibility contract. The public C17 API has 52 functions.

V2 capabilities

• Hierarchical LksPath ordering coordinates and a mutable Path-keyed Tree, with stable placement after comparator-equal items.
• lks_path_before(), lks_path_after(), and lks_path_between() for coordinate generation; exact-Path Tree removal and failure-atomic rekey.
• Canonical Path display formatting and parsing, plus the separate versioned LK1: durable key whose same-version bytewise lexical order matches lks_path_compare().
• Immutable Group and GroupBatch results, stable merging, and the lks_sort() convenience API.
• CMake layerkeysort source integration and documented direct C17 source integration.

A Path or LK1 key is an ordering coordinate, not an application item ID. Keep durable business identity separately and account for coordinates changing after Tree mutation.

Validation

The retained RC observation commit adds a compact business-ID/LK1 persistence round trip, deterministic parser torture, multi-seed mutation-soak support, and Path-growth OOM rollback coverage. Before stable publication, 20 soak seeds passed 100,000 operations each and 16 parser seeds passed 100,000 cases each. The exact stable release-state commit passed Windows MSVC, Ubuntu GCC, Ubuntu Clang, Ubuntu Clang with sanitizers, and macOS AppleClang. Each configuration ran CTest 7/7, including the new tests and benchmark correctness smoke tests; both examples ran. An independent clean checkout also passed strict GCC C17 build, CTest 7/7, both examples, and an add_subdirectory consumer.

Compatibility and limits

The 2.x compatibility contract covers public source/API and documented semantics, canonical display grammar, and LK1 v1 bytes. Exact generated Path coordinates, AVL physical shape, and internal heuristics are implementation details.

Full Tree rebuild remains a potentially costly fallback. Complete comparator-driven insertion has no claimed worst-case O(log n) or formal amortized bound; callers must maintain comparator compatibility with existing Path order. This release does not provide whole-Tree serialization, distributed/CRDT convergence, or high-level move-before/move-after helpers. These are documented limits, not claims that they were solved by the stable label.

Release commit: 9fb7a9b0ae8d71cbd7410822e37702f6a6dc4d88.