Struct scc::hash_index::HashIndex
source · [−]pub struct HashIndex<K, V, H = RandomState> where
K: 'static + Clone + Eq + Hash + Sync,
V: 'static + Clone + Sync,
H: BuildHasher, { /* private fields */ }
Expand description
Scalable concurrent hash index data structure.
HashIndex
is a concurrent hash index data structure that is optimized for read
operations. The key characteristics of HashIndex
are similar to that of
HashMap
.
The key differences between HashIndex
and HashMap
.
- Lock-free-read: read and scan operations do not modify shared data.
- Immutability: the data in the container is treated 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 operations required for an operation on a single key: 2.
- The expected number of atomic variables accessed during a single key operation: 1.
- 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
sourceimpl<K, V, H> HashIndex<K, V, H> where
K: 'static + Clone + Eq + Hash + Sync,
V: 'static + Clone + Sync,
H: BuildHasher,
impl<K, V, H> HashIndex<K, V, H> where
K: 'static + Clone + Eq + Hash + Sync,
V: 'static + Clone + Sync,
H: BuildHasher,
sourcepub fn new(capacity: usize, build_hasher: H) -> HashIndex<K, V, H>
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.
Panics
Panics if memory allocation fails.
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);
sourcepub fn insert(&self, key: K, val: V) -> Result<(), (K, V)>
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.
Panics
Panics if memory allocation fails, or the number of entries in the target cell reaches
u32::MAX
.
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));
sourcepub fn remove<Q>(&self, key_ref: &Q) -> bool where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
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));
sourcepub fn remove_if<Q, F: FnOnce(&V) -> bool>(
&self,
key_ref: &Q,
condition: F
) -> bool where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
pub fn remove_if<Q, F: FnOnce(&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));
sourcepub fn read<Q, R, F: FnOnce(&K, &V) -> R>(
&self,
key_ref: &Q,
reader: F
) -> Option<R> where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
pub fn read<Q, R, F: FnOnce(&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);
sourcepub fn read_with<'b, Q, R, F: FnOnce(&'b K, &'b V) -> R>(
&self,
key_ref: &Q,
reader: F,
barrier: &'b Barrier
) -> Option<R> where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
pub fn read_with<'b, Q, R, F: FnOnce(&'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);
sourcepub fn contains<Q>(&self, key: &Q) -> bool where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
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));
sourcepub fn clear(&self) -> usize
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);
sourcepub fn len(&self) -> usize
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);
sourcepub fn iter<'h, 'b>(&'h self, barrier: &'b Barrier) -> Visitor<'h, 'b, K, V, H>ⓘNotable traits for Visitor<'h, 'b, K, V, H>impl<'h, 'b, K, V, H> Iterator for Visitor<'h, 'b, K, V, H> where
K: 'static + Clone + Eq + Hash + Sync,
V: 'static + Clone + Sync,
H: 'static + BuildHasher, type Item = (&'b K, &'b V);
pub fn iter<'h, 'b>(&'h self, barrier: &'b Barrier) -> Visitor<'h, 'b, K, V, H>ⓘNotable traits for Visitor<'h, 'b, K, V, H>impl<'h, 'b, K, V, H> Iterator for Visitor<'h, 'b, K, V, H> where
K: 'static + Clone + Eq + Hash + Sync,
V: 'static + Clone + Sync,
H: 'static + BuildHasher, type Item = (&'b K, &'b V);
K: 'static + Clone + Eq + Hash + Sync,
V: 'static + Clone + Sync,
H: 'static + BuildHasher, type Item = (&'b K, &'b V);
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
Auto Trait Implementations
impl<K, V, H> RefUnwindSafe for HashIndex<K, V, H> where
H: RefUnwindSafe,
impl<K, V, H> Send for HashIndex<K, V, H> where
H: Send,
impl<K, V, H> Sync for HashIndex<K, V, H> where
H: Sync,
impl<K, V, H> Unpin for HashIndex<K, V, H> where
H: Unpin,
impl<K, V, H = RandomState> !UnwindSafe for HashIndex<K, V, H>
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more