std.map

Reed's standard library. Imported with use std.map; not on disk.

Functions

int_mapAn empty IntMap.
int_map_with_capacityAn empty IntMap with room for capacity entries before the first rehash.
slot_count_forThe power-of-two slot count that holds capacity entries under the 75% load factor.
hash_intMixes an i32 into a well-distributed hash.
str_mapAn empty StrMap.

int_map #

line 74 
func int_map() -> &IntMap

An empty IntMap.

Returns
a new empty map
See also
int_map_with_capacity
Source 
func int_map() -> &IntMap {
  return int_map_with_capacity(16);
}

int_map_with_capacity #

line 85 
func int_map_with_capacity(capacity: i32) -> &IntMap

An empty IntMap with room for capacity entries before the first rehash.

The backing arrays are rounded up to a power of two at least twice capacity, so a map built with the eventual size never rehashes.

Parameters
capacity — how many entries to plan for
Returns
a new empty map
Source 
func int_map_with_capacity(capacity: i32) -> &IntMap {
  let slots: i32 = slot_count_for(capacity);
  return new IntMap {
    keys: new I32Values[slots]{},
    values: new I32Values[slots]{},
    states: new SlotStates[slots]{},
    count: 0,
    used: 0,
  };
}

slot_count_for #

line 97 
func slot_count_for(capacity: i32) -> i32

The power-of-two slot count that holds capacity entries under the 75% load factor.

Source 
func slot_count_for(capacity: i32) -> i32 {
  var slots: i32 = 16;
  loop grow() {
    if (slots * 3 >= capacity * 4 || slots >= 0x20000000) { break grow(); }
    slots = slots * 2;
    continue grow();
  }
  return slots;
}

hash_int #

line 117 
func hash_int(key: i32) -> i32

Mixes an i32 into a well-distributed hash.

This is the finalizer from MurmurHash3. Without a mix step, sequential integer keys land in sequential slots, which is fine until a rehash and catastrophic for any key set with a stride matching the capacity -- and capacities here are powers of two, so a stride of 16 would collide on every entry. It is not a cryptographic hash and must not be used as one.

Parameters
key — the value to hash
Returns
a well-distributed hash of key
Source 
func hash_int(key: i32) -> i32 {
  var h: i32 = key;
  h = h ^ (h >>> 16);
  h = h * 0x85EBCA6B;
  h = h ^ (h >>> 13);
  h = h * 0xC2B2AE35;
  return h ^ (h >>> 16);
}

str_map #

line 316 
func str_map() -> &StrMap

An empty StrMap.

Returns
a new empty map
Source 
func str_map() -> &StrMap {
  return new StrMap {
    keys: new AnyValues[16]{},
    values: new AnyValues[16]{},
    states: new SlotStates[16]{},
    count: 0,
    used: 0,
  };
}

Methods

IntMap.lenHow many entries the map holds.
IntMap.is_emptyWhether the map holds no entries.
IntMap.putInserts or overwrites the value for key.
IntMap.getThe value for key, with a flag saying whether it was present.
IntMap.get_orThe value for key, or fallback when it is absent.
IntMap.containsWhether key has an entry.
IntMap.removeRemoves key's entry.
IntMap.incrementAdds delta to key's value, inserting delta when the key is absent.
IntMap.clearRemoves every entry, keeping the allocated capacity.
IntMap.keysEvery key in the map, in unspecified order.
IntMap.valuesEvery value in the map, in the same order as keys.
IntMap.rehashDoubles the table and reinserts every live entry, discarding tombstones.
StrMap.lenHow many entries the map holds.
StrMap.is_emptyWhether the map holds no entries.
StrMap.putInserts or overwrites the value for key, comparing keys by content.
StrMap.getThe value for key, with a flag saying whether it was present.
StrMap.containsWhether key has an entry.
StrMap.removeRemoves key's entry, leaving a tombstone.
StrMap.clearRemoves every entry, releasing the map's references to its keys and values.
StrMap.rehashDoubles the table and reinserts every live entry, discarding tombstones.

IntMap.len #

line 129 
func IntMap.len(self: &IntMap) -> i32

How many entries the map holds.

Returns
the entry count
Source 
func IntMap.len(self: &IntMap) -> i32 {
  return self->count;
}

IntMap.is_empty #

line 136 
func IntMap.is_empty(self: &IntMap) -> i32

Whether the map holds no entries.

Returns
1 when empty, 0 otherwise
Source 
func IntMap.is_empty(self: &IntMap) -> i32 {
  return self->count == 0;
}

IntMap.put #

line 145 
func IntMap.put(self: &IntMap, key: i32, value: i32) -> void

Inserts or overwrites the value for key.

Parameters
key — the key
value — the value to associate with it
See also
IntMap.get
Source 
func IntMap.put(self: &IntMap, key: i32, value: i32) {
  // Grow *before* inserting, so the insert below always finds a slot.
  if ((self->used + 1) * 4 >= #self->keys * 3) { self.rehash(); }
  let mask: i32 = #self->keys - 1;
  var slot: i32 = hash_int(key) & mask;
  // The first tombstone passed, if any: reusing it keeps the table compact, but only after
  // confirming the key is not already live further along the chain.
  var reusable: i32 = -1;
  loop probe() {
    let state: i32 = self->states[slot].u;
    if (state == SlotEmpty) { break probe(); }
    if (state == SlotTomb && reusable < 0) { reusable = slot; }
    if (state == SlotLive && self->keys[slot] == key) {
      self->values[slot] = value;
      return;
    }
    slot = (slot + 1) & mask;
    continue probe();
  }
  if (reusable >= 0) {
    // Reusing a tombstone does not consume a fresh slot, so `used` is unchanged.
    slot = reusable;
  } else {
    self->used = self->used + 1;
  }
  self->keys[slot] = key;
  self->values[slot] = value;
  self->states[slot] = SlotLive;
  self->count = self->count + 1;
}

IntMap.get #

line 184 
func IntMap.get(self: &IntMap, key: i32) -> (i32, i32)

The value for key, with a flag saying whether it was present.

The flag is why this returns a pair: any i32 is a legitimate stored value, so no sentinel can distinguish "absent" from "present and equal to the sentinel".

Parameters
key — the key to look up
Returns
(value, found)
See also
IntMap.get_or, IntMap.contains
Source 
func IntMap.get(self: &IntMap, key: i32) -> (i32, i32) {
  let mask: i32 = #self->keys - 1;
  var slot: i32 = hash_int(key) & mask;
  loop probe() {
    let state: i32 = self->states[slot].u;
    if (state == SlotEmpty) { break probe(); }
    if (state == SlotLive && self->keys[slot] == key) {
      return (self->values[slot], 1);
    }
    slot = (slot + 1) & mask;
    continue probe();
  }
  return (0, 0);
}

IntMap.get_or #

line 205 
func IntMap.get_or(self: &IntMap, key: i32, fallback: i32) -> i32

The value for key, or fallback when it is absent.

Parameters
key — the key to look up
fallback — what to return when absent
Returns
the value or fallback
See also
IntMap.get
Source 
func IntMap.get_or(self: &IntMap, key: i32, fallback: i32) -> i32 {
  let (value, found): (i32, i32) = self.get(key);
  return found != 0 ? value : fallback;
}

IntMap.contains #

line 214 
func IntMap.contains(self: &IntMap, key: i32) -> i32

Whether key has an entry.

Parameters
key — the key to test
Returns
1 when present, 0 otherwise
Source 
func IntMap.contains(self: &IntMap, key: i32) -> i32 {
  let (_value, found): (i32, i32) = self.get(key);
  return found;
}

IntMap.remove #

line 226 
func IntMap.remove(self: &IntMap, key: i32) -> i32

Removes key's entry.

Leaves a tombstone rather than an empty slot, so probe chains running through this position keep working. See this module's header.

Parameters
key — the key to remove
Returns
1 when an entry was removed, 0 when the key was absent
Source 
func IntMap.remove(self: &IntMap, key: i32) -> i32 {
  let mask: i32 = #self->keys - 1;
  var slot: i32 = hash_int(key) & mask;
  loop probe() {
    let state: i32 = self->states[slot].u;
    if (state == SlotEmpty) { break probe(); }
    if (state == SlotLive && self->keys[slot] == key) {
      self->states[slot] = SlotTomb;
      self->count = self->count - 1;
      return 1;
    }
    slot = (slot + 1) & mask;
    continue probe();
  }
  return 0;
}

IntMap.increment #

line 251 
func IntMap.increment(self: &IntMap, key: i32, delta: i32) -> i32

Adds delta to key's value, inserting delta when the key is absent.

The counting idiom in one operation and one probe, rather than a get followed by a put.

Parameters
key — the key
delta — how much to add
Returns
the new value
Source 
func IntMap.increment(self: &IntMap, key: i32, delta: i32) -> i32 {
  let (current, _found): (i32, i32) = self.get(key);
  let next: i32 = current + delta;
  self.put(key, next);
  return next;
}

IntMap.clear #

line 259 
func IntMap.clear(self: &IntMap) -> void

Removes every entry, keeping the allocated capacity.

Source 
func IntMap.clear(self: &IntMap) {
  self->states.fill(0, SlotEmpty, #self->states);
  self->count = 0;
  self->used = 0;
}

IntMap.keys #

line 269 
func IntMap.keys(self: &IntMap) -> &IntList

Every key in the map, in unspecified order.

Returns
a list of the keys
See also
IntMap.values
Source 
func IntMap.keys(self: &IntMap) -> &IntList {
  let out: &IntList = int_list();
  for i in 0..#self->keys {
    if (self->states[i].u == SlotLive) { out.push(self->keys[i]); }
  }
  return out;
}

IntMap.values #

line 281 
func IntMap.values(self: &IntMap) -> &IntList

Every value in the map, in the same order as keys.

Returns
a list of the values
See also
IntMap.keys
Source 
func IntMap.values(self: &IntMap) -> &IntList {
  let out: &IntList = int_list();
  for i in 0..#self->keys {
    if (self->states[i].u == SlotLive) { out.push(self->values[i]); }
  }
  return out;
}

IntMap.rehash #

line 293 
func IntMap.rehash(self: &IntMap) -> void

Doubles the table and reinserts every live entry, discarding tombstones.

Sized from count (live entries), not used: a map that is mostly tombstones needs a clean-out, not a bigger table.

Source 
func IntMap.rehash(self: &IntMap) {
  let old_keys: &I32Values = self->keys;
  let old_values: &I32Values = self->values;
  let old_states: &SlotStates = self->states;
  var slots: i32 = #old_keys;
  // Only actually grow when live entries justify it; otherwise reuse the same size and
  // simply drop the tombstones.
  if ((self->count + 1) * 4 >= slots * 3) { slots = slots * 2; }
  self->keys = new I32Values[slots]{};
  self->values = new I32Values[slots]{};
  self->states = new SlotStates[slots]{};
  self->count = 0;
  self->used = 0;
  for i in 0..#old_keys {
    if (old_states[i].u == SlotLive) {
      self.put(old_keys[i], old_values[i]);
    }
  }
}

StrMap.len #

line 329 
func StrMap.len(self: &StrMap) -> i32

How many entries the map holds.

Returns
the entry count
Source 
func StrMap.len(self: &StrMap) -> i32 {
  return self->count;
}

StrMap.is_empty #

line 336 
func StrMap.is_empty(self: &StrMap) -> i32

Whether the map holds no entries.

Returns
1 when empty, 0 otherwise
Source 
func StrMap.is_empty(self: &StrMap) -> i32 {
  return self->count == 0;
}

StrMap.put #

line 345 
func StrMap.put(self: &StrMap, key: &Str, value: ?any) -> void

Inserts or overwrites the value for key, comparing keys by content.

Parameters
key — the key
value — the value to associate with it
See also
StrMap.get
Source 
func StrMap.put(self: &StrMap, key: &Str, value: ?any) {
  if ((self->used + 1) * 4 >= #self->keys * 3) { self.rehash(); }
  let mask: i32 = #self->keys - 1;
  var slot: i32 = key.hash() & mask;
  var reusable: i32 = -1;
  loop probe() {
    let state: i32 = self->states[slot].u;
    if (state == SlotEmpty) { break probe(); }
    if (state == SlotTomb && reusable < 0) { reusable = slot; }
    if (state == SlotLive) {
      let existing: ?any = self->keys[slot];
      if (existing is &Str) {
        if (existing.equals(key)) {
          self->values[slot] = value;
          return;
        }
      }
    }
    slot = (slot + 1) & mask;
    continue probe();
  }
  if (reusable >= 0) {
    slot = reusable;
  } else {
    self->used = self->used + 1;
  }
  self->keys[slot] = key;
  self->values[slot] = value;
  self->states[slot] = SlotLive;
  self->count = self->count + 1;
}

StrMap.get #

line 384 
func StrMap.get(self: &StrMap, key: &Str) -> (?any, i32)

The value for key, with a flag saying whether it was present.

A present entry whose value is null is distinguishable from an absent one, which is exactly why the flag exists.

Parameters
key — the key to look up
Returns
(value, found)
Source 
func StrMap.get(self: &StrMap, key: &Str) -> (?any, i32) {
  let mask: i32 = #self->keys - 1;
  var slot: i32 = key.hash() & mask;
  loop probe() {
    let state: i32 = self->states[slot].u;
    if (state == SlotEmpty) { break probe(); }
    if (state == SlotLive) {
      let existing: ?any = self->keys[slot];
      if (existing is &Str) {
        if (existing.equals(key)) {
          return (self->values[slot], 1);
        }
      }
    }
    slot = (slot + 1) & mask;
    continue probe();
  }
  return (null, 0);
}

StrMap.contains #

line 408 
func StrMap.contains(self: &StrMap, key: &Str) -> i32

Whether key has an entry.

Parameters
key — the key to test
Returns
1 when present, 0 otherwise
Source 
func StrMap.contains(self: &StrMap, key: &Str) -> i32 {
  let (_value, found): (?any, i32) = self.get(key);
  return found;
}

StrMap.remove #

line 417 
func StrMap.remove(self: &StrMap, key: &Str) -> i32

Removes key's entry, leaving a tombstone.

Parameters
key — the key to remove
Returns
1 when an entry was removed, 0 when the key was absent
Source 
func StrMap.remove(self: &StrMap, key: &Str) -> i32 {
  let mask: i32 = #self->keys - 1;
  var slot: i32 = key.hash() & mask;
  loop probe() {
    let state: i32 = self->states[slot].u;
    if (state == SlotEmpty) { break probe(); }
    if (state == SlotLive) {
      let existing: ?any = self->keys[slot];
      if (existing is &Str) {
        if (existing.equals(key)) {
          self->states[slot] = SlotTomb;
          // Release both references: a tombstone must not pin the key and value it used to
          // hold, or a long-lived map leaks every entry ever removed from it.
          self->keys[slot] = null;
          self->values[slot] = null;
          self->count = self->count - 1;
          return 1;
        }
      }
    }
    slot = (slot + 1) & mask;
    continue probe();
  }
  return 0;
}

StrMap.clear #

line 444 
func StrMap.clear(self: &StrMap) -> void

Removes every entry, releasing the map's references to its keys and values.

Source 
func StrMap.clear(self: &StrMap) {
  self->keys.fill(0, null, #self->keys);
  self->values.fill(0, null, #self->values);
  self->states.fill(0, SlotEmpty, #self->states);
  self->count = 0;
  self->used = 0;
}

StrMap.rehash #

line 453 
func StrMap.rehash(self: &StrMap) -> void

Doubles the table and reinserts every live entry, discarding tombstones.

Source 
func StrMap.rehash(self: &StrMap) {
  let old_keys: &AnyValues = self->keys;
  let old_values: &AnyValues = self->values;
  let old_states: &SlotStates = self->states;
  var slots: i32 = #old_keys;
  if ((self->count + 1) * 4 >= slots * 3) { slots = slots * 2; }
  self->keys = new AnyValues[slots]{};
  self->values = new AnyValues[slots]{};
  self->states = new SlotStates[slots]{};
  self->count = 0;
  self->used = 0;
  for i in 0..#old_keys {
    if (old_states[i].u == SlotLive) {
      let key: ?any = old_keys[i];
      if (key is &Str) {
        self.put(key, old_values[i]);
      }
    }
  }
}

Types

SlotStatesThe state of one slot.
IntMapA hash map from i32 keys to i32 values.
StrMapA hash map from string keys to nullable reference values.

SlotStates #

line 35 
array SlotStates { mut i32 }

The state of one slot. Kept in a parallel byte array rather than encoded as a reserved key value, because every i32 is a legitimate key and there is no value left over to mean "empty".

IntMap #

line 48 
struct IntMap {
  keys: mut &I32Values,
  values: mut &I32Values,
  states: mut &SlotStates,
  count: mut i32,
  used: mut i32,
}

A hash map from i32 keys to i32 values.

Source 
struct IntMap {
  keys: mut &I32Values,
  values: mut &I32Values,
  states: mut &SlotStates,
  /// Live entries.
  count: mut i32,
  /// Live entries plus tombstones: what the load factor is actually measured against.
  used: mut i32,
}

StrMap #

line 62 
struct StrMap {
  keys: mut &AnyValues,
  values: mut &AnyValues,
  states: mut &SlotStates,
  count: mut i32,
  used: mut i32,
}

A hash map from string keys to nullable reference values.

Keys are compared by content, so a lookup with a freshly built string finds an entry inserted under an equal one.

Source 
struct StrMap {
  keys: mut &AnyValues,
  values: mut &AnyValues,
  states: mut &SlotStates,
  count: mut i32,
  used: mut i32,
}

Compile-time values

SlotEmptyA slot that has never held an entry.
SlotLiveA slot holding a live entry.
SlotTombA slot whose entry was removed.

SlotEmpty #

line 39 
param SlotEmpty: i32 = 0

A slot that has never held an entry. A probe reaching one stops: nothing beyond it can belong to the chain being followed.

SlotLive #

line 41 
param SlotLive: i32 = 1

A slot holding a live entry.

SlotTomb #

line 45 
param SlotTomb: i32 = 2

A slot whose entry was removed. A probe passes through it (the chain continues) but an insert may reuse it. Deleting by returning a slot to SlotEmpty instead would break every probe chain running through that slot.