Struct scc::hash_index::HashIndex [−][src]
pub struct HashIndex<K, V, H = RandomState> where
K: 'static + Clone + Eq + Hash + Sync,
V: 'static + Clone + Sync,
H: BuildHasher, { /* fields omitted */ }Expand description
A 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 entail shared data modification.
- 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 number of entries a single linked list entry manages: 32.
- The expected maximum linked list length when resize is triggered: log(capacity) / 8.
Implementations
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, _> = Default::default();
let result = hashindex.capacity();
assert_eq!(result, 64);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> = Default::default();
assert!(hashindex.insert(1, 0).is_ok());
assert_eq!(hashindex.insert(1, 1).unwrap_err(), (1, 1));Removes a key-value pair and returns the 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> = Default::default();
assert!(!hashindex.remove(&1));
assert!(hashindex.insert(1, 0).is_ok());
assert!(hashindex.remove(&1));Removes a key-value pair and returns the 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> = Default::default();
assert!(hashindex.insert(1, 0).is_ok());
assert!(!hashindex.remove_if(&1, |v| *v == 1));
assert!(hashindex.remove_if(&1, |v| *v == 0));Reads a key-value pair.
It returns None if the key does not exist.
Examples
use scc::HashIndex;
let hashindex: HashIndex<u64, u32> = Default::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);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> = Default::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);Checks if the key exists.
Examples
use scc::HashIndex;
let hashindex: HashIndex<u64, u32> = Default::default();
assert!(!hashindex.contains(&1));
assert!(hashindex.insert(1, 0).is_ok());
assert!(hashindex.contains(&1));Clears all the key-value pairs.
Examples
use scc::HashIndex;
let hashindex: HashIndex<u64, u32> = Default::default();
assert!(hashindex.insert(1, 0).is_ok());
assert_eq!(hashindex.clear(), 1);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> = Default::default();
assert!(hashindex.insert(1, 0).is_ok());
assert_eq!(hashindex.len(), 1);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> = Default::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));