Crate iddqd

Expand description

Maps where keys are borrowed from values.

This crate consists of several map types, collectively called ID maps:

IdOrdMap: A B-Tree based map where keys are borrowed from values.
IdHashMap: A hash map where keys are borrowed from values.
BiHashMap: A bijective (1:1) hash map with two keys, borrowed from values.
TriHashMap: A trijective (1:1:1) hash map with three keys, borrowed from values.

§Usage

Pick your ID map type.
Depending on the ID map type, implement IdOrdItem, IdHashItem, BiHashItem, or TriHashItem for your value type.
Store values in the ID map type.

§Features

This crate was built out a practical need for map types, and addresses issues encountered using Rust’s default map types in practice at Oxide.

Keys are retrieved from values, not stored separately from them. Separate storage has been a recurring pain point in our codebases: if keys are duplicated within values, it’s proven to be hard to maintain consistency between keys and values. This crate addresses that need.
Keys may be borrowed from values, which allows for more flexible implementations. (They don’t have to be borrowed, but they can be.)
There’s no insert method; insertion must be through either insert_overwrite or insert_unique. You must pick an insertion behavior.
For hash maps, the default hasher is [foldhash], which is much faster than SipHash. However, foldhash does not provide the same level of HashDoS resistance as SipHash. If that is important to you, you can use a different hasher. (Disable the default-hasher feature to require a hash builder type parameter to be passed in.)
The serde implementations reject duplicate keys.

We’ve also sometimes needed to index a set of data by more than one key, or perhaps map one key to another. For that purpose, this crate provides BiHashMap and TriHashMap.

BiHashMap has two keys, and provides a bijection (1:1 relationship) between the keys.
TriHashMap has three keys, and provides a trijection (1:1:1 relationship) between the keys.

As a consequence of the general API structure, maps can have arbitrary non-key data associated with them as well.

§Examples

An example for IdOrdMap:

use iddqd::{IdOrdItem, IdOrdMap, id_upcast};

#[derive(Debug)]
struct User {
    name: String,
    age: u8,
}

// Implement IdOrdItem so the map knows how to get the key from the value.
impl IdOrdItem for User {
    // The key type can borrow from the value.
    type Key<'a> = &'a str;

    fn key(&self) -> Self::Key<'_> {
        &self.name
    }

    id_upcast!();
}

let mut users = IdOrdMap::<User>::new();

// You must pick an insertion behavior. insert_unique returns an error if
// the key already exists.
users.insert_unique(User { name: "Alice".to_string(), age: 30 }).unwrap();
users.insert_unique(User { name: "Bob".to_string(), age: 35 }).unwrap();

// Lookup by name:
assert_eq!(users.get("Alice").unwrap().age, 30);
assert_eq!(users.get("Bob").unwrap().age, 35);

// Iterate over users:
for user in &users {
    println!("User {}: {}", user.name, user.age);
}

Keys don’t have to be borrowed from the value. For smaller Copy types, it’s recommended that you use owned keys. Here’s an example of using IdOrdMap with a small integer key:

struct Record {
    id: u32,
    data: String,
}

impl IdOrdItem for Record {
    // The key type is small, so an owned key is preferred.
    type Key<'a> = u32;

    fn key(&self) -> Self::Key<'_> {
        self.id
    }

    id_upcast!();
}

// ...

An example for IdHashMap, showing a complex borrowed key. Here, “complex” means that the key is not a reference itself, but a struct that returns references to more than one field from the value.

use iddqd::{IdHashItem, id_hash_map, id_upcast};

#[derive(Debug)]
struct Artifact {
    name: String,
    version: String,
    data: Vec<u8>,
}

// The key type is a borrowed form of the name and version. It needs to
// implement `Eq + Hash`.
#[derive(Eq, Hash, PartialEq)]
struct ArtifactKey<'a> {
    name: &'a str,
    version: &'a str,
}

impl IdHashItem for Artifact {
    // The key type can borrow from the value.
    type Key<'a> = ArtifactKey<'a>;

    fn key(&self) -> Self::Key<'_> {
        ArtifactKey { name: &self.name, version: &self.version }
    }

    id_upcast!();
}

// Create a new `IdHashMap` with the given artifacts. This uses the
// `id_hash_map!` macro that comes with iddqd.
let artifacts = id_hash_map! {
    Artifact {
        name: "artifact1".to_owned(),
        version: "1.0".to_owned(),
        data: b"data1".to_vec(),
    },
    Artifact {
        name: "artifact2".to_owned(),
        version: "1.0".to_owned(),
        data: b"data2".to_vec(),
    },
};

// Look up artifacts by name and version.
assert_eq!(
    artifacts
        .get(&ArtifactKey { name: "artifact1", version: "1.0" })
        .unwrap()
        .data,
    b"data1",
);

For more examples, see the examples and extended examples directories.

§`Equivalent` and `Comparable`

An important feature of the standard library’s maps is that they allow any borrowed form of the key type to be used for lookups; for example, a HashMap<String, T> type can be looked up with a &str key. This is done through the Borrow trait.

But the Borrow trait is a bit too restrictive for complex keys such as ArtifactKey above, requiring workarounds such as dynamic dispatch. To address this, the crates.io ecosystem has standardized on the [Equivalent] and [Comparable] traits as generalizations of Borrow. The map types in this crate require these traits.

For a key type T::Key<'_> and a lookup type L:

The hash map types require L: Hash + Equivalent<T::Key<'_>>. Also, L must hash in the same way as T::Key<'_>. Typically, this is done by ensuring that enum variants and struct fields are in the same order¹.
IdOrdMap requires L: Comparable<T::Key<'_>>, which in turn requires Equivalent<T::Key<'_>>. (There’s no need for L to implement Ord or Eq itself.)

Continuing the ArtifactKey example from above, we can perform a lookup using a key of this owned form:

use equivalent::Equivalent;

// This is an owned form of ArtifactKey. The fields are in the same
// order as ArtifactKey's fields, so it hashes the same way.
#[derive(Hash)]
struct OwnedArtifactKey {
    name: String,
    version: String,
}

impl Equivalent<ArtifactKey<'_>> for OwnedArtifactKey {
    fn equivalent(&self, other: &ArtifactKey<'_>) -> bool {
        self.name == other.name && self.version == other.version
    }
}

// Now you can use OwnedArtifactKey to look up the artifact.
let owned_key = OwnedArtifactKey {
    name: "artifact1".to_owned(),
    version: "1.0".to_owned(),
};
assert_eq!(artifacts.get(&owned_key).unwrap().data, b"data1",);

There’s a blanket implementation of [Equivalent] and [Comparable] for Borrow, so if your type already implements Borrow, there aren’t any extra steps to take.

§Testing

This crate is validated through a combination of:

Unit tests
Property-based tests using a naive map as an oracle
Chaos tests for several kinds of buggy Eq and Ord implementations
Miri tests for unsafe code

If you see a gap in testing, new tests are welcome. Thank you!

§No-std compatibility

Most of this crate is no-std compatible, though alloc is required.

The IdOrdMap type is not currently no-std compatible due to its use of a thread-local. This thread-local is just a way to work around a limitation in std’s BTreeMap API, though. Either a custom B-Tree implementation, or a platform-specific notion of thread locals, would suffice to make IdOrdMap no-std compatible.

§Optional features

allocator-api2: Enables support for custom allocators via the [allocator_api2] crate. Both global and scoped/arena allocators (such as bumpalo) are supported. Custom allocators are not currently supported by IdOrdMap.
daft: Enables [daft] support for all ID map types. Not enabled by default.
default-hasher: Enables the DefaultHashBuilder type. Disable this feature to require a hash builder type parameter to be passed into IdHashMap, BiHashMap, and TriHashMap. Enabled by default.
proptest: Enables [proptest] support for all ID map types, providing Arbitrary implementations and strategies for property-based testing. Not enabled by default.
schemars08: Enables schemars support for all ID map types, including support for automatic replacement through typify or dropshot. Not enabled by default.
serde: Enables serde support for all ID map types. Not enabled by default.
std: Enables std support. Enabled by default.

bimap provides a bijective map, but does not have a way to associate arbitrary values with each pair of keys. However, it does support an ordered map type without the need for std.
multi_index_map provides maps with arbitrary indexes on fields, and is more flexible than this crate. However, it doesn’t expose generic traits for map types, and it requires key types to be Clone. In iddqd, we pick a somewhat different point in the design space, but we think multi_index_map is also great.
In general, this is similar to relational database records with indexes. For sufficiently complex use cases, consider an embedded database like SQLite, or even a networked database like PostgreSQL. iddqd is a good fit for simple in-memory caches of data stored in these databases.

§Minimum supported Rust version (MSRV)

This crate’s MSRV is Rust 1.81. In general we aim for 6 months of Rust compatibility.

§What does iddqd mean?

The name iddqd is a reference to a cheat code in the classic video game Doom. It has id in the name, and is short and memorable.

We recommend that you test this with e.g. a property-based test: see this example. ↩

Re-exports§

pub use equivalent::Comparable;
pub use equivalent::Equivalent;

Modules§

bi_hash_map: A hash map where values are uniquely indexed by two keys.
errors: Error types for this crate.
id_hash_map: A hash map where keys are part of the values.
id_ord_map: An ordered map where the keys are part of the values, based on a B-Tree.
tri_hash_map: A hash map where values are uniquely indexed by three keys.

Macros§

bi_hash_map: Creates a BiHashMap from a list of items.
bi_upcast: Implement upcasts for BiHashMap.
id_hash_map: Creates an IdHashMap from a list of items.
id_ord_map: Creates an IdOrdMap from a list of items.
id_upcast: Implement upcasts for IdOrdMap or IdHashMap.
tri_hash_map: Creates a TriHashMap from a list of items.
tri_upcast: Implement upcasts for TriHashMap.

Structs§

BiHashMap: A 1:1 (bijective) map for two keys and a value.
IdHashMap: A hash map where the key is part of the value.
IdOrdMap: An ordered map where the keys are part of the values, based on a B-Tree.
TriHashMap: A 1:1:1 (trijective) map for three keys and a value.

Traits§

BiHashItem: An item in a BiHashMap.
IdHashItem: An element stored in an IdHashMap.
IdOrdItem: An element stored in an IdOrdMap.
TriHashItem: An item in a TriHashMap.

Type Aliases§

DefaultHashBuilder: Default hasher for hash map types.

Crate iddqd

Crate iddqd Copy item path

§Usage

§Features

§Examples

§Equivalent and Comparable

§Testing

§No-std compatibility

§Optional features

§Related work

§Minimum supported Rust version (MSRV)

§What does iddqd mean?

Re-exports§

Modules§

Macros§

Structs§

Traits§

Type Aliases§

Crate iddqd

§`Equivalent` and `Comparable`