3 个版本

0.1.2 2023 年 6 月 28 日
0.1.1 2023 年 6 月 28 日
0.1.0 2023 年 6 月 28 日

#895并发

Download history • Rust 包仓库 3318/week @ 2024-04-03 • Rust 包仓库 2549/week @ 2024-04-10 • Rust 包仓库 1967/week @ 2024-04-17 • Rust 包仓库 1307/week @ 2024-04-24 • Rust 包仓库 1574/week @ 2024-05-01 • Rust 包仓库 1946/week @ 2024-05-08 • Rust 包仓库 1680/week @ 2024-05-15 • Rust 包仓库 1998/week @ 2024-05-22 • Rust 包仓库 1827/week @ 2024-05-29 • Rust 包仓库 1892/week @ 2024-06-05 • Rust 包仓库 2342/week @ 2024-06-12 • Rust 包仓库 1894/week @ 2024-06-19 • Rust 包仓库 2104/week @ 2024-06-26 • Rust 包仓库 1759/week @ 2024-07-03 • Rust 包仓库 2342/week @ 2024-07-10 • Rust 包仓库 1781/week @ 2024-07-17 • Rust 包仓库

8,412 每月下载量
qcell 中使用

CC0 许可证

20KB
258

Tests codecov

一个无锁并发集合。

已通过 loommiri 测试。


lib.rs:

一个无锁并发集合。该集合的操作复杂度为 O(n),其中 n 是已插入集合中的不同值的数量。

预期的使用场景是为确保对代码关键部分按值进行唯一性提供一种方式,其中不同值的数量较小但动态。

此数据结构使用两种形式的原子单链表来实现其操作。一种列表为每个曾经插入的不同值都有一个节点。另一种类型的列表存在于这些节点内部,并管理一个等待在 wait_to_insert 方法中另一个线程调用 remove 的线程队列。

原子单链表相对简单地进行插入:分配一个新的节点,然后在循环中,更新节点的 'next' 指针为 'head' 指针的最新值,然后尝试 compare-exchange,用新节点的指针替换旧的 'head'。

一旦你考虑从列表中删除项目,事情就会变得更加复杂。现在任何解引用节点指针的操作都存在尝试解引用在加载返回指针和解引用指针之间被删除的值的危险。请注意,删除本身需要解引用头指针,以确定 head.next 的值。此数据结构以两种不同方式避免此类问题。

每个值的节点主列表通过仅在 Drop 中删除节点来避免问题。Drop 的独占访问保证确保在释放期间没有其他线程尝试访问列表。

等待线程列表通过指定每个等待线程列表,在当前集合的上下文中,意味着对于每个唯一值,一次只能有一个线程解引用指针,从而避免了这个问题。它将此协议作为不安全 remove 方法的安全要求。对于只有逻辑“所有者”从集合中删除值,并且知道它之前插入了一个值的程序,这个要求很容易满足。

示例

以下代码将一些值插入集合中,然后删除其中之一,然后启动一个等待插入集合的第二个线程。

运行此代码后,我们可以期待数据结构看起来像这样

依赖项

~0–26MB
~330K SLoC