示例

大多数 HashSet 方法与 HashMap 相同，只是它们不接收值参数，并且一些用于值修改的 HashMap 方法在 HashSet 中没有实现。

use scc::HashSet;

let hashset: HashSet<u64> = HashSet::default();

assert!(hashset.read(&1, |_| true).is_none());
assert!(hashset.insert(1).is_ok());
assert!(hashset.read(&1, |_| true).unwrap());

let future_insert = hashset.insert_async(2);
let future_remove = hashset.remove_async(&1);

HashIndex

HashIndex 是 HashMap 的读取优化版本。在 HashIndex 中，不仅桶数组的内存由 sdd 管理着，而且条目桶的内存也受到 sdd 的保护，从而实现了对单个条目无锁的读取访问。

条目生命周期

HashIndex 不会立即丢弃删除的条目，而是在以下任一条件满足时才会进行丢弃。

1. Epoch 达到桶中上次删除条目后的下一代，并且桶被写入访问。
2. HashIndex 被清空或调整大小。
3. 充满删除条目的桶占用了50%的容量。

这些条件并不能保证删除的条目在特定时间内被丢弃，因此如果工作负载以写入为主且条目大小较大，那么 HashIndex 可能不是最佳选择。

示例

peek 和 peek_with 方法是完全无锁的。

use scc::HashIndex;

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

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

// `peek` and `peek_with` are lock-free.
assert_eq!(hashindex.peek_with(&1, |_, v| *v).unwrap(), 0);

let future_insert = hashindex.insert_async(2, 1);
let future_remove = hashindex.remove_if_async(&1, |_| true);

HashIndex 的 Entry API 可以用于就地更新条目。

use scc::HashIndex;

let hashindex: HashIndex<u64, u32> = HashIndex::default();
assert!(hashindex.insert(1, 1).is_ok());

if let Some(mut o) = hashindex.get(&1) {
    // Create a new version of the entry.
    o.update(2);
};

if let Some(mut o) = hashindex.get(&1) {
    // Update the entry in-place.
    unsafe { *o.get_mut() = 3; }
};

为 HashIndex 实现了 Iterator，因为任何派生的引用只要关联的 ebr::Guard 存活，就可以存活。

use scc::ebr::Guard;
use scc::HashIndex;

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

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

// Existing values can be replaced with a new one.
hashindex.get(&1).unwrap().update(1);

let guard = Guard::new();

// An `Guard` has to be supplied to `iter`.
let mut iter = hashindex.iter(&guard);

// The derived reference can live as long as `guard`.
let entry_ref = iter.next().unwrap();
assert_eq!(iter.next(), None);

drop(hashindex);

// The entry can be read after `hashindex` is dropped.
assert_eq!(entry_ref, (&1, &1));

HashCache

HashCache 是一个基于 HashMap 实现的32路关联并发缓存。与 HashCache 不同，它不跟踪整个缓存中最少使用过的条目，而是每个桶维护一个双链表，用于存储已占用条目，以便在访问条目时更新，以跟踪桶内最少使用的条目。

示例

当一个桶满时，新条目被插入，最少使用的条目将被淘汰。

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::with_capacity(100, 2000);

/// The capacity cannot exceed the maximum capacity.
assert_eq!(hashcache.capacity_range(), 128..=2048);

/// If the bucket corresponding to `1` or `2` is full, the LRU entry will be evicted.
assert!(hashcache.put(1, 0).is_ok());
assert!(hashcache.put(2, 0).is_ok());

/// `1` becomes the most recently accessed entry in the bucket.
assert!(hashcache.get(&1).is_some());

/// An entry can be normally removed.
assert_eq!(hashcache.remove(&2).unwrap(), (2, 0));

TreeIndex

TreeIndex 是一种B+树变体，优化了读取操作。由于 sdd 保护了各个条目使用的内存，因此可以实现对它们的无锁读取访问。

锁定行为

读取访问总是无锁且非阻塞的。只要不需要进行结构变更，对条目的写入访问也是无锁和非阻塞的。然而，当节点由于写入操作而被分割或合并时，受影响的范围内对键的其它写入操作将被阻塞。

条目生命周期

TreeIndex 不会立即丢弃删除的条目，而是在叶节点被清空或分割时才会进行丢弃，这使得 TreeIndex 在工作负载以写入为主时不是一个最佳选择。

示例

如果键是唯一的，可以插入条目，然后读取，最后删除。只有在内部节点分割或合并时才会获取或等待锁。

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

assert!(treeindex.insert(1, 2).is_ok());

// `peek` and `peek_with` are lock-free.
assert_eq!(treeindex.peek_with(&1, |_, v| *v).unwrap(), 2);
assert!(treeindex.remove(&1));

let future_insert = treeindex.insert_async(2, 3);
let future_remove = treeindex.remove_if_async(&1, |v| *v == 2);

可以无锁地进行条目扫描。

use scc::TreeIndex;
use sdd::Guard;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

assert!(treeindex.insert(1, 10).is_ok());
assert!(treeindex.insert(2, 11).is_ok());
assert!(treeindex.insert(3, 13).is_ok());

let guard = Guard::new();

// `visitor` iterates over entries without acquiring a lock.
let mut visitor = treeindex.iter(&guard);
assert_eq!(visitor.next().unwrap(), (&1, &10));
assert_eq!(visitor.next().unwrap(), (&2, &11));
assert_eq!(visitor.next().unwrap(), (&3, &13));
assert!(visitor.next().is_none());

可以扫描特定范围的键。

use scc::ebr::Guard;
use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

for i in 0..10 {
    assert!(treeindex.insert(i, 10).is_ok());
}

let guard = Guard::new();

assert_eq!(treeindex.range(1..1, &guard).count(), 0);
assert_eq!(treeindex.range(4..8, &guard).count(), 4);
assert_eq!(treeindex.range(4..=8, &guard).count(), 5);

Bag

Bag 是一个无锁并发非顺序容器。 Bag 完全透明，不允许访问包含的实例，直到它们被弹出。 Bag 特别高效，如果包含的实例数量可以保持在 ARRAY_LEN (默认: usize::BITS / 2)

use scc::Bag;

let bag: Bag<usize> = Bag::default();

bag.push(1);
assert!(!bag.is_empty());
assert_eq!(bag.pop(), Some(1));
assert!(bag.is_empty());

use scc::Queue;

let queue: Queue<usize> = Queue::default();

queue.push(1);
assert!(queue.push_if(2, |e| e.map_or(false, |x| **x == 1)).is_ok());
assert!(queue.push_if(3, |e| e.map_or(false, |x| **x == 1)).is_err());
assert_eq!(queue.pop().map(|e| **e), Some(1));
assert_eq!(queue.pop().map(|e| **e), Some(2));
assert!(queue.pop().is_none());

use scc::Stack;

let stack: Stack<usize> = Stack::default();

stack.push(1);
stack.push(2);
assert_eq!(stack.pop().map(|e| **e), Some(2));
assert_eq!(stack.pop().map(|e| **e), Some(1));
assert!(stack.pop().is_none());

use scc::ebr::{AtomicShared, Guard, Shared};
use scc::LinkedList;
use std::sync::atomic::Ordering::Relaxed;

#[derive(Default)]
struct L(AtomicShared<L>, usize);
impl LinkedList for L {
    fn link_ref(&self) -> &AtomicShared<L> {
        &self.0
    }
}

let guard = Guard::new();

let head: L = L::default();
let tail: Shared<L> = Shared::new(L(AtomicShared::null(), 1));

// A new entry is pushed.
assert!(head.push_back(tail.clone(), false, Relaxed, &guard).is_ok());
assert!(!head.is_marked(Relaxed));

// Users can mark a flag on an entry.
head.mark(Relaxed);
assert!(head.is_marked(Relaxed));

// `next_ptr` traverses the linked list.
let next_ptr = head.next_ptr(Relaxed, &guard);
assert_eq!(next_ptr.as_ref().unwrap().1, 1);

// Once `tail` is deleted, it becomes invisible.
tail.delete_self(Relaxed);
assert!(head.next_ptr(Relaxed, &guard).is_null());