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
| Name | Description |
|---|---|
K | the key type |
V | the value type |
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.
| Name | Type | Description |
|---|---|---|
allocator | Allocator | where the storage comes from |
seed | TableSeed | the two words that key the hash, which decide the iteration order |
Returns: an empty table that has taken no storage yet
Associated functions
CapacityFor
pub func CapacityFor(length: uint) -> uint throws AllocError
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.
| Name | Type | Description |
|---|---|---|
length | uint | how many elements |
Returns: the table size that holds that many entries, or throws Unsupported when there is none
Methods
Length
pub func Length(&self) -> uint
How many entries the table holds.
self is borrowed.
Returns: how many entries it holds
Capacity
pub func Capacity(&self) -> 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
IsEmpty
pub func IsEmpty(&self) -> bool
Whether the table holds no entries.
self is borrowed.
Returns: whether it holds nothing
IsOccupied
pub func IsOccupied(&self, 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.
| Name | Type | Description |
|---|---|---|
index | uint | which one, counting from zero |
Returns: whether that slot holds an entry
Find
pub func Find(
&self,
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.
| Name | Type | Description |
|---|---|---|
key | K | the key to look up |
hash | func(K, uint64, uint64) -> uint64 | how a key is hashed, taking the key and the two seed words |
equals | func(K, K) -> bool | whether two keys are the same |
Returns: the slot the key belongs in, occupied or not
Rehash
pub unsafe func Rehash(
&var self,
capacity: uint,
hash: func(K, uint64, uint64) -> uint64
)
Rebuilds the table at capacity slots, reinserting every entry.
self is borrowed mutably; hash must be the one the table was filled with. Terminates the program when the
new runs cannot be had; TryRehash reports that instead.
Runs in time proportional to the capacity.
Safety: capacity must be a power of two no smaller than MinimumTableCapacity, as CapacityFor returns:
every slot index is masked by it, so any other value addresses past the runs.
| Name | Type | Description |
|---|---|---|
capacity | uint | how many elements to make room for |
hash | func(K, uint64, uint64) -> uint64 | how a key is hashed, taking the key and the two seed words |
TryRehash
pub unsafe func TryRehash(
&var self,
capacity: uint,
hash: func(K, uint64, uint64) -> uint64
) throws AllocError
Rebuilds the table at capacity slots, reinserting every entry, or throws why the new runs could not be had.
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.
Safety: capacity must be a power of two no smaller than MinimumTableCapacity, as CapacityFor returns:
every slot index is masked by it, so any other value addresses past the runs.
| Name | Type | Description |
|---|---|---|
capacity | uint | how many elements to make room for |
hash | func(K, uint64, uint64) -> uint64 | how a key is hashed, taking the key and the two seed words |
Returns: nothing, or throws the allocator's refusal
EnsureRoom
pub func EnsureRoom(
&var self,
hash: func(K, uint64, uint64) -> uint64
)
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. Terminates the program when the
table cannot grow; TryEnsureRoom reports that instead.
| Name | Type | Description |
|---|---|---|
hash | func(K, uint64, uint64) -> uint64 | how a key is hashed, taking the key and the two seed words |
TryEnsureRoom
pub func TryEnsureRoom(
&var self,
hash: func(K, uint64, uint64) -> uint64
) throws AllocError
Makes sure one more entry will fit, growing the table when it will not, or throws why it could not grow.
self is borrowed mutably; hash must be the one the table was filled with. A failure leaves the table
exactly as it was.
| Name | Type | Description |
|---|---|---|
hash | func(K, uint64, uint64) -> uint64 | how a key is hashed, taking the key and the two seed words |
Returns: nothing, or throws the allocator's refusal
Reserve
pub func Reserve(
&var self,
additional: uint,
hash: func(K, uint64, uint64) -> uint64
)
Makes room for additional more entries on top of those already present.
self is borrowed mutably; the length does not change. Terminates the program when the table cannot grow;
TryReserve reports that instead.
| Name | Type | Description |
|---|---|---|
additional | uint | how many more elements to make room for |
hash | func(K, uint64, uint64) -> uint64 | how a key is hashed, taking the key and the two seed words |
TryReserve
pub func TryReserve(
&var self,
additional: uint,
hash: func(K, uint64, uint64) -> uint64
) throws AllocError
Makes room for additional more entries on top of those already present, or throws why it could not.
self is borrowed mutably; the length does not change. A failure leaves the table exactly as it was.
| Name | Type | Description |
|---|---|---|
additional | uint | how many more elements to make room for |
hash | func(K, uint64, uint64) -> uint64 | how a key is hashed, taking the key and the two seed words |
Returns: nothing, or throws the allocator's refusal
ShrinkToFit
pub func ShrinkToFit(
&var self,
hash: func(K, uint64, uint64) -> uint64
)
Releases the capacity the entry count does not need.
self is borrowed mutably. An empty table gives up its storage entirely. Terminates the program when the
allocator refuses the smaller runs.
| Name | Type | Description |
|---|---|---|
hash | func(K, uint64, uint64) -> uint64 | how a key is hashed, taking the key and the two seed words |
Clear
pub func Clear(&var self)
Destroys every entry, keeping the storage.
self is borrowed mutably. Runs in time proportional to the capacity.
Destructor
func ~Table(&var self)
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.
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.
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.
MinimumTableCapacity
pub const MinimumTableCapacity: uint = 8;
Eight slots is where a table starts. Below that the load factor rounds away to nothing useful.