LayerKeySort v2.0.0-preview.3

LayerKeySort v2.0.0-preview.3

v2.0.0-preview.3 is the third public development snapshot of the LayerKeySort 2.0 architecture.

This Preview focuses on two representation limits exposed by the earlier V2 allocator:

1. the narrow per-level slot coordinate range;
2. the rapidly growing textual representation of deep or skipped-level Paths.

Warning

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

LayerKeySort Preview releases are public development snapshots.
Algorithms, heuristics, generated Path layouts, text representation, and
performance characteristics may still change before a stable 2.0 release.

---

Full 16-bit slot coordinate space

Preview.3 expands the slot domain from the earlier small coordinate range to:

0..65535

All 65,536 slot values are available.

Paths store slot values numerically as uint16_t after public-range validation.
The public slot-facing API continues to use unsigned int.

This substantially increases the amount of local coordinate space available
before deeper Paths, local repair, or full rebuild become necessary.

---

Fixed-width radix-54 slot text

Each numeric slot now formats as exactly three characters using the current
ASCII alphabet:

23456789ABCDEFGHJKMNPQRSTUVWXYZabcdefghjkmnpqrstuvwxyz

The alphabet contains 54 characters and is ordered by codec rank:

digits < uppercase letters < lowercase letters

The exact current order is:

2 < 3 < 4 < 5 < 6 < 7 < 8 < 9
  < A < B < C < D < E < F < G < H
  < J < K < M < N < P < Q < R < S < T < U < V < W < X < Y < Z
  < a < b < c < d < e < f < g < h
  < j < k < m < n < p < q < r < s < t < u < v < w < x < y < z

Therefore:

digits < uppercase < lowercase
A < a
Z < a

The encoding is case-sensitive and uses fixed ASCII bytes rather than
locale-sensitive alphabetic ordering.

The first alphabet character is radix digit zero:

'2' -> rank 0
'3' -> rank 1
...
'9' -> rank 7
'A' -> rank 8
...
'z' -> rank 53

So the visible character 2 represents radix digit value zero in the slot
codec; it does not mean numeric value 2.

Slot tokens always contain exactly three characters. Leading radix-zero
characters are retained.

Verified examples include:

0      -> 222
1      -> 223
53     -> 22z
54     -> 232
130    -> 24R
259    -> 26p
32767  -> DEp
32768  -> DEq
65535  -> RUc

The slot alphabet intentionally excludes visually ambiguous characters:

0 O o
1 I i L l

These exclusions apply only to slot tokens. Characters 0 and 1 are still
used elsewhere in formatted Path text for direction, ZERO, and decimal level
metadata.

Slot tokens intentionally use no punctuation.

Because tokens are fixed-width and the alphabet follows increasing ASCII byte
order, numeric slot order is monotonic with bytewise lexical token order.

This property applies only to individual three-character slot tokens.

Complete formatted Paths are not a general lexical sort key.
Use lks_path_compare() for Path ordering.

---

Compact level representation

Preview.3 removes the older unary slash-based level text growth.

/ now only separates Path steps.

The current formatter grammar is conceptually:

ZERO:
000

NONZERO:
DIRECTION FIRST_SEGMENT ( "/" NEXT_SEGMENT )*

Direction characters are:

0 = positive
1 = negative

Every segment ends with exactly one three-character slot token.

For the first step:

• level 0 is omitted;
• a nonzero absolute first level is written as minimal unsigned decimal
  immediately before the slot token.

For later steps:

• delta = current_level - previous_level;
• delta 1 is omitted;
• a delta greater than 1 is written as minimal unsigned decimal immediately
  before the slot token.

Examples of the structure are:

levels 0,1,2:
0XXX/YYY/ZZZ

levels 0,5,6:
0XXX/5YYY/ZZZ

first level 12:
012XXX

levels 0 -> 12:
0XXX/12YYY

Here XXX, YYY, and ZZZ stand for three-character slot tokens.

Decimal level metadata is emitted canonically:

• no unnecessary leading zeroes;
• first level 0 is omitted;
• later delta 1 is omitted;
• no spaces are emitted;
• no empty or repeated slash-separated segments are emitted.

/ is now only a structural step separator. Slash count no longer encodes the
numeric level.

lks_path_text_length() reports the formatted length excluding the terminating
NUL.

lks_path_format() writes a NUL-terminated C string.

---

ZERO

The ZERO Path formats exactly as:

000

ZERO has Path depth 0.

It is a Path value and is distinct from the mutable Tree's virtual structural
root.

A valid nonzero formatted Path contains a direction character followed by at
least one three-character slot token, so its minimum formatted length is four
characters. Therefore it does not collide with 000.

---

Path text size

The older representation used unary slash growth for explicit levels, which
could make text size grow rapidly for deeper Paths.

For common consecutive levels beginning at level 0, Preview.3 uses:

1 direction character
+ 3 characters per slot
+ 1 separator between adjacent steps

so the common consecutive-level length is:

4 * depth

for nonzero depth.

Representative formatted lengths:

Depth	Preview.2	Preview.3
1	3	4
2	6	8
4	15	16
8	45	32
16	153	64
32	561	128
64	2145	256

Shallow Preview.3 Paths can therefore be slightly longer than the older form,
while deeper Paths become substantially shorter.

For skipped levels, additional text cost is proportional to the decimal digits
required for the absolute first level or later level deltas.

Internal Path storage remains numeric and proportional to Path depth; the text
representation is only a formatter output.

---

Path ordering remains API-defined

The ordering contract continues to be defined by lks_path_compare().

Current top-level ordering is:

NEGATIVE < ZERO < POSITIVE

Within the same nonzero direction, Paths are compared from the root step
forward.

At the first differing step:

1. level is compared first;
2. a numerically larger level sorts earlier;
3. if levels are equal, slot comparison normally uses ascending numeric order.

There is one directional exception:

negative root slot ordering is reversed

So at the root step of two negative Paths, the larger numeric slot sorts
earlier.

For deeper steps of negative Paths, slot ordering returns to the normal
ascending rule.

If all shared steps are identical and one Path ends first, the shorter parent
Path sorts before its descendant.

Therefore:

• a larger numeric level may sort before a smaller one;
• negative root slot ordering is reversed;
• negative descendant slot ordering is not reversed;
• parent Paths sort before their descendants.

Do not derive the complete Path order from the formatted string.

In particular:

strcmp(formatted_a, formatted_b)

is not a substitute for:

lks_path_compare(a, b)

The complete formatted representation includes direction, optional decimal
level metadata, separators, and omitted default deltas, so full-string lexical
order is not the public ordering contract.

---

Full 16-bit sparse bulk placement

Bulk construction now distributes blocks sparsely across the full 16-bit slot
domain.

The current root-slot policy is based on the full 65,536-value space and places
blocks conceptually according to:

slot = ((block_index + 1) * 65536) / (blocks + 1)

using sufficiently wide arithmetic.

For one block this places the root at:

32768

The policy deliberately leaves unused coordinate space both between generated
blocks and near the ends of the slot domain.

The maximum bulk child block count remains 26.

That count is independent from the radix-54 text codec.

This follows the V2 design principle:

preserve useful future coordinate space rather than trying to exhaust every
representable slot immediately.

---

Preview.2 repair policy intentionally retained

Preview.3 widens the coordinate domain without simultaneously retuning the
Preview.2 repair heuristics.

The existing policy still includes:

preferred online depth:       4
hard online depth:            6
local repair windows:         8 -> 16 -> 32 -> 64
minimum useful spacing:       2
minimum repair depth gain:    1
endpoint target spacing:     10

Keeping endpoint target spacing at 10 is intentional.

Preview.3 is designed to isolate the effect of widening the coordinate space
before later heuristic tuning.

These values remain Preview policy rather than permanent format rules.

---

Measured online-insertion effect

For the current ascending online-insertion test with 1024 items:

Metric	Preview.2	Preview.3
Maximum Path depth	4	1
Local repair attempts	563	0
Local repair successes	38	0
Abandoned repairs	525	0
Accepted deeper Paths	520	0
Full-tree rebuilds	5	0
Peak live bytes	210176	90200

Preview.3 additionally measured approximately:

average depth: 0.999
P95 depth:     1
P99 depth:     1
maximum text length: 4
successful requested cumulative bytes: 196736

The average includes the depth-zero ZERO Path.

For the current descending online-insertion test with 256 items:

Preview.2 maximum depth: 1
Preview.3 maximum depth: 1
Preview.3 repairs:       0
Preview.3 peak bytes:    22616

For the current all-equal online-insertion test with 128 items:

Metric	Preview.2	Preview.3
Maximum Path depth	5	1
Local repairs	5	0
Peak live bytes	22760	11352

For the current NarrowGap test with 62 items, the structural maximum depth
remains 1 with no repair in both Preview.2 and Preview.3; Preview.3's measured
maximum text length is 6.

These measurements show that the wider coordinate space substantially reduced
congestion in these tested workloads.

They do not mean:

• local repair is obsolete;
• full rebuild can no longer occur;
• all workloads remain at depth 1;
• worst-case complexity is solved.

Forced regression tests continue to exercise both local repair and full-tree
fallback behavior.

---

Strong failure behavior remains

Preview.3 retains the strong mutation guarantees established by the V2 Tree
work.

Local repair and full-tree replacement are prepared before committing changes.

Allocation-failure tests verify that failed operations preserve:

• logical Tree contents;
• Tree size;
• ordering;
• existing live allocation accounting;
• out_node == NULL;
• leak-free cleanup;
• absence of partially committed repairs.

Preview.3 fault-injection coverage included:

Local-repair failure points: 195
Full-rebuild failure points:  49

All tested failure points passed.

---

Historical v1 regression isolation

The historical v1 owned-base merge helper is retained only for regression and
benchmark validation of old behavior.

It is gated behind the private build option:

LKS_ENABLE_V1_REGRESSION_HELPERS

The normal production library does not contain the historical helper.

Diagnostic/regression builds may include it where historical tests require it.

Current public V2 Group merge semantics are different:

• source Groups remain unchanged;
• comparator-equal ordering is stable;
• Base equal items precede Incoming equal items;
• the result receives a fresh Path coordinate space;
• source Path values are not persistent identity in the merged result.

---

Path lifetime and identity

A Path is an ordering coordinate, not a permanent item identifier.

For a published immutable Group:

• its Paths remain stable for that Group's lifetime.

For a mutable Tree:

• a successful mutation may perform direct insertion, local relabel, or rebuild;
• existing Paths may therefore be re-encoded;
• borrowed Tree nodes, Paths, and navigation results must be reacquired after a
  successful mutation.

Build and merge operations do not mutate their source Groups.

The result owns its structural Path data while caller-provided item objects
remain caller-owned.

---

Persistence and serialization status

Preview.3 defines a current human-readable formatter representation.

It does not define:

• a public Path parser;
• a durable persistence format;
• a binary serialization format;
• a stable network/wire protocol;
• permanent compatibility of exact formatted Path strings across future
  Preview versions.

Exact generated Paths and exact text representations remain subject to change
during V2 Preview development.

Applications should not use formatted Path text as a permanent item ID.

---

Public API

Preview.3 does not add or remove public functions or public types.

Functions: 46
Types:      9

The simple sorting entry point remains:

#include "layerkeysort.h"

lks_sort(items, count, compare_items, NULL);

lks_sort() stable-sorts the caller-owned pointer array.

The pointed-to objects remain caller-owned.

Advanced Path, Tree, Group, and GroupBatch APIs remain available when explicit
ordering coordinates or incremental structures are required.

---

Validation

Preview.3 validation includes:

• exhaustive checks for all 65,536 slot encodings;
• verification that every emitted slot character belongs to the current
  radix-54 alphabet;
• adjacent slot-token lexical-order checks;
• exact slot-codec examples;
• public slot-boundary tests;
• SIZE_MAX first-level formatting;
• Path text buffer behavior;
• depth/text-length checks;
• bulk roots for 1, 2, 25, and 26 blocks;
• explicit boundary cases that trigger local repair and region expansion;
• full-tree fallback cases;
• LEVEL_LIMIT fallback;
• allocation-failure rollback testing;
• deterministic property testing;
• deterministic stress testing;
• example and public API smoke tests.

Local validation passed with:

• GCC C17;
• -Wall -Wextra -Wpedantic -Werror;
• CMake / CTest;
• MSVC x64 Debug;
• MSVC x64 Release;
• MSVC x64 ASan;
• example/public API smoke tests;
• deterministic property/stress tests;
• git diff --check.

No local Clang installation was available during implementation work.

The configured GitHub Actions matrix subsequently passed on main, including
the repository's Ubuntu Clang jobs.

GitHub Pages deployment for the final release commit also completed
successfully.

---

Maintainability audit

The Preview.3 maintainability pass consolidated responsibilities so that:

• the public slot range is defined in the public header;
• current allocator/policy constants remain centralized in the internal policy
  layer;
• the production slot alphabet exists in the slot codec implementation;
• tests keep an independent expected alphabet so production mistakes can still
  be detected;
• Path storage remains numeric;
• the slot codec is responsible only for numeric slot-to-token conversion;
• Path text formatting owns level metadata and complete Path text;
• bulk and gap logic do not depend on textual alphabet details.

The historical v1 helper remains separated from ordinary production builds.

No public API was added for the private codec.

The remaining Tree/Path topology coupling is recognized as architectural debt
and is intentionally deferred rather than hidden by additional local
complexity.

---

Still intentionally deferred

Preview.3 does not attempt to finish every remaining V2 concern.

Still deferred include:

• comparator-equal run lookup optimization;
• child-storage redesign;
• deeper Tree/Path topology decoupling;
• further heuristic tuning;
• insertion-direction or insertion-history prediction;
• deletion;
• move/rekey operations;
• persistence / serialization design;
• public Path parsing;
• collaborative/distributed ordering semantics;
• formal amortized or worst-case complexity claims.

These remain candidates for later Preview work and may be changed or
superseded as the architecture evolves.

---

Release commit

9fa2eadcca422be9483a050505f0c332558c5908

Tag:

v2.0.0-preview.3

---

Documentation

Preview.3 documentation has been synchronized across:

• README.md
• docs/API.md
• docs/USAGE.md
• docs/DEVELOPMENT.md
• CHANGELOG.md
• the active V2 roadmap Issue

The project development guide now explicitly requires this documentation and
roadmap review before future Preview releases are finalized.

---

Final note

v2.0.0-preview.3 is a tested V2 development snapshot, not a stable production
release.

It demonstrates that the wider slot coordinate domain and compact Path text
representation materially improve the current V2 design while preserving the
existing public ordering model.

The stable historical v1.0.0 release remains available separately.

Full Changelog: v2.0.0-preview.2...v2.0.0-preview.3