<!-- cargo-sync-rdme title [[ -->

iddqd

<!-- cargo-sync-rdme ]] --> <!-- cargo-sync-rdme badge [[ -->

<!-- cargo-sync-rdme ]] --> <!-- cargo-sync-rdme rustdoc [[ -->

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[^proptest].
• 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.)

[^proptest]: We recommend that you test this with e.g. a property-based test: see this example.

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 crat