🥮 mooncakes.io

slotmap

Stable-key map containers for MoonBit with slot reuse and self-invalidating secondary maps.

slotmap
hashmap
densemap
secondarymap
moon add Milky2018/slotmap@0.1.2
Download zip
Author
Version
0.1.2
License
Apache-2.0
Repository
Last updated
3 months ago
Downloads
83
README

#slotmap

Stable-key map containers for MoonBit.

#Choosing a Container

  • Use SlotMap[K, V] as the default primary container when you need stable keys and expect frequent insert / remove / get.
  • Use DenseSlotMap[K, V] when you still need stable keys but spend more time iterating live values than mutating the map.
  • Use SecondaryMap[K, V] when most live primary keys also carry side metadata and you want the fastest key-indexed secondary lookup.
  • Use SparseSecondaryMap[K, V] when only a small subset of primary keys carry side metadata and dense secondary storage would be mostly empty.
  • Use builtin Map or @hashmap.HashMap instead when you do not need slot reuse, versioned invalidation, or long-lived stable keys.

#Benchmark Snapshot

The repository includes benchmark_test.mbt for comparative benchmarks against MoonBit builtin Map and @hashmap.HashMap.

The following numbers are from one local moon bench --release run on April 22, 2026:

ScenarioFastestNotes
Churn (insert + remove + get)SlotMap (59.74 µs)@hashmap.HashMap (84.38 µs) beats builtin Map (107.68 µs), but both trail stable-slot reuse.
Iterate after holesbuiltin Map (2.64 µs)DenseSlotMap (4.04 µs) is much better than SlotMap (10.17 µs) once iteration dominates.
Dense sidecar probeSecondaryMap (25.29 µs)Direct index lookup is far ahead of sparse hash-based sidecars.
Sparse sidecar iteratebuiltin Map (15.76 µs)SparseSecondaryMap (21.08 µs) is better than SecondaryMap (33.02 µs) for sparse metadata scans.

These benchmarks are meant to show container tradeoffs, not absolute performance guarantees. Exact numbers depend on backend, MoonBit version, and machine.

///|
struct UserKey(@slotmap.KeyData) derive(Eq, Compare, Hash, Debug)

///|
impl @slotmap.Key for UserKey with null() {
  UserKey(@slotmap.KeyData::null())
}

///|
impl @slotmap.Key for UserKey with is_null(self) {
  self.0.is_null()
}

///|
impl @slotmap.Key for UserKey with index(self) {
  self.0.index()
}

///|
impl @slotmap.Key for UserKey with version(self) {
  self.0.version()
}

///|
impl @slotmap.Key for UserKey with from_raw_parts(index, version) {
  UserKey(@slotmap.KeyData::from_raw_parts(index, version))
}

///|
impl @slotmap.Key for UserKey with into_raw_parts(self) {
  self.0.into_raw_parts()
}

///|
impl Show for UserKey with output(self, logger) {
  logger.write_object(self.0)
}

///|
test {
  let sm : @slotmap.SlotMap[UserKey, String] = @slotmap.SlotMap::new()
  let sec : @slotmap.SecondaryMap[UserKey, String] = @slotmap.SecondaryMap::new()
  let foo = sm.insert("foo")
  let bar = sm.insert("bar")
  sec[foo] = "noun"
  sec[bar] = "verb"
  debug_inspect(sm.get(foo), content="Some(\"foo\")")
  debug_inspect(sm.get(bar), content="Some(\"bar\")")
  debug_inspect(sec.get(foo), content="Some(\"noun\")")

  ignore(sm.remove(bar))
  let reuse = sm.insert("reuse")
  debug_inspect(sm.contains_key(bar), content="false")
  debug_inspect(sec.get(bar), content="Some(\"verb\")")
  sec[reuse] = "adjective"
  debug_inspect(sec.get(bar), content="None")
  debug_inspect(sm.get(reuse), content="Some(\"reuse\")")
  debug_inspect(sec.get(reuse), content="Some(\"adjective\")")
}

#
Key

source
pub(open) trait Key : Eq + Show {
  null() -> Self
  is_null(Self) -> Bool
  index(Self) -> Int
  version(Self) -> Int
  from_raw_parts(Int, Int) -> Self
  into_raw_parts(Self) -> (Int, Int)
}

#
DefaultKey

source
pub struct DefaultKey {
  data : KeyData
} derive(Compare, Eq, Hash, 
Debug)

impl Key for DefaultKey
impl Show for DefaultKey

#
DenseSlotEntry

source
type DenseSlotEntry

#
DenseSlotMap

source
pub struct DenseSlotMap[K, V] {
  slots : Array[DenseSlotEntry]
  dense_keys : Array[K]
  dense_values : Array[V]
  free_head : Int?
}

#
DenseSlotMap::as_slices

source
fn[K, V] DenseSlotMap::as_slices(self : DenseSlotMap[K, V]) -> (ArrayView[K], ArrayView[V])

#
DenseSlotMap::at

source
#alias("_[_]")
fn[K : Key + Eq + Show, V] DenseSlotMap::at(self : DenseSlotMap[K, V], key : K) -> V

#
DenseSlotMap::capacity

source
fn[K, V] DenseSlotMap::capacity(self : DenseSlotMap[K, V]) -> Int

#
DenseSlotMap::clear

source
fn[K : Key + Eq + Show, V] DenseSlotMap::clear(self : DenseSlotMap[K, V]) -> Unit

#
DenseSlotMap::contains

source
fn[K : Key + Eq + Show, V] DenseSlotMap::contains(self : DenseSlotMap[K, V], key : K) -> Bool

#
DenseSlotMap::contains_key

source
fn[K : Key + Eq + Show, V] DenseSlotMap::contains_key(self : DenseSlotMap[K, V], key : K) -> Bool

#
DenseSlotMap::default

source
fn[K, V] DenseSlotMap::default() -> DenseSlotMap[K, V]

#
DenseSlotMap::detach

source
fn[K : Key + Eq + Show, V] DenseSlotMap::detach(self : DenseSlotMap[K, V], key : K) -> V?

#
DenseSlotMap::drain

source
fn[K : Key + Eq + Show, V] DenseSlotMap::drain(self : DenseSlotMap[K, V]) -> Array[(K, V)]

#
DenseSlotMap::each

source
fn[K, V] DenseSlotMap::each(self : DenseSlotMap[K, V], visit : (K, V) -> Unit) -> Unit

#
DenseSlotMap::get

source
fn[K : Key + Eq + Show, V] DenseSlotMap::get(self : DenseSlotMap[K, V], key : K) -> V?

#
DenseSlotMap::insert

source
fn[K : Key + Eq + Show, V] DenseSlotMap::insert(self : DenseSlotMap[K, V], value : V) -> K

#
DenseSlotMap::insert_with_key

source
fn[K : Key + Eq + Show, V] DenseSlotMap::insert_with_key(self : DenseSlotMap[K, V], create : (K) -> V) -> K

#
DenseSlotMap::is_empty

source
fn[K, V] DenseSlotMap::is_empty(self : DenseSlotMap[K, V]) -> Bool

#
DenseSlotMap::iter

source
fn[K, V] DenseSlotMap::iter(self : DenseSlotMap[K, V]) -> Array[(K, V)]

#
DenseSlotMap::iter2

source
#alias(iterator2, deprecated="`iterator2` is deprecated, use `iter2` instead")
fn[K, V] DenseSlotMap::iter2(self : DenseSlotMap[K, V]) -> Iter2[K, V]

#
DenseSlotMap::keys

source
fn[K, V] DenseSlotMap::keys(self : DenseSlotMap[K, V]) -> Array[K]

#
DenseSlotMap::keys_as_slice

source
fn[K, V] DenseSlotMap::keys_as_slice(self : DenseSlotMap[K, V]) -> ArrayView[K]

#
DenseSlotMap::len

source
fn[K, V] DenseSlotMap::len(self : DenseSlotMap[K, V]) -> Int

#
DenseSlotMap::length

source
fn[K, V] DenseSlotMap::length(self : DenseSlotMap[K, V]) -> Int

#
DenseSlotMap::new

source
fn[K, V] DenseSlotMap::new(capacity? : Int) -> DenseSlotMap[K, V]

#
DenseSlotMap::reattach

source
fn[K : Key + Eq + Show, V] DenseSlotMap::reattach(self : DenseSlotMap[K, V], detached_key : K, value : V) -> Unit

#
DenseSlotMap::remove

source
fn[K : Key + Eq + Show, V] DenseSlotMap::remove(self : DenseSlotMap[K, V], key : K) -> V?

#
DenseSlotMap::replace

source
fn[K : Key + Eq + Show, V] DenseSlotMap::replace(self : DenseSlotMap[K, V], key : K, value : V) -> Bool

#
DenseSlotMap::reserve

source
fn[K, V] DenseSlotMap::reserve(self : DenseSlotMap[K, V], additional : Int) -> Unit

#
DenseSlotMap::retain

source
fn[K : Key + Eq + Show, V] DenseSlotMap::retain(self : DenseSlotMap[K, V], predicate : (K, V) -> Bool) -> Unit

#
DenseSlotMap::set

source
#alias("_[_]=_")
fn[K : Key + Eq + Show, V] DenseSlotMap::set(self : DenseSlotMap[K, V], key : K, value : V) -> Unit

#
DenseSlotMap::to_array

source
fn[K, V] DenseSlotMap::to_array(self : DenseSlotMap[K, V]) -> Array[(K, V)]

#
DenseSlotMap::update

source
fn[K : Key + Eq + Show, V] DenseSlotMap::update(self : DenseSlotMap[K, V], key : K, updater : (V?) -> V?) -> Unit

#
DenseSlotMap::values

source
fn[K, V] DenseSlotMap::values(self : DenseSlotMap[K, V]) -> Array[V]

#
DenseSlotMap::values_as_slice

source
fn[K, V] DenseSlotMap::values_as_slice(self : DenseSlotMap[K, V]) -> ArrayView[V]

#
DenseSlotMap::with_capacity

source
fn[K, V] DenseSlotMap::with_capacity(capacity : Int) -> DenseSlotMap[K, V]

#
KeyData

source
pub(all) struct KeyData {
  idx : Int
  version : Int
} derive(Compare, Eq, Hash, 
Debug)

impl Show for KeyData

#
KeyData::default

source
fn KeyData::default() -> KeyData

#
KeyData::from_raw_parts

source
fn KeyData::from_raw_parts(index : Int, version : Int) -> KeyData

#
KeyData::index

source
fn KeyData::index(self : KeyData) -> Int

#
KeyData::into_raw_parts

source
fn KeyData::into_raw_parts(self : KeyData) -> (Int, Int)

#
KeyData::is_null

source
fn KeyData::is_null(self : KeyData) -> Bool

#
KeyData::null

source
fn KeyData::null() -> KeyData

#
KeyData::version

source
fn KeyData::version(self : KeyData) -> Int

#
SecondaryMap

source
pub struct SecondaryMap[K, V] {
  slots : Array[(Int, V)?]
  size : Int
  _key : K?
}

#
SecondaryMap::at

source
#alias("_[_]")
fn[K : Key + Eq + Show, V] SecondaryMap::at(self : SecondaryMap[K, V], key : K) -> V

#
SecondaryMap::capacity

source
fn[K, V] SecondaryMap::capacity(self : SecondaryMap[K, V]) -> Int

#
SecondaryMap::clear

source
fn[K, V] SecondaryMap::clear(self : SecondaryMap[K, V]) -> Unit

#
SecondaryMap::contains

source
fn[K : Key + Eq + Show, V] SecondaryMap::contains(self : SecondaryMap[K, V], key : K) -> Bool

#
SecondaryMap::contains_key

source
fn[K : Key + Eq + Show, V] SecondaryMap::contains_key(self : SecondaryMap[K, V], key : K) -> Bool

#
SecondaryMap::default

source
fn[K, V] SecondaryMap::default() -> SecondaryMap[K, V]

#
SecondaryMap::drain

source
fn[K : Key + Eq + Show, V] SecondaryMap::drain(self : SecondaryMap[K, V]) -> Array[(K, V)]

#
SecondaryMap::each

source
fn[K : Key + Eq + Show, V] SecondaryMap::each(self : SecondaryMap[K, V], visit : (K, V) -> Unit) -> Unit

#
SecondaryMap::get

source
fn[K : Key + Eq + Show, V] SecondaryMap::get(self : SecondaryMap[K, V], key : K) -> V?

#
SecondaryMap::get_or_default

source
fn[K : Key + Eq + Show, V] SecondaryMap::get_or_default(self : SecondaryMap[K, V], key : K, default : V) -> V?

#
SecondaryMap::get_or_init

source
fn[K : Key + Eq + Show, V] SecondaryMap::get_or_init(self : SecondaryMap[K, V], key : K, init : () -> V) -> V?

#
SecondaryMap::insert

source
fn[K : Key + Eq + Show, V] SecondaryMap::insert(self : SecondaryMap[K, V], key : K, value : V) -> V?

#
SecondaryMap::is_empty

source
fn[K, V] SecondaryMap::is_empty(self : SecondaryMap[K, V]) -> Bool

#
SecondaryMap::iter

source
fn[K : Key + Eq + Show, V] SecondaryMap::iter(self : SecondaryMap[K, V]) -> Array[(K, V)]

#
SecondaryMap::iter2

source
#alias(iterator2, deprecated="`iterator2` is deprecated, use `iter2` instead")
fn[K : Key + Eq + Show, V] SecondaryMap::iter2(self : SecondaryMap[K, V]) -> Iter2[K, V]

#
SecondaryMap::keys

source
fn[K : Key + Eq + Show, V] SecondaryMap::keys(self : SecondaryMap[K, V]) -> Array[K]

#
SecondaryMap::len

source
fn[K, V] SecondaryMap::len(self : SecondaryMap[K, V]) -> Int

#
SecondaryMap::length

source
fn[K, V] SecondaryMap::length(self : SecondaryMap[K, V]) -> Int

#
SecondaryMap::new

source
fn[K, V] SecondaryMap::new(capacity? : Int) -> SecondaryMap[K, V]

#
SecondaryMap::remove

source
fn[K : Key + Eq + Show, V] SecondaryMap::remove(self : SecondaryMap[K, V], key : K) -> V?

#
SecondaryMap::retain

source
fn[K : Key + Eq + Show, V] SecondaryMap::retain(self : SecondaryMap[K, V], predicate : (K, V) -> Bool) -> Unit

#
SecondaryMap::set

source
#alias("_[_]=_")
fn[K : Key + Eq + Show, V] SecondaryMap::set(self : SecondaryMap[K, V], key : K, value : V) -> Unit

#
SecondaryMap::to_array

source
fn[K : Key + Eq + Show, V] SecondaryMap::to_array(self : SecondaryMap[K, V]) -> Array[(K, V)]

#
SecondaryMap::update

source
fn[K : Key + Eq + Show, V] SecondaryMap::update(self : SecondaryMap[K, V], key : K, updater : (V?) -> V?) -> Unit

#
SecondaryMap::values

source
fn[K, V] SecondaryMap::values(self : SecondaryMap[K, V]) -> Array[V]

#
SecondaryMap::with_capacity

source
fn[K, V] SecondaryMap::with_capacity(capacity : Int) -> SecondaryMap[K, V]

#
SlotEntry

source
type SlotEntry[V]

#
SlotMap

source
pub struct SlotMap[K, V] {
  slots : Array[SlotEntry[V]]
  free_head : Int?
  size : Int
  _key : K?
}

#
SlotMap::at

source
#alias("_[_]")
fn[K : Key + Eq + Show, V] SlotMap::at(self : SlotMap[K, V], key : K) -> V

#
SlotMap::capacity

source
fn[K, V] SlotMap::capacity(self : SlotMap[K, V]) -> Int

#
SlotMap::clear

source
fn[K, V] SlotMap::clear(self : SlotMap[K, V]) -> Unit

#
SlotMap::contains

source
fn[K : Key + Eq + Show, V] SlotMap::contains(self : SlotMap[K, V], key : K) -> Bool

#
SlotMap::contains_key

source
fn[K : Key + Eq + Show, V] SlotMap::contains_key(self : SlotMap[K, V], key : K) -> Bool

#
SlotMap::default

source
fn[K, V] SlotMap::default() -> SlotMap[K, V]

#
SlotMap::detach

source
fn[K : Key + Eq + Show, V] SlotMap::detach(self : SlotMap[K, V], key : K) -> V?

#
SlotMap::drain

source
fn[K : Key + Eq + Show, V] SlotMap::drain(self : SlotMap[K, V]) -> Array[(K, V)]

#
SlotMap::each

source
fn[K : Key + Eq + Show, V] SlotMap::each(self : SlotMap[K, V], visit : (K, V) -> Unit) -> Unit

#
SlotMap::get

source
fn[K : Key + Eq + Show, V] SlotMap::get(self : SlotMap[K, V], key : K) -> V?

#
SlotMap::insert

source
fn[K : Key + Eq + Show, V] SlotMap::insert(self : SlotMap[K, V], value : V) -> K

#
SlotMap::insert_with_key

source
fn[K : Key + Eq + Show, V] SlotMap::insert_with_key(self : SlotMap[K, V], create : (K) -> V) -> K

#
SlotMap::is_empty

source
fn[K, V] SlotMap::is_empty(self : SlotMap[K, V]) -> Bool

#
SlotMap::iter

source
fn[K : Key + Eq + Show, V] SlotMap::iter(self : SlotMap[K, V]) -> Array[(K, V)]

#
SlotMap::iter2

source
#alias(iterator2, deprecated="`iterator2` is deprecated, use `iter2` instead")
fn[K : Key + Eq + Show, V] SlotMap::iter2(self : SlotMap[K, V]) -> Iter2[K, V]

#
SlotMap::keys

source
fn[K : Key + Eq + Show, V] SlotMap::keys(self : SlotMap[K, V]) -> Array[K]

#
SlotMap::len

source
fn[K, V] SlotMap::len(self : SlotMap[K, V]) -> Int

#
SlotMap::length

source
fn[K, V] SlotMap::length(self : SlotMap[K, V]) -> Int

#
SlotMap::new

source
fn[K, V] SlotMap::new(capacity? : Int) -> SlotMap[K, V]

#
SlotMap::reattach

source
fn[K : Key + Eq + Show, V] SlotMap::reattach(self : SlotMap[K, V], detached_key : K, value : V) -> Unit

#
SlotMap::remove

source
fn[K : Key + Eq + Show, V] SlotMap::remove(self : SlotMap[K, V], key : K) -> V?

#
SlotMap::replace

source
fn[K : Key + Eq + Show, V] SlotMap::replace(self : SlotMap[K, V], key : K, value : V) -> Bool

#
SlotMap::reserve

source
fn[K, V] SlotMap::reserve(self : SlotMap[K, V], additional : Int) -> Unit

#
SlotMap::retain

source
fn[K : Key + Eq + Show, V] SlotMap::retain(self : SlotMap[K, V], predicate : (K, V) -> Bool) -> Unit

#
SlotMap::set

source
#alias("_[_]=_")
fn[K : Key + Eq + Show, V] SlotMap::set(self : SlotMap[K, V], key : K, value : V) -> Unit

#
SlotMap::to_array

source
fn[K : Key + Eq + Show, V] SlotMap::to_array(self : SlotMap[K, V]) -> Array[(K, V)]

#
SlotMap::update

source
fn[K : Key + Eq + Show, V] SlotMap::update(self : SlotMap[K, V], key : K, updater : (V?) -> V?) -> Unit

#
SlotMap::values

source
fn[K, V] SlotMap::values(self : SlotMap[K, V]) -> Array[V]

#
SlotMap::with_capacity

source
fn[K, V] SlotMap::with_capacity(capacity : Int) -> SlotMap[K, V]

#
SparseSecondaryMap

source
pub struct SparseSecondaryMap[K, V] {
  slots : Map[Int, (Int, V)]
  _key : K?
}

#
SparseSecondaryMap::at

source
#alias("_[_]")
fn[K : Key + Eq + Show, V] SparseSecondaryMap::at(self : SparseSecondaryMap[K, V], key : K) -> V

#
SparseSecondaryMap::capacity

source
fn[K, V] SparseSecondaryMap::capacity(self : SparseSecondaryMap[K, V]) -> Int

#
SparseSecondaryMap::clear

source
fn[K, V] SparseSecondaryMap::clear(self : SparseSecondaryMap[K, V]) -> Unit

#
SparseSecondaryMap::contains

source
fn[K : Key + Eq + Show, V] SparseSecondaryMap::contains(self : SparseSecondaryMap[K, V], key : K) -> Bool

#
SparseSecondaryMap::contains_key

source
fn[K : Key + Eq + Show, V] SparseSecondaryMap::contains_key(self : SparseSecondaryMap[K, V], key : K) -> Bool

#
SparseSecondaryMap::default

source
fn[K, V] SparseSecondaryMap::default() -> SparseSecondaryMap[K, V]

#
SparseSecondaryMap::drain

source
fn[K : Key + Eq + Show, V] SparseSecondaryMap::drain(self : SparseSecondaryMap[K, V]) -> Array[(K, V)]

#
SparseSecondaryMap::each

source
fn[K : Key + Eq + Show, V] SparseSecondaryMap::each(self : SparseSecondaryMap[K, V], visit : (K, V) -> Unit) -> Unit

#
SparseSecondaryMap::get

source
fn[K : Key + Eq + Show, V] SparseSecondaryMap::get(self : SparseSecondaryMap[K, V], key : K) -> V?

#
SparseSecondaryMap::get_or_default

source
fn[K : Key + Eq + Show, V] SparseSecondaryMap::get_or_default(self : SparseSecondaryMap[K, V], key : K, default : V) -> V?

#
SparseSecondaryMap::get_or_init

source
fn[K : Key + Eq + Show, V] SparseSecondaryMap::get_or_init(self : SparseSecondaryMap[K, V], key : K, init : () -> V) -> V?

#
SparseSecondaryMap::insert

source
fn[K : Key + Eq + Show, V] SparseSecondaryMap::insert(self : SparseSecondaryMap[K, V], key : K, value : V) -> V?

#
SparseSecondaryMap::is_empty

source
fn[K, V] SparseSecondaryMap::is_empty(self : SparseSecondaryMap[K, V]) -> Bool

#
SparseSecondaryMap::iter

source
fn[K : Key + Eq + Show, V] SparseSecondaryMap::iter(self : SparseSecondaryMap[K, V]) -> Array[(K, V)]

#
SparseSecondaryMap::iter2

source
#alias(iterator2, deprecated="`iterator2` is deprecated, use `iter2` instead")
fn[K : Key + Eq + Show, V] SparseSecondaryMap::iter2(self : SparseSecondaryMap[K, V]) -> Iter2[K, V]

#
SparseSecondaryMap::keys

source
fn[K : Key + Eq + Show, V] SparseSecondaryMap::keys(self : SparseSecondaryMap[K, V]) -> Array[K]

#
SparseSecondaryMap::len

source
fn[K, V] SparseSecondaryMap::len(self : SparseSecondaryMap[K, V]) -> Int

#
SparseSecondaryMap::length

source
fn[K, V] SparseSecondaryMap::length(self : SparseSecondaryMap[K, V]) -> Int

#
SparseSecondaryMap::new

source
fn[K, V] SparseSecondaryMap::new(capacity? : Int) -> SparseSecondaryMap[K, V]

#
SparseSecondaryMap::remove

source
fn[K : Key + Eq + Show, V] SparseSecondaryMap::remove(self : SparseSecondaryMap[K, V], key : K) -> V?

#
SparseSecondaryMap::retain

source
fn[K : Key + Eq + Show, V] SparseSecondaryMap::retain(self : SparseSecondaryMap[K, V], predicate : (K, V) -> Bool) -> Unit

#
SparseSecondaryMap::set

source
#alias("_[_]=_")
fn[K : Key + Eq + Show, V] SparseSecondaryMap::set(self : SparseSecondaryMap[K, V], key : K, value : V) -> Unit

#
SparseSecondaryMap::to_array

source
fn[K : Key + Eq + Show, V] SparseSecondaryMap::to_array(self : SparseSecondaryMap[K, V]) -> Array[(K, V)]

#
SparseSecondaryMap::update

source
fn[K : Key + Eq + Show, V] SparseSecondaryMap::update(self : SparseSecondaryMap[K, V], key : K, updater : (V?) -> V?) -> Unit

#
SparseSecondaryMap::values

source
fn[K, V] SparseSecondaryMap::values(self : SparseSecondaryMap[K, V]) -> Array[V]

#
SparseSecondaryMap::with_capacity

source
fn[K, V] SparseSecondaryMap::with_capacity(capacity : Int) -> SparseSecondaryMap[K, V]

Source Files

Powered by MoonBit

Site sourceReport issuePackagesBuild queueSkillsStatistics

© 2026 mooncakes.io