# gizfs:ordered

An ordered map from byte strings to integers: a B+tree whose inner nodes keep each child's largest key and entry count, so seek, insert and delete cost O(log n) and rank queries too. Keys compare as bytes; callers encode what they order so that byte order is their order (the caller's value encoding). One structure serves retained roots, database ordered indexes and key-value sorted sets.

Nodes live in one pool and name each other by position. The pool is kept in pages of NP nodes: when a tree is shared with other threads' readers (an engine or storage snapshot), a write copies the pages it changes, not every node. Leaves are linked both ways for scans. A child's recorded largest key may be stale after a delete (larger than its real largest): it still bounds the child, so routing stays correct, and it is never smaller.

```gizlang
import * as Ordered from "gizfs:ordered";
```

## Types

### `Ordered`

```gizlang
type Ordered
```

An ordered map from byte keys to integers in memory (a B+ tree with counts, so rank and position are fast), or a
view of a paged tree in a file.

- `pages`: `M39.DirectoryPages<Vec<M39.Node>>`
- `used`: `i64`
- `free`: `M39.DirectoryPages<i64>`
- `root`: `i64`
- `size`: `i64`
- `weighted`: `bool`
- `population`: `i64`
- `directoryNodes`: `i64`
- `directorySlots`: `i64`
- `leafKeyCredit`: `i64`
- `innerKeyCredit`: `i64`
- `structuralCredit`: `i64`
- `cold`: `Vec<M39.ColdPages>`

### `ColdPages`

```gizlang
type ColdPages = { disk: Disk; path: string; end: Task.Atomic; cursor: i64; }
```

Where a tree's evicted leaf pages are (Ordered.evictLeaves): an append-only spill file, never
rewritten, so every copy of the tree reads back the page version its directory names. The file is
scratch: the WAL and segment files rebuild the tree at open, which removes it.

- `disk`: `M37.Disk`
- `path`: `string`
- `end`: `gizlang_task.Atomic`
- `cursor`: `i64`

### `Pos`

```gizlang
type Pos = { node: i64; at: i64; }
```

A position: an entry of a leaf, or past the end when `node` is -1.

- `node`: `i64`
- `at`: `i64`

### `OrderedImage`

```gizlang
type OrderedImage = { pages: PageDirectory<Vec<Node>>; used: i64; free: PageDirectory<i64>; root: i64; size: i64; weighted: bool; population: i64; directoryNodes: i64; directorySlots: i64; leafKeyCredit: i64; innerKeyCredit: i64; structuralCredit: i64; cold: Vec<ColdPages>; }
```

An Ordered with its pages in owned directories and no native owner, as a value with no Ref: it crosses threads
(Task.cell), as a database's read view does.

- `pages`: `_gizlang_sdk_collections.PageDirectory<Vec<M39.Node>>`
- `used`: `i64`
- `free`: `_gizlang_sdk_collections.PageDirectory<i64>`
- `root`: `i64`
- `size`: `i64`
- `weighted`: `bool`
- `population`: `i64`
- `directoryNodes`: `i64`
- `directorySlots`: `i64`
- `leafKeyCredit`: `i64`
- `innerKeyCredit`: `i64`
- `structuralCredit`: `i64`
- `cold`: `Vec<M39.ColdPages>`

### `OrderedEntries`

```gizlang
type OrderedEntries = { keys: Vec<bytes>; vals: Vec<i64>; }
```

Entries as two parallel lists: the keys and their values.

- `keys`: `Vec<bytes>`
- `vals`: `Vec<i64>`

### `OrderedRun`

```gizlang
type OrderedRun = { keys: Vec<bytes>; vals: Vec<i64>; past: Pos; }
```

Up to N entries from P on, toward the end or (DESC) the start, and the position past them.

- `keys`: `Vec<bytes>`
- `vals`: `Vec<i64>`
- `past`: `M39.Pos`

### `OrderedEntry`

```gizlang
type OrderedEntry = { key: bytes; value: i64; }
```

A key and its value.

- `key`: `bytes`
- `value`: `i64`

### `PagedOrdered`

```gizlang
type PagedOrdered = { root: StoredPage; count: i64; height: i64; maxPageBytes: i64; }
```

A paged ordered tree in a file: its root page, its number of entries, its height and its greatest page size.

- `root`: `M37.StoredPage`
- `count`: `i64`
- `height`: `i64`
- `maxPageBytes`: `i64`

### `OrderedPosition`

```gizlang
type OrderedPosition = { root: PagePosition; count: i64; height: i64; maxPageBytes: i64; }
```

Where a paged tree is, as it is stored: the position of its root page and its size.

- `root`: `M37.PagePosition`
- `count`: `i64`
- `height`: `i64`
- `maxPageBytes`: `i64`

### `OrderedPages`

```gizlang
type OrderedPages = { tree: PagedOrdered; end: i64; }
```

A paged tree that a build made, and the end of its pages in the file.

- `tree`: `M39.PagedOrdered`
- `end`: `i64`

### `OrderedCursor`

```gizlang
type OrderedCursor = { tree: PagedOrdered; frames: Vec<OrderedFrame>; leaf: Option<OrderedNodeLease>; at: i64; descending: bool; lease: ResourceLease; closed: bool; }
```

A cursor over the entries of a paged tree, in key order or in reverse.

- `tree`: `M39.PagedOrdered`
- `frames`: `Vec<M39.OrderedFrame>`
- `leaf`: `_gizlang_sdk_core.Option<M39.OrderedNodeLease>`
- `at`: `i64`
- `descending`: `bool`
- `lease`: `M37.ResourceLease`
- `closed`: `bool`

### `OrderedUpdate`

```gizlang
type OrderedUpdate = { tree: PagedOrdered; end: i64; changed: bool; fresh: bool; }
```

A paged tree after a change: its new tree, the end of its pages, and whether the change changed it and wrote new
pages.

- `tree`: `M39.PagedOrdered`
- `end`: `i64`
- `changed`: `bool`
- `fresh`: `bool`

### `OrderedEdit`

```gizlang
type OrderedEdit = { key: bytes; value: Option<i64>; }
```

A change of one key: a new value, or none to remove it.

- `key`: `bytes`
- `value`: `_gizlang_sdk_core.Option<i64>`

## Functions

### `newOrdered`

```gizlang
function newOrdered(): Ordered
```

An empty ordered map.

Effects: fail, read, write.

### `newManagedOrdered`

```gizlang
function newManagedOrdered(): Ordered
```

Ref-held metadata keeps node-page roots as identities; ordinary value trees
retain their buffers under the ordinary allocation budget.

Effects: fail, read, write.

### `orderedOfImage`

```gizlang
function orderedOfImage(image: OrderedImage): Ordered
```

The ordered map of IMAGE.

Effects: fail.

### `nativeOrdered`

```gizlang
function nativeOrdered(owner: Ref<NativePages>): Result<Ordered, IoError>
```

Same ordered-map contract, with roots in the caller's common page owner.

Effects: fail, read, write, console, io.

### `adoptOrdered`

```gizlang
function adoptOrdered(owner: Ref<NativePages>, tree: PagedOrdered): Ordered
```

The ordered map that reads the paged tree TREE of OWNER.

Effects: fail, read, write.

### `treeRoot`

```gizlang
function treeRoot(tree: Ordered, written: bool): PagedOrdered
```

The root of the native TREE for a snapshot (WRITTEN: nativeRoot) or for its size (storedRoot).

Effects: fail, read, write, console, io.

### `newWeightedOrdered`

```gizlang
function newWeightedOrdered(): Ordered
```

Optional population/peak summaries share the same tree, page pool and mutations.

Effects: fail, read, write.

### `orderedSorted`

```gizlang
function orderedSorted(keys: Vec<bytes>, vals: Vec<i64>): Ordered
```

A tree of KEYS, strictly ascending, and their VALS, built bottom up: the leaves take the entries in order and each
inner level their maxima, where putting them one by one descended the tree and split it for each key (a million-key
rebuild was most of ADD PRIMARY KEY and of a large memtable flush).

Effects: fail, read, write, console, io.

### `prefixEnd`

```gizlang
function prefixEnd(prefix: bytes): Option<bytes>
```

The smallest key above every key that starts with `prefix`, or none when no key is (the
prefix is all 0xFF): with `seek`, the end of a prefix range.

Effects: fail.

### `formats`

```gizlang
function formats(): Vec<Format>
```

The on-disk formats of this module. A test opens a committed store sample of every version.

Effects: fail.

### `orderedPosition`

```gizlang
function orderedPosition(tree: PagedOrdered): OrderedPosition
```

The stored position of TREE.

### `bindOrdered`

```gizlang
function bindOrdered(position: OrderedPosition, object: bytes, path: string): PagedOrdered
```

The paged tree at POSITION in OBJECT of the file at PATH.

### `writeOrderedPosition`

```gizlang
function writeOrderedPosition(out: mut bytes, position: OrderedPosition): void
```

Appends POSITION.

Effects: fail.

### `buildOrderedPagesContext`

```gizlang
function buildOrderedPagesContext(file: File, path: string, object: bytes, credits: mut ResourceContext, maxPageBytes: i64, pull: () => Result<Option<OrderedEntry>, IoError>): Result<OrderedPages, IoError>
```

Bounded bulk build from strictly ascending keys. The file must already be caller-owned
staging storage; errors roll back its appended tail. Success does not sync or publish a
root: the existing Engine checkpoint/WAL owner must do that before making it visible.

Effects: fail, read, write, console, io.

### `buildOrderedPages`

```gizlang
function buildOrderedPages(file: File, path: string, object: bytes, credits: mut Resources, maxPageBytes: i64, pull: () => Result<Option<OrderedEntry>, IoError>): Result<OrderedPages, IoError>
```

A paged tree of the entries that PULL gives in key order, written to FILE at PATH from the end of OBJECT. Pages are
at most MAXPAGEBYTES.

Effects: fail, read, write, console, io.

## Methods

### `Ordered.evictLeaves`

```gizlang
function Ordered.evictLeaves(self: mut Ordered, disk: Disk, path: string, bytes: i64): Result<i64, IoError>
```

Moves about `bytes` of leaf pages to the spill file, on from where the last eviction stopped, as
LeanStore picks pages to cool without tracking each access; its bytes in memory left. A page with an
inner node, the root's included, stays: a lookup then reads at most one page back.

Effects: fail, read, write, console, io.

### `Ordered.residentBytes`

```gizlang
function Ordered.residentBytes(self: Ordered): i64
```

The bytes of the tree's nodes held in memory (their reservations).

Effects: fail.

### `Ordered.image`

```gizlang
function Ordered.image(self: Ordered): Option<OrderedImage>
```

The image of the tree, or none for a managed or native one. It shares the tree's pages.

Effects: fail.

### `Ordered.nativeRoot`

```gizlang
function Ordered.nativeRoot(self: Ordered): Option<PagedOrdered>
```

The paged tree under the map, when the map reads one.

Effects: fail, read, write, console, io.

### `Ordered.storedRoot`

```gizlang
function Ordered.storedRoot(self: Ordered): Option<PagedOrdered>
```

The root of the pages of a native tree, without its pending edits. It encodes in as many bytes as the root that
writes them (nativeRoot), so a size needs no write.

Effects: fail, read.

### `Ordered.count`

```gizlang
function Ordered.count(self: Ordered): i64
```

The number of entries.

### `Ordered.recycledNodes`

```gizlang
function Ordered.recycledNodes(self: Ordered): i64
```

Retained pool nodes available for reuse, independent of their page carrier.

Effects: fail.

### `Ordered.weightCount`

```gizlang
function Ordered.weightCount(self: Ordered): Option<i64>
```

The sum of the weights, when the map is weighted.

### `Ordered.putWeight`

```gizlang
function Ordered.putWeight(self: mut Ordered, key: bytes, weight: i64): Result<bool, string>
```

Sets the weight of KEY in a weighted map; true when KEY is new. It fails when the map is not weighted or WEIGHT is
negative.

Effects: fail, read, write, console, io.

### `Ordered.keyReservation`

```gizlang
function Ordered.keyReservation(self: Ordered, includeLeaf: bool): i64
```

Reserved key-buffer credit, maintained only on touched nodes. Separator references always count.

Effects: fail.

### `Ordered.reservation`

```gizlang
function Ordered.reservation(self: Ordered, includeLeaf: bool): i64
```

Conservative single-version reservation: bounded node vectors, directories and key buffers.
includeLeaf=false excludes only leaf keys already charged by a caller's canonical bag wire owner.
It never excludes separator keys. Shared historical versions and allocator overhead are not measured.

Effects: fail.

### `Ordered.entries`

```gizlang
function Ordered.entries(self: Ordered): OrderedEntries
```

Every entry in key order, read a leaf at a time (first and next read a node for each entry).

Effects: fail, read, write, console, io.

### `Ordered.putFresh`

```gizlang
function Ordered.putFresh(self: mut Ordered, key: bytes, val: i64): bool
```

KEY, which the caller knows is not in the tree, put with VAL: a native tree reads no page to learn it.

Effects: fail, read, write, console, io.

### `Ordered.removePresent`

```gizlang
function Ordered.removePresent(self: mut Ordered, key: bytes): bool
```

KEY, which the caller knows is in the tree, removed: a native tree reads no page to learn it.

Effects: fail, read, write, console, io.

### `Ordered.put`

```gizlang
function Ordered.put(self: mut Ordered, key: bytes, val: i64): bool
```

Sets KEY to VAL; true when KEY is new.

Effects: fail, read, write, console, io.

### `Ordered.swap`

```gizlang
function Ordered.swap(self: mut Ordered, key: bytes, val: i64): Option<i64>
```

Puts KEY and gives the value it replaced, in one descent (a get, then a put, read the path twice).

Effects: fail, read, write, console, io.

### `Ordered.remove`

```gizlang
function Ordered.remove(self: mut Ordered, key: bytes): bool
```

Removes `key`; whether it was there. An emptied node leaves its parent; a root with one
child gives way to it.

Effects: fail, read, write, console, io.

### `Ordered.rekey`

```gizlang
function Ordered.rekey(self: mut Ordered, oldKey: bytes, newKey: bytes, val: i64): Result<bool, string>
```

A key transfer uses one pool-page candidate, including both search paths.
Collision checks precede all edits and leave diagnostics unchanged.

Effects: fail, read, write, console, io.

### `Ordered.get`

```gizlang
function Ordered.get(self: Ordered, key: bytes): Option<i64>
```

The value of `key`, or none.

Effects: fail, read, write, console, io.

### `Ordered.seek`

```gizlang
function Ordered.seek(self: Ordered, key: bytes): Pos
```

The first entry not below `key`.

Effects: fail, read, write, console, io.

### `Ordered.first`

```gizlang
function Ordered.first(self: Ordered): Pos
```

The position of the first entry.

Effects: fail, read, write, console, io.

### `Ordered.last`

```gizlang
function Ordered.last(self: Ordered): Pos
```

The position of the last entry.

Effects: fail, read, write, console, io.

### `Ordered.next`

```gizlang
function Ordered.next(self: Ordered, p: Pos): Pos
```

The position after P.

Effects: fail, read, write, console, io.

### `Ordered.prev`

```gizlang
function Ordered.prev(self: Ordered, p: Pos): Pos
```

The position before P.

Effects: fail, read, write, console, io.

### `Ordered.keyAt`

```gizlang
function Ordered.keyAt(self: Ordered, p: Pos): bytes
```

The key at P.

Effects: fail, read, write, console, io.

### `Ordered.valAt`

```gizlang
function Ordered.valAt(self: Ordered, p: Pos): i64
```

The value at P.

Effects: fail, read, write, console, io.

### `Ordered.run`

```gizlang
function Ordered.run(self: Ordered, p: Pos, desc: bool, n: i64): OrderedRun
```

OrderedRun read a leaf at a time: keyAt, valAt and next or prev read the node for each entry, and were half of a walk
back through a district's orders.

Effects: fail, read, write, console, io.

### `Ordered.before`

```gizlang
function Ordered.before(self: Ordered, key: bytes): Pos
```

The last entry below `key`.

Effects: fail, read, write, console, io.

### `Ordered.rank`

```gizlang
function Ordered.rank(self: Ordered, key: bytes): i64
```

How many entries are below `key`.

Effects: fail, read, write, console, io.

### `Ordered.atRank`

```gizlang
function Ordered.atRank(self: Ordered, r0: i64): Pos
```

The entry of rank `r` (0-based), or past the end.

Effects: fail, read, write, console, io.

### `Ordered.weightRank`

```gizlang
function Ordered.weightRank(self: Ordered, key: bytes): Option<i64>
```

Payload population below key; ordinary maps have no weight summaries.

Effects: fail, read, write, console, io.

### `Ordered.atWeight`

```gizlang
function Ordered.atWeight(self: Ordered, rank: i64): Pos
```

Entry containing zero-based population rank; zero-weight entries contribute no positions.

Effects: fail, read, write, console, io.

### `Ordered.peakWeight`

```gizlang
function Ordered.peakWeight(self: Ordered): Option<i64>
```

Largest payload population; zero for an empty/zero-population weighted map.

Effects: fail, read, write, console, io.

### `Ordered.atPeak`

```gizlang
function Ordered.atPeak(self: Ordered, descending: bool): Pos
```

First/last key at the largest positive population, in bounded tree-height work.

Effects: fail, read, write, console, io.

### `Ordered.firstEntry`

```gizlang
function Ordered.firstEntry(self: Ordered): Option<OrderedEntry>
```

The first entry. A native tree reads it from its pages and pending edits, with no write of them, when its pending
removals of stored keys are its first stored keys (a free list that hands out its first slot); else it settles.

Effects: fail, read, write, console, io.

### `Ordered.prefixCount`

```gizlang
function Ordered.prefixCount(self: Ordered, prefix: bytes): i64
```

The number of keys that start with PREFIX.

Effects: fail, read, write, console, io.

### `Ordered.prefixValues`

```gizlang
function Ordered.prefixValues(self: Ordered, prefix: bytes): Vec<i64>
```

Materialize only the requested prefix, never unrelated entries.

Effects: fail, read, write, console, io.

### `Reader.orderedPosition`

```gizlang
function Reader.orderedPosition(self: mut Reader): OrderedPosition
```

The next position of a paged tree.

Effects: fail, read, write, console, io.

### `PagedOrdered.seekManyContext`

```gizlang
function PagedOrdered.seekManyContext(self: PagedOrdered, cache: mut PageCache, credits: mut ResourceContext, queries: Vec<bytes>): Result<Vec<Option<OrderedEntry>>, IoError>
```

For each of the ascending `queries`, the first entry at or above it, or none: one descent for
the whole batch that loads each page it touches once, instead of one root-to-leaf path per
query. A query above every key finds none (deep review §8: a commit's keys probe the root
per page, not per row).

Effects: fail, read, write, console, io.

### `PagedOrdered.rankContext`

```gizlang
function PagedOrdered.rankContext(self: PagedOrdered, cache: mut PageCache, credits: mut ResourceContext, key: bytes): Result<i64, IoError>
```

Exact lookup/rank touches one page per level and drops decoded parents immediately.

Effects: fail, read, write, console, io.

### `PagedOrdered.getContext`

```gizlang
function PagedOrdered.getContext(self: PagedOrdered, cache: mut PageCache, credits: mut ResourceContext, key: bytes): Result<Option<i64>, IoError>
```

The value of KEY, or none; reads are charged to CREDITS.

Effects: fail, read, write, console, io.

### `PagedOrdered.atRankContext`

```gizlang
function PagedOrdered.atRankContext(self: PagedOrdered, cache: mut PageCache, credits: mut ResourceContext, rank: i64): Result<Option<OrderedEntry>, IoError>
```

Select by the same checked subtree counts used by rank; no leaf directory
is loaded or reconstructed in RAM.

Effects: fail, read, write, console, io.

### `PagedOrdered.residentEntries`

```gizlang
function PagedOrdered.residentEntries(self: PagedOrdered, cache: mut PageCache, key: bytes, count: i64): Option<Vec<OrderedEntry>>
```

Up to `count` entries from the first key at or above `key`, read from resident decoded pages alone (PageCache.resident):
no pin, no grant and no cursor. None when a page on the path is not resident and decoded, or when the entries run
past their leaf; the caller then seeks with a cursor. Each child agrees with its parent's separator, and each node with
its link's level and count, as a cursor checks. An empty result means no key is at or above `key`.

Effects: fail, write.

### `PagedOrdered.residentAround`

```gizlang
function PagedOrdered.residentAround(self: PagedOrdered, cache: mut PageCache, key: bytes, end: bytes): Option<Vec<OrderedEntry>>
```

The last entry below KEY, then the entries at or above KEY and below END, from resident decoded pages alone (no pin,
grant or cursor). None when a page on the path is not resident and decoded, or when an entry may be in another leaf;
the caller then uses cursors. A write reads the spans it meets this way (Store.Spans.edit).

Effects: fail, write.

### `PagedOrdered.seekContext`

```gizlang
function PagedOrdered.seekContext(self: PagedOrdered, cache: mut PageCache, credits: mut ResourceContext, key: bytes): Result<OrderedCursor, IoError>
```

Cursor memory is one leaf plus a bounded path of physical ranges, never all leaf links.

Effects: fail, read, write, console, io.

### `PagedOrdered.beforeContext`

```gizlang
function PagedOrdered.beforeContext(self: PagedOrdered, cache: mut PageCache, credits: mut ResourceContext, key: Option<bytes>): Result<OrderedCursor, IoError>
```

The same checked traversal walks backwards, strictly below the optional upper cut.
No upper cut starts at the real final leaf; an empty tree still returns EOF.

Effects: fail, read, write, console, io.

### `OrderedCursor.nextContext`

```gizlang
function OrderedCursor.nextContext(self: mut OrderedCursor, cache: mut PageCache, credits: mut ResourceContext): Result<Option<OrderedEntry>, IoError>
```

The next entry, or none at the end; reads are charged to CREDITS.

Effects: fail, read, write, console, io.

### `OrderedCursor.nextManyContext`

```gizlang
function OrderedCursor.nextManyContext(self: mut OrderedCursor, cache: mut PageCache, credits: mut ResourceContext, limit: i64): Result<Vec<OrderedEntry>, IoError>
```

Up to `limit` next entries, in one call.

Effects: fail, read, write, console, io.

### `OrderedCursor.closeContext`

```gizlang
function OrderedCursor.closeContext(self: mut OrderedCursor, credits: mut ResourceContext): Result<bool, IoError>
```

Closes the cursor and gives back its charges.

Effects: fail, read, write, console, io.

### `PagedOrdered.putContext`

```gizlang
function PagedOrdered.putContext(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut ResourceContext, key: bytes, value: i64): Result<OrderedUpdate, IoError>
```

Path-copy mutation appends only affected pages. Prior roots stay valid for MVCC readers.
File/sync/WAL/root publication remain the caller's existing Store transaction contract.

Effects: fail, read, write, console, io.

### `PagedOrdered.removeContext`

```gizlang
function PagedOrdered.removeContext(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut ResourceContext, key: bytes): Result<OrderedUpdate, IoError>
```

The tree without KEY; reads are charged to CREDITS.

Effects: fail, read, write, console, io.

### `PagedOrdered.putSortedContext`

```gizlang
function PagedOrdered.putSortedContext(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut ResourceContext, entries: Vec<OrderedEntry>): Result<OrderedUpdate, IoError>
```

Puts strictly ascending entries in one merge: each touched page is copied once, not once per
key, and an existing key takes the new value. The caller bounds the batch (a commit chunk).

Effects: fail, read, write, console, io.

### `PagedOrdered.editContext`

```gizlang
function PagedOrdered.editContext(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut ResourceContext, edits: Vec<OrderedEdit>): Result<OrderedUpdate, IoError>
```

Puts and removes strictly ascending keys in one merge (a value puts its key, none removes it): each touched page is
copied once. StoredCatalog.editContext changes many rows this way.

Effects: fail, read, write, console, io.

### `PagedOrdered.replaceContext`

```gizlang
function PagedOrdered.replaceContext(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut ResourceContext, prior: bytes, target: bytes, value: i64): Result<OrderedUpdate, IoError>
```

Moves VALUE from key PRIOR to key TARGET (PRIOR !== TARGET) in one path copy when both are in one leaf. The update is fresh
when TARGET was absent, and keeps the tree's count when PRIOR was present. A catalog row whose value changes does this.

Effects: fail, read, write, console, io.

### `PagedOrdered.rank`

```gizlang
function PagedOrdered.rank(self: PagedOrdered, cache: mut PageCache, credits: mut Resources, key: bytes): Result<i64, IoError>
```

The number of keys less than KEY.

Effects: fail, read, write, console, io.

### `PagedOrdered.get`

```gizlang
function PagedOrdered.get(self: PagedOrdered, cache: mut PageCache, credits: mut Resources, key: bytes): Result<Option<i64>, IoError>
```

The value of KEY, or none.

Effects: fail, read, write, console, io.

### `PagedOrdered.seek`

```gizlang
function PagedOrdered.seek(self: PagedOrdered, cache: mut PageCache, credits: mut Resources, key: bytes): Result<OrderedCursor, IoError>
```

A cursor from the first key not less than KEY.

Effects: fail, read, write, console, io.

### `PagedOrdered.before`

```gizlang
function PagedOrdered.before(self: PagedOrdered, cache: mut PageCache, credits: mut Resources, key: Option<bytes>): Result<OrderedCursor, IoError>
```

A cursor in reverse from the last key less than KEY, or from the last key when KEY is none.

Effects: fail, read, write, console, io.

### `OrderedCursor.next`

```gizlang
function OrderedCursor.next(self: mut OrderedCursor, cache: mut PageCache, credits: mut Resources): Result<Option<OrderedEntry>, IoError>
```

The next entry, or none at the end.

Effects: fail, read, write, console, io.

### `OrderedCursor.close`

```gizlang
function OrderedCursor.close(self: mut OrderedCursor, credits: mut Resources): Result<bool, IoError>
```

Closes the cursor and gives back its charges.

Effects: fail, read, write, console, io.

### `PagedOrdered.put`

```gizlang
function PagedOrdered.put(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut Resources, key: bytes, value: i64): Result<OrderedUpdate, IoError>
```

The tree with KEY set to VALUE; new pages go to FILE.

Effects: fail, read, write, console, io.

### `PagedOrdered.remove`

```gizlang
function PagedOrdered.remove(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut Resources, key: bytes): Result<OrderedUpdate, IoError>
```

The tree without KEY; new pages go to FILE.

Effects: fail, read, write, console, io.

### `PagedOrdered.removeRangeContext`

```gizlang
function PagedOrdered.removeRangeContext(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut ResourceContext, start: bytes, end: bytes): Result<OrderedUpdate, IoError>
```

Delete [start,end) by copying boundary paths, with the same tail rollback,
cache invalidation and root contraction as point mutations.

Effects: fail, read, write, console, io.

## Constants

### `MIN_ORDERED_PAGE_BYTES`

```gizlang
const MIN_ORDERED_PAGE_BYTES = 128
```

The least page size of a paged ordered tree.

### `MAX_ORDERED_PAGE_BYTES`

```gizlang
const MAX_ORDERED_PAGE_BYTES = 1048576
```

The greatest page size of a paged ordered tree.

### `ORDERED_HEIGHT`

```gizlang
const ORDERED_HEIGHT = 64
```

The most levels of a paged tree.

### `ORDERED_HEAD`

```gizlang
const ORDERED_HEAD = 24
```

The bytes of the head of a page of a paged tree.

### `ORDERED_BRANCH_BYTES`

```gizlang
const ORDERED_BRANCH_BYTES = 32
```

The bytes of one branch of an inner page.

gizfs:ordered

An ordered map from byte strings to integers: a B+tree whose inner nodes keep each child's largest key and entry count, so seek, insert and delete cost O(log n) and rank queries too. Keys compare as bytes; callers encode what they order so that byte order is their order (the caller's value encoding). One structure serves retained roots, database ordered indexes and key-value sorted sets.

Nodes live in one pool and name each other by position. The pool is kept in pages of NP nodes: when a tree is shared with other threads' readers (an engine or storage snapshot), a write copies the pages it changes, not every node. Leaves are linked both ways for scans. A child's recorded largest key may be stale after a delete (larger than its real largest): it still bounds the child, so routing stays correct, and it is never smaller.

gizlang

import * as Ordered from "gizfs:ordered";

Types

`Ordered`

gizlang

type Ordered

An ordered map from byte keys to integers in memory (a B+ tree with counts, so rank and position are fast), or a view of a paged tree in a file.

pages: M39.DirectoryPages<Vec<M39.Node>>
used: i64
free: M39.DirectoryPages<i64>
root: i64
size: i64
weighted: bool
population: i64
directoryNodes: i64
directorySlots: i64
leafKeyCredit: i64
innerKeyCredit: i64
structuralCredit: i64
cold: Vec<M39.ColdPages>

`ColdPages`

gizlang

type ColdPages = { disk: Disk; path: string; end: Task.Atomic; cursor: i64; }

Where a tree's evicted leaf pages are (Ordered.evictLeaves): an append-only spill file, never rewritten, so every copy of the tree reads back the page version its directory names. The file is scratch: the WAL and segment files rebuild the tree at open, which removes it.

disk: M37.Disk
path: string
end: gizlang_task.Atomic
cursor: i64

`Pos`

gizlang

type Pos = { node: i64; at: i64; }

A position: an entry of a leaf, or past the end when node is -1.

node: i64
at: i64

`OrderedImage`

gizlang

type OrderedImage = { pages: PageDirectory<Vec<Node>>; used: i64; free: PageDirectory<i64>; root: i64; size: i64; weighted: bool; population: i64; directoryNodes: i64; directorySlots: i64; leafKeyCredit: i64; innerKeyCredit: i64; structuralCredit: i64; cold: Vec<ColdPages>; }

An Ordered with its pages in owned directories and no native owner, as a value with no Ref: it crosses threads (Task.cell), as a database's read view does.

pages: _gizlang_sdk_collections.PageDirectory<Vec<M39.Node>>
used: i64
free: _gizlang_sdk_collections.PageDirectory<i64>
root: i64
size: i64
weighted: bool
population: i64
directoryNodes: i64
directorySlots: i64
leafKeyCredit: i64
innerKeyCredit: i64
structuralCredit: i64
cold: Vec<M39.ColdPages>

`OrderedEntries`

gizlang

type OrderedEntries = { keys: Vec<bytes>; vals: Vec<i64>; }

Entries as two parallel lists: the keys and their values.

keys: Vec<bytes>
vals: Vec<i64>

`OrderedRun`

gizlang

type OrderedRun = { keys: Vec<bytes>; vals: Vec<i64>; past: Pos; }

Up to N entries from P on, toward the end or (DESC) the start, and the position past them.

keys: Vec<bytes>
vals: Vec<i64>
past: M39.Pos

`OrderedEntry`

gizlang

type OrderedEntry = { key: bytes; value: i64; }

A key and its value.

key: bytes
value: i64

`PagedOrdered`

gizlang

type PagedOrdered = { root: StoredPage; count: i64; height: i64; maxPageBytes: i64; }

A paged ordered tree in a file: its root page, its number of entries, its height and its greatest page size.

root: M37.StoredPage
count: i64
height: i64
maxPageBytes: i64

`OrderedPosition`

gizlang

type OrderedPosition = { root: PagePosition; count: i64; height: i64; maxPageBytes: i64; }

Where a paged tree is, as it is stored: the position of its root page and its size.

root: M37.PagePosition
count: i64
height: i64
maxPageBytes: i64

`OrderedPages`

gizlang

type OrderedPages = { tree: PagedOrdered; end: i64; }

A paged tree that a build made, and the end of its pages in the file.

tree: M39.PagedOrdered
end: i64

`OrderedCursor`

gizlang

type OrderedCursor = { tree: PagedOrdered; frames: Vec<OrderedFrame>; leaf: Option<OrderedNodeLease>; at: i64; descending: bool; lease: ResourceLease; closed: bool; }

A cursor over the entries of a paged tree, in key order or in reverse.

tree: M39.PagedOrdered
frames: Vec<M39.OrderedFrame>
leaf: _gizlang_sdk_core.Option<M39.OrderedNodeLease>
at: i64
descending: bool
lease: M37.ResourceLease
closed: bool

`OrderedUpdate`

gizlang

type OrderedUpdate = { tree: PagedOrdered; end: i64; changed: bool; fresh: bool; }

A paged tree after a change: its new tree, the end of its pages, and whether the change changed it and wrote new pages.

tree: M39.PagedOrdered
end: i64
changed: bool
fresh: bool

`OrderedEdit`

gizlang

type OrderedEdit = { key: bytes; value: Option<i64>; }

A change of one key: a new value, or none to remove it.

key: bytes
value: _gizlang_sdk_core.Option<i64>

Functions

`newOrdered`

gizlang

function newOrdered(): Ordered

An empty ordered map.

Effects: fail, read, write.

`newManagedOrdered`

gizlang

function newManagedOrdered(): Ordered

Ref-held metadata keeps node-page roots as identities; ordinary value trees retain their buffers under the ordinary allocation budget.

Effects: fail, read, write.

`orderedOfImage`

gizlang

function orderedOfImage(image: OrderedImage): Ordered

The ordered map of IMAGE.

Effects: fail.

`nativeOrdered`

gizlang

function nativeOrdered(owner: Ref<NativePages>): Result<Ordered, IoError>

Same ordered-map contract, with roots in the caller's common page owner.

Effects: fail, read, write, console, io.

`adoptOrdered`

gizlang

function adoptOrdered(owner: Ref<NativePages>, tree: PagedOrdered): Ordered

The ordered map that reads the paged tree TREE of OWNER.

Effects: fail, read, write.

`treeRoot`

gizlang

function treeRoot(tree: Ordered, written: bool): PagedOrdered

The root of the native TREE for a snapshot (WRITTEN: nativeRoot) or for its size (storedRoot).

Effects: fail, read, write, console, io.

`newWeightedOrdered`

gizlang

function newWeightedOrdered(): Ordered

Optional population/peak summaries share the same tree, page pool and mutations.

Effects: fail, read, write.

`orderedSorted`

gizlang

function orderedSorted(keys: Vec<bytes>, vals: Vec<i64>): Ordered

A tree of KEYS, strictly ascending, and their VALS, built bottom up: the leaves take the entries in order and each inner level their maxima, where putting them one by one descended the tree and split it for each key (a million-key rebuild was most of ADD PRIMARY KEY and of a large memtable flush).

Effects: fail, read, write, console, io.

`prefixEnd`

gizlang

function prefixEnd(prefix: bytes): Option<bytes>

The smallest key above every key that starts with prefix, or none when no key is (the prefix is all 0xFF): with seek, the end of a prefix range.

Effects: fail.

`formats`

gizlang

function formats(): Vec<Format>

The on-disk formats of this module. A test opens a committed store sample of every version.

Effects: fail.

`orderedPosition`

gizlang

function orderedPosition(tree: PagedOrdered): OrderedPosition

The stored position of TREE.

`bindOrdered`

gizlang

function bindOrdered(position: OrderedPosition, object: bytes, path: string): PagedOrdered

The paged tree at POSITION in OBJECT of the file at PATH.

`writeOrderedPosition`

gizlang

function writeOrderedPosition(out: mut bytes, position: OrderedPosition): void

Appends POSITION.

Effects: fail.

`buildOrderedPagesContext`

gizlang

function buildOrderedPagesContext(file: File, path: string, object: bytes, credits: mut ResourceContext, maxPageBytes: i64, pull: () => Result<Option<OrderedEntry>, IoError>): Result<OrderedPages, IoError>

Bounded bulk build from strictly ascending keys. The file must already be caller-owned staging storage; errors roll back its appended tail. Success does not sync or publish a root: the existing Engine checkpoint/WAL owner must do that before making it visible.

Effects: fail, read, write, console, io.

`buildOrderedPages`

gizlang

function buildOrderedPages(file: File, path: string, object: bytes, credits: mut Resources, maxPageBytes: i64, pull: () => Result<Option<OrderedEntry>, IoError>): Result<OrderedPages, IoError>

A paged tree of the entries that PULL gives in key order, written to FILE at PATH from the end of OBJECT. Pages are at most MAXPAGEBYTES.

Effects: fail, read, write, console, io.

Methods

`Ordered.evictLeaves`

gizlang

function Ordered.evictLeaves(self: mut Ordered, disk: Disk, path: string, bytes: i64): Result<i64, IoError>

Moves about bytes of leaf pages to the spill file, on from where the last eviction stopped, as LeanStore picks pages to cool without tracking each access; its bytes in memory left. A page with an inner node, the root's included, stays: a lookup then reads at most one page back.

Effects: fail, read, write, console, io.

`Ordered.residentBytes`

gizlang

function Ordered.residentBytes(self: Ordered): i64

The bytes of the tree's nodes held in memory (their reservations).

Effects: fail.

`Ordered.image`

gizlang

function Ordered.image(self: Ordered): Option<OrderedImage>

The image of the tree, or none for a managed or native one. It shares the tree's pages.

Effects: fail.

`Ordered.nativeRoot`

gizlang

function Ordered.nativeRoot(self: Ordered): Option<PagedOrdered>

The paged tree under the map, when the map reads one.

Effects: fail, read, write, console, io.

`Ordered.storedRoot`

gizlang

function Ordered.storedRoot(self: Ordered): Option<PagedOrdered>

The root of the pages of a native tree, without its pending edits. It encodes in as many bytes as the root that writes them (nativeRoot), so a size needs no write.

Effects: fail, read.

`Ordered.count`

gizlang

function Ordered.count(self: Ordered): i64

The number of entries.

`Ordered.recycledNodes`

gizlang

function Ordered.recycledNodes(self: Ordered): i64

Retained pool nodes available for reuse, independent of their page carrier.

Effects: fail.

`Ordered.weightCount`

gizlang

function Ordered.weightCount(self: Ordered): Option<i64>

The sum of the weights, when the map is weighted.

`Ordered.putWeight`

gizlang

function Ordered.putWeight(self: mut Ordered, key: bytes, weight: i64): Result<bool, string>

Sets the weight of KEY in a weighted map; true when KEY is new. It fails when the map is not weighted or WEIGHT is negative.

Effects: fail, read, write, console, io.

`Ordered.keyReservation`

gizlang

function Ordered.keyReservation(self: Ordered, includeLeaf: bool): i64

Reserved key-buffer credit, maintained only on touched nodes. Separator references always count.

Effects: fail.

`Ordered.reservation`

gizlang

function Ordered.reservation(self: Ordered, includeLeaf: bool): i64

Conservative single-version reservation: bounded node vectors, directories and key buffers. includeLeaf=false excludes only leaf keys already charged by a caller's canonical bag wire owner. It never excludes separator keys. Shared historical versions and allocator overhead are not measured.

Effects: fail.

`Ordered.entries`

gizlang

function Ordered.entries(self: Ordered): OrderedEntries

Every entry in key order, read a leaf at a time (first and next read a node for each entry).

Effects: fail, read, write, console, io.

`Ordered.putFresh`

gizlang

function Ordered.putFresh(self: mut Ordered, key: bytes, val: i64): bool

KEY, which the caller knows is not in the tree, put with VAL: a native tree reads no page to learn it.

Effects: fail, read, write, console, io.

`Ordered.removePresent`

gizlang

function Ordered.removePresent(self: mut Ordered, key: bytes): bool

KEY, which the caller knows is in the tree, removed: a native tree reads no page to learn it.

Effects: fail, read, write, console, io.

`Ordered.put`

gizlang

function Ordered.put(self: mut Ordered, key: bytes, val: i64): bool

Sets KEY to VAL; true when KEY is new.

Effects: fail, read, write, console, io.

`Ordered.swap`

gizlang

function Ordered.swap(self: mut Ordered, key: bytes, val: i64): Option<i64>

Puts KEY and gives the value it replaced, in one descent (a get, then a put, read the path twice).

Effects: fail, read, write, console, io.

`Ordered.remove`

gizlang

function Ordered.remove(self: mut Ordered, key: bytes): bool

Removes key; whether it was there. An emptied node leaves its parent; a root with one child gives way to it.

Effects: fail, read, write, console, io.

`Ordered.rekey`

gizlang

function Ordered.rekey(self: mut Ordered, oldKey: bytes, newKey: bytes, val: i64): Result<bool, string>

A key transfer uses one pool-page candidate, including both search paths. Collision checks precede all edits and leave diagnostics unchanged.

Effects: fail, read, write, console, io.

`Ordered.get`

gizlang

function Ordered.get(self: Ordered, key: bytes): Option<i64>

The value of key, or none.

Effects: fail, read, write, console, io.

`Ordered.seek`

gizlang

function Ordered.seek(self: Ordered, key: bytes): Pos

The first entry not below key.

Effects: fail, read, write, console, io.

`Ordered.first`

gizlang

function Ordered.first(self: Ordered): Pos

The position of the first entry.

Effects: fail, read, write, console, io.

`Ordered.last`

gizlang

function Ordered.last(self: Ordered): Pos

The position of the last entry.

Effects: fail, read, write, console, io.

`Ordered.next`

gizlang

function Ordered.next(self: Ordered, p: Pos): Pos

The position after P.

Effects: fail, read, write, console, io.

`Ordered.prev`

gizlang

function Ordered.prev(self: Ordered, p: Pos): Pos

The position before P.

Effects: fail, read, write, console, io.

`Ordered.keyAt`

gizlang

function Ordered.keyAt(self: Ordered, p: Pos): bytes

The key at P.

Effects: fail, read, write, console, io.

`Ordered.valAt`

gizlang

function Ordered.valAt(self: Ordered, p: Pos): i64

The value at P.

Effects: fail, read, write, console, io.

`Ordered.run`

gizlang

function Ordered.run(self: Ordered, p: Pos, desc: bool, n: i64): OrderedRun

OrderedRun read a leaf at a time: keyAt, valAt and next or prev read the node for each entry, and were half of a walk back through a district's orders.

Effects: fail, read, write, console, io.

`Ordered.before`

gizlang

function Ordered.before(self: Ordered, key: bytes): Pos

The last entry below key.

Effects: fail, read, write, console, io.

`Ordered.rank`

gizlang

function Ordered.rank(self: Ordered, key: bytes): i64

How many entries are below key.

Effects: fail, read, write, console, io.

`Ordered.atRank`

gizlang

function Ordered.atRank(self: Ordered, r0: i64): Pos

The entry of rank r (0-based), or past the end.

Effects: fail, read, write, console, io.

`Ordered.weightRank`

gizlang

function Ordered.weightRank(self: Ordered, key: bytes): Option<i64>

Payload population below key; ordinary maps have no weight summaries.

Effects: fail, read, write, console, io.

`Ordered.atWeight`

gizlang

function Ordered.atWeight(self: Ordered, rank: i64): Pos

Entry containing zero-based population rank; zero-weight entries contribute no positions.

Effects: fail, read, write, console, io.

`Ordered.peakWeight`

gizlang

function Ordered.peakWeight(self: Ordered): Option<i64>

Largest payload population; zero for an empty/zero-population weighted map.

Effects: fail, read, write, console, io.

`Ordered.atPeak`

gizlang

function Ordered.atPeak(self: Ordered, descending: bool): Pos

First/last key at the largest positive population, in bounded tree-height work.

Effects: fail, read, write, console, io.

`Ordered.firstEntry`

gizlang

function Ordered.firstEntry(self: Ordered): Option<OrderedEntry>

The first entry. A native tree reads it from its pages and pending edits, with no write of them, when its pending removals of stored keys are its first stored keys (a free list that hands out its first slot); else it settles.

Effects: fail, read, write, console, io.

`Ordered.prefixCount`

gizlang

function Ordered.prefixCount(self: Ordered, prefix: bytes): i64

The number of keys that start with PREFIX.

Effects: fail, read, write, console, io.

`Ordered.prefixValues`

gizlang

function Ordered.prefixValues(self: Ordered, prefix: bytes): Vec<i64>

Materialize only the requested prefix, never unrelated entries.

Effects: fail, read, write, console, io.

`Reader.orderedPosition`

gizlang

function Reader.orderedPosition(self: mut Reader): OrderedPosition

The next position of a paged tree.

Effects: fail, read, write, console, io.

`PagedOrdered.seekManyContext`

gizlang

function PagedOrdered.seekManyContext(self: PagedOrdered, cache: mut PageCache, credits: mut ResourceContext, queries: Vec<bytes>): Result<Vec<Option<OrderedEntry>>, IoError>

For each of the ascending queries, the first entry at or above it, or none: one descent for the whole batch that loads each page it touches once, instead of one root-to-leaf path per query. A query above every key finds none (deep review §8: a commit's keys probe the root per page, not per row).

Effects: fail, read, write, console, io.

`PagedOrdered.rankContext`

gizlang

function PagedOrdered.rankContext(self: PagedOrdered, cache: mut PageCache, credits: mut ResourceContext, key: bytes): Result<i64, IoError>

Exact lookup/rank touches one page per level and drops decoded parents immediately.

Effects: fail, read, write, console, io.

`PagedOrdered.getContext`

gizlang

function PagedOrdered.getContext(self: PagedOrdered, cache: mut PageCache, credits: mut ResourceContext, key: bytes): Result<Option<i64>, IoError>

The value of KEY, or none; reads are charged to CREDITS.

Effects: fail, read, write, console, io.

`PagedOrdered.atRankContext`

gizlang

function PagedOrdered.atRankContext(self: PagedOrdered, cache: mut PageCache, credits: mut ResourceContext, rank: i64): Result<Option<OrderedEntry>, IoError>

Select by the same checked subtree counts used by rank; no leaf directory is loaded or reconstructed in RAM.

Effects: fail, read, write, console, io.

`PagedOrdered.residentEntries`

gizlang

function PagedOrdered.residentEntries(self: PagedOrdered, cache: mut PageCache, key: bytes, count: i64): Option<Vec<OrderedEntry>>

Up to count entries from the first key at or above key, read from resident decoded pages alone (PageCache.resident): no pin, no grant and no cursor. None when a page on the path is not resident and decoded, or when the entries run past their leaf; the caller then seeks with a cursor. Each child agrees with its parent's separator, and each node with its link's level and count, as a cursor checks. An empty result means no key is at or above key.

Effects: fail, write.

`PagedOrdered.residentAround`

gizlang

function PagedOrdered.residentAround(self: PagedOrdered, cache: mut PageCache, key: bytes, end: bytes): Option<Vec<OrderedEntry>>

The last entry below KEY, then the entries at or above KEY and below END, from resident decoded pages alone (no pin, grant or cursor). None when a page on the path is not resident and decoded, or when an entry may be in another leaf; the caller then uses cursors. A write reads the spans it meets this way (Store.Spans.edit).

Effects: fail, write.

`PagedOrdered.seekContext`

gizlang

function PagedOrdered.seekContext(self: PagedOrdered, cache: mut PageCache, credits: mut ResourceContext, key: bytes): Result<OrderedCursor, IoError>

Cursor memory is one leaf plus a bounded path of physical ranges, never all leaf links.

Effects: fail, read, write, console, io.

`PagedOrdered.beforeContext`

gizlang

function PagedOrdered.beforeContext(self: PagedOrdered, cache: mut PageCache, credits: mut ResourceContext, key: Option<bytes>): Result<OrderedCursor, IoError>

The same checked traversal walks backwards, strictly below the optional upper cut. No upper cut starts at the real final leaf; an empty tree still returns EOF.

Effects: fail, read, write, console, io.

`OrderedCursor.nextContext`

gizlang

function OrderedCursor.nextContext(self: mut OrderedCursor, cache: mut PageCache, credits: mut ResourceContext): Result<Option<OrderedEntry>, IoError>

The next entry, or none at the end; reads are charged to CREDITS.

Effects: fail, read, write, console, io.

`OrderedCursor.nextManyContext`

gizlang

function OrderedCursor.nextManyContext(self: mut OrderedCursor, cache: mut PageCache, credits: mut ResourceContext, limit: i64): Result<Vec<OrderedEntry>, IoError>

Up to limit next entries, in one call.

Effects: fail, read, write, console, io.

`OrderedCursor.closeContext`

gizlang

function OrderedCursor.closeContext(self: mut OrderedCursor, credits: mut ResourceContext): Result<bool, IoError>

Closes the cursor and gives back its charges.

Effects: fail, read, write, console, io.

`PagedOrdered.putContext`

gizlang

function PagedOrdered.putContext(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut ResourceContext, key: bytes, value: i64): Result<OrderedUpdate, IoError>

Path-copy mutation appends only affected pages. Prior roots stay valid for MVCC readers. File/sync/WAL/root publication remain the caller's existing Store transaction contract.

Effects: fail, read, write, console, io.

`PagedOrdered.removeContext`

gizlang

function PagedOrdered.removeContext(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut ResourceContext, key: bytes): Result<OrderedUpdate, IoError>

The tree without KEY; reads are charged to CREDITS.

Effects: fail, read, write, console, io.

`PagedOrdered.putSortedContext`

gizlang

function PagedOrdered.putSortedContext(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut ResourceContext, entries: Vec<OrderedEntry>): Result<OrderedUpdate, IoError>

Puts strictly ascending entries in one merge: each touched page is copied once, not once per key, and an existing key takes the new value. The caller bounds the batch (a commit chunk).

Effects: fail, read, write, console, io.

`PagedOrdered.editContext`

gizlang

function PagedOrdered.editContext(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut ResourceContext, edits: Vec<OrderedEdit>): Result<OrderedUpdate, IoError>

Puts and removes strictly ascending keys in one merge (a value puts its key, none removes it): each touched page is copied once. StoredCatalog.editContext changes many rows this way.

Effects: fail, read, write, console, io.

`PagedOrdered.replaceContext`

gizlang

function PagedOrdered.replaceContext(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut ResourceContext, prior: bytes, target: bytes, value: i64): Result<OrderedUpdate, IoError>

Moves VALUE from key PRIOR to key TARGET (PRIOR !== TARGET) in one path copy when both are in one leaf. The update is fresh when TARGET was absent, and keeps the tree's count when PRIOR was present. A catalog row whose value changes does this.

Effects: fail, read, write, console, io.

`PagedOrdered.rank`

gizlang

function PagedOrdered.rank(self: PagedOrdered, cache: mut PageCache, credits: mut Resources, key: bytes): Result<i64, IoError>

The number of keys less than KEY.

Effects: fail, read, write, console, io.

`PagedOrdered.get`

gizlang

function PagedOrdered.get(self: PagedOrdered, cache: mut PageCache, credits: mut Resources, key: bytes): Result<Option<i64>, IoError>

The value of KEY, or none.

Effects: fail, read, write, console, io.

`PagedOrdered.seek`

gizlang

function PagedOrdered.seek(self: PagedOrdered, cache: mut PageCache, credits: mut Resources, key: bytes): Result<OrderedCursor, IoError>

A cursor from the first key not less than KEY.

Effects: fail, read, write, console, io.

`PagedOrdered.before`

gizlang

function PagedOrdered.before(self: PagedOrdered, cache: mut PageCache, credits: mut Resources, key: Option<bytes>): Result<OrderedCursor, IoError>

A cursor in reverse from the last key less than KEY, or from the last key when KEY is none.

Effects: fail, read, write, console, io.

`OrderedCursor.next`

gizlang

function OrderedCursor.next(self: mut OrderedCursor, cache: mut PageCache, credits: mut Resources): Result<Option<OrderedEntry>, IoError>

The next entry, or none at the end.

Effects: fail, read, write, console, io.

`OrderedCursor.close`

gizlang

function OrderedCursor.close(self: mut OrderedCursor, credits: mut Resources): Result<bool, IoError>

Closes the cursor and gives back its charges.

Effects: fail, read, write, console, io.

`PagedOrdered.put`

gizlang

function PagedOrdered.put(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut Resources, key: bytes, value: i64): Result<OrderedUpdate, IoError>

The tree with KEY set to VALUE; new pages go to FILE.

Effects: fail, read, write, console, io.

`PagedOrdered.remove`

gizlang

function PagedOrdered.remove(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut Resources, key: bytes): Result<OrderedUpdate, IoError>

The tree without KEY; new pages go to FILE.

Effects: fail, read, write, console, io.

`PagedOrdered.removeRangeContext`

gizlang

function PagedOrdered.removeRangeContext(self: PagedOrdered, file: File, cache: mut PageCache, credits: mut ResourceContext, start: bytes, end: bytes): Result<OrderedUpdate, IoError>

Delete [start,end) by copying boundary paths, with the same tail rollback, cache invalidation and root contraction as point mutations.

Effects: fail, read, write, console, io.

Constants

`MIN_ORDERED_PAGE_BYTES`

gizlang

const MIN_ORDERED_PAGE_BYTES = 128

The least page size of a paged ordered tree.

`MAX_ORDERED_PAGE_BYTES`

gizlang

const MAX_ORDERED_PAGE_BYTES = 1048576

The greatest page size of a paged ordered tree.

`ORDERED_HEIGHT`

gizlang

const ORDERED_HEIGHT = 64

The most levels of a paged tree.

`ORDERED_HEAD`

gizlang

const ORDERED_HEAD = 24

The bytes of the head of a page of a paged tree.

`ORDERED_BRANCH_BYTES`

gizlang

const ORDERED_BRANCH_BYTES = 32

The bytes of one branch of an inner page.