Table<K, V> structv0.1.0

pub struct Table<K, V> {
    // private fields
}

Holds keys, values, one distance byte and one hash tag per slot in four parallel runs. A set instantiates the value type with something that occupies nothing worth reading, which is what lets one kernel serve both. Move-only: it owns its storage and entries, prohibits copying, and destroys both with ~Table.

Type parameters

Constructors

Table

pub func Table(
    allocator: Allocator,
    seed: TableSeed
) -> Table<K, V>

An empty table that has not allocated anything. allocator is borrowed for the call and kept; seed is read by value. Costs nothing: a table nothing is put into never allocates.

Returns: an empty table that has taken no storage yet

Source

Associated functions

CapacityFor

pub func CapacityFor(length: uint) -> uint ! CollectionError

The smallest power-of-two capacity that holds length entries without passing the three-quarter load factor. length is read by value. Derived from the entry count rather than from the current capacity, so one rule covers growing and settling alike.

Returns: the table size that holds that many entries, or CapacityOverflow when there is none

Source

Methods

Length

pub func Length(self: &Table<K, V>) -> uint

How many entries the table holds. self is borrowed.

Returns: how many entries it holds

Source

Capacity

pub func Capacity(self: &Table<K, V>) -> uint

How many slots the table has. self is borrowed. A power of two, or zero. Not how many entries fit: the load factor keeps a quarter of them free, because a table run fuller than that spends its time displacing entries rather than storing them.

Returns: how many slots it has

Source

IsEmpty

pub func IsEmpty(self: &Table<K, V>) -> bool

Whether the table holds no entries. self is borrowed.

Returns: whether it holds nothing

Source

IsOccupied

pub func IsOccupied(self: &Table<K, V>, index: uint) -> bool

Whether the slot at index holds an entry. self is borrowed. This is what an iteration over the slots asks of each one.

Returns: whether that slot holds an entry

Source

Find

pub func Find(
    self: &Table<K, V>,
    key: K,
    hash: func(K, uint64, uint64) -> uint64,
    equals: func(K, K) -> bool
) -> uint?

The slot holding key, or none when the table does not have it. self is borrowed; key is read by value; hash and equals decide identity and must be the same pair the table was filled with. The seed is handed to hash, so a table's hashes are its own. Stops at the first slot whose occupant is closer to home than the search has travelled: the key would have displaced that occupant on its way past, so it cannot be further along. Runs in constant expected time and allocates nothing.

Returns: the slot the key belongs in, occupied or not

Source

Rehash

pub func Rehash(
    self: &var Table<K, V>,
    capacity: uint,
    hash: func(K, uint64, uint64) -> uint64
) -> ! CollectionError

Rebuilds the table at capacity slots, reinserting every entry. self is borrowed mutably; hash must be the one the table was filled with. A failure leaves the table exactly as it was: the new runs are taken and filled before the old ones are released. Runs in time proportional to the capacity.

Returns: nothing when the operation succeeded, or why it did not

Source

EnsureRoom

pub func EnsureRoom(
    self: &var Table<K, V>,
    hash: func(K, uint64, uint64) -> uint64
) -> ! CollectionError

Makes sure one more entry will fit, growing the table when it will not. self is borrowed mutably; hash must be the one the table was filled with.

Returns: nothing when the operation succeeded, or why it did not

Source

Reserve

pub func Reserve(
    self: &var Table<K, V>,
    additional: uint,
    hash: func(K, uint64, uint64) -> uint64
) -> ! CollectionError

Makes room for additional more entries on top of those already present. self is borrowed mutably; the length does not change. A failure leaves the table exactly as it was.

Returns: nothing when the operation succeeded, or why it did not

Source

ShrinkToFit

pub func ShrinkToFit(
    self: &var Table<K, V>,
    hash: func(K, uint64, uint64) -> uint64
) -> ! CollectionError

Releases the capacity the entry count does not need. self is borrowed mutably. An empty table gives up its storage entirely. A failure leaves the table usable at its current capacity, since failing to hand memory back is never a reason to stop working.

Returns: nothing when the operation succeeded, or why it did not

Source

Clear

pub func Clear(self: &var Table<K, V>)

Destroys every entry, keeping the storage. self is borrowed mutably. Runs in time proportional to the capacity.

Source

Destructor

func ~Table(self: &var Table<K, V>)

Destroys every entry and releases the storage. Runs when the table's life ends. The entries go first and the runs second, since one destroyed after its storage was released would be read from freed memory.

Source

Related

SlotEmpty

pub const SlotEmpty: uint8 = 0;

The state byte of a slot that has never held an entry, and does not now. Distances are stored one higher than they are, so zero can mean empty and nothing else has to.

Source

MaximumProbeDistance

pub const MaximumProbeDistance: uint = 254;

The furthest an entry may sit from home before the table gives up and grows. A byte holds the distance plus one, so 254 is what fits. Reaching it means the hash is doing nothing useful for these keys, and a table that grew would only spread the same collisions over more slots — so the insertion is refused rather than looped on.

Source

MinimumTableCapacity

pub const MinimumTableCapacity: uint = 8;

Eight slots is where a table starts. Below that the load factor rounds away to nothing useful.

Source