Struct HopscotchMap 

pub struct HopscotchMap<K, V, S = FixedState>
where
    K: 'static,
    V: 'static,
{ /* private fields */ }

A concurrent hash map, from the kovan-map crate: see its docs. A concurrent, lock-free hash map based on Hopscotch Hashing.

Implementations

impl<K, V, S> HopscotchMap<K, V, S>

where K: Hash + Eq + Clone + MaybeSend + 'static, V: Clone + MaybeSend + 'static, S: BuildHasher,

pub fn remove_if<Q, F>(&self, key: &Q, pred: F) -> Option<V>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized, F: FnOnce(&V) -> bool,

Removes the key’s entry if pred holds for its value, returning the value removed.

Answers None when the key is absent or pred refused its value, and then changes nothing. Linearizable and exact: pred runs exactly once when the key is present (never when it is absent), on the value the key holds at the operation’s linearization point, while the key’s home is held, so no write of the key lands between the check and the unlink. A slow pred stalls every writer of that home (and a resize) until it returns, and pred must not write to this map (a write to a key of the same home would wait for itself). A pred that panics leaves the map unchanged.

Examples

use kovan_map::HopscotchMap;

let map = HopscotchMap::new();
map.insert(1, 10);
assert_eq!(map.remove_if(&2, |_| true), None); // absent
assert_eq!(map.remove_if(&1, |v| *v > 10), None); // refused, kept
assert_eq!(map.get(&1), Some(10));
assert_eq!(map.remove_if(&1, |v| *v == 10), Some(10));
assert_eq!(map.get(&1), None);

pub fn compare_and_remove<Q>(&self, key: &Q, expected: &V) -> Option<V>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized, V: PartialEq,

Removes the key’s entry if its value equals expected, returning the value removed: remove_if with an equality predicate.

Examples

use kovan_map::HopscotchMap;

let map = HopscotchMap::new();
map.insert("job", 3);
assert_eq!(map.compare_and_remove("job", &4), None);
assert_eq!(map.compare_and_remove("job", &3), Some(3));
assert!(map.is_empty());

pub fn replace_if<F>(&self, key: K, value: V, pred: F) -> Result<V, Option<V>>

where F: FnOnce(&V) -> bool,

Replaces the key’s value with value if pred holds for the present one.

Ok with the value replaced when it replaced; Err(Some(current)) when pred refused the present value current; Err(None) when the key is absent (nothing is inserted). Either Err drops key and value. Linearizable and exact, as remove_if: pred runs exactly once when the key is present, under the key’s home guard, on the value the replace would replace, and the same cautions hold for a slow, writing or panicking pred. Allocates only when it replaces.

Examples

use kovan_map::HopscotchMap;

let map = HopscotchMap::new();
assert_eq!(map.replace_if(1, 20, |_| true), Err(None)); // absent: not inserted
map.insert(1, 10);
assert_eq!(map.replace_if(1, 20, |v| *v > 10), Err(Some(10)));
assert_eq!(map.replace_if(1, 20, |v| *v == 10), Ok(10));
assert_eq!(map.get(&1), Some(20));

pub fn compare_and_swap( &self, key: K, expected: &V, value: V, ) -> Result<V, Option<V>>

where V: PartialEq,

Replaces the key’s value with value if the present one equals expected: replace_if with an equality predicate, answered the same way.

Examples

use kovan_map::HopscotchMap;

let map = HopscotchMap::new();
map.insert(7, 1);
assert_eq!(map.compare_and_swap(7, &2, 3), Err(Some(1)));
assert_eq!(map.compare_and_swap(7, &1, 3), Ok(1));
assert_eq!(map.compare_and_swap(8, &1, 3), Err(None));
assert_eq!(map.get(&7), Some(3));

pub fn compute<F>(&self, key: K, f: F) -> Option<V>

where F: FnOnce(Option<&V>) -> Option<V>,

One atomic read-modify-write of the key: f sees the present value (None when the key is absent) and answers the value the key holds next, Some(new) to insert or replace, None to remove (or leave the key absent). Answers the value the map holds for the key after the call.

f runs exactly once, under the key’s home guard, so no write of the key lands between what f saw and what it wrote: the operation is linearizable. A slow f stalls every writer of that home (and a resize) until it returns, and f must not write to this map (a write to a key of the same home would wait for itself). An f that panics leaves the map unchanged. Allocates only when it links an entry (f answered Some).

Examples

use kovan_map::HopscotchMap;

let hits = HopscotchMap::new();
let bump = |seen: Option<&u32>| Some(seen.map_or(1, |n| n + 1));
assert_eq!(hits.compute("page", bump), Some(1));
assert_eq!(hits.compute("page", bump), Some(2));
// `None` removes the key.
assert_eq!(hits.compute("page", |_| None), None);
assert_eq!(hits.get("page"), None);

impl<K, V, S> HopscotchMap<K, V, S>

where K: Eq + 'static, V: 'static,

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

Returns an iterator over the map entries.

The iterator walks the table that is current when it is created, to its end, even when a resize replaces that table meanwhile (the walk’s position means nothing in another table, whose layout differs). An entry present from the iterator’s creation to its end is yielded exactly once: a resize neither skips nor repeats it, and a displacement, which moves an entry to a higher slot of its neighborhood, links it there before unlinking it from its old slot (so the walk meets it) and the walk recognizes a key it already met there (so it is not repeated). An insert publishes its entry’s hop bit before it links the entry, so an entry the walk finds in a slot is one a lookup finds too. An entry inserted, removed or updated concurrently may or may not be reflected, and no key is yielded twice. The iterator’s own loop (fold, and for_each, count and the other folds built on it) reads a group of slots before it yields their entries, so a write its closure makes is one of those concurrent writes too.

pub fn keys(&self) -> HopscotchKeys<'_, K, V, S>

Returns an iterator over the map keys.

pub fn values(&self) -> HopscotchValues<'_, K, V, S>

Returns an iterator over the map values (clones V).

impl<K, V, S> HopscotchMap<K, V, S>

where K: 'static, V: 'static,

pub fn with_hasher(hasher: S) -> HopscotchMap<K, V, S>

Creates a new HopscotchMap with the specified hasher and default capacity.

pub fn with_capacity_and_hasher( capacity: usize, hasher: S, ) -> HopscotchMap<K, V, S>

Creates a new HopscotchMap with the specified capacity and hasher.

pub fn len(&self) -> usize

Returns the number of elements in the map.

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

pub fn capacity(&self) -> usize

Returns the current capacity of the map.

pub fn hasher(&self) -> &S

Get the underlying hasher.

impl<K, V> HopscotchMap<K, V>

where K: 'static, V: 'static,

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

Creates a new HopscotchMap with default capacity and hasher.

pub fn with_capacity(capacity: usize) -> HopscotchMap<K, V>

Creates a new HopscotchMap with the specified capacity and default hasher.

impl<K, V, S> HopscotchMap<K, V, S>

where K: Hash + Eq + Clone + MaybeSend + 'static, V: Clone + MaybeSend + 'static, S: BuildHasher,

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

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

Returns the value corresponding to the key.

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

Inserts a key-value pair into the map, returning the value it replaced.

Linearizable at the write under the key’s home guard; the answer is exactly the value that write replaced.

pub fn get_or_insert(&self, key: K, value: V) -> V

Returns the value corresponding to the key, or inserts the given value if the key is not present.

Linearizable and exact: of the callers racing for an absent key, the one whose write links the key’s entry (under the key’s home guard) gets its own value back, and every other gets the value it found there (the winner’s, unless a later write already replaced it). A present key is answered by a lookup that takes no guard.

pub fn insert_if_absent(&self, key: K, value: V) -> Option<V>

Insert a key-value pair only if the key does not exist. Returns None if inserted, Some(existing_value) if the key already exists.

Exact: None exactly when this call linked the key’s entry, Some with the value it found under the key’s home guard otherwise; never both, and a resize in flight changes neither (a write that landed is final). A call that finds the key present drops its own key and value, once.

pub fn force_remove<Q>(&self, key: &Q) -> Option<V>

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

Remove all nodes matching key, returning the most recent value if the key was present.

Every write of a home runs under its writer guard, so a key has at most one entry and this removes what remove removes. It keeps removing until a scan finds no match, so the key is absent at the linearization point of the final scan, and it is kept for parity with HashMap::force_remove.

Note: a concurrent insert of the same key can land after the final scan, as with any removal under contention.

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

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

Removes a key from the map, returning the value at the key if the key was previously in the map.

Linearizable at the unlink under the key’s home guard: remove_if with a predicate that always holds, one write path for both.

pub fn clear(&self)

Clears the map, removing all key-value pairs.

pub fn contains_key<Q>(&self, key: &Q) -> bool

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

Returns true if the key is present.

pub fn extend<I>(&self, iter: I)

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

Insert all (K, V) pairs from iter. Takes &self (concurrent map).

Trait Implementations

impl<K, V, S> Clone for HopscotchMap<K, V, S>

where K: Hash + Eq + Clone + MaybeSend + 'static, V: Clone + MaybeSend + 'static, S: BuildHasher + Clone,

A snapshot copy: a new map with the same capacity and a clone of the hasher, populated by inserting a clone of every entry this map held at some point during the walk. Like iter, a concurrent write to self during the clone may or may not be reflected in the result.

fn clone(&self) -> HopscotchMap<K, V, S>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K, V, S> Debug for HopscotchMap<K, V, S>

where K: Eq + Clone + Debug + 'static, V: Clone + Debug + 'static,

A snapshot of the map’s entries, as std::collections::HashMap’s Debug prints its own. Bounded by what the walk needs (owned clones, keys compared to skip one met twice), never by Hash or S: BuildHasher: printing hashes nothing.

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

Formats the value using the given formatter.

impl<K, V, S> Default for HopscotchMap<K, V, S>

where K: 'static, V: 'static, S: Default,

Creates an empty map with S’s default hasher and the default capacity, bounded by exactly what std::collections::HashMap’s Default needs: S: Default (construction never hashes, so K/V carry only the struct’s own 'static, and S needs no BuildHasher either). Not #[cfg(feature = "std")]: unlike HopscotchMap::new (which needs foldhash::fast::FixedState’s std-only default), this is generic over the caller’s own S.

fn default() -> HopscotchMap<K, V, S>

Returns the “default value” for a type.

impl<K, V, S> Drop for HopscotchMap<K, V, S>

fn drop(&mut self)

Executes the destructor for this type.

fn pin_drop(self: Pin<&mut Self>)

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

Execute the destructor for this type, but different to Drop::drop, it requires self to be pinned.

impl<K, V, S> Eq for HopscotchMap<K, V, S>

where K: Hash + Eq + Clone + MaybeSend + 'static, V: Clone + Eq + MaybeSend + 'static, S: BuildHasher,

V: Eq makes the snapshot comparison above reflexive, symmetric and transitive at quiescence, as std::collections::HashMap’s Eq is.

impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HopscotchMap<K, V, S>

where K: Hash + Eq + Copy + MaybeSend + 'static, V: Copy + MaybeSend + 'static, S: BuildHasher,

As std::collections::HashMap’s Extend<(&K, &V)>: K and V copied out of the borrowed pairs, then inserted the same way as the owned-pair impl above.

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

where I: IntoIterator<Item = (&'a K, &'a 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, S> Extend<(K, V)> for HopscotchMap<K, V, S>

where K: Hash + Eq + Clone + MaybeSend + 'static, V: Clone + MaybeSend + 'static, S: BuildHasher,

Inserts every pair, through the same write path HopscotchMap::extend (&self) uses: a &mut self receiver only because Extend requires one, never taken as exclusive access to the map’s own writers.

fn extend<I>(&mut self, iter: 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, S> FromIterator<(K, V)> for HopscotchMap<K, V, S>

where K: Hash + Eq + Clone + MaybeSend + 'static, V: Clone + MaybeSend + 'static, S: BuildHasher + Default,

fn from_iter<I>(iter: I) -> HopscotchMap<K, V, S>

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

Creates a value from an iterator.

impl<K, V, S> IntoIterator for HopscotchMap<K, V, S>

where K: 'static, V: 'static,

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = HopscotchIntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> HopscotchIntoIter<K, V>

Creates an iterator from a value.

impl<'a, K, V, S> IntoIterator for &'a HopscotchMap<K, V, S>

where K: Eq + Clone + 'static, V: Clone + 'static,

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = HopscotchIter<'a, K, V, S>

Which kind of iterator are we turning this into?

fn into_iter(self) -> <&'a HopscotchMap<K, V, S> as IntoIterator>::IntoIter

Creates an iterator from a value.

impl<K, V, S> PartialEq for HopscotchMap<K, V, S>

where K: Hash + Eq + Clone + MaybeSend + 'static, V: Clone + PartialEq + MaybeSend + 'static, S: BuildHasher,

Content equality of a snapshot of each map: the same length and, for every pair this map’s walk found, the other map holding that key with an equal value. Exact at quiescence and best-effort under a concurrent write to either map, the same honesty HopscotchMap::len documents; a lock-free map cannot hold both maps still for the comparison the way an exclusively-borrowed std::collections::HashMap can.

fn eq(&self, other: &HopscotchMap<K, V, S>) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl<K, V, S> RefUnwindSafe for HopscotchMap<K, V, S>

where K: RefUnwindSafe, V: RefUnwindSafe, S: RefUnwindSafe,

impl<K, V, S> Send for HopscotchMap<K, V, S>

where K: Send, V: Send, S: Send,

impl<K, V, S> Sync for HopscotchMap<K, V, S>

where K: Send + Sync, V: Send + Sync, S: Send + Sync,

impl<K, V, S> UnwindSafe for HopscotchMap<K, V, S>

where K: UnwindSafe, V: UnwindSafe, S: UnwindSafe,