HashMap<K, V> structv0.1.0

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

Move-only: it owns its entries and storage and prohibits copying.

Type parameters

Constructors

HashMap

pub func HashMap(
    allocator: Allocator,
    hash: func(K, uint64, uint64) -> uint64,
    equals: func(K, K) -> bool
) -> HashMap<K, V>

An empty map that has not allocated anything, with a seed drawn from the operating system. allocator is borrowed for the call and kept. A program making many maps should draw one seed with TableSeed::Random and use WithSeed, since each draw here is a system call.

Returns: an empty collection that has taken no storage yet

Source

Associated functions

WithSeed

pub func WithSeed(
    allocator: Allocator,
    seed: TableSeed,
    hash: func(K, uint64, uint64) -> uint64,
    equals: func(K, K) -> bool
) -> HashMap<K, V>

An empty map that has not allocated anything, hashing with seed. allocator is borrowed for the call and kept; seed is read by value. Two maps sharing a seed hash alike, which is what a caller drawing one seed for many maps wants and what a test needing the same table twice needs.

Returns: an empty map keyed with that seed

Source

WithCapacity

pub func WithCapacity(
    allocator: Allocator,
    capacity: uint,
    hash: func(K, uint64, uint64) -> uint64,
    equals: func(K, K) -> bool
) -> HashMap<K, V> ! CollectionError

An empty map with room for capacity entries already taken. The capacity actually taken is rounded up to a power of two above the load factor, so it is larger than asked for.

Returns: an empty map with room for that many entries already taken

Source

Methods

Length

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

How many entries the map holds.

Returns: how many entries it holds

Source

Capacity

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

How many slots the table has. Not how many entries fit: a quarter of the slots are kept free, because a table run fuller spends its time displacing entries rather than storing them.

Returns: how many entries fit before the next growth

Source

IsEmpty

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

Whether the map holds no entries.

Returns: whether it holds nothing

Source

ContainsKey

pub func ContainsKey(self: &HashMap<K, V>, key: K) -> bool

Whether the map has an entry for key. self is borrowed; key is read by value. Runs in constant expected time and allocates nothing.

Returns: whether an entry with that key is present

Source

Get

pub func Get(self: &HashMap<K, V>, key: K) -> V?

The value stored under key, or none when there is no such entry. self is borrowed; the value is returned by copy.

Returns: a copy of the value, or none when the key is absent

Source

Reference

pub func Reference(self: &HashMap<K, V>, key: K) -> (*V)?

A pointer to the value stored under key, or none when there is no such entry. self is borrowed; the pointer borrows the value where it sits, which is how one that owns something is read without being taken. The pointer is valid until the map grows, shrinks, or has anything inserted or removed.

Returns: the address of the value, or none when the key is absent

Source

TryReferenceMutable

pub func TryReferenceMutable(
    self: &var HashMap<K, V>,
    key: K,
    value: *var *var V
) -> bool

Points value at the stored value for key, so it can be changed in place. self is borrowed mutably; value receives the pointer and is left alone when there is no such entry. Reports whether there was one. An out-parameter rather than an (*var V)?, which does not survive lowering inside a generic today. The pointer is valid until the map grows, shrinks, or has anything inserted or removed. Overwriting through it replaces the value without destroying what was there.

Returns: whether the key was present

Source

Insert

pub func Insert(
    self: &var HashMap<K, V>,
    key: K,
    value: V
) -> ! CollectionError

Stores value under key, replacing whatever was there. self is borrowed mutably; both are moved in. A key already present keeps its stored key and takes the new value, and the value it had is destroyed — use Remove first where the old one is wanted. A failure leaves the map exactly as it was and both arguments with the caller. Runs in constant expected time.

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

Source

Remove

pub func Remove(self: &var HashMap<K, V>, key: K) -> V?

Takes the entry for key out and hands back its value. self is borrowed mutably. The value is moved out rather than destroyed, so one that owns something leaves intact; the key is destroyed, having no other owner. Reports none when there is no such entry. The gap closes behind the entry, so the table is left exactly as if it had never been inserted. Runs in constant expected time.

Returns: the value that was stored, or none when the key was absent

Source

Reserve

pub func Reserve(
    self: &var HashMap<K, V>,
    additional: uint
) -> ! 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 map exactly as it was.

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

Source

ShrinkToFit

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

Releases the capacity the entry count does not need. self is borrowed mutably. An empty map gives up its storage entirely.

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

Source

Clear

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

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

Source

TryNextEntry

pub func TryNextEntry(
    self: &HashMap<K, V>,
    cursor: *var uint,
    key: *var K,
    value: *var V
) -> bool

Walks to the next occupied slot at or after cursor, reporting the entry it holds. self is borrowed; cursor is read and advanced past whatever is reported, so a caller starts it at zero and keeps calling. key and value receive copies and are left alone when this reports false. The order is the table's, which is the seed's and not the insertion's. Nothing may be inserted or removed while a walk is in progress: either moves entries between slots, and a cursor is a slot.

Returns: whether an entry was read; false at the end

Source

GetOrInsert

pub func GetOrInsert(
    self: &var HashMap<K, V>,
    key: K,
    value: V,
    existing: *var *var V,
    inserted: *var bool
) -> ! CollectionError

Points existing at the value stored under key, inserting value first when there is none. self is borrowed mutably; key and value are moved in only when there was no entry, and destroyed otherwise — the map keeps what it already had. existing receives a pointer to the stored value either way, and inserted receives whether the map grew; both may be null. This is what an entry API is for, without pretending Rux has closures: a caller that wants to read a value or put one there gets one operation instead of a lookup followed by an insertion, and does not have to name the key twice. A failure leaves the map exactly as it was. The pointer is valid until the map grows, shrinks, or has anything inserted or removed.

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

Source

Replace

pub func Replace(
    self: &var HashMap<K, V>,
    key: K,
    value: V
) -> V? ! CollectionError

Stores value under key and hands back the value that was there. self is borrowed mutably; both are moved in. The old value is moved out rather than destroyed, which is the difference between this and Insert: one hands the previous value back and the other throws it away. Reports none when there was no entry, having inserted this one. A failure leaves the map exactly as it was, and is reported apart from the absence.

Returns: the value that was there, or none when the key was absent

Source

RemoveEntry

pub func RemoveEntry(
    self: &var HashMap<K, V>,
    key: K
) -> KeyValue<K, V>?

Takes the entry for key out and hands back both halves of it. self is borrowed mutably. Both the stored key and the value are moved out, so a key that owns something leaves intact too — which Remove does not offer, since it destroys the key. Reports none when there is no such entry. The stored key is handed back rather than the one that was looked up: the two compare equal, but a key type carrying anything the equality ignores makes them different values, and the map's is the one that was kept.

Returns: the whole entry, or none when the key was absent

Source

Iterate

pub func Iterate(self: &HashMap<K, V>) -> HashMapIterator<K, V>

An iterator over the entries, by copy. self is borrowed and must outlive the iterator. This is the method a for loop finds. The order is the table's, which is the seed's and not the insertion's. Nothing may be inserted or removed while the iterator is alive.

Returns: a cursor over the entries, in an order the seed decides

Source

IntoIterator

pub func IntoIterator(self: HashMap<K, V>) -> HashMapIntoIterator<K, V>

Takes the map apart into an iterator over its entries. Consumes the map: it is moved into the iterator, and the storage goes with it, so nothing is copied and nothing is reallocated. Each entry comes out by value, which is how one whose key or value owns something leaves. Whatever is not taken is destroyed when the iterator's life ends.

Returns: a cursor that consumes the map as it goes

Source

Related

HashMapIterator<K, V>

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

An iterator over the entries of a map, by copy. Borrows the map, so the map must outlive it and must not be inserted into or removed from while it is alive: either moves entries between slots, and this walks slots.

Source

Type parameters

Implements Iterator

HashMapIterator<K, V> conforms to Iterator.

Next

pub func Next(self: &var HashMapIterator<K, V>) -> KeyValue<K, V>?

The next entry, or none once every slot has been looked at. self is borrowed mutably and advanced. The key and value are copies; a map of things that own something is walked with TryNextEntry and a pointer instead.

Returns: the next entry, or none at the end

Source

HashMapIntoIterator<K, V>

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

An iterator that takes a map apart, yielding each entry by value. Move-only: it owns the storage the map owned. Whatever is left when its life ends is destroyed with it, which is what makes stopping part-way safe.

Source

Type parameters

Implements Iterator

HashMapIntoIterator<K, V> conforms to Iterator.

Next

pub func Next(self: &var HashMapIntoIterator<K, V>) -> KeyValue<K, V>?

The next entry, moved out, or none once every slot has been looked at. self is borrowed mutably and advanced. The slot is emptied as the entry leaves, so what remains for the destructor is exactly what nobody took.

Returns: the next entry, or none at the end

Source

WriteHashMapDebug<K, V>

pub func WriteHashMapDebug<K: Debug, V: Debug>(
    writer: &var TextWriter,
    value: &HashMap<K, V>,
    spec: FormatSpec
) -> ! FormatError

Writes a borrowed hash map as {key: value, key: value}. An empty map is {}. Braces rather than brackets, because a map is not a run of elements and reading its rendering as one would be reading it wrongly. The order is the table's, which follows from the seed the map was made with and from every insertion and removal since — so it is not the insertion order, it does not hold between two maps with the same entries, and it changes between runs of the same program. Nothing here sorts, since that would need an ordering on the key that a hash map does not have. TreeMap is the container whose rendering is stable. Every key and value is shown through a borrow of it, so a map of move-only entries is shown without taking one out. spec is handed to each of them unchanged. Reports whatever the writer or an entry's implementation reported, stopping at the first refusal.

Source

Type parameters

Parameters

Returns: success when the whole rendering was accepted