#key #map #generate-keys #arena #storage

provenance

Container structures that generate key upon insertion that only works with the map that generated it

1 unstable release

0.1.0 Jan 12, 2021

#2058 in Data structures

MIT license

24KB
143 lines

Provenance

A Rust library that provides containers that upon insertion generate a key. This key will only work with the map that generated it.

Using the library

Add the following to your Cargo.toml:

[dependencies]
provenance = "0.1.0"

Example

use provenance::ProvenanceMap;

fn main() {
    let ages = ProvenanceMap::<u32>::new().unwrap();
    let names = ProvenanceMap::<String>::new().unwrap();
    
    let middle_age: Key<u32> = ages.insert(40); // Key generated on insert
    assert_eq!(&40, ages.get(middle_age)); // Key is used to retrieve stored value
    
    // names.get(middle_age); // Compile error, key can only be used with it's map
}

lib.rs:

This library provides containers where the keys are guaranteed to be valid. The key is generated when a value is inserted into the container. That key is guaranteed to only work with the map that generated it, and within that container always reference the same value.

use provenance::ProvenanceMap;

// A new map is easily created
let mut map = ProvenanceMap::<i32>::new().unwrap();

// Inserting a value into the map returns a key
let key = map.insert(5);

// That key is guaranteed to be able retrieve that value
assert_eq!(&5, map.get(key));
// Notice that the retrieved value is not wrapped in an Option or Result

Using a key with a map that did not create it is a compile time error:

use provenance::ProvenanceMap;

let mut map1 = ProvenanceMap::<i32>::new().unwrap();
let mut map2 = ProvenanceMap::<bool>::new().unwrap();

let key = map1.insert(5);
map2.get(key); // Using a key generated by map1 with map2 is a compilation error

Map uniqueness

To be able to guarantee that only keys created by a map can be used with that map, each map and key has a type parameter dedicated to denote provenance. However, for every provenance, there may only exist a unique map, thus creating a map may fail.

use provenance::ProvenanceMap;

// Creating a map is ok
let map = ProvenanceMap::<i32>::new();
assert!(map.is_some());

// Creating another with the same provenance is not
let map = ProvenanceMap::<i32>::new();
assert!(map.is_none()); // Creation failed and `None` were returned

Lightweight keys

The keys generated by this library's maps are ligthweight in the sense that they are copiable. This means that other copiable values can link to non-copiable values without worrying about lifetimes.

use provenance::{Key, ProvenanceMap};
use std::ops::Add;

struct Currency { name: String }

#[derive(Copy, Clone)]
struct Money { amount: i32, currency: Key<Currency> }
impl Add for Money {
    type Output = Money;

    fn add(self, rhs: Self) -> Self::Output {
        Money {
            amount: self.amount + rhs.amount,
            currency: self.currency,
        }
    }
}

let mut currencies = ProvenanceMap::<Currency>::new().unwrap();
let sek = currencies.insert(Currency { name: "Swedish Krona".into() });

let mon1 = Money { amount: 5, currency: sek };
let mon2 = Money { amount: 10, currency: sek };
let sum = mon1 + mon2;

assert_eq!(sek, sum.currency);
assert_eq!("Swedish Krona".to_string(), currencies.get(sum.currency).name);

Dependencies

~11KB