kudzu:跳过清单 源码

Kudzu-并发集和地图数据结构 信息单调增长。 Kudzu在并发跳过列表的顶部提供了Map和Set 。 kudzu和其他并发数据结构中的类型之间的主要区别在于kudzu的数据结构不支持删除操作。 这种限制使类型更易于实现,并希望性能更高,协调开销更少,同时对于许多应用程序仍然有用。 用例 这些可用于其中仅增长映射或集合而不会丢失成员的任何并发算法。 例如,可以将其与人造丝组合,作为带有重复子问题(例如,斐波那契)的分治算法的记忆表。 并发属性 假设我的实现是正确的,并且我的推理是合理的(大的假设),那么所有这些事情都应该是正确的: 数据竞赛是不可能的。 映射上的所有操作都是无锁的:同一集合上的两个并发操作不可能创建死锁。 查找是免等待的:在集合中查找项目永远不会等待另一个线程完成。 跳过列表绝不会处于与跳过列表的属性不一致的状态(也就是说,每个通道始终都是其下面的通道的子集)。