gizlang:collections

import * as Collections from "gizlang:collections";

Types

Key

interface Key { hash(self: Self): u64 effects { fail }; }

A Map or Set key: equal keys (===) have equal hashes. Scalars, strings and bytes are keys; a record becomes one by giving it hash.

• hash

Map

type Map<K, V>

Keys in insertion order with their values. _slots is an open-addressing table of entry index + 1 (0 empty). _live stays empty until the first deletion, then marks each entry; a deleted entry stays as a hole until the table next grows, when the entries are compacted.

Opaque: create and use it through this module's functions.

PageDirectory

type PageDirectory<T>

A directory of pages that it owns, addressed by index.

Opaque: create and use it through this module's functions.

ManagedPageDirectory

type ManagedPageDirectory<T>

A directory of pages that a manager owns, addressed by index.

Opaque: create and use it through this module's functions.

Set

type Set<K>

Keys in insertion order: a Map whose values are unused.

Opaque: create and use it through this module's functions.

HashTrieNode

type HashTrieNode = { bitmap: u64; kids: u64; hashes: Vec<u64>; vals: Vec<i64>; children: Vec<HashTrieNode>; }

A node: bitmap marks the slots that hold an entry (hash and location, in slot order), kids those that hold a child node (in slot order). A slot holds one or the other.

• bitmap: u64
• kids: u64
• hashes: Vec<u64>
• vals: Vec<i64>
• children: Vec<_gizlang_sdk_collections.HashTrieNode>

HashTrie

type HashTrie = { root: HashTrieNode; count: i64; }

A map from 64-bit hashes to locations: a trie of 32-way nodes, five hash bits a level.

• root: _gizlang_sdk_collections.HashTrieNode
• count: i64

HashEntry

type HashEntry = { hash: u64; loc: i64; }

A hash and its location.

• hash: u64
• loc: i64

Functions

sameItems

function sameItems<T>(a: Vec<T>, b: Vec<T>): bool

Whether a and b have the same length and equal items (===) in the same order.

some

function some<T, F extends(value: T) => bool>(values: Vec<T>, predicate: F): bool effects { predicate, fail }

Whether an item of VALUES meets PREDICATE.

concat

function concat<T>(a: Vec<T>, b: Vec<T>): Vec<T>

A followed by B.

indices

function indices(n: i64): Vec<i64>

The indices 0, 1, ..., N - 1.

Effects: fail.

includes

function includes<T>(values: Vec<T>, value: T): bool

Whether VALUES has an item equal to VALUE.

indexOf

function indexOf<T>(values: Vec<T>, value: T): i64

The index of the first item equal to VALUE, or -1.

at

function at<T>(values: Vec<T>, index: i64): Option<T>

The item at INDEX, counted from the end when it is negative (-1 is the last), or none.

pop

function pop<T>(values: mut Vec<T>): Option<T>

Removes the last item of VALUES and gives it, or none when VALUES is empty.

shift

function shift<T>(values: mut Vec<T>): Option<T>

Removes the first item of VALUES and gives it, or none when VALUES is empty.

every

function every<T, F extends(value: T) => bool>(values: Vec<T>, predicate: F): bool effects { predicate, fail }

Whether every item of VALUES meets PREDICATE.

count

function count<T, F extends(value: T) => bool>(values: Vec<T>, predicate: F): i64 effects { predicate, fail }

The number of items of VALUES that meet PREDICATE.

reduce

function reduce<T, A, F extends(accumulator: A, value: T) => A> (values: Vec<T>, combine: F, initial: A): A effects { combine, fail }

COMBINE applied to INITIAL and each item of VALUES in order.

findIndex

function findIndex<T, F extends(value: T) => bool> (values: Vec<T>, predicate: F): i64 effects { predicate, fail }

The index of the first value the predicate accepts, or -1.

filter

function filter<T, F extends(value: T) => bool> (values: Vec<T>, predicate: F): Vec<T> effects { predicate, fail }

The values the predicate accepts, in order.

toSorted

function toSorted<T, F extends(a: T, b: T) => bool>(values: Vec<T>, before: F): Vec<T> effects { before, fail }

The values ordered by before(a, b) (a goes first), keeping the order of values neither goes before: a copy sorted by sort, as TypeScript's toSorted. A comparator that returns a number ((a, b) => a - b) means before when the number is negative.

sorted

function sorted<T, F extends(a: T, b: T) => bool>(values: Vec<T>, before: F): Vec<T> effects { before, fail }

toSorted, by its former name: giz fmt writes toSorted.

sort

function sort<T, F extends(a: T, b: T) => bool>(values: mut Vec<T>, before: F): void effects { before, fail }

Sorts in place by before(a, b), preserving the order of ties. The typed adapter applies an index permutation; the ordering kernel never depends on the element representation. The original value stays immutable while the comparator runs.

newMap

function newMap<K extends Key, V>(entries: Vec<[K, V]> = []): Map<K, V>

A map of ENTRIES (new Map([["a", 1]])), empty by default; a later entry of a key replaces an earlier one.

newPageDirectory

function newPageDirectory<T>(): PageDirectory<T>

An empty page directory.

newManagedPageDirectory

function newManagedPageDirectory<T>(): ManagedPageDirectory<T>

Managed roots preserve local boxed snapshots; individual payload quotas still apply. Bulk owned data uses newPageDirectory without a managed heap.

pageDirectoryReservation

function pageDirectoryReservation(count: i64, slotBytes: i64): i64

Structural credit before constructing a directory of count entries.

Effects: fail.

newSet

function newSet<K extends Key>(items: Vec<K> = []): Set<K>

A set of ITEMS (new Set([1, 2])), empty by default.

newHashTrie

function newHashTrie(): HashTrie

An empty hash trie.

removeAt

function removeAt<T>(v: Vec<T>, at: i64): Vec<T>

V without the item at AT.

hashTrieOfSorted

function hashTrieOfSorted(hashes: Vec<u64>, locs: Vec<i64>): HashTrie

The trie of HASHES (ascending, none twice) and their LOCS, built at once: a node is made with its entries, as a restart rebuilds a table's hash primary (db/core/table.giz Table.reindexHashed); a put a key copied and shifted node vectors.

Effects: fail.

hashOrder

function hashOrder(hashes: Vec<u64>): Vec<i64>

The positions of HASHES in ascending hash order, equal hashes in their own order: a stable radix sort, 16 bits a pass.

Effects: fail.

find

function find<T, F extends(value: T) => bool> (values: Vec<T>, predicate: F): Option<T> effects { predicate, fail }

First matching value, or none. Unlike findIndex, no sentinel is exposed.

findLast

function findLast<T, F extends(value: T) => bool> (values: Vec<T>, predicate: F): Option<T> effects { predicate, fail }

The last value the predicate accepts, or none.

findLastIndex

function findLastIndex<T, F extends(value: T) => bool> (values: Vec<T>, predicate: F): i64 effects { predicate, fail }

The index of the last value the predicate accepts, or -1.

lastIndexOf

function lastIndexOf<T>(values: Vec<T>, value: T): i64

The index of the last item equal to VALUE, or -1.

flat

function flat<T>(values: Vec<Vec<T>>): Vec<T>

The items of each inner Vec, in order: TypeScript's flat() of one level.

flatMap

function flatMap<T, F extends(value: T) => Vec <_>> (values: Vec<T>, select: F): ReturnType<F> effects { select, fail }

The Vecs SELECT makes of each value, joined in order.

toReversed

function toReversed<T>(values: Vec<T>): Vec<T>

A copy in the opposite order.

reverse

function reverse<T>(values: mut Vec<T>): void

Reverses VALUES in place.

with

function with<T>(values: Vec<T>, index: i64, value: T): Vec<T>

A copy with the item at INDEX (from the end when negative) replaced by VALUE; INDEX must be in range.

toSpliced

function toSpliced<T>(values: Vec<T>, start: i64, count: i64, ...items: T[]): Vec<T>

A copy without COUNT items from START (from the end when negative) and with ITEMS there instead.

splice

function splice<T>(values: mut Vec<T>, start: i64, count: i64, ...items: T[]): Vec<T>

Removes COUNT items from START, puts ITEMS there and gives the removed items.

unshift

function unshift<T>(values: mut Vec<T>, ...items: T[]): i64

Puts ITEMS before the first item and gives the new length.

fill

function fill<T>(values: mut Vec<T>, value: T): void

Sets every item to VALUE.

values

function values<T>(values: Vec<T>): Vec<T>

The items of VALUES: a Vec spreads as a Set or a Map does ([...x] reads x.values()).

fromLength

function fromLength<F extends(item: i64, index: i64) => _>(length: i64, make: F): Vec<ReturnType<F>>

TypeScript's Array.from({ length }, make): make(i, i) for each index i from 0 to LENGTH less 1 (TypeScript passes undefined, then the index).

keys

function keys<T>(values: Vec<T>): Vec<i64>

The indexes of VALUES, 0 to its length less 1.

entries

function entries<T>(values: Vec<T>): Vec<[i64, T]>

Each index of VALUES with its item.

sumBy

function sumBy<T, F extends(value: T) => i64>(values: Vec<T>, select: F): i64 effects { select, fail }

Checked i64 sum of a projection.

Methods

i64.hash

function i64.hash(self: i64): u64

The key's hash.

Effects: fail.

u64.hash

function u64.hash(self: u64): u64

The key's hash.

Effects: fail.

bool.hash

function bool.hash(self: bool): u64

The key's hash.

Effects: fail.

string.hash

function string.hash(self: string): u64

Strings and bytes hash eight bytes at a time (wyhash's folded 128-bit product): a byte at a time serializes on the multiply.

Effects: fail.

bytes.hash

function bytes.hash(self: bytes): u64

The bytes' hash, eight bytes at a time (as string.hash).

Effects: fail.

Map.size

function Map.size<K extends Key, V>(self: Map<K, V>): i64

The number of entries.

Map.retainedBytes

function Map.retainedBytes<K extends Key, V>(self: Map<K, V>, keyBytes: i64, valueBytes: i64): i64

Retained array content bytes, including holes, live flags and hash slots. Supply the inline carrier widths of K and V. Referenced payloads, allocator headers, spare capacity and separately retained snapshots are not included. Invalid widths or overflow return the signed maximum to refuse admission.

Map.has

function Map.has<K extends Key, V>(self: Map<K, V>, key: K): bool

Whether KEY has an entry.

Map.get

function Map.get<K extends Key, V>(self: Map<K, V>, key: K): Option<V>

The value under KEY, or none.

Map.set

function Map.set<K extends Key, V>(self: mut Map<K, V>, key: K, value: V): bool

Sets the key's value; whether the key is new.

Map.merge

function Map.merge<K extends Key, V, F extends(old: V, value: V) => V> (self: mut Map<K, V>, key: K, value: V, combine: F): V effects { combine, fail }

The key's value becomes value when it is absent, else combine(old, value) (Java's Map.merge; counts.merge(word, 1, add) counts); the new value.

Map.delete

function Map.delete<K extends Key, V>(self: mut Map<K, V>, key: K): bool

Removes the key; whether it was there.

Map.pick

function Map.pick<K extends Key, V>(self: Map<K, V>, seed: u64): Option<K>

A key chosen by seed (a random number gives a random key: Redis's SPOP and RANDOMKEY), or none when empty. Expected O(1): holes never exceed entries.

Map.keys

function Map.keys<K extends Key, V>(self: Map<K, V>): Vec<K>

The keys, values and entries in insertion order.

Map.values

function Map.values<K extends Key, V>(self: Map<K, V>): Vec<V>

The values in insertion order.

Map.entries

function Map.entries<K extends Key, V>(self: Map<K, V>): Vec<[K, V]>

The entries as [key, value] pairs in insertion order: what a for...of over a Map gives, as in TypeScript.

Map.visit

function Map.visit<K extends Key, V, T, F>(self: Map<K, V>, context: mut T, visit: F): void effects { visit, fail }

Visits live entries in insertion order without constructing a keys/values vector. The map is an immutable value for the visit; the callback receives its mutable accumulator explicitly and can change a separate map value.

Map.visitRetained

function Map.visitRetained<K extends Key, V, T, F>(self: Map<K, V>, context: mut T, visit: F): void effects { visit, fail }

Visits every physically retained key/value, including deleted slots awaiting compaction. Resource admission uses this view rather than logical size; no filtered vectors or map copies are created.

PageDirectory.count

function PageDirectory.count<T>(self: PageDirectory<T>): i64

The number of entries.

ManagedPageDirectory.count

function ManagedPageDirectory.count<T>(self: ManagedPageDirectory<T>): i64

The number of entries.

PageDirectory.capacity

function PageDirectory.capacity<T>(self: PageDirectory<T>): i64

The number of entries that the directory holds without growing.

ManagedPageDirectory.capacity

function ManagedPageDirectory.capacity<T>(self: ManagedPageDirectory<T>): i64

The number of entries that the directory holds without growing.

PageDirectory.reservation

function PageDirectory.reservation<T>(self: PageDirectory<T>, slotBytes: i64): i64

The bytes that the directory structure takes for its entries, with SLOTBYTES for each slot (pageDirectoryReservation).

ManagedPageDirectory.reservation

function ManagedPageDirectory.reservation<T>(self: ManagedPageDirectory<T>, slotBytes: i64): i64

The bytes that the directory structure takes for its entries, with SLOTBYTES for each slot (pageDirectoryReservation).

PageDirectory.get

function PageDirectory.get<T>(self: PageDirectory<T>, at: i64): Option<T>

The entry at AT, or none when AT is out of range.

ManagedPageDirectory.get

function ManagedPageDirectory.get<T>(self: ManagedPageDirectory<T>, at: i64): Option<T>

The entry at AT, or none when AT is out of range.

PageDirectory.set

function PageDirectory.set<T>(self: mut PageDirectory<T>, at: i64, value: T): bool

Replaces the entry at AT with VALUE; false when AT is out of range.

ManagedPageDirectory.set

function ManagedPageDirectory.set<T>(self: mut ManagedPageDirectory<T>, at: i64, value: T): bool

Replaces the entry at AT with VALUE; false when AT is out of range.

PageDirectory.append

function PageDirectory.append<T>(self: mut PageDirectory<T>, value: T): i64 throws string

Adds VALUE at the end; its index. It fails when the directory is full.

ManagedPageDirectory.append

function ManagedPageDirectory.append<T>(self: mut ManagedPageDirectory<T>, value: T): i64 throws string

Adds VALUE at the end; its index. It fails when the directory is full.

PageDirectory.pop

function PageDirectory.pop<T>(self: mut PageDirectory<T>): Option<T>

Removes the last entry and gives it, or none when the directory is empty.

ManagedPageDirectory.pop

function ManagedPageDirectory.pop<T>(self: mut ManagedPageDirectory<T>): Option<T>

Removes the last entry and gives it, or none when the directory is empty.

PageDirectory.pathWork

function PageDirectory.pathWork<T>(self: PageDirectory<T>): Vec<i64>

The directory nodes and the slots that the writes copied so far: logical work, not malloc or RSS.

ManagedPageDirectory.pathWork

function ManagedPageDirectory.pathWork<T>(self: ManagedPageDirectory<T>): Vec<i64>

The directory nodes and the slots that the writes copied so far: logical work, not malloc or RSS.

Set.size

function Set.size<K extends Key>(self: Set<K>): i64

The number of keys.

Set.has

function Set.has<K extends Key>(self: Set<K>, key: K): bool

Whether the set holds KEY.

Set.add

function Set.add<K extends Key>(self: mut Set<K>, key: K): bool

Adds the key; whether it is new.

Set.delete

function Set.delete<K extends Key>(self: mut Set<K>, key: K): bool

Removes the key; whether it was there.

Set.pick

function Set.pick<K extends Key>(self: Set<K>, seed: u64): Option<K>

A key chosen by SEED (as Map.pick), or none when empty.

Set.values

function Set.values<K extends Key>(self: Set<K>): Vec<K>

The keys in insertion order.

HashTrie.get

function HashTrie.get(self: HashTrie, hash: u64): Option<i64>

The location of HASH, or none.

Effects: fail.

HashTrie.put

function HashTrie.put(self: mut HashTrie, hash: u64, loc: i64): Option<i64>

Puts HASH at LOC; the location it had, or none.

Effects: fail.

HashTrie.remove

function HashTrie.remove(self: mut HashTrie, hash: u64): bool

Removes HASH; whether it was there. A child left empty goes.

Effects: fail.

HashTrie.ceiling

function HashTrie.ceiling(self: HashTrie, hash: u64): Option<HashEntry>

The entry of the least hash at or above HASH, or none.

Effects: fail.

HashTrie.entries

function HashTrie.entries(self: HashTrie): Vec<HashEntry>

Every entry, in hash order.

Effects: fail.

HashTrie.residentBytes

function HashTrie.residentBytes(self: HashTrie): i64

The bytes the trie holds, counted from its entries (a node a few entries): for the memory budget.

Effects: fail.

Constants

HASH_COLLIDED

const HASH_COLLIDED: i64 = -2

The location of a hash whose keys the caller keeps apart.