How they work

What each structure keeps in memory, and what its operations cost. Each method is documented on its function in src/.

A method that hands back storage, such as GrowableBuffer:Raw(), returns the structure’s own buffer. Take it again after anything that can grow the structure, since growing replaces the buffer.

Handles

SlotMap and SlotAllocator give out handles. A handle is one number: a slot in its low 24 bits and the slot’s generation above them. Collections.UnpackHandle splits one and Collections.PackHandle builds one.

Removing a value adds one to its slot’s generation, so old handles to it stop matching, even once the slot holds a new value. A slot is reused 65,535 times in a SlotMap and 32,767 times in a SlotAllocator, then retired, so an old handle never matches again.

Slots run from 1 to 16,777,215. Taking a new slot past that raises an error, where a handle to it would otherwise match a different slot.

SlotMap

Values sit in one packed list, and each slot records where its value is. Remove moves the last value into the gap, so Iter and RawValues never see a hole, and the order changes as values are removed. Iter walks the list from the end, so a loop can remove the value it is on; a value the loop inserts is not visited.

Values live in a table by default. A Backend of Stride, Read and Write keeps them in a buffer instead, Stride bytes each. An Insert whose value the backend cannot write raises and stores nothing.

new tries a Backend with a Stride of 4 on five full 32-bit words. If it stores and reads them exactly as buffer.writeu32 and buffer.readu32 do, a wrapper around them included, the map takes a faster path that uses those two directly and never calls the backend again. Every other backend is called for each value.

Get, Set, Remove and IsAlive are O(1). Insert takes the lowest free slot through a two-level bitmap, reading one summary word per 1,024 slots of capacity until it finds one. When no slot is free it skips the scan and takes a new slot, so filling a map stays O(1). Once a slot retires after running out of generations, Insert reads every summary word again whenever none is free.

SlotAllocator

Hands out handles without storing values, for data kept in your own arrays, indexed by slot. Allocate returns the handle and its slot, and SlotOf gives a live handle’s slot. OnGrow, in the config, is called with the old and new capacity whenever it grows, so those arrays can grow with it.

Free slots are bits in a bitmap, and Allocate takes the lowest, starting at a hint that Free lowers. Free, IsAlive and SlotOf are O(1), and so is Allocate while it takes new slots or the slot just freed. Taking an older freed slot reads the bitmap from the hint up to it, one word per 32 slots, and once the last freed slot is taken, the next Allocate reads to the end of the bitmap once.

SparseSet

A set of integer ids from 1. One buffer maps each id to its position, and a second lists the ids packed, with no gaps. Add, Remove and Has are O(1), and Add doubles either buffer when it runs out of room. The first buffer is sized by the largest id, not by how many ids the set holds.

Remove moves the last id into the gap. It returns the position that was freed, from 1, and the id now there, or the removed id when it was last, so arrays kept in the same order can make the same move. An id that is not in the set returns 0, 0. RawDense returns the packed list, a u32 per id from byte 0, and the count.

StampSet

A set of integers from 0 up to a Capacity fixed at new. Each integer has a u32 stamp, and it is in the set when its stamp equals the set’s current era. ClearAll adds one to the era instead of touching the stamps, so it is O(1) however full the set is. Once every 4,294,967,295 clears, it zero-fills the stamps and starts over.

Add, Remove, Test and Count are O(1). An integer outside the range is ignored, and Add and Test return false for it.

Bitmap

A fixed number of bits, from 0, packed 32 to a u32 word. Set, Clear, Toggle and Test are O(1), and an index outside the bitmap does nothing. SetAll and ClearAll fill the whole buffer in one call, and PopCount counts the set bits a word at a time. Raw returns the buffer.

GrowableBuffer

A list of numbers of one Kind: U8, U16, U32, F32 or F64. Push appends and returns the new value’s index, from 0. When the buffer is full it moves to one twice the size, so Push is O(1) on average.

Get and Set are O(1) and do not check the index against Length. Raw returns the buffer and the length. A Push of a value that is not a number raises and stores nothing.

Ring

A first-in, first-out queue with a Capacity fixed at new. Push adds at the tail, and Pop and Peek read the head, all O(1). Drain passes every entry to a function, oldest first, and empties the ring. It reads from a copy of the head and resets the ring once at the end, which keeps it fast, so the function must not push, pop or clear the ring. If the function raises, a buffer ring still holds every entry, and the next Drain passes them all again. A "Table" ring clears each slot as it goes, so it still counts every entry but gives nil for the ones already passed.

OnFull says what a push into a full ring does: "Reject" returns false, "Overwrite" drops the oldest entry, and "Error" throws.

By default, entries are numbers in a buffer, Stride numbers to an entry, so Push(x, y) and Pop() take and give two at a Stride of 2. A buffer ring that would store an entry with a number missing raises and changes nothing. A Backend of "Table" holds any value, one to an entry.

MinHeap

Gives back the entry with the smallest key first. Each entry is a number key and a u32 value, a whole number from 0 to 4,294,967,295, such as an array index. A value outside that range wraps. SlotMap and SlotAllocator handles can be outside it, so to queue them, push an index into your own array of handles. All entries sit in one buffer.

Each parent has 8 children rather than 2, so the heap stays shallow. Push and Pop are O(log n), and Peek is O(1). Equal keys come out in no set order, but the same pushes and pops always give the same order. Push raises and stores nothing when the key is NaN or not a number, or the value is not a number.

BucketQueue

A priority queue for whole-number priorities that move forward a little at a time, as in path-finding. It keeps one bucket per priority, for a window of Span priorities that starts at a cursor: the lower of the lowest priority in the queue and the last priority popped since the queue was last empty. This is Dial’s algorithm.

Push is O(1). Pop moves forward to the next bucket that holds an entry, at most Span of them, and a steady drain checks one or two. Pop returns the priority and the value, a u32 that wraps like MinHeap’s, so it cannot hold a handle either. PopOrder picks "fifo", the default, or "lifo" among equal priorities. Push raises and stores nothing when the priority is not a whole number or the value is not a number.

After each push, every priority in the queue must lie in the window, so the highest must be less than Span above the cursor. That is not checked, which Limitations explains.

Interner

Gives each distinct string a number from 1, in the order first seen, and KeyOf turns the number back into the string. One table holds both directions. Intern and KeyOf are O(1). Strings are never removed, and Intern errors on anything that is not a string.

Registry

Stores values by string key. OverridePolicy says what a second Register of a key does: "Throw" errors, "Warn" replaces the value and passes a message to WarnSink, if one was given, and "Last" replaces it quietly. ValidateValue, when given, checks each value as it is registered.

Register, Unregister, Get and Has are O(1). The registry keeps no count, so List and Each walk every entry. Seed registers each entry of a table of defaults.