5 stable releases
2.4.2 | Jul 22, 2024 |
---|---|
2.4.0 | Jul 21, 2024 |
2.3.0 | Oct 18, 2023 |
2.2.0 | Jul 9, 2023 |
#58 in #constant-time
97 downloads per month
Used in 5 crates
(2 directly)
16KB
170 lines
🌀⏱️ CW Wormhole ⏱️🌀
A CosmWasm KV store that allows setting values from the past. For example:
use cosmwasm_std::{testing::mock_dependencies, Uint128, Addr};
use cw_wormhole::Wormhole;
let storage = &mut mock_dependencies().storage;
let w: Wormhole<Addr, Uint128> = Wormhole::new("ns");
let key = Addr::unchecked("violet");
// increment the value by one at time 10.
w.increment(storage, key.clone(), 10, Uint128::new(1))
.unwrap();
// increment the value by two at time 9.
w.increment(storage, key.clone(), 9, Uint128::new(2))
.unwrap();
// the value at time 10 is now three.
assert_eq!(
w.load(storage, key, 10).unwrap(),
Some(Uint128::new(3))
);
Loading a value from the map is always constant time. Updating values in the map is O(# future values). This has the effect of moving the complexity of incrementing a future value into the present.
For a more in-depth analysis of the runtime of this data structure, please see this essay.
Limitations
Reference types may not be used as keys.
Consider the trait bound:
for<'a> &'a (K, u64): PrimaryKey<'a>
This bound says, for any lifetime 'a
a reference to the tuple (K, u64)
will be a valid PrimaryKey
with lifetime 'a
, thus we can
store tuples of this type in the map.
In order to allow K to have a lifetime (call it 'k
), we'd need to
write:
for<'a where 'a: 'k> &'a (K, u64): PrimaryKey<'a>
As the lifetime of the primary key is 'a + 'k
(the minimum of the
key's lifetime and the tuple's lifetime).
Unfourtunately, Rust does not support this. There is an RFC to implement it here.
Dependencies
~5–6.5MB
~141K SLoC