Rust library useful for storing structs that needs to be accessed through various different indexes of the fields of the struct. Inspired by C++/Boost Multi-index Containers but redesigned for a more idiomatic Rust API.
Current implementation supports: * Hashed indexes using FxHashMap from rustc-hash. * Sorted indexes using BTreeMap from std::collections. * Unique and non-unique indexes. * Unindexed fields. * Iterators for each indexed field. * Iterators for the underlying backing storage.
panic.This crate provides a derive macro MultiIndexMap, which when applied to the struct representing an element will generate a map to store and access these elements.
Annotations are used to specify which fields to index. Currently hashed_unique, hashed_non_unique, ordered_unique, and ordered_non_unique are supported.
The types of all indexed fields must implement Clone.
If the MultiIndexMap needs to be cloned, Clone can be implemented manually, or if nightly rust is used, the feature trivial_bounds can be enabled.
This will autoderive implementations of both Debug and Clone where possible.
See examples/main.rs for an example of how to do it both ways.
```rust use multiindexmap::MultiIndexMap;
struct Order { #[multiindex(hashedunique)] orderid: u32, #[multiindex(orderedunique)] timestamp: u64, #[multiindex(hashednonunique)] trader_name: String, filled: bool, volume: u64, }
fn main() { let order1 = Order { orderid: 1, timestamp: 1656145181, tradername: "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.insert(order1);
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);
// See examples and tests directories for more in depth usage.
} ```
The above example will generate the following MultiIndexMap and associated Iterators.
The Orders are stored in a Slab, in contiguous memory, which allows for fast lookup and quick iteration.
A lookup table is created for each indexed field, which maps the index key to a index in the Slab.
The exact type used for these depends on the annotations.
For hashed_unique and hashed_non_unique a FxHashMap is used, for ordered_unique and ordered_non_unique a BTreeMap is used.
* When inserting an element, we add it to the backing store, then add elements to each lookup table pointing to the index in the backing store.
* When retrieving elements for a given key, we lookup the key in the lookup table, then retrieve the item at that index in the backing store.
* When removing an element for a given key, we do the same, but we then must also remove keys from all the other lookup tables before returning the element.
* When iterating over an index, we use the default iterators for the lookup table, then simply retrieve the element at the given index in the backing store.
* When updating un-indexed fields, we lookup the element(s) through the given key, then apply the closure to modify just the unindexed fields in-place.
We then return a reference to the modified element(s).
If the key doesn't match, the closure won't be applied, and Option::None will be returned.
* When modifying indexed fields of an element, we do the same process, but the closure takes a mutable reference to the whole element.
Any fields, indexed and un-indexed can be modified.
We must then update all the lookup tables to account for any changes to indexed fields, so this is slower than an un-indexed update.
```rust
struct MultiIndexOrderMap {
store: slab::Slab
struct MultiIndexOrderMapOrderIdIter<'a> { ... }
struct MultiIndexOrderMapTimestampIter<'a> { ... }
struct MultiIndexOrderMapTraderNameIter<'a> { ... }
impl MultiIndexOrderMap { fn insert(&mut self, elem: 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;
} ```
See Cargo.toml for information on each dependency.