solidstate-network / solidstate-solidity

💠 Upgradeable-first Solidity smart contract development library 💠
https://discord.gg/BnvwfM6bRe
MIT License
428 stars 87 forks source link

Organize data structures #128

Closed ItsNickBarry closed 1 year ago

ItsNickBarry commented 2 years ago

As we add more data structure libraries, it makes sense to standardize their interfaces and how they're published. This will affect the scope of #126 and #127.

Data structures should all be stored in the contracts/data/ directory.

It seems like each data structure should have an implementation for each of address, uint256, and bytes32. What do you think, @0xCourtney?

ItsNickBarry commented 2 years ago

Also related: #34, #69.

0xCourtney commented 2 years ago

These data structures can accommodate the three types suggested above. The AVL tree structure has an Index struct which stores data about the tree such as the root node id, length, and mapping of nodes. The Node struct stores node metadata (parent, left, right indexes, node height), the id, and arbitrary values. I propose having three different Node types. AddressNode, UintNode, and Bytes32Node similar to what has been done in the EnumerableSet library.

struct Index {
   bytes32 head;
   bytes32 length;
   bytes32 root;
   mapping (bytes32 => Node) nodes;
}

struct Node {
   bytes32 id;
   bytes32 value;
   bytes32 parent;
   bytes32 left;
   bytes32 right;
   bytes32 height;
}

struct Bytes32Node {
   Index _index;
}

struct AddressNode {
   Index _index;
}

struct UintNode {
   Index _index;
}
ItsNickBarry commented 2 years ago

Okay, let's repeat that pattern then. Best to branch off of data-structures branch for each new data structure (for now).