solidstate-solidity icon indicating copy to clipboard operation
solidstate-solidity copied to clipboard

Organize data structures

Open ItsNickBarry opened this issue 2 years ago • 3 comments

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 avatar Jul 25 '22 12:07 ItsNickBarry

Also related: #34, #69.

ItsNickBarry avatar Jul 25 '22 12:07 ItsNickBarry

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;
}

0xCourtney avatar Jul 26 '22 19:07 0xCourtney

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

ItsNickBarry avatar Jul 26 '22 20:07 ItsNickBarry