Struct scc::hash_index::HashIndex

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

Scalable concurrent hash index.

HashIndex is a concurrent and asynchronous hash map data structure that is optimized for read operations. The key characteristics of HashIndex are similar to that of HashMap except that its read operations are lock-free.

Notes

HashIndex methods are linearizable, however Visitor methods are not; Visitor is only guaranteed to observe events happened before the first call to Iterator::next.

The key differences between HashIndex and HashMap.

• Lock-free-read: read and scan operations do not modify shared data and are never blocked.
• Immutability: the data in the container is immutable until it becomes unreachable.

The key statistics for HashIndex

• The expected size of metadata for a single key-value pair: 2-byte.
• The expected number of atomic write operations required for an operation on a single key: 2.
• The expected number of atomic variables accessed during a single key operation: 2.
• The number of entries managed by a single metadata cell without a linked list: 32.
• The expected maximum linked list length when resize is triggered: log(capacity) / 8.

Implementations

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

pub fn new(capacity: usize, build_hasher: H) -> HashIndex<K, V, H>

Creates an empty HashIndex with the given capacity and build hasher.

The actual capacity is equal to or greater than the given capacity.

Examples

use scc::HashIndex;
use std::collections::hash_map::RandomState;

let hashindex: HashIndex<u64, u32, RandomState> = HashIndex::new(1000, RandomState::new());

let result = hashindex.capacity();
assert_eq!(result, 1024);


let hashindex: HashIndex<u64, u32, _> = HashIndex::default();
let result = hashindex.capacity();
assert_eq!(result, 64);

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 remove<Q>(&self, key_ref: &Q) -> bool where
    K: Borrow<Q>,
    Q: Eq + Hash + ?Sized, 

Removes a key-value pair if the key exists.

This method only marks the entry unreachable, and 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));

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

Removes a key-value pair if the key exists.

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_remove = hashindex.remove_async(&11);

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

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

This method only marks the entry unreachable, and 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));

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

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

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_remove = hashindex.remove_if_async(&11, |_| true);

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

Reads a key-value pair.

It returns None if the key does not exist.

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: FnMut(&'b K, &'b V) -> R>(
    &self,
    key_ref: &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.

It enables the caller to use the value reference outside the method. It returns None if the key does not exist.

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) -> bool where
    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 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 scans the entire array to calculate the number of valid entries, making its time complexity O(N).

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.

It scans the entire array to calculate the number of valid entries, making its time complexity O(N).

Examples

use scc::HashIndex;

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

assert!(hashindex.is_empty());

pub fn capacity(&self) -> usize

Returns the capacity of the HashIndex.

Examples

use scc::HashIndex;
use std::collections::hash_map::RandomState;

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

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<K, V> Default for HashIndex<K, V, RandomState> where
    K: 'static + Clone + Eq + Hash + Sync,
    V: 'static + Clone + Sync, 

fn default() -> Self

Creates a HashIndex with the default parameters.

The default hash builder is RandomState, and the default capacity is 64.

Examples

use scc::HashIndex;

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

let result = hashindex.capacity();
assert_eq!(result, 64);