Directories and paging

A directory is a sorted array of [name, Entry] pairs, stored either flat (one "d" node) or paged (a "d" node holding a one-level index over "ds" segment nodes). Sorted arrays give ordered listing for free and point lookup by binary search; paging bounds block size.

Page segments are globally sorted, with one page level only.

#8.1 The size function and the flat/paged decision

• pairSize(name, entry) = the byte length of the canonical CBOR encoding of the 2-element array [name, entry].
• The directory is flat if and only if Σ pairSize over all entries is ≤ pageThreshold (default 262144; see §14). Otherwise it is paged.

#8.2 Canonical segmentation (writers)

Segment boundaries are content-defined: whether an entry begins a new segment is primarily a function of its own name — the same trick the FastCDC chunker uses for file content (§9.4). This makes a paged directory's layout a pure function of the entry set, independent of edit history, while keeping edits segment-local (§8.4).

Boundary predicate. With H the store's multihash function (§3.4):

boundary(name) = (u32be(H(utf8(name))[0..4]) AND SEG_MASK) == 0
SEG_MASK       = 2^10 − 1 = 0x3ff

i.e. hash the name's UTF-8 bytes, read the first 4 bytes as a big-endian 32-bit unsigned integer, and test its low 10 bits. SEG_MASK is a format constant, not a parameter — like the GEAR table (§14). One name in 1024 is a boundary name in expectation, so with typical entry encodings (~10^2 bytes) the average span between boundary names is well under the default pageThreshold and the size clause below fires rarely.

Segmentation pass. Writers MUST cut segments in one pass over the sorted pairs:

for each [name, entry] pair, in name order:
    if the open segment is non-empty
       and (boundary(name)
            or segmentSize + pairSize(pair) > pageThreshold):
        flush the open segment as a "ds" node
    append the pair to the open segment
flush the final segment

A boundary name therefore always begins a segment, and no segment's encoded entries exceed pageThreshold — except that an oversized single pair (pairSize > pageThreshold) gets a segment of its own. Each segment becomes a "ds" node; the root "d" node holds p: an array of [firstName, Ref] pairs, where firstName is the name of the segment's first entry and each Ref is dag-cbor-codec, with firstNames strictly ascending in name order.

If the encoded root "d" node itself exceeds pageThreshold, the directory is too large and MUST be rejected at build time (≈ 5 million entries at the defaults with short names). Paging is exactly one level deep — a page index never points at another page index.

#8.3 Reading (all readers)

Validation on read:

• p MUST be a non-empty array of [firstName, Ref] pairs — each Ref dag-cbor-codec — with firstNames valid names (§6) strictly ascending in name order.
• A fetched segment MUST be a "ds" node with a non-empty, sorted entries array, and its first entry's name MUST equal the index's firstName for that segment.
• Canonical boundaries: no entry after a segment's first may be a boundary name (§8.2) — in canonical form a boundary name always begins a segment, so an interior boundary name MUST be rejected. This check needs only the store's hash function, is local to one segment, and MUST be applied to every fetched segment, including a single segment fetched for a point lookup.
• When listing across segments, ordering MUST be validated across segment boundaries too: every name in a segment MUST order strictly before the next segment's firstName. Note for implementations that cache decoded segments: this cross-segment check is a property of the referencing page index, not of the segment block, and MUST be applied even when the segment is served from a cache.

The remaining aspects of canonical form — the flat/paged decision (§8.1) and the segment size clause (§8.2) — depend on the writer's pageThreshold (§14). A reader that knows the effective value (e.g. its own store's, §10.3) SHOULD enforce them too; a reader MUST NOT reject a directory by applying a threshold the writer did not use.

Point lookup: flat → binary search e. Paged → binary search p for the last firstName ≤ the sought name, fetch that one segment, binary search its e. (Two block reads for any directory size.)

Listing: flat → e; paged → concatenate segments in index order (the result is globally sorted by construction; the reader still validates it).

#8.4 Edit locality

Because segmentation is content-defined, a paged directory's layout is part of its logical identity: one entry set, one segmentation, one ref — however the directory was reached (§13.1). There is no separate edit path: a writer updating a paged directory MUST produce exactly the blocks the pass of §8.2 produces for the new entry set.

That recomputation is local, not global: the pass never looks backwards, so cuts strictly before the edited position are unchanged. A writer MAY recompute incrementally, starting from the last cut strictly before the edit. It MAY then stop as soon as a recomputed cut falls immediately before the same pair as an old one, since every later segment is unchanged from that point on. The boundary predicate guarantees this resynchronization no later than the first boundary name after the edit, in expectation about one segment away. (Contrast purely size-based greedy packing, where one insertion shifts every subsequent cut to the end of the directory.)

Underflow needs no special rule: deleting entries changes the entry set, and the canonical pass over the new set merges or drops segments as required — a delete-heavy directory cannot accumulate a history-dependent sparse layout.