Struct scc::hash_index::Reserve

pub struct Reserve<'h, K, V, H = RandomState>where
    K: 'static + Clone + Eq + Hash,
    V: 'static + Clone,
    H: BuildHasher,{ /* private fields */ }

Reserve keeps the capacity of the associated HashIndex higher than a certain level.

The HashIndex does not shrink the capacity below the reserved capacity.

Implementations

impl<'h, K, V, H> Reserve<'h, K, V, H>where K: 'static + Clone + Eq + Hash, V: 'static + Clone, H: BuildHasher,

pub fn additional_capacity(&self) -> usize

Returns the number of reserved slots.

Methods from Deref<Target = HashIndex<K, V, H>>

pub fn reserve( &self, additional_capacity: usize ) -> Option<Reserve<'_, K, V, H>>

Temporarily increases the minimum capacity of the HashIndex.

A Reserve is returned if the HashIndex could increase the minimum capacity while the increased capacity is not exclusively owned by the returned Reserve, allowing others to benefit from it. The memory for the additional space may not be immediately allocated if the HashIndex is empty or currently being resized, however once the memory is reserved eventually, the capacity will not shrink below the additional capacity until the returned Reserve is dropped.

Errors

Returns None if a too large number is given.

Examples

use scc::HashIndex;

let hashindex: HashIndex<usize, usize> = HashIndex::with_capacity(1000);
assert_eq!(hashindex.capacity(), 1024);

let reserved = hashindex.reserve(10000);
assert!(reserved.is_some());
assert_eq!(hashindex.capacity(), 16384);

assert!(hashindex.reserve(usize::MAX).is_none());
assert_eq!(hashindex.capacity(), 16384);

for i in 0..16 {
    assert!(hashindex.insert(i, i).is_ok());
}
drop(reserved);

assert_eq!(hashindex.capacity(), 1024);

pub fn entry(&self, key: K) -> Entry<'_, K, V, H>

Gets the entry associated with the given key in the map for in-place manipulation.

Examples

use scc::HashIndex;

let hashindex: HashIndex<char, u32> = HashIndex::default();

for ch in "a short treatise on fungi".chars() {
    unsafe {
        hashindex.entry(ch).and_modify(|counter| *counter += 1).or_insert(1);
    }
}

assert_eq!(hashindex.read(&'s', |_, v| *v), Some(2));
assert_eq!(hashindex.read(&'t', |_, v| *v), Some(3));
assert!(hashindex.read(&'y', |_, v| *v).is_none());

pub async fn entry_async(&self, key: K) -> Entry<'_, K, V, H>

Gets the entry associated with the given key in the map for in-place manipulation.

It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashIndex;

let hashindex: HashIndex<char, u32> = HashIndex::default();

let future_entry = hashindex.entry_async('b');

pub fn first_occupied_entry(&self) -> Option<OccupiedEntry<'_, K, V, H>>

Gets the first occupied entry for in-place manipulation.

The returned OccupiedEntry in combination with OccupiedEntry::next or OccupiedEntry::next_async can act as a mutable iterator over entries.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.insert(1, 0).is_ok());

let mut first_entry = hashindex.first_occupied_entry().unwrap();
unsafe {
    *first_entry.get_mut() = 2;
}

assert!(first_entry.next().is_none());
assert_eq!(hashindex.read(&1, |_, v| *v), Some(2));

pub async fn first_occupied_entry_async( &self ) -> Option<OccupiedEntry<'_, K, V, H>>

Gets the first occupied entry for in-place manipulation.

The returned OccupiedEntry in combination with OccupiedEntry::next or OccupiedEntry::next_async can act as a mutable iterator over entries.

It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashIndex;

let hashindex: HashIndex<char, u32> = HashIndex::default();

let future_entry = hashindex.first_occupied_entry_async();

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

Inserts a key-value pair into the HashIndex.

Errors

Returns an error along with the supplied key-value pair if the key exists.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.insert(1, 0).is_ok());
assert_eq!(hashindex.insert(1, 1).unwrap_err(), (1, 1));

pub async fn insert_async(&self, key: K, val: V) -> Result<(), (K, V)>

Inserts a key-value pair into the HashIndex.

It is an asynchronous method returning an impl Future for the caller to await.

Errors

Returns an error along with the supplied key-value pair if the key exists.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();
let future_insert = hashindex.insert_async(11, 17);

pub fn modify<Q, F, R>(&self, key: &Q, updater: F) -> boolwhere K: Borrow<Q>, Q: Eq + Hash + ?Sized, F: FnOnce(&K, &V) -> R, R: Into<ModifyAction<V>>,

Modifies the existing entry associated with the specified key.

The return value of the supplied closure denotes the type of an action this method should take. The closure may return ModifyAction or Option<new_version> where the type of new_version is Option<V>.

To be specific, this method takes either one of the following actions if the key exists.

• Do nothing if ModifyAction::Keep or None is returned from the supplied closure.
• Remove the entry if ModifyAction::Remove or Some(None) is returned from the supplied closure.
• A new version of the entry is created with the current version removed if the supplied closure returns ModifyAction::Update or Some(Some(new_value)).

Returns true if the entry was either removed or updated; in other words, false is returned if the key does not exist or the entry was not removed and updated.

Examples

use scc::hash_index::ModifyAction;
use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(unsafe { hashindex.update(&1, |_, _| true).is_none() });
assert!(hashindex.insert(1, 0).is_ok());

assert!(!hashindex.modify(&0, |_, v| Some(Some(1))));
assert!(hashindex.modify(&1, |_, v| ModifyAction::Update(1)));
assert_eq!(hashindex.read(&1, |_, v| *v).unwrap(), 1);

assert!(hashindex.modify(&1, |_, v| ModifyAction::Remove));
assert!(hashindex.read(&1, |_, v| *v).is_none());

pub async fn modify_async<Q, F, R>(&self, key: &Q, updater: F) -> boolwhere K: Borrow<Q>, Q: Eq + Hash + ?Sized, F: FnOnce(&K, &V) -> R, R: Into<ModifyAction<V>>,

Modifies the existing entry associated with the specified key.

The return value of the supplied closure denotes the type of an action this method should take. The closure may return ModifyAction or Option<new_version> where the type of new_version is Option<V>.

To be specific, this method takes either one of the following actions if the key exists.

• Do nothing if ModifyAction::Keep or None is returned from the supplied closure.
• Remove the entry if ModifyAction::Remove or Some(None) is returned from the supplied closure.
• A new version of the entry is created with the current version removed if the supplied closure returns ModifyAction::Update or Some(Some(new_value)).

Returns true if the entry was either removed or updated; in other words, false is returned if the key does not exist or the entry was not removed and updated. It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::hash_index::ModifyAction;
use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.insert(1, 0).is_ok());
let future_update = hashindex.modify_async(&1, |_, v| Some(Some(2)));
let future_remove = hashindex.modify_async(&1, |_, v| ModifyAction::Remove);

pub unsafe fn update<Q, F, R>(&self, key: &Q, updater: F) -> Option<R>where K: Borrow<Q>, Q: Eq + Hash + ?Sized, F: FnOnce(&K, &mut V) -> R,

Updates the existing value corresponding to the key.

Returns None if the key does not exist.

Safety

The caller has to make sure that there are no readers of the entry, e.g., a reader keeping a reference to the entry via HashIndex::iter, HashIndex::read, or HashIndex::read_with, unless an instance of V can be safely read when there is a single writer, e.g., V = [u8; 32].

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(unsafe { hashindex.update(&1, |_, _| true).is_none() });
assert!(hashindex.insert(1, 0).is_ok());
assert_eq!(unsafe { hashindex.update(&1, |_, v| { *v = 2; *v }).unwrap() }, 2);
assert_eq!(hashindex.read(&1, |_, v| *v).unwrap(), 2);

pub async unsafe fn update_async<Q, F, R>( &self, key: &Q, updater: F ) -> Option<R>where K: Borrow<Q>, Q: Eq + Hash + ?Sized, F: FnOnce(&K, &mut V) -> R,

Updates the existing value corresponding to the key.

Returns None if the key does not exist. It is an asynchronous method returning an impl Future for the caller to await.

Safety

The caller has to make sure that there are no readers of the entry, e.g., a reader keeping a reference to the entry via HashIndex::iter, HashIndex::read, or HashIndex::read_with, unless an instance of V can be safely read when there is a single writer, e.g., V = [u8; 32].

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.insert(1, 0).is_ok());
let future_update = unsafe { hashindex.update_async(&1, |_, v| { *v = 2; *v }) };

pub fn remove<Q>(&self, key: &Q) -> boolwhere K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Removes a key-value pair if the key exists.

Returns false if the key does not exist.

Returns true if the key existed and the condition was met after marking the entry unreachable; the memory will be reclaimed later.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(!hashindex.remove(&1));
assert!(hashindex.insert(1, 0).is_ok());
assert!(hashindex.remove(&1));
assert_eq!(hashindex.capacity(), 0);

pub async fn remove_async<Q>(&self, key: &Q) -> boolwhere K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Removes a key-value pair if the key exists.

Returns false if the key does not exist. It is an asynchronous method returning an impl Future for the caller to await.

Returns true if the key existed and the condition was met after marking the entry unreachable; the memory will be reclaimed later.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();
let future_insert = hashindex.insert_async(11, 17);
let future_remove = hashindex.remove_async(&11);

pub fn remove_if<Q, F: FnOnce(&V) -> bool>(&self, key: &Q, condition: F) -> boolwhere K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Removes a key-value pair if the key exists and the given condition is met.

Returns false if the key does not exist or the condition was not met.

Returns true if the key existed and the condition was met after marking the entry unreachable; the memory will be reclaimed later.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.insert(1, 0).is_ok());
assert!(!hashindex.remove_if(&1, |v| *v == 1));
assert!(hashindex.remove_if(&1, |v| *v == 0));
assert_eq!(hashindex.capacity(), 0);

pub async fn remove_if_async<Q, F: FnOnce(&V) -> bool>( &self, key: &Q, condition: F ) -> boolwhere K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Removes a key-value pair if the key exists and the given condition is met.

Returns false if the key does not exist or the condition was not met. It is an asynchronous method returning an impl Future for the caller to await.

Returns true if the key existed and the condition was met after marking the entry unreachable; the memory will be reclaimed later.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();
let future_insert = hashindex.insert_async(11, 17);
let future_remove = hashindex.remove_if_async(&11, |_| true);

pub fn get<Q>(&self, key: &Q) -> Option<OccupiedEntry<'_, K, V, H>>where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Gets an occupied entry corresponding to the key.

Returns None if the key does not exist.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.get(&1).is_none());
assert!(hashindex.insert(1, 10).is_ok());
assert_eq!(*hashindex.get(&1).unwrap().get(), 10);

pub async fn get_async<Q>(&self, key: &Q) -> Option<OccupiedEntry<'_, K, V, H>>where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Gets an occupied entry corresponding to the key.

Returns None if the key does not exist. It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();
let future_insert = hashindex.insert_async(11, 17);
let future_get = hashindex.get_async(&11);

pub fn read<Q, R, F: FnOnce(&K, &V) -> R>( &self, key: &Q, reader: F ) -> Option<R>where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Reads a key-value pair.

Returns None if the key does not exist. This method is not linearizable; the key-value pair being read by this method can be removed from the container or copied to a different memory location.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.read(&1, |_, v| *v).is_none());
assert!(hashindex.insert(1, 10).is_ok());
assert_eq!(hashindex.read(&1, |_, v| *v).unwrap(), 10);

pub fn read_with<'b, Q, R, F: FnOnce(&'b K, &'b V) -> R>( &self, key: &Q, reader: F, barrier: &'b Barrier ) -> Option<R>where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Reads a key-value pair using the supplied Barrier.

Returns None if the key does not exist. It enables the caller to use the value reference outside the method. This method is not linearizable; the key-value pair being read by this method can be removed from the container or copied to a different memory location.

Examples

use scc::ebr::Barrier;
use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.insert(1, 10).is_ok());

let barrier = Barrier::new();
let value_ref = hashindex.read_with(&1, |k, v| v, &barrier).unwrap();
assert_eq!(*value_ref, 10);

pub fn contains<Q>(&self, key: &Q) -> boolwhere K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Checks if the key exists.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(!hashindex.contains(&1));
assert!(hashindex.insert(1, 0).is_ok());
assert!(hashindex.contains(&1));

pub fn retain<F: FnMut(&K, &V) -> bool>(&self, pred: F) -> (usize, usize)

Retains the entries specified by the predicate.

Entries that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same entry can be visited more than once if the HashIndex gets resized by another thread.

Returns (number of remaining entries, number of removed entries) where the number of remaining entries can be larger than the actual number since the same entry can be visited more than once.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.insert(1, 0).is_ok());
assert!(hashindex.insert(2, 1).is_ok());
assert!(hashindex.insert(3, 2).is_ok());

assert_eq!(hashindex.retain(|k, v| *k == 1 && *v == 0), (1, 2));

pub async fn retain_async<F: FnMut(&K, &V) -> bool>( &self, pred: F ) -> (usize, usize)

Retains the entries specified by the predicate.

Entries that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same entry can be visited more than once if the HashIndex gets resized by another thread.

Returns (number of remaining entries, number of removed entries) where the number of remaining entries can be larger than the actual number since the same entry can be visited more than once. It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

let future_insert = hashindex.insert_async(1, 0);
let future_retain = hashindex.retain_async(|k, v| *k == 1);

pub fn clear(&self) -> usize

Clears all the key-value pairs.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.insert(1, 0).is_ok());
assert_eq!(hashindex.clear(), 1);

pub async fn clear_async(&self) -> usize

Clears all the key-value pairs.

It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

let future_insert = hashindex.insert_async(1, 0);
let future_retain = hashindex.clear_async();

pub fn len(&self) -> usize

Returns the number of entries in the HashIndex.

It reads the entire metadata area of the bucket array to calculate the number of valid entries, making its time complexity O(N). Furthermore, it may overcount entries if an old bucket array has yet to be dropped.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.insert(1, 0).is_ok());
assert_eq!(hashindex.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the HashIndex is empty.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.is_empty());
assert!(hashindex.insert(1, 0).is_ok());
assert!(!hashindex.is_empty());

pub fn capacity(&self) -> usize

Returns the capacity of the HashIndex.

Examples

use scc::HashIndex;

let hashindex_default: HashIndex<u64, u32> = HashIndex::default();
assert_eq!(hashindex_default.capacity(), 0);

assert!(hashindex_default.insert(1, 0).is_ok());
assert_eq!(hashindex_default.capacity(), 64);

let hashindex: HashIndex<u64, u32> = HashIndex::with_capacity(1000000);
assert_eq!(hashindex.capacity(), 1048576);

pub fn capacity_range(&self) -> RangeInclusive<usize>

Returns the current capacity range of the HashIndex.

Examples

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert_eq!(hashindex.capacity_range(), 0..=(1_usize << (usize::BITS - 1)));

let reserved = hashindex.reserve(1000);
assert_eq!(hashindex.capacity_range(), 1000..=(1_usize << (usize::BITS - 1)));

pub fn iter<'h, 'b>(&'h self, barrier: &'b Barrier) -> Visitor<'h, 'b, K, V, H>

Returns a Visitor that iterates over all the entries in the HashIndex.

It is guaranteed to go through all the key-value pairs pertaining in the HashIndex at the moment, however the same key-value pair can be visited more than once if the HashIndex is being resized.

It requires the user to supply a reference to a Barrier.

Examples

use scc::ebr::Barrier;
use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.insert(1, 0).is_ok());

let barrier = Barrier::new();

let mut iter = hashindex.iter(&barrier);
let entry_ref = iter.next().unwrap();
assert_eq!(iter.next(), None);

for iter in hashindex.iter(&barrier) {
    assert_eq!(iter, (&1, &0));
}

drop(hashindex);

assert_eq!(entry_ref, (&1, &0));

Trait Implementations

impl<'h, K, V, H> AsRef<HashIndex<K, V, H>> for Reserve<'h, K, V, H>where K: 'static + Clone + Eq + Hash, V: 'static + Clone, H: BuildHasher,

fn as_ref(&self) -> &HashIndex<K, V, H>

Converts this type into a shared reference of the (usually inferred) input type.

impl<'h, K, V, H> Debug for Reserve<'h, K, V, H>where K: 'static + Clone + Eq + Hash, V: 'static + Clone, H: BuildHasher,

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

Formats the value using the given formatter.

impl<'h, K, V, H> Deref for Reserve<'h, K, V, H>where K: 'static + Clone + Eq + Hash, V: 'static + Clone, H: BuildHasher,

type Target = HashIndex<K, V, H>

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<'h, K, V, H> Drop for Reserve<'h, K, V, H>where K: 'static + Clone + Eq + Hash, V: 'static + Clone, H: BuildHasher,

fn drop(&mut self)

Executes the destructor for this type.