LayerKeySort

A C17 library for stable ordering with hierarchical Path positions. Latest prerelease: v2.0.0-rc.1.

LayerKeySort orders caller-owned item pointers with a comparator and gives each item an explicit Path position. Groups can be built independently and merged while preserving the order of comparator-equal items. The public API is C17 and models paths, trees, groups, and batches directly.

Warning

V2 is at Release Candidate stage. RC.1 freezes the feature, public API, Path display, and LK1 format contract for final validation. It is still a prerelease, not stable or production-ready 2.0. Exact automatically generated Path layouts and performance remain implementation details.

Passing tests confirms the tested correctness properties. It does not establish final optimization, complexity, heuristic tuning, or production readiness.

Quick start

#include "layerkeysort.h"

lks_sort(items, count, compare_items, NULL);

items is a caller-owned pointer array; compare_items defines the order. Sorting is stable, and the pointed-to objects remain caller-owned. lks_sort returns LksStatus, which production code should check. See the complete, compilable basic example. The Preview.5 layer-list example shows dynamic Path ordering. For Path, Tree, and Group operations, see the usage guide.

V2 development status

Version	Main purpose	Still provisional or deferred
v2.0.0-preview.1	Establish the V2 baseline: re-encodable Paths, sparse bulk Group/Batch construction, lks_sort, CMake/CI, and production diagnostic isolation.	Local congestion handling, online insertion policy, heuristic tuning, and final performance.
v2.0.0-preview.2 (released)	Add bounded local Tree relabel/rebuild before accepting a deeper Path or using the full-Tree fallback.	Window and depth heuristics, equal-run lookup performance, allocator tuning, long-term Tree/Path design, and complexity analysis.
v2.0.0-preview.3 (released)	Use the full 16-bit slot range and a compact Path text codec while keeping the V2 ordering model.	Equal-run lookup, child storage, topology coupling, and heuristic tuning remain open.
v2.0.0-preview.4 (released)	Add a Path-keyed AVL Tree, remove/rekey, canonical display parsing, LK1 sortable keys, and measured endpoint insertion improvements.	Preview semantics and generated Paths remain provisional; full rebuild has adversarial costs, and some insertion workloads regress.
v2.0.0-preview.5 (released)	Improve real-use examples, integration guidance, long-run mutation testing, platform coverage, and public-contract review.	Still a Preview; core complexity and persistence limits remain.
v2.0.0-rc.1 (released candidate)	Freeze and validate the V2 public contract and documented source integration.	Still a prerelease; release blockers, if found, require an RC fix before stable 2.0.0.

RC.1 retains Preview.5's Path-keyed Tree, remove/rekey, canonical display parsing, LK1 sortable keys, usage guidance, mutation soak, and macOS validation. It freezes the intended public 2.x contract without changing the production algorithm. See the compatibility contract.

Open the live interactive visualizer

The visual shows a historical v1 Path showcase. The local browser visualizer in docs/demo/ does not execute the production C implementation and its recorded Path values do not describe the V2 allocator.

Visual overview

flowchart TD
    A[Input items] --> B[Build local Groups]
    B --> C[Assign local hierarchical Paths]
    C --> D[Stable merge]
    D --> E[Assign fresh result Paths]
    E --> G[Final ordered Group]

Loading

Paths in separate Groups are local positions. A merge leaves both inputs unchanged and assigns a fresh coordinate layout to the result; exact Base Paths may change.

Why LayerKeySort?

• Stable ordering for items that compare equal.
• Hierarchical Path positions that can represent deeper levels and gaps.
• A one-call stable pointer-array sort for ordinary use.
• Explicit Group and GroupBatch construction and merge operations.
• Base-first ordering for equal items from a public two-Group merge.
• A C17 public API that borrows caller-owned item pointers.

When to use it

Use the Path and Tree APIs when an application keeps a mutable order over time, needs explicit hierarchical coordinates and before/after/between placement, and can update coordinates when items move or a Tree is rebuilt. UI layers, playlists, workflow editors, timelines, dynamic task lists, and scene ordering are possible application categories; this list does not imply that those projects use LayerKeySort. The library also provides stable handling of comparator-equal items, remove/rekey, and optional versioned LK1: keys for persisting one sortable coordinate. The layer-list example shows this workflow with application IDs separate from Paths.

When not to use it

• For one-time array sorting, an ordinary sorting routine may be simpler. lks_sort() is available when a stable pointer-array sort is useful, but dynamic Path machinery is unnecessary.
• If only occasional database reorder operations need a compact lexical rank string, a simpler fractional-ranking scheme may have lower conceptual and storage overhead.
• The current mutable Path model does not provide distributed/CRDT replica convergence or immutable permanent rank or item-identity values.
• Complete comparator-driven insertion has no claimed worst-case O(log n) bound or formal amortized bound. Choose a different design if a proven operation bound is required.

Core idea

A Path is an ordering coordinate, not a permanent item ID. 000 is the ZERO Path, distinct from the Tree's virtual root. Since Preview.3, Paths have all 65,536 numeric slots (0..65535); each formats as three radix-54 characters from the current ASCII alphabet. Positive Paths begin with 0, negative Paths with 1; / separates steps, and optional decimal metadata records a nonzero first level or a later level jump. A parent sorts before its descendants. Use lks_path_compare() for ordering: complete formatted Path strings are not a general lexicographic sort key. The exact alphabet, comparison rules, and formatter grammar are specified in the API reference.

For example, an additional position can be inserted between a parent and an existing descendant by using a deeper skipped level:

A         0DEq
Inserted  0DEq/5222
X         0DEq/2222
B         0DEr

The Path comparison and gap APIs implement this ordering. Tree mutations may re-encode Paths; reacquire borrowed Tree nodes and Paths after an actual mutation. Preview.4 can parse canonical display text and persist a coordinate as a separate LK1: order key. For example, display 0222 has key LK1:201FF0000!. A persisted coordinate is not a permanent item identity. Preview.3 did not contain these APIs.

Ordering and stability guarantees

• A comparator result below zero places the left item first; zero means equal under that comparator; above zero places it after the right item.
• Comparator-equal items retain their input/source order. In a public two-Group merge, equal Base items precede equal Incoming items; Batch merging preserves chunk order.
• Group and Batch merge inputs must have ordering semantics compatible with the supplied merge comparator and context.
• Item pointers are borrowed. LayerKeySort does not clone or free caller-owned items; callers manage their lifetime.

Public API overview

The public header is include/layerkeysort.h.

• Path: create, clone, append, format/parse display text, format/parse durable keys, compare, and find positions before, after, or between other Paths.
• Simple sort: lks_sort() stable-sorts the caller's pointer array.
• Tree: insert, remove by Path, rekey an item's Path, locate entries, and navigate nodes.
• Group: build a sorted Group and access its items and Paths.
• GroupBatch / merge: build Groups from consecutive input chunks and merge Groups or a Batch.
• Status / comparator: report operation status and supply a comparison callback with caller-owned context.

Build

For the reusable library and test suite:

cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure

The existing LayerKeySort.slnx / .vcxproj remain available for MSVC C17 validation. Build artifacts belong in an out-of-source build/ directory.

Validation

The repository includes deterministic property tests, stress tests, a Preview.5 mutation soak, allocation-failure and out-of-memory tests, and a public API smoke test. CI is configured for Windows/MSVC, Ubuntu/GCC and Clang (including sanitizer validation), and macOS/AppleClang. A passing runner does not guarantee every platform version. Path heuristics are internal and may change; no optimal complexity claim is made.

Performance evidence

The Preview.4 benchmark report gives reproducible Preview.3, Stage 4, and Stage 5 measurements, including regressions and memory tradeoffs. The benchmark harness is optional in CMake. The Path-keyed Tree is much faster on several equal-key and open-end insertion workloads, but alternating and small random cases do not improve across the board. Full rebuild remains a correctness fallback, so online insertion has no claimed worst-case O(log n) time bound.

Current limitations

• Shared mutable objects are not guaranteed to be thread-safe; use external synchronization when sharing them.
• Paths from separate Groups are local coordinates until a merge establishes the result's path space.
• Published Groups are immutable; their borrowed Paths stay stable until Group destruction. After an actual Tree mutation, reacquire all borrowed Tree nodes, Paths, and navigation results. Equal-Path rekey is a no-op and preserves them.
• Preview.4 Tree remove does not compact Paths; rekey changes the selected item's coordinate. AVL rotations change physical links, not Path encodings. Caller-selected rekeys must preserve comparator order before later comparator-driven operations.
• No binary serialization protocol, fixed memory ceiling, or public allocator/fault-injection API is provided. The Preview.4 LK1: key requires bytewise ASCII database collation for ordering.
• The Preview.4 key persists one Path coordinate; it does not save a Tree or caller items, assign permanent item IDs, or provide distributed/CRDT conflict resolution. Package-manager recipes and a public custom allocator are optional future integrations.

Project layout

include/layerkeysort.h
src/
examples/basic.c
examples/layer_list.c
tests/
demo/main.c
LayerKeySort.slnx
LayerKeySort.vcxproj
LICENSE
CHANGELOG.md

Documentation

• Usage guide
• Integration guide
• 2.x compatibility contract
• API reference
• Development guide
• Benchmark report
• Contributing
• Interactive visualizer source

License

LayerKeySort is licensed under the MIT License.