Struct lockfree::map::Map

pub struct Map<K, V, H = RandomState> { /* fields omitted */ }

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. 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 references to the entries, neither allow the user to move out removed values, as they must be deinitialized correctly. Returning references would also imply pausing the deallocation of sensitive resources for indefinite time.

Methods

impl<K, V> Map<K, V>

pub fn new() -> Self

Creates a new empty map with a random state.

impl<K, V, H> Map<K, V, H>

pub fn with_hasher(builder: H) -> Self where     H: BuildHasher,

Creates a new empty map with a hash builder.

pub fn insert(&self, key: K, val: V) -> Option<Removed<K, V>> where     K: Hash + Ord,     H: BuildHasher,

Sets the mapped value of a key, disregarding it exists or not. If it does exists, the old pair is removed and returned.

pub fn insert_with<F>(     &self,     key: K,     update: F ) -> Insertion<K, V, (K, Option<V>)> where     K: Hash + Ord,     H: BuildHasher,     F: FnMut(&K, Option<&V>, Option<(&K, &V)>) -> Preview<V>,

An interactive insertion. Instead of providing a key and value, one provides a key and a closure. The closure will check the status of the insertion and then return an action. The closure may be called multiple times, as different things are discovered by the map implementation.

The first argument of the closure is the provided key. The second argument of the closure is a value previously generated by the closure, if there is one. The third argument is the stored pair, if there is one. If there was not one, None is passed.

pub fn reinsert(&self, removed: Removed<K, V>) -> Option<Removed<K, V>> where     K: Hash + Ord,     H: BuildHasher,

Reinserts a removed pair (which can have been removed from any map), disregarding the key entry exists or not. If it does exists, the old pair is removed and returned.

pub fn reinsert_with<F>(     &self,     removed: Removed<K, V>,     validate: F ) -> Insertion<K, V, Removed<K, V>> where     K: Hash + Ord,     H: BuildHasher,     F: FnMut(&Removed<K, V>, Option<(&K, &V)>) -> bool,

An interactive reinsertion. A closure and a previously removed entry is provided. The closure will check the status of the insertion and then return whether the condition met with the expected ones. The closure may be called multiple times, as different things are discovered by the map implementation.

The first argument of the closure is the provided removed entry. The second argument is the pair found in the map's stored entry. If there was no entry, None is passed.

pub fn get<Q: ?Sized, F, T>(&self, key: &Q, reader: F) -> Option<T> where     Q: Hash + Ord,     K: Borrow<Q>,     H: BuildHasher,     F: FnOnce(&V) -> T,

Gets a reference to the mapped value of a key, it exists. Then, it calls the reader function argument with the reference. Please note that returning a reference would imply in pausing any sensitive incinerator resource deallocation for indefinite time.

pub fn get_pair<Q: ?Sized, F, T>(&self, key: &Q, reader: F) -> Option<T> where     Q: Hash + Ord,     K: Borrow<Q>,     H: BuildHasher,     F: FnOnce(&K, &V) -> T,

Same as get, but calls the reader function argument with key and value, respectively, instead.

pub fn remove<Q: ?Sized>(&self, key: &Q) -> Option<Removed<K, V>> where     Q: Hash + Ord,     K: Borrow<Q>,     H: BuildHasher,

Removes the given entry identified by the given key.

Important traits for Iter<'map, K, V, R>

impl<'map, K, V, R> Iterator for Iter<'map, K, V, R> where
    R: IterReader<K, V>,  type Item = R::Out;

pub fn iter<'map, F, T>(&'map self, reader: F) -> Iter<'map, K, V, F> where     F: FnMut(&K, &V) -> T,

Iterates over the map with a given reader. The reader must be a function/closure. This methods is just a specific version of iter_with_reader due to Rust limitations on inference of closures polymorphic on lifetimes.

Important traits for Iter<'map, K, V, R>

impl<'map, K, V, R> Iterator for Iter<'map, K, V, R> where
    R: IterReader<K, V>,  type Item = R::Out;

pub fn iter_with_reader<'map, R>(&'map self, reader: R) -> Iter<'map, K, V, R> where     R: IterReader<K, V>,

Iterates over the map with a given reader. The reader may be a closure, primitive function, or any other type that implements the reader trait.

Important traits for &'a mut R

impl<'a, R> Read for &'a mut R where
    R: Read + ?Sized, impl<'a, W> Write for &'a mut W where
    W: Write + ?Sized, impl<'a, I> Iterator for &'a mut I where
    I: Iterator + ?Sized,  type Item = <I as Iterator>::Item;

pub fn hasher(&self) -> &H

The hasher builder with which this map was created.

pub fn remove_unneeded_tables(&mut self)

Removes any unnecessary sub-table. This operation cannot be performed with a shared map, and the mutable reference required by this method ensures that.

Trait Implementations

impl<K, V, H> Drop for Map<K, V, H>

fn drop(&mut self)

Executes the destructor for this type.

impl<K, V, H> Default for Map<K, V, H> where     H: BuildHasher + Default,

fn default() -> Self

Returns the "default value" for a type.

impl<K, V, H> Send for Map<K, V, H> where     K: Send + Sync,     V: Send + Sync,     H: Send,

impl<K, V, H> Sync for Map<K, V, H> where     K: Send + Sync,     V: Send + Sync,     H: Sync,

impl<K, V, H> Debug for Map<K, V, H> where     H: Debug,

fn fmt(&self, fmtr: &mut Formatter) -> Result

Formats the value using the given formatter.