pub struct Map<K, V, H = RandomState> { /* private fields */ }
Expand description
A lock-free map. Implemented using multi-level hash-tables (in a tree fashion) with ordered buckets.
Design
In order to implement this map, we shall fix a constant named BITS
, which
should be smaller than the number of bits in the hash (and not 0). We chose
8
for it. Now, we define a table structure: an array of nodes with length
1 << BITS
(256
in this case).
For inserting, we take the first BITS
bits of the hash. Now, we verify
the node. If it is empty, insert a new bucket with our entry (a leaf of the
tree), and assign our hash to the bucket. If there is a branch (i.e. a
sub-table), we shift the hash BITS
bits to the left, but we also keep the
original hash for consultation. Then we try again in the sub-table. If
there is another leaf, and if the hash of the leaf’s bucket is equal to
ours, we insert our entry into the bucket. If the hashes are not equal, we
create a sub-table, insert the old leaf into the new sub-table, and insert
our pair after.
Entries in a bucket are a single linked list ordered by key. The ordering of the list is because of possible race conditions if e.g. new nodes were always inserted at end. And if a bucket is detected to be empty, the table will be requested to delete the bucket.
For searching, in a similar way, the hash is shifted and sub-tables are entered until either a node is empty or a leaf is found. If the hash of the leaf’s bucket is equal to our hash, we search for the entry into the bucket. Because the bucket is ordered, we may know the entry is not present with ease.
Because of limitation of sharing in concurrent contexts, we do return plain references to the entries, neither allow the user to move out removed values, as they must be deinitialized correctly. Instead, we return guarded references to the entries and wrappers over removed entries.
Implementations
sourceimpl<K, V> Map<K, V>
impl<K, V> Map<K, V>
sourcepub fn with_incin(incin: SharedIncin<K, V>) -> Self
pub fn with_incin(incin: SharedIncin<K, V>) -> Self
Creates the Map
using the given shared incinerator.
sourceimpl<K, V, H> Map<K, V, H>
impl<K, V, H> Map<K, V, H>
sourcepub fn iter(&self) -> Iter<'_, K, V> ⓘ
pub fn iter(&self) -> Iter<'_, K, V> ⓘ
Creates an iterator over guarded references to the key-value entries.
sourcepub fn iter_mut(&mut self) -> IterMut<'_, K, V> ⓘ
pub fn iter_mut(&mut self) -> IterMut<'_, K, V> ⓘ
Creates an iterator over the key-value entries, with a mutable reference to the value.
sourcepub fn optimize_space(&mut self)
pub fn optimize_space(&mut self)
Tries to optimize space by removing unnecessary tables without removing any entry. This method might also clear delayed resource destruction. This method cannot be performed in a shared context.
sourceimpl<K, V, H> Map<K, V, H>where
H: BuildHasher,
impl<K, V, H> Map<K, V, H>where
H: BuildHasher,
sourcepub fn with_hasher(builder: H) -> Self
pub fn with_hasher(builder: H) -> Self
Creates the Map
using the given hasher builder.
sourcepub fn with_hasher_and_incin(builder: H, incin: SharedIncin<K, V>) -> Self
pub fn with_hasher_and_incin(builder: H, incin: SharedIncin<K, V>) -> Self
Creates the Map
using the given hasher builder and shared
incinerator.
sourcepub fn incin(&self) -> SharedIncin<K, V>
pub fn incin(&self) -> SharedIncin<K, V>
The shared incinerator used by this Map
.
sourcepub fn get<'map, Q>(&'map self, key: &Q) -> Option<ReadGuard<'map, K, V>>where
Q: ?Sized + Hash + Ord,
K: Borrow<Q>,
pub fn get<'map, Q>(&'map self, key: &Q) -> Option<ReadGuard<'map, K, V>>where
Q: ?Sized + Hash + Ord,
K: Borrow<Q>,
Searches for the entry identified by the given key. The returned value
is a guarded reference. Guarded to ensure no thread deallocates the
allocation for the entry while it is being used. The method accepts
a type resulted from borrowing the stored key. This method will only
work correctly if Hash
and Ord
are implemented in the same way
for the borrowed type and the stored type. If the entry was not
found, None
is returned.
sourcepub fn insert(&self, key: K, val: V) -> Option<Removed<K, V>>where
K: Hash + Ord,
pub fn insert(&self, key: K, val: V) -> Option<Removed<K, V>>where
K: Hash + Ord,
Inserts unconditionally the given key and value. If there was a previously stored value, it is returned.
sourcepub fn insert_with<F>(
&self,
key: K,
interactive: F
) -> Insertion<K, V, (K, Option<V>)>where
K: Hash + Ord,
F: FnMut(&K, Option<&mut V>, Option<&(K, V)>) -> Preview<V>,
pub fn insert_with<F>(
&self,
key: K,
interactive: F
) -> Insertion<K, V, (K, Option<V>)>where
K: Hash + Ord,
F: FnMut(&K, Option<&mut V>, Option<&(K, V)>) -> Preview<V>,
Inserts interactively the given key. A closure is passed to generate
the value part of the entry and validate it with the found value. Even
though the closure may have already accepted some condition, it might
get recalled many times due to concurrent modifications of the Map
.
The first argument passed to the closure is the key passed in first
place. The second argument is an optional mutable reference to a
previously generated value. Obviously, if no value was ever generated,
it is None
. The third argument is a reference to the found stored
entry. Obviously, if no stored entry was found, it is None
. The return
value of the closure is a specification of “what to do with the
insertion now”.
sourcepub fn reinsert(&self, removed: Removed<K, V>) -> Insertion<K, V, Removed<K, V>>where
K: Hash + Ord,
pub fn reinsert(&self, removed: Removed<K, V>) -> Insertion<K, V, Removed<K, V>>where
K: Hash + Ord,
Reinserts a previously removed entry. The entry must have been either:
- Removed from any
Map
using the sameSharedIncin
as thisMap
. 2. Removed from an already deadMap
with deadSharedIncin
. 3. Removed from aMap
whoseSharedIncin
has no sensitive reads active.
If the removed entry does not fit any category, the insertion will fail. Otherwise, insertion cannot fail.
sourcepub fn reinsert_with<F>(
&self,
removed: Removed<K, V>,
interactive: F
) -> Insertion<K, V, Removed<K, V>>where
K: Hash + Ord,
F: FnMut(&(K, V), Option<&(K, V)>) -> bool,
pub fn reinsert_with<F>(
&self,
removed: Removed<K, V>,
interactive: F
) -> Insertion<K, V, Removed<K, V>>where
K: Hash + Ord,
F: FnMut(&(K, V), Option<&(K, V)>) -> bool,
Reinserts interactively a previously removed entry. A closure will be
passed to validate if the conditions are correct for the reinsertion.
The first argument passed to the closure is a reference to the removed
entry, the second argument is a reference to the stored found entry.
Obviously, if no stored entry was found, the argument is None
. The
returned value is a boolean indicating if the reinsertion should go on.
Even though the closure may have already accepted some condition, it
might get recalled many times due to concurrent modifications of the
Map
.
The entry must have been either:
- Removed from any
Map
using the sameSharedIncin
as thisMap
. 2. Removed from an already deadMap
with deadSharedIncin
. 3. Removed from aMap
whoseSharedIncin
has no sensitive reads active.
If the removed entry does not fit any category, the insertion will fail. Otherwise, insertion cannot fail.
sourcepub fn remove<Q>(&self, key: &Q) -> Option<Removed<K, V>>where
Q: ?Sized + Hash + Ord,
K: Borrow<Q>,
pub fn remove<Q>(&self, key: &Q) -> Option<Removed<K, V>>where
Q: ?Sized + Hash + Ord,
K: Borrow<Q>,
sourcepub fn remove_with<Q, F>(&self, key: &Q, interactive: F) -> Option<Removed<K, V>>where
Q: ?Sized + Hash + Ord,
K: Borrow<Q>,
F: FnMut(&(K, V)) -> bool,
pub fn remove_with<Q, F>(&self, key: &Q, interactive: F) -> Option<Removed<K, V>>where
Q: ?Sized + Hash + Ord,
K: Borrow<Q>,
F: FnMut(&(K, V)) -> bool,
Removes interactively the entry identified by the given key. A closure
is passed to validate the removal. The only argument passed to the
closure is a reference to the found entry. The closure returns if the
removal should go on. If no entry was found, None
is returned. This
method will only work correctly if Hash
and Ord
are implemented
in the same way for the borrowed type and the stored type. If the
entry was not found, None
is returned.
sourcepub fn extend<I>(&self, iterable: I)where
I: IntoIterator<Item = (K, V)>,
K: Hash + Ord,
pub fn extend<I>(&self, iterable: I)where
I: IntoIterator<Item = (K, V)>,
K: Hash + Ord,
Acts just like Extend::extend
but does not require mutability.
Trait Implementations
sourceimpl<K, V, H> Default for Map<K, V, H>where
H: BuildHasher + Default,
impl<K, V, H> Default for Map<K, V, H>where
H: BuildHasher + Default,
sourceimpl<K, V, H> Extend<(K, V)> for Map<K, V, H>where
H: BuildHasher,
K: Hash + Ord,
impl<K, V, H> Extend<(K, V)> for Map<K, V, H>where
H: BuildHasher,
K: Hash + Ord,
sourcefn extend<I>(&mut self, iterable: I)where
I: IntoIterator<Item = (K, V)>,
fn extend<I>(&mut self, iterable: I)where
I: IntoIterator<Item = (K, V)>,
sourcefn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)sourcefn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)