3

Inspired by Garbage collection

A hierarchical storage pattern of objects inside objects is a pretty common device. How could one organize such a thing and avoid problems with increasing gas cost at scale?

  • A lot of this type of question have been posted recently, but really it just comes down to understanding classical data structures. Essentially the same things will be efficient on the EVM as will be in C or Java. – Tjaden Hess Apr 4 '17 at 3:06
5

In the spirit of Are there well-solved and simple storage patterns for Solidity?.

This one is a little more involved, but it seems like a re-usable pattern. The basic structure of each node is:

  1. A bool to indicate that the node is valid
  2. A parent key pointer for crawling UP
  3. An unordered list of child keys
  4. A row number of "this" node on the corresponding parent's list of children

This pattern attempts to eliminate unbounded search operations in the contract by pushing most of the recursive/loopy functions to the client-side. A node can be validated (exists) in one move. Searches and inserts use a "hint" that should be "approximately" near the insertion point or solution. The contract will resolve the exact location in the ordered list. The hint helps reduce gas cost for potentially high-cost searches. The better the hint, the lower the cost.

The pattern supports pruning of branches and their contents at any scale with a consistent, low gas cost.

In the case that a client wants to validate that a nodeId isn't inside a pruned branch, the client should recursively explore the parents until the "root" parent (has parent == 0) is found and confirm that isNode == true ... otherwise the key to check is inside a pruned branch.

Example:

pragma solidity ^0.4.6; 

// Simple, Scalable Object Tree 
// Supports top-down tree exploration
// and pruning of branches. 

// Random node membership can be confirmed client-side.
// Crawl parents recursively and confirm root node (parent=0) isNode==true. 
// Not the case for members of pruned branches. 

contract ObjectTree {

    bytes32 public treeRoot;

    struct NodeStruct {
        bool isNode;
        bytes32 parent; // the id of the parent node
        uint parentIndex; //  the position of this node in the Parent's children list
        bytes32[] children; // unordered list of children below this node
        // more node attributes here
    }

    mapping(bytes32 => NodeStruct) public nodeStructs;

    event LogNewNode(address sender, bytes32 nodeId, bytes32 parentId);
    event LogDelNode(address sender, bytes32 nodeId);

    function ObjectTree() {
        treeRoot = newNode(0);
    }

    function isNode(bytes32 nodeId)
        public
        constant
        returns(bool isIndeed)
    {
        return nodeStructs[nodeId].isNode;
    }

    function newNode(bytes32 parent) 
        public
        returns(bytes32 newNodeId)
    {
        if(!isNode(parent) && parent > 0) throw; // zero is a new root node
        newNodeId = sha3(parent, msg.sender, block.number);
        NodeStruct memory node;
        node.parent = parent;
        node.isNode = true;
        // more node atributes here
        if(parent>0) {
            node.parentIndex = registerChild(parent,newNodeId);
        }
        nodeStructs[newNodeId] = node;
        LogNewNode(msg.sender, newNodeId, parent);
        return newNodeId;
    }

    /*
    Depends entirely on the attributes you want to store in the nodes

    function updateNode(bytes32 nodeId, attr ... )
        public
        returns(bool success)
    {
        nodeStructs[nodeId].attrib = attrib];
        Log ... 
        return true;
    }
    */

    function registerChild(bytes32 parentId, bytes32 childId)
        private
        returns(uint index)
    {
        return nodeStructs[parentId].children.push(childId) - 1;
    }

    // Invalidates and detaches node to prune. 
    // Does not invalidate recursively (scalability). 
    // Top-Down crawl will avoid pruned branches. 
    // Bottom-Up validation will find apparent "root" isNode==false. 

    function pruneBranch(bytes32 nodeId)
        public
        returns(bool success)
    {
        bytes32 parent = nodeStructs[nodeId].parent;
        uint rowToDelete = nodeStructs[nodeId].parentIndex;
        uint rowToMove = nodeStructs[parent].children.length-1; // last child in the list
        nodeStructs[parent].children[rowToDelete] = nodeStructs[parent].children[rowToMove];
        nodeStructs[nodeStructs[parent].children[rowToMove]].parentIndex = rowToMove;
        nodeStructs[parent].children.length--;
        nodeStructs[nodeId].parent=0;
        nodeStructs[nodeId].parentIndex=0;
        nodeStructs[nodeId].isNode = false;
        LogDelNode(msg.sender, nodeId);
        return true;
    }

    function getNodeChildCount(bytes32 nodeId)
        public
        constant
        returns(uint childCount)
    {
        return(nodeStructs[nodeId].children.length);
    }

    function getNodeChildAtIndex(bytes32 nodeId, uint index) 
        public 
        constant
        returns(bytes32 childId)
    {
        return nodeStructs[nodeId].children[index];
    }

}

Hope it helps.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.