Contract 0x7AE716d9935F41F173D944FE6557c1e117d561E9

Txn Hash Method
Block
From
To
Value [Txn Fee]
0x67fd0f3f033440b25a1910291823675ad2dcda618b4e86b3b8b6f05ca636ff690x6108d061168955982021-07-03 20:53:15518 days 19 hrs ago0x42fc1fe86e15eb56a2815e6230aa88efc87f5c15 IN  Create: SortitionSumTreeFactory0 xDAI0.00539257
[ Download CSV Export 
View more zero value Internal Transactions in Advanced View mode
Loading

Contract Source Code Verified (Exact Match)

Contract Name:
SortitionSumTreeFactory

Compiler Version
v0.4.26+commit.4563c3fc

Optimization Enabled:
Yes with 200 runs

Other Settings:
default evmVersion
/**
 *Submitted for verification at gnosisscan.io on 2022-08-04
*/

// File: @kleros/kleros/contracts/data-structures/SortitionSumTreeFactory.sol

/**
 *  @authors: [@epiqueras]
 *  @reviewers: [@clesaege, @unknownunknown1, @ferittuncer, @remedcu]
 *  @auditors: []
 *  @bounties: [{ duration: 28 days, link: https://github.com/kleros/kleros/issues/115, maxPayout: 50 ETH }]
 *  @deployments: [ https://etherscan.io/address/0x180eba68d164c3f8c3f6dc354125ebccf4dfcb86 ]
 */

pragma solidity ^0.4.24;

/**
 *  @title SortitionSumTreeFactory
 *  @author Enrique Piqueras - <[email protected]>
 *  @dev A factory of trees that keep track of staked values for sortition.
 */
library SortitionSumTreeFactory {
    /* Structs */

    struct SortitionSumTree {
        uint K; // The maximum number of childs per node.
        // We use this to keep track of vacant positions in the tree after removing a leaf. This is for keeping the tree as balanced as possible without spending gas on moving nodes around.
        uint[] stack;
        uint[] nodes;
        // Two-way mapping of IDs to node indexes. Note that node index 0 is reserved for the root node, and means the ID does not have a node.
        mapping(bytes32 => uint) IDsToNodeIndexes;
        mapping(uint => bytes32) nodeIndexesToIDs;
    }

    /* Storage */

    struct SortitionSumTrees {
        mapping(bytes32 => SortitionSumTree) sortitionSumTrees;
    }

    /* Public */

    /**
     *  @dev Create a sortition sum tree at the specified key.
     *  @param _key The key of the new tree.
     *  @param _K The number of children each node in the tree should have.
     */
    function createTree(SortitionSumTrees storage self, bytes32 _key, uint _K) public {
        SortitionSumTree storage tree = self.sortitionSumTrees[_key];
        require(tree.K == 0, "Tree already exists.");
        require(_K > 1, "K must be greater than one.");
        tree.K = _K;
        tree.stack.length = 0;
        tree.nodes.length = 0;
        tree.nodes.push(0);
    }

    /**
     *  @dev Set a value of a tree.
     *  @param _key The key of the tree.
     *  @param _value The new value.
     *  @param _ID The ID of the value.
     *  `O(log_k(n))` where
     *  `k` is the maximum number of childs per node in the tree,
     *   and `n` is the maximum number of nodes ever appended.
     */
    function set(SortitionSumTrees storage self, bytes32 _key, uint _value, bytes32 _ID) public {
        SortitionSumTree storage tree = self.sortitionSumTrees[_key];
        uint treeIndex = tree.IDsToNodeIndexes[_ID];

        if (treeIndex == 0) { // No existing node.
            if (_value != 0) { // Non zero value.
                // Append.
                // Add node.
                if (tree.stack.length == 0) { // No vacant spots.
                    // Get the index and append the value.
                    treeIndex = tree.nodes.length;
                    tree.nodes.push(_value);

                    // Potentially append a new node and make the parent a sum node.
                    if (treeIndex != 1 && (treeIndex - 1) % tree.K == 0) { // Is first child.
                        uint parentIndex = treeIndex / tree.K;
                        bytes32 parentID = tree.nodeIndexesToIDs[parentIndex];
                        uint newIndex = treeIndex + 1;
                        tree.nodes.push(tree.nodes[parentIndex]);
                        delete tree.nodeIndexesToIDs[parentIndex];
                        tree.IDsToNodeIndexes[parentID] = newIndex;
                        tree.nodeIndexesToIDs[newIndex] = parentID;
                    }
                } else { // Some vacant spot.
                    // Pop the stack and append the value.
                    treeIndex = tree.stack[tree.stack.length - 1];
                    tree.stack.length--;
                    tree.nodes[treeIndex] = _value;
                }

                // Add label.
                tree.IDsToNodeIndexes[_ID] = treeIndex;
                tree.nodeIndexesToIDs[treeIndex] = _ID;

                updateParents(self, _key, treeIndex, true, _value);
            }
        } else { // Existing node.
            if (_value == 0) { // Zero value.
                // Remove.
                // Remember value and set to 0.
                uint value = tree.nodes[treeIndex];
                tree.nodes[treeIndex] = 0;

                // Push to stack.
                tree.stack.push(treeIndex);

                // Clear label.
                delete tree.IDsToNodeIndexes[_ID];
                delete tree.nodeIndexesToIDs[treeIndex];

                updateParents(self, _key, treeIndex, false, value);
            } else if (_value != tree.nodes[treeIndex]) { // New, non zero value.
                // Set.
                bool plusOrMinus = tree.nodes[treeIndex] <= _value;
                uint plusOrMinusValue = plusOrMinus ? _value - tree.nodes[treeIndex] : tree.nodes[treeIndex] - _value;
                tree.nodes[treeIndex] = _value;

                updateParents(self, _key, treeIndex, plusOrMinus, plusOrMinusValue);
            }
        }
    }

    /* Public Views */

    /**
     *  @dev Query the leaves of a tree. Note that if `startIndex == 0`, the tree is empty and the root node will be returned.
     *  @param _key The key of the tree to get the leaves from.
     *  @param _cursor The pagination cursor.
     *  @param _count The number of items to return.
     *  @return startIndex The index at which leaves start.
     *  @return values The values of the returned leaves.
     *  @return hasMore Whether there are more for pagination.
     *  `O(n)` where
     *  `n` is the maximum number of nodes ever appended.
     */
    function queryLeafs(
        SortitionSumTrees storage self,
        bytes32 _key,
        uint _cursor,
        uint _count
    ) public view returns(uint startIndex, uint[] values, bool hasMore) {
        SortitionSumTree storage tree = self.sortitionSumTrees[_key];

        // Find the start index.
        for (uint i = 0; i < tree.nodes.length; i++) {
            if ((tree.K * i) + 1 >= tree.nodes.length) {
                startIndex = i;
                break;
            }
        }

        // Get the values.
        uint loopStartIndex = startIndex + _cursor;
        values = new uint[](loopStartIndex + _count > tree.nodes.length ? tree.nodes.length - loopStartIndex : _count);
        uint valuesIndex = 0;
        for (uint j = loopStartIndex; j < tree.nodes.length; j++) {
            if (valuesIndex < _count) {
                values[valuesIndex] = tree.nodes[j];
                valuesIndex++;
            } else {
                hasMore = true;
                break;
            }
        }
    }

    /**
     *  @dev Draw an ID from a tree using a number. Note that this function reverts if the sum of all values in the tree is 0.
     *  @param _key The key of the tree.
     *  @param _drawnNumber The drawn number.
     *  @return ID The drawn ID.
     *  `O(k * log_k(n))` where
     *  `k` is the maximum number of childs per node in the tree,
     *   and `n` is the maximum number of nodes ever appended.
     */
    function draw(SortitionSumTrees storage self, bytes32 _key, uint _drawnNumber) public view returns(bytes32 ID) {
        SortitionSumTree storage tree = self.sortitionSumTrees[_key];
        uint treeIndex = 0;
        uint currentDrawnNumber = _drawnNumber % tree.nodes[0];

        while ((tree.K * treeIndex) + 1 < tree.nodes.length)  // While it still has children.
            for (uint i = 1; i <= tree.K; i++) { // Loop over children.
                uint nodeIndex = (tree.K * treeIndex) + i;
                uint nodeValue = tree.nodes[nodeIndex];

                if (currentDrawnNumber >= nodeValue) currentDrawnNumber -= nodeValue; // Go to the next child.
                else { // Pick this child.
                    treeIndex = nodeIndex;
                    break;
                }
            }

        ID = tree.nodeIndexesToIDs[treeIndex];
    }

    /** @dev Gets a specified ID's associated value.
     *  @param _key The key of the tree.
     *  @param _ID The ID of the value.
     *  @return value The associated value.
     */
    function stakeOf(SortitionSumTrees storage self, bytes32 _key, bytes32 _ID) public view returns(uint value) {
        SortitionSumTree storage tree = self.sortitionSumTrees[_key];
        uint treeIndex = tree.IDsToNodeIndexes[_ID];

        if (treeIndex == 0) value = 0;
        else value = tree.nodes[treeIndex];
    }

    /* Private */

    /**
     *  @dev Update all the parents of a node.
     *  @param _key The key of the tree to update.
     *  @param _treeIndex The index of the node to start from.
     *  @param _plusOrMinus Wether to add (true) or substract (false).
     *  @param _value The value to add or substract.
     *  `O(log_k(n))` where
     *  `k` is the maximum number of childs per node in the tree,
     *   and `n` is the maximum number of nodes ever appended.
     */
    function updateParents(SortitionSumTrees storage self, bytes32 _key, uint _treeIndex, bool _plusOrMinus, uint _value) private {
        SortitionSumTree storage tree = self.sortitionSumTrees[_key];

        uint parentIndex = _treeIndex;
        while (parentIndex != 0) {
            parentIndex = (parentIndex - 1) / tree.K;
            tree.nodes[parentIndex] = _plusOrMinus ? tree.nodes[parentIndex] + _value : tree.nodes[parentIndex] - _value;
        }
    }
}

Contract ABI

[{"constant":false,"inputs":[{"name":"self","type":"SortitionSumTreeFactory.SortitionSumTrees storage"},{"name":"_key","type":"bytes32"},{"name":"_value","type":"uint256"},{"name":"_ID","type":"bytes32"}],"name":"set","outputs":[],"payable":false,"stateMutability":"nonpayable","type":"function"},{"constant":true,"inputs":[{"name":"self","type":"SortitionSumTreeFactory.SortitionSumTrees storage"},{"name":"_key","type":"bytes32"},{"name":"_cursor","type":"uint256"},{"name":"_count","type":"uint256"}],"name":"queryLeafs","outputs":[{"name":"startIndex","type":"uint256"},{"name":"values","type":"uint256[]"},{"name":"hasMore","type":"bool"}],"payable":false,"stateMutability":"view","type":"function"},{"constant":true,"inputs":[{"name":"self","type":"SortitionSumTreeFactory.SortitionSumTrees storage"},{"name":"_key","type":"bytes32"},{"name":"_ID","type":"bytes32"}],"name":"stakeOf","outputs":[{"name":"value","type":"uint256"}],"payable":false,"stateMutability":"view","type":"function"},{"constant":true,"inputs":[{"name":"self","type":"SortitionSumTreeFactory.SortitionSumTrees storage"},{"name":"_key","type":"bytes32"},{"name":"_drawnNumber","type":"uint256"}],"name":"draw","outputs":[{"name":"ID","type":"bytes32"}],"payable":false,"stateMutability":"view","type":"function"},{"constant":false,"inputs":[{"name":"self","type":"SortitionSumTreeFactory.SortitionSumTrees storage"},{"name":"_key","type":"bytes32"},{"name":"_K","type":"uint256"}],"name":"createTree","outputs":[],"payable":false,"stateMutability":"nonpayable","type":"function"}]

6108d0610030600b82828239805160001a6073146000811461002057610022565bfe5b5030600052607381538281f30073000000000000000000000000000000000000000030146080604052600436106100835763ffffffff7c01000000000000000000000000000000000000000000000000000000006000350416632e25c38a811461008857806365b81f4f146100ab5780637521ccb11461012557806388c1d467146101485780639075789e14610159575b600080fd5b81801561009457600080fd5b506100a9600435602435604435606435610177565b005b6100bf600435602435604435606435610464565b604051808481526020018060200183151515158152602001828103825284818151815260200191508051906020019060200280838360005b8381101561010f5781810151838201526020016100f7565b5050505090500194505050505060405180910390f35b610136600435602435604435610573565b60408051918252519081900360200190f35b6101366004356024356044356105c6565b81801561016557600080fd5b506100a9600435602435604435610697565b600083815260208581526040808320848452600381019092528220549091808080808086151561031157891561030c576001880154151561028257600288018054600180820183556000928352602090922081018c9055975087148015906101ed5750875460001988018115156101ea57fe5b06155b1561027d578754878115156101fe57fe5b04600081815260048a01602052604090205460028a0180549298509096506001890195509081908890811061022f57fe5b600091825260208083209091015483546001810185559383528183209093019290925587815260048a01808352604080832083905588835260038c0184528083208890558783529252208590555b6102d9565b600188018054600019810190811061029657fe5b6000918252602090912001546001890180549198506102b990600019830161085a565b508988600201888154811015156102cc57fe5b6000918252602090912001555b600089815260038901602090815260408083208a905589835260048b01909152902089905561030c8c8c8960018e6107c0565b610456565b89151561039f576002880180548890811061032857fe5b906000526020600020015492506000886002018881548110151561034857fe5b60009182526020808320909101929092556001808b01805491820181558252828220018990558a815260038a018252604080822082905589825260048b0190925290812081905561030c908d908d908a90876107c0565b600288018054889081106103af57fe5b90600052602060002001548a141515610456578988600201888154811015156103d457fe5b9060005260206000200154111591508161040b578988600201888154811015156103fa57fe5b906000526020600020015403610429565b6002880180548890811061041b57fe5b90600052602060002001548a035b905089886002018881548110151561043d57fe5b6000918252602090912001556104568c8c8985856107c0565b505050505050505050505050565b60008381526020859052604081206060908290818080805b60028501548410156104ac57600285015485548502600101106104a1578397506104ac565b60019093019261047c565b6002850154888b019350898401116104c457886104cd565b60028501548390035b6040519080825280602002602001820160405280156104f6578160200160208202803883390190505b509650600091508290505b60028501548110156105645788821015610553576002850180548290811061052557fe5b9060005260206000200154878381518110151561053e57fe5b6020908102909101015260019091019061055c565b60019550610564565b600101610501565b50505050509450945094915050565b6000828152602084815260408083208484526003810190925282205480151561059f57600092506105bd565b600282018054829081106105af57fe5b906000526020600020015492505b50509392505050565b60008281526020849052604081206002810180548391829182918291829190829081106105ef57fe5b90600052602060002001548881151561060457fe5b0693505b600286015486548602600101101561067957600192505b8554831161067457855460028701805491870285019350908390811061064157fe5b906000526020600020015490508084101515610661578084039350610669565b819450610674565b60019092019161061f565b610608565b50505060009182525060049091016020526040902054949350505050565b600082815260208490526040902080541561071357604080517f08c379a000000000000000000000000000000000000000000000000000000000815260206004820152601460248201527f5472656520616c7265616479206578697374732e000000000000000000000000604482015290519081900360640190fd5b6001821161078257604080517f08c379a000000000000000000000000000000000000000000000000000000000815260206004820152601b60248201527f4b206d7573742062652067726561746572207468616e206f6e652e0000000000604482015290519081900360640190fd5b8181556000610794600183018261085a565b5060006107a4600283018261085a565b5060020180546001810182556000918252602082200155505050565b6000848152602086905260409020835b801561085157815460001982018115156107e657fe5b049050836108115782826002018281548110151561080057fe5b906000526020600020015403610830565b82826002018281548110151561082357fe5b9060005260206000200154015b6002830180548390811061084057fe5b6000918252602090912001556107d0565b50505050505050565b81548183558181111561087e5760008381526020902061087e918101908301610883565b505050565b6108a191905b8082111561089d5760008155600101610889565b5090565b905600a165627a7a72305820f7b0b6cb20b64775129cdb830e5e8035676b7963618d7e4d6e2a3931d91377bc0029

Block Transaction Gas Used Reward
Age Block Fee Address BC Fee Address Voting Power Jailed Incoming
Block Uncle Number Difficulty Gas Used Reward
Loading
Make sure to use the "Vote Down" button for any spammy posts, and the "Vote Up" for interesting conversations.