Crate secret_toolkit_incubator
source ·Expand description
Secret Contract Development Toolkit - Incubator
⚠️ This package is a sub-package of the secret-toolkit
package. Please see its crate page for more context.
This package contains tools that are not yet final and may change or contain unknown bugs, and are pending more testing or reviews.
Max heap storage
A “max heap store” is a storage wrapper that implements a binary tree maxheap data structure. https://en.wikipedia.org/wiki/Min-max_heap Implementation based on https://algorithmtutor.com/Data-Structures/Tree/Binary-Heaps/
- Insertion O(log n)
- Remove max O(log n)
Usage
The usage of MaxHeapStoreMut
and MaxHeapStore
are modeled on AppendStoreMut
and AppendStore
, respectively. To add an item to the heap use insert
and to take the top value off use remove
, which also returns the item that was removed. To peek at the max value without removing, use the get_max
function. Duplicate items can be added to the heap.
let mut storage = MockStorage::new();
let mut heap_store = MaxHeapStoreMut::attach_or_create(&mut storage)?;
heap_store.insert(&1234)?;
heap_store.insert(&2143)?;
heap_store.insert(&4321)?;
heap_store.insert(&3412)?;
heap_store.insert(&2143)?;
assert_eq!(heap_store.remove(), Ok(4321));
assert_eq!(heap_store.remove(), Ok(3412));
assert_eq!(heap_store.remove(), Ok(2143));
assert_eq!(heap_store.remove(), Ok(2143));
assert_eq!(heap_store.remove(), Ok(1234));
In order to use a custom struct with MaxHeapStore
you will need to implement the appropriate Ordering traits. The following is an example with a custom struct Tx
that uses the amount
field to determine order in the heap:
#[derive(Serialize, Deserialize, Clone, Debug, Eq)]
pub struct Tx {
address: Addr,
amount: u128,
}
impl PartialOrd for Tx {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Tx {
fn cmp(&self, other: &Self) -> Ordering {
self.amount.cmp(&other.amount)
}
}
impl PartialEq for Tx {
fn eq(&self, other: &Self) -> bool {
self.amount == other.amount
}
}
let mut storage = MockStorage::new();
let mut heap_store = MaxHeapStoreMut::attach_or_create(&mut storage)?;
heap_store.insert(&Tx{
address: Addr::unchecked("address1"),
amount: 100,
})?;
heap_store.insert(&Tx{
address: Addr::unchecked("address2"),
amount: 200,
})?;
heap_store.insert(&Tx{
address: Addr::unchecked("address5"),
amount: 50,
})?;
assert_eq!(heap_store.remove(), Ok(Tx{
address: Addr::unchecked("address3"),
amount: 200,
}));
assert_eq!(heap_store.remove(), Ok(Tx{
address: Addr::unchecked("address4"),
amount: 100,
}));
assert_eq!(heap_store.remove(), Ok(Tx{
address: Addr::unchecked("address1"),
amount: 50,
}));
MaxHeapStore
is modeled on an AppendStore
and stores the array representation of the heap in the same way, e.g. using len
key to store the length. Therefore, you can attach an AppendStore
to a max heap instead of MaxHeapStore
if you want to iterate over all the values for some reason.
Generational index storage
Also known as a slot map, a generational index storage is an iterable data structure where each element in the list is identified by a unique key that is a pair (index, generation). Each time an item is removed from the list the generation of the storage increments by one. If a new item is placed at the same index as a previous item which had been removed previously, the old references will not point to the new element. This is because although the index matches, the generation does not. This ensures that each reference to an element in the list is stable and safe.
Starting with an empty set, if we insert A we will have key: (index: 0, generation: 0). Inserting B will have the key: (index: 1, generation: 0). When we remove A the generation will increment by 1 and index 0 will be freed up. When we insert C it will go to the head of our list of free slots and be given the key (index: 0, generation: 1). If you attempt to get A the result will be None, even though A and C have both been at “0” position in the list.
Unlike AppendStore, iteration over a generational index storage is not in order of insertion.
Use cases
The main use for this type of storage is when we want sets of elements that might be referenced by other structs or lists in a contract, and we want to ensure if an element is removed that our other references do not break. For example, imagine we have a contract where we want a collection of User structs that are independent of secret addresses (perhaps we want people to be able to move their accounts from one address to another). We also want people to be able to remove User accounts, so we use a generational index storage. We can reference the User account by its generational index key (index, generation). We can also reference relationships between users by adding a field in the User struct that points to another key in the generation index storage. If we remove a User and a new User is put in the same index but at a different generation, then there is no risk that the links will point to the wrong user. One can easily imagine this being expanded to a more heterogeneous group of inter-related elements, not just users.
In effect, this example is a graph structure where the nodes are elements and the references to unique (index, generation) pairs are the edges. Any graph like that could be implemented using the generational index storage.
Usage
See tests in generational_store.rs
for more examples, including iteration.
let mut storage = MockStorage::new();
let mut gen_store = GenerationalStoreMut::attach_or_create(&mut storage)?;
let alpha = gen_store.insert(String::from("Alpha"));
let beta = gen_store.insert(String::from("Beta"));
let gamma = gen_store.insert(String::from("Gamma"));
assert_eq!(gen_store.len(), 3_u32);
assert_eq!(gen_store.remove(beta.clone()), Ok(Some(String::from("Beta"))));
assert_eq!(gen_store.len(), 2_u32);
assert_eq!(gen_store.get(alpha), Some(String::from("Alpha")));
assert_eq!(gen_store.get(beta.clone()), None);
assert_eq!(gen_store.get(gamma), Some(String::from("Gamma")));
let delta = gen_store.insert(String::from("Delta"));
assert_eq!(gen_store.get(delta.clone()), Some(String::from("Delta")));
// check that the generation has updated
assert_ne!(delta.clone(), Index::from_raw_parts(1, 0));
// delta has filled the slot where beta was but generation is now 1
assert_eq!(delta, Index::from_raw_parts(1, 1));
// cannot remove twice
assert!(gen_store.remove(beta).is_err());
Todo
Rename as SlotMap? (see: https://docs.rs/slotmap/1.0.5/slotmap/) Simpler name though maybe not as evocative of what it actually does.
Re-exports
pub use generational_store::GenerationalStore;
pub use generational_store::GenerationalStoreMut;
pub use maxheap::MaxHeapStore;
pub use maxheap::MaxHeapStoreMut;
Modules
- A “generational index store” is a storage wrapper for a generational index, which allows for constant time insert and removal of arbitrary entries in a list. In this case an appendstore will not be suitable because it will mess up the indexes of all entries that follow the one that was deleted. Each get from the store requires a tuple of (index, generation), where generation is a monotonically increasing value that records the generation of the current data value at that index.
- A “max heap store” is a storage wrapper that implements a binary tree maxheap data structure. https://en.wikipedia.org/wiki/Min-max_heap Implementation based on https://algorithmtutor.com/Data-Structures/Tree/Binary-Heaps/