MultiIndexMap

同时在crates.io上可用。

Rust库，用于存储需要通过结构体不同字段的各种不同索引进行访问的结构体。受C++/Boost多索引容器的启发，但重新设计以适应更符合Rust语法的API。

当前实现支持

• 使用来自rustc-hash的FxHashMap的哈希索引。
• 使用来自std::collections的BTreeMap的排序索引。
• 唯一和非唯一索引。
• 未索引的字段。
• 每个索引字段的迭代器。
• 底层存储的迭代器。

性能特性

唯一索引

• 哈希索引检索是常数时间。 (FxHashMap + Slab)
• 排序索引检索是对数时间。 (BTreeMap + Slab)
• 遍历哈希索引与FxHashMap相同，此外每个元素还需要从底层存储中检索。
• 遍历有序索引与BTreeMap相同，此外每个元素还需要从底层存储中检索。
• 遍历底层存储与Slab相同，因此是连续内存，但可能有空槽。
• 插入、删除和修改的复杂度随着索引字段数量的增加而增长。在这些操作中必须更新所有索引，因此这些操作较慢。
• 通过不安全mut方法修改未索引字段的时间与常规检索时间相同。
• 违反唯一性的修改将导致 panic。
• 违反唯一性的插入不会修改映射，而是将元素作为Err变体包装并返回给用户。

非唯一索引

• 哈希索引检索的总元素数仍然是常数时间，但与匹配元素的数量呈线性时间。（FxHashMap + (Slab * num_matches)）。
• 排序索引检索的总元素数仍然是对数时间，但与匹配元素的数量呈线性时间。（BTreeMap + (Slab * num_matches)）。
• 任何非唯一索引的相等范围都存储为BTreeSet，在检索所有匹配元素时以及遍历整个索引时，我们必须遍历其长度。

如何使用

• 这个crate提供了一个derive宏MultiIndexMap，将其应用于表示元素的struct时，将生成一个用于存储和访问这些元素的映射。
• 使用注释来指定要索引的字段。目前支持hashed_unique、hashed_non_unique、ordered_unique和ordered_non_unique。
• 所有索引字段都必须实现Clone。
• 可选地，可以使用multi_index_derive来在生成的MultiIndexMap上派生特质，例如#[multi_index_derive(Clone, Debug)]有关详细信息，请参阅examples/main.rs。

示例

use multi_index_map::MultiIndexMap;

#[derive(MultiIndexMap, Debug)]
#[multi_index_derive(Debug)]
struct Order {
    #[multi_index(hashed_unique)]
    order_id: u32,
    #[multi_index(ordered_unique)]
    timestamp: u64,
    #[multi_index(hashed_non_unique)]
    trader_name: String,
    filled: bool,
    volume: u64,
}

fn main() {
    let order1 = Order {
        order_id: 1,
        timestamp: 1656145181,
        trader_name: "JohnDoe".into(),
        filled: false,
        volume: 100,
    };

    let order2 = Order {
        order_id: 2,
        timestamp: 1656145182,
        trader_name: "JohnDoe".into(),
        filled: false,
        volume: 100,
    };

    let mut map = MultiIndexOrderMap::default();

    map.try_insert(order1).unwrap();
    map.insert(order2);

    let orders = map.get_by_trader_name(&"JohnDoe".to_string());
    assert_eq!(orders.len(), 2);
    println!("Found 2 orders for JohnDoe: [{orders:?}]");

    let order1_ref = map.get_by_order_id(&1).unwrap();
    assert_eq!(order1_ref.timestamp, 1656145181);

    let order2_ref = map
        .modify_by_order_id(&2, |o| {
            o.timestamp = 1656145183;
            o.order_id = 42;
        })
        .unwrap();

    assert_eq!(order2_ref.timestamp, 1656145183);
    assert_eq!(order2_ref.order_id, 42);
    assert_eq!(order2_ref.trader_name, "JohnDoe".to_string());

    let order2_ref = map
        .update_by_order_id(&42, |filled: &mut bool, volume: &mut u64| {
            *filled = true;
            *volume = 0;
        })
        .unwrap();
    assert_eq!(order2_ref.filled, true);
    assert_eq!(order2_ref.volume, 0);

    let orders = map.get_by_trader_name(&"JohnDoe".to_string());
    assert_eq!(orders.len(), 2);
    println!("Found 2 orders for JohnDoe: [{orders:?}]");

    let orders = map.remove_by_trader_name(&"JohnDoe".to_string());
    for (_idx, order) in map.iter() {
        assert_eq!(order.trader_name, "JohnDoe");
    }
    assert_eq!(orders.len(), 2);

    println!("{map:?}");

    // See examples and tests directories for more in depth usage.
}

内部原理

上述示例将生成以下MultiIndexMap和相关迭代器。Order存储在Slab中，在连续的内存中，这允许快速查找和快速迭代。为每个索引字段创建一个查找表，该表将索引键映射到Slab中的索引。这些的确切类型取决于注释。对于hashed_unique和hashed_non_unique，使用FxHashMap，对于ordered_unique和ordered_non_unique，使用BTreeMap。

struct MultiIndexOrderMap {
    _store: slab::Slab<Order>,
    _order_id_index: rustc_hash::FxHashMap<u32, usize>,
    _timestamp_index: std::collections::BTreeMap<u64, usize>,
    _trader_name_index: rustc_hash::FxHashMap<String, BTreeSet<usize>>,
}

struct MultiIndexOrderMapOrderIdIter<'a> {
    ...
}

struct MultiIndexOrderMapTimestampIter<'a> {
    ...
}

struct MultiIndexOrderMapTraderNameIter<'a> {
    ...
}

impl MultiIndexOrderMap {
    fn try_insert(&mut self, elem: Order) -> Result<&Order, MultiIndexMapError<Order>>;
    fn insert(&mut self, elem: Order) -> &Order;
    
    fn len(&self) -> usize;
    fn is_empty(&self) -> bool;
    fn clear(&mut self);
    
    fn get_by_order_id(&self, key: &u32) -> Option<&Order>;
    fn get_by_timestamp(&self, key: &u64) -> Option<&Order>;
    fn get_by_trader_name(&self, key: &String) -> Vec<&Order>;

    fn update_by_order_id(&mut self, key: &u32, f: impl FnOnce(&mut bool, &mut u64)) -> Option<&Order>;
    fn update_by_timestamp(&mut self, key: &u64, f: impl FnOnce(&mut bool, &mut u64)) -> Option<&Order>;
    fn update_by_trader_name(&mut self, key: &String, f: impl FnMut(&mut bool, &mut u64)) -> Vec<&Order>;
    
    fn modify_by_order_id(&mut self, key: &u32, f: impl FnOnce(&mut Order)) -> Option<&Order>;
    fn modify_by_timestamp(&mut self, key: &u64, f: impl FnOnce(&mut Order)) -> Option<&Order>;
    fn modify_by_trader_name(&mut self, key: &String, f: impl FnMut(&mut Order)) -> Vec<&Order>;
    
    fn remove_by_order_id(&mut self, key: &u32) -> Option<Order>;
    fn remove_by_timestamp(&mut self, key: &u64) -> Option<Order>;
    fn remove_by_trader_name(&mut self, key: &String) -> Vec<Order>;
    
    fn iter(&self) -> slab::Iter<Order>;
    unsafe fn iter_mut(&mut self) -> slab::IterMut<Order>;
    
    fn iter_by_order_id(&self) -> MultiIndexOrderMapOrderIdIter;
    fn iter_by_timestamp(&self) -> MultiIndexOrderMapTimestampIter;
    fn iter_by_trader_name(&self) -> MultiIndexOrderMapTraderNameIter;
}