fast-list

使用SlotMap提高缓存局部性，并解决ABA问题。

✅ 平均比标准的LinkedList快2-3倍，适用于所有操作。

✅ 平均比Vec和VecDeque快2-3倍，适用于随机插入（目前随机删除的速度大致相同）。

✅ 对于大多数其他操作，仅略慢于Vec和VecDeque。

✅ 通过内部使用SlotMap，安全地解决ABA问题，使得在多线程中迭代和修改列表更为安全。与仅使用SlotMap相比，其优点是迭代时的顺序不是任意的。

✅ 完全使用100%安全的Rust编写。

示例

基本示例

use fast_list::LinkedList;

// the extend() function accepts an iterator over T (i32 in this case)
let mut list = LinkedList::new();
list.extend(0..=100);

assert_eq!(list.head().unwrap().value, 0);
assert_eq!(list.tail().unwrap().value, 100);

list.push_front(42);
assert_eq!(list.head().unwrap().value, 42);

assert_eq!(list.iter().count(), 102); // 101 items from our range, one item from push_back
// These two iterators are equivalent
assert_eq!(
    list.iter_next(list.head.unwrap()).count(), 
    list.iter().count()
);

多线程迭代和修改

use fast_list::LinkedList;
use std::thread;
use std::sync::{Arc, Mutex};

let mut list = LinkedList::new();
let indexes = Arc::new(list.extend(0..10_000));

// You can also get the ordered indexes with something like this:
// let indexes = Arc::new(
//     list.cursor_next(list.head.unwrap()).collect::<Vec<_>>()
// );

let list_mut = Arc::new(Mutex::new(list));

let mut threads = Vec::new();
for _ in 0..3 {
    let list_mut = Arc::clone(&list_mut);
    let indexes = Arc::clone(&indexes);
    let t = thread::spawn(move || {
        for index in indexes.iter().take(9_000)  {
            list_mut.lock().unwrap().remove(*index); // returns None if the index does not exist
        }
    });
    threads.push(t);
}

for t in threads {
    t.join().unwrap();
}

// Even though remove() is called 9000*3 times, only 9000 items are removed.
{
    assert_eq!(list_mut.lock().unwrap().head().unwrap().value, 9_000);
}

结构

LinkedList - 存储列表的主要结构。

// A doubly linked list using SlotMap for better cache performance than a linked list using pointers, and which also solves the ABA problem.
pub struct LinkedList<T = ()> {
    // The index of the first item in the list.
    pub head: Option<LinkedListIndex>,
    // The index of the last item in the list.
    pub tail: Option<LinkedListIndex>,
    // The items in the list.
    items: SlotMap<LinkedListIndex, LinkedListItem<T>>,
}

LinkedListIndex - 列表的索引。

new_key_type! {
    /// A newtype for the index of an item in the list.
    pub struct LinkedListIndex;
}

LinkedListItem - 列表中的项。

pub struct LinkedListItem<T> {
    /// The index of the item in the list.
    pub index: LinkedListIndex,
    /// The value of the item.
    pub value: T,
    /// The index of the next item in the list.
    pub next_index: Option<LinkedListIndex>,
    /// The index of the previous item in the list.
    pub prev_index: Option<LinkedListIndex>,
}

LinkedListWalker - [feature = "unstable"] 一个遍历类型（如petgraph中的），可以用来遍历列表。