Struct LockFreeMap

pub struct LockFreeMap<K, V, H = RandomState> { /* private fields */ }

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

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

pub fn new() -> Map<K, V>

Creates a new Map with the default hasher builder.

pub fn with_incin(incin: SharedIncin<K, V>) -> Map<K, V>

Creates the Map using the given shared incinerator.

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

pub fn iter(&self) -> Iter<'_, K, V>

Creates an iterator over guarded references to the key-value entries.

pub fn iter_mut(&mut self) -> IterMut<'_, K, V>

Creates an iterator over the key-value entries, with a mutable reference to the value.

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.

pub fn clear(&mut self)

Removes all entries. This method might also clear delayed resource destruction. This method cannot be performed in a shared context.

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

where H: BuildHasher,

pub fn with_hasher(builder: H) -> Map<K, V, H>

Creates the Map using the given hasher builder.

pub fn with_hasher_and_incin( builder: H, incin: SharedIncin<K, V>, ) -> Map<K, V, H>

Creates the Map using the given hasher builder and shared incinerator.

pub fn incin(&self) -> SharedIncin<K, V>

The shared incinerator used by this Map.

pub fn hasher(&self) -> &H

The hasher buider used by this Map.

pub fn get<'map, Q>(&'map self, key: &Q) -> Option<ReadGuard<'map, K, V>>

where Q: Hash + Ord + ?Sized, 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.

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.

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”.

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:

1. Removed from any Map using the same SharedIncin as this Map. 2. Removed from an already dead Map with dead SharedIncin. 3. Removed from a Map whose SharedIncin has no sensitive reads active.

If the removed entry does not fit any category, the insertion will fail. Otherwise, insertion cannot fail.

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:

1. Removed from any Map using the same SharedIncin as this Map. 2. Removed from an already dead Map with dead SharedIncin. 3. Removed from a Map whose SharedIncin has no sensitive reads active.

If the removed entry does not fit any category, the insertion will fail. Otherwise, insertion cannot fail.

pub fn remove<Q>(&self, key: &Q) -> Option<Removed<K, V>>

where Q: Hash + Ord + ?Sized, K: Borrow<Q>,

Removes unconditionally the entry identified by the given key. 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.

pub fn remove_with<Q, F>( &self, key: &Q, interactive: F, ) -> Option<Removed<K, V>>

where Q: Hash + Ord + ?Sized, 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.

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

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

where H: Debug,

fn fmt(&self, fmtr: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

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

where H: BuildHasher + Default,

fn default() -> Map<K, V, H>

Returns the “default value” for a type.

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

fn drop(&mut self)

Executes the destructor for this type.

impl<K, V, H> Extend<(K, V)> for Map<K, V, H>

where H: BuildHasher, K: Hash + Ord,

fn extend<I>(&mut self, iterable: I)

where I: IntoIterator<Item = (K, V)>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V, H> FromIterator<(K, V)> for Map<K, V, H>

where H: BuildHasher + Default, K: Hash + Ord,

fn from_iter<I>(iterable: I) -> Map<K, V, H>

where I: IntoIterator<Item = (K, V)>,

Creates a value from an iterator.

impl<'map, K, V, H> IntoIterator for &'map Map<K, V, H>

type Item = ReadGuard<'map, K, V>

The type of the elements being iterated over.

type IntoIter = Iter<'map, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> <&'map Map<K, V, H> as IntoIterator>::IntoIter

Creates an iterator from a value.

impl<'map, K, V, H> IntoIterator for &'map mut Map<K, V, H>

type Item = (&'map K, &'map mut V)

The type of the elements being iterated over.

type IntoIter = IterMut<'map, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> <&'map mut Map<K, V, H> as IntoIterator>::IntoIter

Creates an iterator from a value.

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

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> <Map<K, V, H> as IntoIterator>::IntoIter

Creates an iterator from a value.

impl<K, V> TableIndex<K, V> for Map<K, V>

where K: Hash + Clone + Ord + Send + Sync + 'static, V: Clone + Send + Sync + 'static,

fn insert(&self, key: K, value: V) -> Result<(), (K, V)>

fn peek(&self, key: &K) -> Option<V>

fn remove(&self, key: &K) -> bool

fn iter<'a>(&'a self) -> impl Iterator<Item = (&'a K, &'a V)>

where K: 'a, V: 'a,

fn range<'a, R: RangeBounds<K>>( &'a self, _: R, ) -> impl Iterator<Item = (&'a K, &'a V)>

where K: 'a, V: 'a,

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

where K: Send, V: Send, H: Send,

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

where K: Sync, V: Sync, H: Sync,