Containers

Vector, HashMap, HashSet, slices and the Hash interface.

Contents

Hash

interface Hash

The requirements for a {K: V} / {T} key: a hash and an equality consistent with it.

If a == b then a.hash() == b.hash(). Hashes are deterministic: no per-process seed, so a map's layout is the same on every run. The primitives, pointers and string conform out of the box; a key type conforms like any type conforms to an interface (its own members, an extend X impl Hash, or structurally). other is const, so comparing two keys copies neither.

Hash.hash

fn hash(const self) -> usize

Returns the key's hash, to be folded into a table slot by the container.

Hash.op ==

fn op ==(const self, const other: Self) -> bool

Returns true when the keys are equal; must agree with hash.

fold_mul

inline fn fold_mul(a: u64, b: u64) -> u64

The 128-bit product of a and b, its high and low halves xored: the folded multiply every mix below is made of. One mul where the target has a 64x64->128 multiply; four 32x32 products elsewhere.

to_usize

inline fn to_usize(h: u64) -> usize

A 64-bit hash as a usize: itself on a 64-bit target, folded on a 32-bit one.

mix64

inline fn mix64(x: u64) -> u64

The integer mix: a full-avalanche hash of 64 bits.

hash_bytes

inline fn hash_bytes(p: unsafe *const u8, len: usize) -> u64

rapidhash (v1) of the len bytes at p.

hash_bytes_seeded

fn hash_bytes_seeded(p: unsafe *const u8, len: usize, seed: u64) -> u64

rapidhash (v1) of the len bytes at p, seeded with seed. (No default argument: a defaulted call goes through an out-of-line thunk.)

Hash implementations for primitives

Each primitive type implements Hash as follows.

extend string impl Hash

extend string impl Hash

A string hashes its bytes with hash_bytes (rapidhash v1).

string.hash

inline fn hash(const self) -> usize

Returns the key's hash, to be folded into a table slot by the container.

HASH_NPOS

eval HASH_NPOS: usize

The "not found" result of an entry-index lookup. Never a valid entry index.

HASH_MIN_CAP

eval HASH_MIN_CAP: usize

The smallest entry capacity a table is created with (8).

tag_of

inline fn tag_of(h: usize) -> u32

Returns the slot tag of hash h: the high 32 bits of h * 0x9e3779b97f4a7c15 (Fibonacci hashing). Mixing makes the table robust against weak hash() implementations.

slot_word

inline fn slot_word(t: u32, e: usize) -> u64

Packs tag t and entry index e into a slot word (tag in the high 32 bits, index + 1 in the low).

slot_entry

inline fn slot_entry(s: u64) -> usize

Returns the entry index a non-empty slot word names (the low half minus 1).

slot_tag

inline fn slot_tag(s: u64) -> u32

Returns the tag stored in a slot word.

shift_for

inline fn shift_for(nslots: usize) -> u32

Returns the shift that maps a tag to its home slot in a table of nslots slots (a power of two): 32 - log2(nslots).

block_bytes

inline fn block_bytes(cap: usize, esize: usize) -> usize

Returns the byte size of a table block: 2 * cap 8-byte slots followed by cap entries of esize bytes.

Panics

when the size overflows (traps).

block_align

inline fn block_align(ealign: usize) -> usize

Returns the alignment of a table block: 8, or ealign when the entries need more.

block_alloc

fn block_alloc(cap: usize, esize: usize, ealign: usize) -> unsafe *u8

Allocates a table block for cap entries of esize bytes from the allocator in effect, with the slots zeroed and the entries uninitialized. Runs the OOM hook on failure.

block_free

inline fn block_free(b: unsafe *u8, cap: usize, esize: usize, ealign: usize)

Frees a block from block_alloc; a no-op when cap is 0 (the empty block is not allocated).

block_empty

inline fn block_empty(ealign: usize) -> unsafe *u8

Returns the block of an empty table: no allocation, but a non-null pointer aligned for the entries.

block_slots

inline fn block_slots(b: unsafe *u8) -> unsafe *u64

Returns the slot array of a block (its first 2 * cap words).

block_entries

inline fn block_entries(b: unsafe *u8, cap: usize) -> unsafe *u8

Returns the entry array of a block: the bytes after its 2 * cap slots.

empty_slot

inline fn empty_slot(slots: unsafe *u64, mask: usize, shift: u32, t: u32) -> usize

Returns the first empty slot on the probe sequence for tag t (linear probing from the home slot). The table is never full, so this terminates.

rebuild

fn rebuild(slots: unsafe *u64, mask: usize, shift: u32, old: unsafe *u64, old_n: usize)

Re-places every occupied slot of old (old_n slots) into the zeroed table slots, using the new mask and shift. Entry indices are unchanged and no key is rehashed.

slot_of_entry

inline fn slot_of_entry(slots: unsafe *u64, mask: usize, shift: u32, t: u32, e: usize) -> usize

Returns the index of the slot that holds entry e (whose tag is t). The slot must exist.

remove_slot

fn remove_slot(slots: unsafe *u64, mask: usize, shift: u32, i: usize)

Empties slot i and closes the gap by backward-shifting later slots of the cluster (no tombstones are ever left).

shift_down_after

fn shift_down_after(slots: unsafe *u64, nslots: usize, e: usize)

After the entries above index e moved down by one (an order-preserving erase), decrements every slot that names an index greater than e. O(nslots).

grown_cap

inline fn grown_cap(cap: usize, want: usize) -> usize

Returns the entry capacity to grow to from cap so that want entries fit: 8 from empty, otherwise doubled until want fits.

Panics

when the result would exceed 2^31 entries (traps): slots hold 32-bit indices.

relocate_entry

inline fn <E> relocate_entry(dst: unsafe *u8, src: unsafe *E)

Moves the entry at src to the uninitialized dst, leaving src's storage uninitialized: a byte copy when E is trivially relocatable, else a copy-construct plus destroy.

MapEntry

class <K, V> MapEntry

One key and its value, as a HashMap stores and iterates them (m.find(k), m.begin(), m.entries()).

No constructor: it is a C++ aggregate built in place as MapEntry(k, v) or MapEntry(k).

MapEntry.key

var key: K

The entry's key. Do not change it through a pointer from the map: the index is keyed on it.

MapEntry.value

var value: V

The entry's value. May be assigned through a pointer from find / begin / entries.

HashMap

class <K impl Hash, V> HashMap

Hash map from K to V. {K: V} desugars to HashMap<K, V>, and {k: v, ...} builds one.

Entries are stored densely in insertion order, so iteration order is deterministic. Lookup, insert and erase are O(1) expected; erase_ordered is O(n). K must implement Hash (a hash() method and ==).

Inserting or erasing invalidates every pointer from find / get / begin / [] and must not happen during for ... in m. A copy is a deep copy.

Example

var m: {i32: i32} = {}
m[1] = 10
m.insert(2, 20)
var found = false
if let v = m.get(2) { found = (*v == 20) }

See also

HashSet

HashMap.HashMap

inline fn HashMap(self)

Creates an empty map. Allocates nothing.

HashMap.HashMap

fn HashMap(self, const items: [(K, V);])

Creates a map from (key, value) pairs, as {k: v, ...} lowers to.

Entries keep written order; a repeated key keeps its first place and takes its last value. V must be default-constructible (each value is assigned after the entry is created).

HashSet

class <T impl Hash> HashSet

Hash set of T. {T} desugars to HashSet<T>, and {a, b, ...} builds one.

Elements are stored densely in insertion order, so iteration order is deterministic. insert, contains and erase are O(1) expected. T must implement Hash. The mutation and invalidation rules are HashMap's: do not insert or erase during iteration.

Example

var s: {i32} = {1, 2, 3}
s.insert(2)
var n = s.size()

See also

HashMap

HashSet.HashSet

inline fn HashSet(self)

Creates an empty set. Allocates nothing.

HashSet.HashSet

fn HashSet(self, const items: [T;])

Creates a set from items, as {a, b, ...} lowers to. Elements keep written order; a repeated element keeps its first place.

Slice

struct <T> Slice

A non-owning view over len contiguous elements. [T;] is Slice<T>, and a [...] literal takes this type against a [T;] target. A [T] converts to it implicitly, with nothing copied.

The view does not keep its elements alive and does not own them; it is a pointer and a length.

See also

Vector

Slice.op []

inline fn op [] (const self, i: usize) -> *T

Returns the element at index i as a place, so s[i] = x assigns through the view.

Notes

This operator does no bounds check of its own (it indexes the pointer); Vector's [] does.

Slice.op []

inline fn op [] (const self, r: Range<usize>) -> [T;]

Returns the sub-view s[a..b] or s[a..=b]. A view: nothing is copied. O(1).

Panics

when a > b or the end is past len (traps; for a..=b, b >= len).

Slice.op []

inline fn op [] (const self, r: RangeFrom<usize>) -> [T;]

Returns the sub-view s[a..]; s[..] is the whole view. O(1).

Panics

when a > len (traps).

Slice.op []

inline fn op [] (const self, r: RangeTo<usize>) -> [T;]

Returns the sub-view s[..b] or s[..=b]. O(1).

Panics

when the end is past len (traps; for ..=b, b >= len).

Vector

class <T> Vector

Growable, owning, contiguous array. [T] desugars to Vector<T>, and the list literal [a, b, c] against a [T] target builds one.

Elements live in one heap block from the allocator in effect. Indexing, front, back and pop_back check bounds and trap (see \panics on each); growth is geometric (twice the capacity, at least 4), so push_back is O(1) amortized. A copy is a deep copy; a [MoveOnly] has no copy and no Vector(n) / resize(n, value) (those members need T to be copyable / default-constructible).

References and pointers into a vector (v[i], begin(), data()) are invalidated by any operation that grows, inserts, erases or clears.

Example

var v: [i32] = [1, 2, 3]
v.push(4)
var sum: i32 = 0
for x in v { sum += x }

See also

Slice

Vector.Vector

inline fn Vector(self)

Empty, no storage. Creates an empty vector. Allocates nothing; capacity() is 0.

Vector.Vector

fn Vector(self, const items: [T;]) requires __builtin_is_constructible<T, const T>()

Creates a vector holding a copy of every element of items.

This is what [a, b, c] lowers to against a [T] target, and what s as [T] calls. O(n).

Vector.Vector

fn Vector(self, n: usize) requires __builtin_is_default_constructible<T>()

Creates a vector of n default-constructed elements, with capacity exactly n. O(n).

Only available when T is default-constructible.

Vector.op []

inline fn op [] (self, i: usize) -> *T

Returns the element at index i as a place, so v[i] = x assigns.

Panics

when i >= size() (traps; no message).

Vector.op []

inline fn op [] (const self, i: usize) -> *const T

Returns the element at index i through a const vector.

Panics

when i >= size() (traps; no message).

Vector.size

inline fn size(const self) -> usize

Returns the number of live elements. O(1).

Vector.empty

inline fn empty(const self) -> bool

Returns true when the vector holds no elements. O(1).

Vector.capacity

inline fn capacity(const self) -> usize

Returns how many elements fit before the next reallocation. O(1).

Vector.data

inline fn data(const self) -> *T

Returns a pointer to the first element (never null: a dangling, aligned pointer while the vector has no storage).

One accessor for const and mutable receivers alike: it returns a mutable *T even from a const self.

Vector.begin

inline fn begin(const self) -> *T

Returns a pointer to the first element; equal to end() when empty.

Together with end() this is the pointer pair insert / erase positions are spelled in.

Vector.end

inline fn end(const self) -> *T

Returns a pointer one past the last element. Not dereferenceable.

Vector.front

inline fn front(const self) -> *T

Returns a pointer to the first element.

Panics

when the vector is empty (traps).

Vector.back

inline fn back(const self) -> *T

Returns a pointer to the last element.

Panics

when the vector is empty (traps).

Vector.op in

fn op in (const self) -> yield T

Iterates the elements in order: for x in v / for *x in v.

for x in v binds each element as a value; for *x in v binds a pointer to the element itself, so it can be modified. Do not grow or erase while iterating.

Vector.push_back

inline fn push_back(self, v: T)

Appends v to the end. O(1) amortized; reallocates when full.

v is taken by value, so it stays valid across the growth (v.push_back(v[0]) is fine). A copyable lvalue is copied, a MOVE value is moved.

Vector.push

inline fn push(self, v: T)

push_back under the name collections.mdx documents. Appends v to the end; the name collections documents for push_back. Same cost.

Vector.emplace_back

inline fn <...A> emplace_back(self, ...args: A) -> *T

Appends a T constructed in place from args and returns a pointer to it. O(1) amortized.

On growth the new element is built in the new block before the old ones move, so an argument that refers into this vector is still valid when read.

Vector.insert

fn insert(self, pos: *T, v: T) -> *T

Inserts v before pos and returns a pointer to the new element. O(n): later elements shift up one slot.

Parameters

• pos: a pointer in [begin(), end()]; end() appends.

Panics

when pos is outside that range (traps).

Vector.pop_back

inline fn pop_back(self)

Destroys the last element. O(1).

Panics

when the vector is empty (traps).

Vector.clear

inline fn clear(self)

Destroys every element and sets the size to 0. Keeps the storage. O(n), O(1) for trivial T.

Vector.erase

fn erase(self, pos: *T) -> *T

Removes the element at pos and returns a pointer to the element that followed it (now at pos). O(n): later elements shift down one slot.

Panics

when pos is not in [begin(), end()) (traps).

Vector.erase

fn erase(self, first: *T, last: *T) -> *T

Removes the elements in [first, last) and returns a pointer to the element that followed them. O(n). An empty range removes nothing.

Panics

when first > last or last > end() (traps).

Vector.reserve

inline fn reserve(self, n: usize)

Ensures capacity for at least n elements. Never shrinks. O(size()) when it reallocates.

Vector.resize

fn resize(self, n: usize) requires __builtin_is_default_constructible<T>()

Resizes to n elements: destroys the tail, or appends default-constructed elements.

Only available when T is default-constructible. O(|n - size()|).

Vector.resize

fn resize(self, n: usize, const value: T) requires __builtin_is_constructible<T, const T>()

Resizes to n elements: destroys the tail, or appends copies of value.

value may be an element of this vector. Only available when T is copyable.

Generated from Kairo source, Apache-2.0 WITH AdditionRef-Kairo-Runtime-exception.