std.map

An open-addressed hash table with linear probing and tombstones. The map owns its keys and values, so Map[u64, Vec[u8]] is ordinary. A borrow cannot be returned, so a lookup answers with a position rather than the value, in one of three forms. find gives the raw slot index, which the caller reads as m.vals[slot], good until the next insert or remove. slot gives a Slot that resolve checks again later: once its key is removed or the map rehashes, it resolves to None, never to another entry. update lends the value to a closure, which cannot reach the map while it holds it. get copies a copyable value out. A map keyed by Vecs is also looked up by a view of the elements (find_view, entry_view), and sorted walks the keys in order. Cost: expected O(1) per operation; insert reallocates and rehashes past three quarters full, so alloc, free and zero_init appear in every caller's row.

// Counts the words of standard input: printf 'b a b' | cairn run count.cairn prints a 1, then b 2.
import std.core (Result);
import std.io as io;
import std.map (Map);
import std.text as text;
import std.vec (Vec);

fn main() -> i32 {
  let mut input = vec.new[u8]();
  match io.read_stdin_to_end(input) { Ok(_) => {} Err(_) => return 1; }
  let mut counts = map.new[Vec[u8], u64]();
  let mut w = text.cursor();
  while text.next_word(input, w) {
    let at = map.entry_view(counts, input.data[w.lo..w.hi], 0);   // copies a word the first time only
    counts.vals[at] += 1;
  }
  let mut order = vec.new[usize]();
  map.sorted(counts, order);                                        // the live slots, words ascending
  for s in order { println(counts.keys[s], ' ', counts.vals[s]); }
  return 0;
}

// state: 0 never used, 1 live, 2 erased. An erased slot still routes probes past it. A live slot's stamp is how many
// keys had been placed when its own key was, so no two entries ever share one, across removals and rehashing alike, and
// a zeroed stamp names nothing.
pub struct Map[K:affine, V:affine] { keys:Buf[K]; vals:Buf[V]; state:Buf[u8]; stamps:Buf[u64]; count:usize; fill:usize; placed:u64; }

// A position that remembers which entry it named.
pub struct Slot { at:usize; stamp:u64; }

pub fn new[K:affine, V:affine]() -> Map[K, V]  // effects: alloc, free, trap, zero_init
pub fn count[K:affine, V:affine](m:ro<Map[K, V]>) -> usize  // effects: read:m
pub fn slots[K:affine, V:affine](m:ro<Map[K, V]>) -> usize  // effects: read:m
pub fn live[K:affine, V:affine](m:ro<Map[K, V]>, slot:usize) -> bool  // effects: read:m, trap

// effects: alloc, diverge, ffi_precondition, free, local_read, local_write, read:m, stack_storage, trap, write:m,
// zero_init
pub fn insert[K:Hash + Eq + affine, V:affine](m:rw<Map[K, V]>, key:K, value:V)

// effects: diverge, ffi_precondition, local_read, local_write, read:key, read:m, stack_storage, trap, zero_init
pub fn find[K:Hash + Eq + affine, V:affine](m:ro<Map[K, V]>, key:ro<K>) -> Option[usize]

// find for a map keyed by Vecs, by a view of the elements the key holds: a word looks itself up where it lies in the
// input, and no Vec is made for it. Cost: one hash of the view and a comparison per key probed.
// effects: diverge, ffi_precondition, local_read, local_write, read:key, read:m, stack_storage, trap, zero_init
pub fn find_view[T:Hash + Eq + copy, V:affine](m:ro<Map[Vec[T], V]>, n:usize, key:ro<T>[n]@host) -> Option[usize]

// The slot of `key`'s entry, inserting `key` with `value` first when there is none; a key or value not needed is
// released. `let at = map.entry(m, key, 0); m.vals[at] += 1;` counts. Good until the next insert.
// effects: alloc, diverge, ffi_precondition, free, local_read, local_write, read:m, stack_storage, trap, write:m,
// zero_init
pub fn entry[K:Hash + Eq + affine, V:affine](m:rw<Map[K, V]>, key:K, value:V) -> usize

// entry for a map keyed by Vecs, by a view: the key is copied into a Vec of its own only when it is inserted, which is
// the one allocation beside the map's own growth.
// effects: alloc, diverge, ffi_precondition, free, local_read, local_write, read:key, read:m, stack_storage, trap,
// write:m, zero_init
pub fn entry_view[T:Hash + Eq + copy, V:affine](m:rw<Map[Vec[T], V]>, n:usize, key:ro<T>[n]@host, value:V) -> usize

// Every live slot appended to `out`, in the order of the keys: the walk a report prints. Cost: one pass over the slots
// and a heapsort of the live ones, O(k log k) comparisons of keys.
// effects: alloc, diverge, ffi_precondition, free, indirect_call, local_read, local_write, read:m, read:out,
// stack_storage, trap, write:out, zero_init
pub fn sorted[K:Ord + affine, V:affine](m:ro<Map[K, V]>, out:rw<Vec[usize]>)

// The entry holding `key` as a Slot, which stays checkable across inserts, removes and growth.
// effects: diverge, ffi_precondition, local_read, local_write, read:key, read:m, stack_storage, trap, zero_init
pub fn slot[K:Hash + Eq + affine, V:affine](m:ro<Map[K, V]>, key:ro<K>) -> Option[Slot]

// Where the entry `s` named is now: None once its key was removed or the map rehashed, when the key has to be looked up
// again. A stale Slot is never taken for another entry of the map that gave it; against another map a Slot is only a
// number, since every map counts its stamps from zero.
pub fn resolve[K:affine, V:affine](m:ro<Map[K, V]>, s:Slot) -> Option[usize]  // effects: read:m, trap

// A copy of the value under `key`.
// effects: diverge, ffi_precondition, local_read, local_write, read:key, read:m, stack_storage, trap, zero_init
pub fn get[K:Hash + Eq + affine, V:copy](m:ro<Map[K, V]>, key:ro<K>) -> Option[V]

// Change the value under `key` in place, or answer false when it is absent. The closure is lent the value alone, and
// the map is lent to this call, so nothing the closure does can move the entry.
// effects: diverge, ffi_precondition, indirect_call, local_read, local_write, read:key, read:m, stack_storage, trap,
// write:m, zero_init
pub fn update[K:Hash + Eq + affine, V:affine](m:rw<Map[K, V]>, key:ro<K>, change:ro<fn(rw<V>)>) -> bool

// effects: diverge, ffi_precondition, local_read, local_write, read:key, read:m, stack_storage, trap, zero_init
pub fn contains[K:Hash + Eq + affine, V:affine](m:ro<Map[K, V]>, key:ro<K>) -> bool

// effects: diverge, ffi_precondition, free, local_read, local_write, read:key, read:m, stack_storage, trap, write:m,
// zero_init
pub fn remove[K:Hash + Eq + affine, V:affine](m:rw<Map[K, V]>, key:ro<K>) -> Option[V]

A generic function's effects are what it may do for any arguments within its bounds, besides what their own trait members do.