Port storage::BTreeMap to storage2

[Robbepop]

The new storage2 module is still missing a BTreeMap storage data structure implementation.

Low Priority

Since the storage2 module already has a map-like collection this issue is not as pressing as the similar issue about adding BinaryHeap or VecDeque to the storage2 module.

Old Implementation

A BTreeMap for the storage has already been implemented by @cmichi in the past for the old storage (revision 1) module. At that time it was really important to have since the old storage::HashMap was not even a real collection so we didn't have any other proper map-like storage collections.

Outline

This issue is about porting the BTreeMap from the old storage module to the storage2 module building on its new lazy abstractions and being operated over the new SpreadLayout trait with semantic that is common with the collections of the new storage2 module.

Benchmarks

Most of all we are this time also interested in how both map-like collections compare in performance and storage accesses with each other. So the main topic with this issue is also providing a set of benchmarks to provide us with more insight into when which map-like storage collection is a better fit.

ToDo List

Subsets of this ToDo list can suffice to craft a PR so we can implement the storage2::BTreeMap in many PRs incrementally.

• Port or implement the BTreeMap over to the storage2 module with this API:
  • new: Creates a new empty b-tree map.
  • len: Returns the number of elements stored in the b-tree map.
  • is_empty: Returns true if the b-tree map is empty.
  • contains_key: Returns true if the given key is contained in the b-tree map.
  • get: Returns a shared reference to the value at the given key.
  • get_mut: Returns an exclusive reference to the value at the given key.
  • get_key_value: Returns a shared reference to the key-value pair at the given key.
  • put: Inserts a new key-value pair into the b-tree map. Returns the old value if any.
  • Bonus insert: Inserts a new key-value pair into the b-tree map. Does NOT return the old value since this tries to minimize the contract storage read accesses.
  • take: Removes the key-value pair identified by the given key and returns it.
  • Bonus remove: Removes the key-value pair identified by the given key and does NOT return it. This tries to avoid read accesses to the contract storage.
  • iter: Returns an iterator over shared references to the key-value pair of the b-tree map.
  • keys: Returns an iterator over shared references to the keys of the b-tree map.
  • values: Returns an iterator over shared references to the values of the b-tree map.
  • values_mut: Returns an iterator over exclusive references to the values of the b-tree map.
  • Bonus clear: Clears all elements from the b-tree map with minimal storage writes and no storage reads. This should be much more efficient than manually removing all elements.
• Implement an Entry-API for the new BTreeMap similar to the one in the old storage module.
• Implement unit tests for all exposed functionality of the BTreeMap.
• Implement benchmark tests to compare both map-like collections:
  • Implement benchmark tests for storage2::BTreeMap.
  • Implement benchmark tests for storage2::HashMap.
  • Compare and discuss their results and take a conclusion when which one is the better fit.
• Implement the SpreadLayout trait for the b-tree map.
• Implement all important standard Rust traits for the b-tree map:
  • Default: For simply contract instantiation.
  • Debug: Should be derivable.
  • PartialEq + Eq if T: PartialEq and T: Eq: Mostly important for testing but anyways nice to have in general.
  • Drop: Must be implemented in order to command the underlying LazyIndexMap to clear its cells. For an example how to implement this properly take a look at the storage2::Vec.
  • Extend and FromIterator: Useful traits to initialize a b-tree map from an iterator.
  • IntoIterator for &BTreeMap and &mut BTreeMap: Generally useful for testing but also nice to have in general.

[KaiserKarel]

Is this issue still relevant? If so I could probably start working on this. Where is the storage2 crate located?

[cmichi]

I'm closing this issue as we've deprecated the BTreeMap in #1111 for now.