IndexWeave

Fork of lun3x/multi_index_map, focused on pragmatic API extensions while staying source-compatible with existing usage where possible.

Fork additions

• [Breaking change] Fluent operation-scoped access API: map.lookup().by_<field>(...).run(), map.contains().by_<field>(...).run(), map.modify().by_<field>(...).run(changed_flags, ...), map.remove().by_<field>(...).run(), and map.entry().by_<field>(...).run().
• Entry-style insertion/removal for hashed unique indexes via entry().by_<field>(key) with and_modify(changed_flags, ...), upsert_with(changed_flags, on_modify, on_insert), remove, or_insert[_with], and or_try_insert* variants (issue #28).
• Optional key indexing via #[multi_index(<kind>, optional)] so Option<T> fields index only Some(T) values (discussion in issue #48 comment).
• Computed indexes via #[multi_index(key_fn(<kind>, <method>, <KeyType>))] with read/mutate/remove APIs (lookup*, iter*, modify*, remove*) and computed entry APIs for hashed-unique indexes.
• Optional computed indexes via #[multi_index(key_fn(<kind>, <method>, Option<T>, optional))], which index only Some(T) values and expose &T lookups.
• Fluent oneof fallback chains via by_<index>(...).or_<other>(...).run(...) with first-selector-wins semantics.
• Optional selector helpers for chains: by_<index>_opt(...) / or_<index>_opt(...) on lookup/contains/modify/remove and oneof entry chains.
• Batch mutation selectors: modify().all().run(changed_flags, ...) and modify().by_<index>_in(&[...]).run(changed_flags, ...).
• Opt-in transactional modify selectors: run_transactional(...) on modify chains with rollback-on-conflict and rollback-then-repanic panic handling (enabled with #[multi_index(transactional)]).
• Direct bulk insert/upsert APIs: insert_many(...), upsert_by_<unique_index>(...), and upsert_many_by_<unique_index>(...).
• Fluent bulk remove selectors: remove().all().run() and remove().by_<index>_in(&[...]).run().

Development disclaimer

This repository is developed with AI assistance (OpenAI Codex). All AI-assisted changes are expected to be reviewed and validated by maintainers before release.

Also available on crates.io.

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 Capabilities

• Derive macro (#[derive(MultiIndexMap)]) for owned row types.
• Schema macro (multi_index_map!) for external row types and schema-first indexing.
• Hashed and ordered indexes via HashMap/BTreeMap, with both unique and non-unique variants.
• Optional indexing (optional) for Option<T>-backed keys.
• Derive key_path extractors for nested fields, including struct-level key_path(...) index declarations.
• Computed indexes on derive maps (key_fn(...)) with fluent read/mutate/remove APIs, plus entry().by_<method> for hashed-unique computed indexes.
• Schema extractors via key_path = ... and key_fn = ..., including nested paths.
• Fluent oneof fallback chains via #[multi_index_oneof_key(<group>, <index_1>, ...)] across derive and schema macros.
• iter_by_* read-only index iteration plus fluent keyed retrieval (lookup().by_*().run()).
• Borrowed-key lookup support across keyed accessors (documented below).

Performance characteristics

Unique Indexes

• Hashed index retrievals are constant-time. (HashMap + Slab).
• Sorted indexes retrievals are logarithmic-time. (BTreeMap + Slab).
• Iteration over hashed index is same as HashMap, plus a retrieval from the backing storage for each element.
• Iteration over ordered index is same as BTreeMap, plus a retrieval from the backing storage for each element.
• Iteration over the backing store is the same as Slab, so contiguous memory but with potentially vacant slots.
• Insertion, removal, and modification complexity grows as the number of indexed fields grow. All indexes must be updated during these operations so these are slower.
• Unindexed-only modifications via modify().by_*().run(<Map>ChangedIndexes::EMPTY, ...) avoid reindex work.
• Batch selectors deduplicate input keys (by_*_in) and skip missing keys, returning the number of rows actually modified.
• run_transactional(...) for modify chains is opt-in and performs clone snapshots + full index rebuild for touched rows; this is slower than run(...) but provides all-or-nothing rollback.
• The Row: Clone requirement is enforced only for run_transactional(...) calls. Non-transactional run(...) keeps its existing behavior and fast path.
• insert_many is best-effort: it processes every item and returns per-item uniqueness errors in the report.
• upsert_many_by_* coalesces duplicate input keys (last key wins), aborts on first error, rolls back prior operations from that call, and returns the triggering error in the report.
• Insertion such that uniqueness would be violated does not mutate the map, instead the element is returned to the user wrapped in an Err variant.

Non-Unique Indexes

• Hashed index retrievals are still constant-time with the total number of elements, but linear-time with the number of matching elements. (HashMap + (Slab * num_matches)).
• Sorted indexes retrievals are still logarithmic-time with total number of elements, but linear-time with the number of matching elements. (BTreeMap + (Slab * num_matches)).
• Each equal range of any non-unique index is stored as a BTreeSet, which we must iterate through the length of when retrieving all matching elements, and also when iterating over the whole index.

Performance Notes (Current)

• Schema fluent modify().by_*().run(...) and oneof fallback modify().by_*().or_*().run(...) paths avoid pre-lookup key reconstruction.
• Benchmark coverage for these schema/oneof_key paths is available in schema_oneof_key:

cargo bench -p indexweave --bench schema_oneof_key --no-run

The bench compares direct vs oneof_key access for lookup and modify.

Default Hasher

• The feature rustc-hash is enabled by default. It will set the default hash as rustc-hash.
• The hash can always be changed by specifying a BuildHasher implementation in the multi_index_hash attribute, eg. #[multi_index_hash(ahash::RandomState)].
• With default features disabled the default hash will be the standard library default (currently SipHash). Default features can be disabled in Cargo.toml like so:

indexweave = { version = "*", default-features = false }

How to use

• 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.
• Add optional as a second attribute argument to index Option<T> fields by T, skipping None entries (for example #[multi_index(hashed_unique, optional)]).
• Add derive field-path extraction for nested row fields using either field-level key_path = <field_path> or struct-level key_path(<kind>, <index_name>, <KeyType>, <field_path>[, optional]) declarations (computed-style, without adding placeholder struct fields).
• Add struct-level computed indexes via #[multi_index(key_fn(<kind>, <method_name>, <KeyType>))]. The method must exist on the element type and return the declared KeyType.
• Add optional as a fourth computed argument to skip indexing None for Option<T> computed keys, eg. #[multi_index(key_fn(hashed_unique, email_norm, Option<String>, optional))]. Optional computed lookups use &T (inner key type).
• Add struct-level oneof_key dispatch over unique indexes (field-backed and key_path(...) computed targets) via #[multi_index_oneof_key(<group_name>, <index_name_1>[, <index_name_N>...])].
• Enable transactional modify APIs with #[multi_index(transactional)] on derive structs, or as an outer schema attribute in multi_index_map! blocks.
• The types of all indexed fields must implement Clone.
• Optionally, multi_index_derive can be used to derive traits on the generated MultiIndexMap, eg. #[multi_index_derive(Clone, Debug)] See examples/main.rs for more details.

Breaking rename (0.17.0)

• Derive struct-level computed declarations now use key_fn(...) instead of computed(...).
• Schema extractor declarations now use key_fn = ... instead of keyfn = ....
• Migration:
  • #[multi_index(computed(<kind>, <method>, <KeyType>[, optional]))] -> #[multi_index(key_fn(<kind>, <method>, <KeyType>[, optional]))]
  • #[multi_index(..., keyfn = some::path)] -> #[multi_index(..., key_fn = some::path)]

Fluent Access Migration (Breaking)

Legacy direct accessors and positional oneof methods were removed from the public API.

Computed indexes

use indexweave::MultiIndexMap;

type UserTierKey = (String, u8);

#[derive(MultiIndexMap)]
#[multi_index(key_fn(ordered_unique, user_tier, UserTierKey))]
#[multi_index(key_fn(hashed_non_unique, domain, String))]
struct User {
    #[multi_index(hashed_unique)]
    id: u64,
    name: String,
    tier: u8,
    email: String,
}

impl User {
    fn user_tier(&self) -> UserTierKey {
        (self.name.clone(), self.tier)
    }

    fn domain(&self) -> String {
        self.email.split('@').nth(1).unwrap_or_default().to_string()
    }
}

fn demo(mut map: MultiIndexUserMap) {
    let _exact = map.lookup().by_user_tier(&("alice".to_string(), 2)).run();
    let _all = map.iter_by_domain();
    let _bucket = map.lookup().by_domain("example.com").run();
    let _updated = map.modify().by_user_tier(&("alice".to_string(), 2)).run(
        MultiIndexUserMapChangedIndexes::ALL,
        |row| {
            row.name = "alice".to_string();
            row.tier = 3;
            row.email = "alice@example.com".to_string();
        },
    );
    let _removed = map.remove().by_user_tier(&("alice".to_string(), 2)).run();
}

Computed indexes expose:

• Read APIs: lookup().by_*.run() (unique -> Option<&Row>, non-unique -> iterator), plus iter_by_*.
• Mutation/removal APIs: modify().by_*.run(changed_flags, ...), remove().by_*.run().
• Upsert APIs for computed unique indexes: upsert_by_<method>(&key, row) and upsert_many_by_<method>(iter).
• Batch mutation APIs: modify().all().run(changed_flags, ...) -> Result<usize, ModifyError> and modify().by_*_in(&[keys]).run(changed_flags, ...) -> Result<usize, ModifyError>.
• Transactional mutation APIs (opt-in via #[multi_index(transactional)]): modify().by_*...run_transactional(changed_flags, ...), modify().all().run_transactional(changed_flags, ...), and modify().by_*_in(&[keys]).run_transactional(changed_flags, ...).
• Batch removal APIs: remove().all().run() -> Vec<Row> and remove().by_*_in(&[keys]).run() -> Vec<Row>.
• Entry APIs: entry().by_*.run() for hashed_unique computed indexes (wrapper supports and_modify(changed_flags, ...), upsert_with(changed_flags, on_modify, on_insert), remove, and insert-or variants).

Derive oneof_key dispatch

use indexweave::MultiIndexMap;

#[derive(MultiIndexMap)]
#[multi_index_oneof_key(user_ref, id, email)]
struct User {
    #[multi_index(hashed_unique)]
    id: u64,
    #[multi_index(ordered_unique)]
    email: String,
    note: String,
}

fn demo(mut map: MultiIndexUserMap) {
    let _ = map.lookup().by_id(&1).or_email("ignored@example.com").run();
    let _ = map.lookup().by_email("a@example.com").run();
    let _ = map
        .modify()
        .by_id(&1)
        .or_email("ignored@example.com")
        .run(MultiIndexUserMapChangedIndexes::EMPTY, |row| row.note.clear());
}

Derive oneof_keys target unique indexes (field-backed unique indexes and key_path(...) computed unique indexes; non-unique targets are rejected). They generate:

• lookup().by_<index>(key).or_<other>(key2)...run() -> Option<&Row>
• contains().by_<index>(key).or_<other>(key2)...run() -> bool
• modify().by_<index>(key).or_<other>(key2)...run(changed_flags, f) -> Result<Option<&Row>, ModifyError>
• modify().by_<index>(key).or_<other>(key2)...run_transactional(changed_flags, f) -> Result<Option<&Row>, ModifyError>
• remove().by_<index>(key).or_<other>(key2)...run() -> Option<Row>
• entry().by_<index>(key).or_<other>(key2)...run() -> Entry when every mapped index is hashed_unique

Behavior rules:

• Chain keys are borrowed at call sites and stored as owned keys internally.
• For lookup/contains/modify/remove, first selected selector is used (first-selector-wins).
• For oneof entry chains, run() picks the first selector that resolves to an occupied entry; if none resolve, it uses the first selected key for insertion.
• by_*_opt(None) / or_*_opt(None) skip selection; run() then returns the operation-specific empty result.
• entry().by_*().or_*() chains are omitted for mixed/ordered oneof groups.

Derive vs schema macro

External row types (multi_index_map!)

When the row type is defined in another crate and you cannot add #[derive(MultiIndexMap)], use the schema macro:

use indexweave::multi_index_map;

mod external {
    pub struct Org {
        pub code: String,
    }

    pub struct Profile {
        pub org: Org,
    }

    pub struct User {
        pub id: u64,
        pub email: String,
        pub tenant: Option<String>,
        pub profile: Profile,
        pub note: String,
    }

    pub fn by_id(u: &User) -> u64 { u.id }
    pub fn by_email(u: &User) -> String { u.email.clone() }
    pub fn by_tenant(u: &User) -> Option<String> { u.tenant.clone() }
}

multi_index_map! {
    #[multi_index_oneof_key(user_ref, id, email)]
    pub struct UserMap for external::User {
        #[multi_index(hashed_unique, key_path = id)]
        pub id: u64,
        #[multi_index(ordered_unique, key_fn = external::by_email)]
        pub email: String,
        #[multi_index(ordered_non_unique, key_path = profile.org.code)]
        pub org_code: String,
        #[multi_index(ordered_non_unique, optional, key_fn = external::by_tenant)]
        pub tenant: String,
    }
}

Notes:

• key_path = <field_path> indexes using direct field access (row.<field_path>.clone()), including nested paths like profile.org.code.
• key_fn = <path> uses a named function/method path (closures are not supported in V1).
• If neither key_path nor key_fn is provided, the extractor defaults to the same-name row field (row.<index_name>).
• Unique schema indexes generate contains().by_<field>(&key) -> bool.
• #[multi_index_oneof_key(<group_name>, <index_name_1>[, <index_name_N>...])] adds fluent fallback chains over unique indexes:
  • lookup().by_<index>(key).or_<other>(key2)...run()
  • contains().by_<index>(key).or_<other>(key2)...run()
  • modify().by_<index>(key).or_<other>(key2)...run(changed_flags, f)
  • remove().by_<index>(key).or_<other>(key2)...run()
  • entry().by_<index>(key).or_<other>(key2)...run() when all mapped indexes are hashed_unique
• oneof_key declarations (derive + schema) must satisfy:
  • every mapped index name exists,
  • every mapped index is unique,
  • mappings are non-empty,
  • mapped index names are unique within the declaration.
• Breaking change: multi_index_alias was removed; only multi_index_oneof_key is supported.
• Breaking change: key = ... is no longer accepted.
  • Migrate key = id -> key_path = id
  • Migrate key = external::by_id -> key_fn = external::by_id
• For optional, the key extractor must return Option<KeyType>.
• #[multi_index_mut(...)] has been removed.
• Keyed accessors support borrowed lookup keys (for example, &str for String indexes) for lookup().by_*, modify().by_*, and contains().by_* (unique) across derive/schema maps.
• Mutable keyed edits go through modify().by_*().run(changed_flags, |row| ...); undeclared indexed-key mutations are rejected.
• Batch keyed edits can use modify().by_*_in(&[...]).run(changed_flags, |row| ...) or modify().all().run(changed_flags, |row| ...).
• Batch removals can use remove().by_*_in(&[...]).run() or remove().all().run().

Example

use indexweave::MultiIndexMap;

#[derive(MultiIndexMap, Debug)]
#[multi_index_derive(Debug)]
#[multi_index_hash(rustc_hash::FxBuildHasher)]
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
        .lookup().by_trader_name(&"JohnDoe".to_string()).run()
        .collect::<Vec<_>>();
    assert_eq!(orders.len(), 2);
    println!("Found 2 orders for JohnDoe: [{orders:?}]");

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

    let order2_ref = map
        .modify()
        .by_order_id(&2)
        .run(MultiIndexOrderMapChangedIndexes::ALL, |o| {
            o.timestamp = 1656145183;
            o.order_id = 42;
        })
        .unwrap()
        .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
        .modify()
        .by_order_id(&42)
        .run(MultiIndexOrderMapChangedIndexes::EMPTY, |o| {
            o.filled = true;
            o.volume = 0;
        })
        .unwrap()
        .unwrap();
    assert_eq!(order2_ref.filled, true);
    assert_eq!(order2_ref.volume, 0);

    let orders = map
        .lookup().by_trader_name(&"JohnDoe".to_string()).run()
        .collect::<Vec<_>>();
    assert_eq!(orders.len(), 2);
    println!("Found 2 orders for JohnDoe: [{orders:?}]");

    let orders = map.remove().by_trader_name(&"JohnDoe".to_string()).run();
    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.
}

Under the hood

IndexWeave stores rows in a slab::Slab<T> and maintains one lookup table per index:

• Unique indexes map Key -> slab_index (HashMap or BTreeMap).
• Non-unique indexes map Key -> BTreeSet<slab_index>.

Core generated API families:

• Insertion: insert, try_insert (Result<&Row, UniquenessError<Row>>), insert_many, upsert_by_<unique_index>, upsert_many_by_<unique_index>, and entry().by_<field> for hashed_unique indexes (field-backed and computed).
• Retrieval: lookup().by_<field>().run() (unique -> Option, non-unique -> iterator), iter_by_<field>, plus iter.
• Mutation: modify().by_<field>().run(changed_flags, ...), modify().by_<field>_in(&[...]).run(changed_flags, ...), and modify().all().run(changed_flags, ...) (full row only).
• Transactional mutation (opt-in via #[multi_index(transactional)]): modify().by_<field>().run_transactional(changed_flags, ...), modify().by_<field>_in(&[...]).run_transactional(changed_flags, ...), and modify().all().run_transactional(changed_flags, ...).
• Removal: remove().by_<field>().run(), remove().by_<field>_in(&[...]).run(), and remove().all().run().
• Fallback groups: oneof_key fluent chains via by_<index>(...).or_<other>(...).run(...) on lookup/contains/modify/remove, plus entry for hashed-only groups.

Borrowed lookup keys are supported by keyed accessors where applicable (for example, &str against String index keys), including lookup().by_* and modify().by_*.

Use modify().by_*().run(changed_flags, ...) for all keyed mutations. Direct mutable bypass APIs (get_mut_by_*, iter_mut, multi_index_mut) are removed. Use run_transactional(...) only when atomic rollback semantics are required; it snapshots touched rows and rebuilds indexes before commit. entry().by_*().run().and_modify(changed_flags, ...) and entry().by_*().upsert_with(changed_flags, on_modify, on_insert).run() use the same changed-flag semantics as modify().run(...); under-declaring changed indexed fields can leave lookup indexes stale.

entry().by_<field>().run() is generated for hashed_unique indexes (including computed hashed-unique indexes) and returns an entry wrapper supporting:

• key, is_occupied, is_vacant, get
• and_modify(changed_flags, f)
• remove
• or_insert, or_insert_with
• or_try_insert, or_try_insert_with

entry().by_<field>(key) chains additionally support:

• upsert_with(changed_flags, on_modify, on_insert).run() -> Result<(&Row, S), <Map>EntryUpsertError<Row>>
• upsert_with(...).run_transactional() for transactional maps (#[multi_index(transactional)])

upsert_with behavior:

• Occupied: runs on_modify(&mut Row) -> S, applies reindexing based on the explicit changed_flags, and returns that state.
• Vacant: ignores changed_flags, runs on_insert(...) -> (Row, S), and returns that state.
• Errors: insert uniqueness failures map to EntryUpsertError::Insert(...); transactional modify failures map to EntryUpsertError::Modify(...).

// Non-transactional upsert_with
let (_row, state) = map
    .entry()
    .by_id(42)
    .upsert_with(
        MultiIndexUserMapChangedIndexes::EMAIL,
        |user| {
            user.email = "alice+new@example.com".to_string();
            "modified-state"
        },
        |id| (User { id: *id, ..new_user() }, "inserted-state"),
    )
    .run()?;

// Transactional upsert_with (requires #[multi_index(transactional)])
let (_row, state) = map
    .entry()
    .by_id(42)
    .upsert_with(
        MultiIndexUserMapChangedIndexes::EMAIL,
        |user| {
            user.email = "alice+new@example.com".to_string();
            "modified-state"
        },
        |id| (User { id: *id, ..new_user() }, "inserted-state"),
    )
    .run_transactional()?;

Limitations / Deferred

• No first-class stable handle API exists yet (SlotMap-like generation-checked IDs are deferred). Slab indices visible during iteration are traversal indices, not persistent handles.

Dependencies

See Cargo.toml for information on each dependency.

Future work

• Potentially a vector-map style lookup table would be very quick for small tables with integer indexes.
• Implement clever tricks used in boost::multi_index_containers to improve performance.