Contract Source Code (Solidity Standard Json-Input format)

IDE

• Blockscan IDE

More Options

• Similar
• Sol2Uml
• Submit Audit
• Compare

// SPDX-FileCopyrightText: 2023 Lido <[email protected]>
// SPDX-License-Identifier: GPL-3.0

/* See contracts/COMPILERS.md */
// solhint-disable-next-line
pragma solidity >=0.4.24 <0.9.0;

import {Math256} from "./Math256.sol";

/// @notice Library with methods to calculate "proportional" allocations among buckets with different
///     capacity and level of filling.
/// @dev The current implementation favors buckets with the least fill factor
library MinFirstAllocationStrategy {
    uint256 private constant MAX_UINT256 = 2**256 - 1;

    /// @notice Allocates passed maxAllocationSize among the buckets. The resulting allocation doesn't exceed the
    ///     capacities of the buckets. An algorithm starts filling from the least populated buckets to equalize the fill factor.
    ///     For example, for buckets: [9998, 70, 0], capacities: [10000, 101, 100], and maxAllocationSize: 101, the allocation happens
    ///     following way:
    ///         1. top up the bucket with index 2 on 70. Intermediate state of the buckets: [9998, 70, 70]. According to the definition,
    ///            the rest allocation must be proportionally split among the buckets with the same values.
    ///         2. top up the bucket with index 1 on 15. Intermediate state of the buckets: [9998, 85, 70].
    ///         3. top up the bucket with index 2 on 15. Intermediate state of the buckets: [9998, 85, 85].
    ///         4. top up the bucket with index 1 on 1. Nothing to distribute. The final state of the buckets: [9998, 86, 85]
    /// @dev Method modifies the passed buckets array to reduce the gas costs on memory allocation.
    /// @param buckets The array of current allocations in the buckets
    /// @param capacities The array of capacities of the buckets
    /// @param allocationSize The desired value to allocate among the buckets
    /// @return allocated The total value allocated among the buckets. Can't exceed the allocationSize value
    function allocate(
        uint256[] memory buckets,
        uint256[] memory capacities,
        uint256 allocationSize
    ) public pure returns (uint256 allocated, uint256[] memory) {
        uint256 allocatedToBestCandidate = 0;
        while (allocated < allocationSize) {
            allocatedToBestCandidate = allocateToBestCandidate(buckets, capacities, allocationSize - allocated);
            if (allocatedToBestCandidate == 0) {
                break;
            }
            allocated += allocatedToBestCandidate;
        }
        return (allocated, buckets);
    }

    /// @notice Allocates the max allowed value not exceeding allocationSize to the bucket with the least value.
    ///     The candidate search happens according to the following algorithm:
    ///         1. Find the first least filled bucket which has free space. Count the number of such buckets.
    ///         2. If no buckets are found terminate the search - no free buckets
    ///         3. Find the first bucket with free space, which has the least value greater
    ///             than the bucket found in step 1. To preserve proportional allocation the resulting allocation can't exceed this value.
    ///         4. Calculate the allocation size as:
    ///             min(
    ///                 (count of least filling buckets > 1 ? ceilDiv(allocationSize, count of least filling buckets) : allocationSize),
    ///                 fill factor of the bucket found in step 3,
    ///                 free space of the least filled bucket
    ///             )
    /// @dev Method modifies the passed buckets array to reduce the gas costs on memory allocation.
    /// @param buckets The array of current allocations in the buckets
    /// @param capacities The array of capacities of the buckets
    /// @param allocationSize The desired value to allocate to the bucket
    /// @return allocated The total value allocated to the bucket. Can't exceed the allocationSize value
    function allocateToBestCandidate(
        uint256[] memory buckets,
        uint256[] memory capacities,
        uint256 allocationSize
    ) internal pure returns (uint256 allocated) {
        uint256 bestCandidateIndex = buckets.length;
        uint256 bestCandidateAllocation = MAX_UINT256;
        uint256 bestCandidatesCount = 0;

        if (allocationSize == 0) {
            return 0;
        }

        for (uint256 i = 0; i < buckets.length; ++i) {
            if (buckets[i] >= capacities[i]) {
                continue;
            } else if (bestCandidateAllocation > buckets[i]) {
                bestCandidateIndex = i;
                bestCandidatesCount = 1;
                bestCandidateAllocation = buckets[i];
            } else if (bestCandidateAllocation == buckets[i]) {
                bestCandidatesCount += 1;
            }
        }

        if (bestCandidatesCount == 0) {
            return 0;
        }

        // cap the allocation by the smallest larger allocation than the found best one
        uint256 allocationSizeUpperBound = MAX_UINT256;
        for (uint256 j = 0; j < buckets.length; ++j) {
            if (buckets[j] >= capacities[j]) {
                continue;
            } else if (buckets[j] > bestCandidateAllocation && buckets[j] < allocationSizeUpperBound) {
                allocationSizeUpperBound = buckets[j];
            }
        }

        allocated = Math256.min(
            bestCandidatesCount > 1 ? Math256.ceilDiv(allocationSize, bestCandidatesCount) : allocationSize,
            Math256.min(allocationSizeUpperBound, capacities[bestCandidateIndex]) - bestCandidateAllocation
        );
        buckets[bestCandidateIndex] += allocated;
    }
}

// SPDX-FileCopyrightText: 2023 Lido <[email protected]>
// SPDX-License-Identifier: MIT

// Copied from: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/0457042d93d9dfd760dbaa06a4d2f1216fdbe297/contracts/utils/math/Math.sol

// See contracts/COMPILERS.md
// solhint-disable-next-line
pragma solidity >=0.4.24 <0.9.0;

library Math256 {
    /// @dev Returns the largest of two numbers.
    function max(uint256 a, uint256 b) internal pure returns (uint256) {
        return a > b ? a : b;
    }

    /// @dev Returns the smallest of two numbers.
    function min(uint256 a, uint256 b) internal pure returns (uint256) {
        return a < b ? a : b;
    }

    /// @dev Returns the largest of two numbers.
    function max(int256 a, int256 b) internal pure returns (int256) {
        return a > b ? a : b;
    }

    /// @dev Returns the smallest of two numbers.
    function min(int256 a, int256 b) internal pure returns (int256) {
        return a < b ? a : b;
    }

    /// @dev Returns the ceiling of the division of two numbers.
    ///
    /// This differs from standard division with `/` in that it rounds up instead
    /// of rounding down.
    function ceilDiv(uint256 a, uint256 b) internal pure returns (uint256) {
        // (a + b - 1) / b can overflow on addition, so we distribute.
        return a == 0 ? 0 : (a - 1) / b + 1;
    }

    /// @dev Returns absolute difference of two numbers.
    function absDiff(uint256 a, uint256 b) internal pure returns (uint256) {
        return a > b ? a - b : b - a;
    }
}

{
  "optimizer": {
    "enabled": true,
    "runs": 200
  },
  "evmVersion": "istanbul",
  "outputSelection": {
    "*": {
      "*": [
        "evm.bytecode",
        "evm.deployedBytecode",
        "devdoc",
        "userdoc",
        "metadata",
        "abi"
      ]
    }
  },
  "libraries": {}
}

[{"inputs":[{"internalType":"uint256[]","name":"buckets","type":"uint256[]"},{"internalType":"uint256[]","name":"capacities","type":"uint256[]"},{"internalType":"uint256","name":"allocationSize","type":"uint256"}],"name":"allocate","outputs":[{"internalType":"uint256","name":"allocated","type":"uint256"},{"internalType":"uint256[]","name":"","type":"uint256[]"}],"stateMutability":"pure","type":"function"}]

61057861003a600b82828239805160001a60731461002d57634e487b7160e01b600052600060045260246000fd5b30600052607381538281f3fe73000000000000000000000000000000000000000030146080604052600436106100355760003560e01c80632529fbc91461003a575b600080fd5b61004d6100483660046103ef565b610064565b60405161005b92919061045c565b60405180910390f35b6000606060005b838310156100a457610087868661008286886104c0565b6100ad565b905080610093576100a4565b61009d81846104d7565b925061006b565b50909492505050565b825160009060001982846100c757600093505050506102ea565b60005b8751811015610199578681815181106100e5576100e56104ef565b60200260200101518882815181106100ff576100ff6104ef565b60200260200101511061011157610189565b878181518110610123576101236104ef565b602002602001015183111561015a578093506001915087818151811061014b5761014b6104ef565b60200260200101519250610189565b87818151811061016c5761016c6104ef565b6020026020010151831415610189576101866001836104d7565b91505b61019281610505565b90506100ca565b50806101ab57600093505050506102ea565b60001960005b885181101561026a578781815181106101cc576101cc6104ef565b60200260200101518982815181106101e6576101e66104ef565b6020026020010151106101f85761025a565b8389828151811061020b5761020b6104ef565b602002602001015111801561023857508189828151811061022e5761022e6104ef565b6020026020010151105b1561025a5788818151811061024f5761024f6104ef565b602002602001015191505b61026381610505565b90506101b1565b506102b96001831161027c5786610286565b61028687846102f1565b846102aa848b898151811061029d5761029d6104ef565b6020026020010151610328565b6102b491906104c0565b610328565b9450848885815181106102ce576102ce6104ef565b602002602001018181516102e291906104d7565b905250505050505b9392505050565b6000821561031f57816103056001856104c0565b61030f9190610520565b61031a9060016104d7565b6102ea565b60009392505050565b600081831061033757816102ea565b5090919050565b634e487b7160e01b600052604160045260246000fd5b600082601f83011261036557600080fd5b8135602067ffffffffffffffff808311156103825761038261033e565b8260051b604051601f19603f830116810181811084821117156103a7576103a761033e565b6040529384528581018301938381019250878511156103c557600080fd5b83870191505b848210156103e4578135835291830191908301906103cb565b979650505050505050565b60008060006060848603121561040457600080fd5b833567ffffffffffffffff8082111561041c57600080fd5b61042887838801610354565b9450602086013591508082111561043e57600080fd5b5061044b86828701610354565b925050604084013590509250925092565b6000604082018483526020604081850152818551808452606086019150828701935060005b8181101561049d57845183529383019391830191600101610481565b5090979650505050505050565b634e487b7160e01b600052601160045260246000fd5b6000828210156104d2576104d26104aa565b500390565b600082198211156104ea576104ea6104aa565b500190565b634e487b7160e01b600052603260045260246000fd5b6000600019821415610519576105196104aa565b5060010190565b60008261053d57634e487b7160e01b600052601260045260246000fd5b50049056fea264697066735822122001a6c38e88f766811a8ef7130a59febae8c4b87c799f9703f0fb21975f50b59664736f6c63430008090033

0x736d1a9bbff97f7565e9532feb7b499982848e5e0730146080604052600436106100355760003560e01c80632529fbc91461003a575b600080fd5b61004d6100483660046103ef565b610064565b60405161005b92919061045c565b60405180910390f35b6000606060005b838310156100a457610087868661008286886104c0565b6100ad565b905080610093576100a4565b61009d81846104d7565b925061006b565b50909492505050565b825160009060001982846100c757600093505050506102ea565b60005b8751811015610199578681815181106100e5576100e56104ef565b60200260200101518882815181106100ff576100ff6104ef565b60200260200101511061011157610189565b878181518110610123576101236104ef565b602002602001015183111561015a578093506001915087818151811061014b5761014b6104ef565b60200260200101519250610189565b87818151811061016c5761016c6104ef565b6020026020010151831415610189576101866001836104d7565b91505b61019281610505565b90506100ca565b50806101ab57600093505050506102ea565b60001960005b885181101561026a578781815181106101cc576101cc6104ef565b60200260200101518982815181106101e6576101e66104ef565b6020026020010151106101f85761025a565b8389828151811061020b5761020b6104ef565b602002602001015111801561023857508189828151811061022e5761022e6104ef565b6020026020010151105b1561025a5788818151811061024f5761024f6104ef565b602002602001015191505b61026381610505565b90506101b1565b506102b96001831161027c5786610286565b61028687846102f1565b846102aa848b898151811061029d5761029d6104ef565b6020026020010151610328565b6102b491906104c0565b610328565b9450848885815181106102ce576102ce6104ef565b602002602001018181516102e291906104d7565b905250505050505b9392505050565b6000821561031f57816103056001856104c0565b61030f9190610520565b61031a9060016104d7565b6102ea565b60009392505050565b600081831061033757816102ea565b5090919050565b634e487b7160e01b600052604160045260246000fd5b600082601f83011261036557600080fd5b8135602067ffffffffffffffff808311156103825761038261033e565b8260051b604051601f19603f830116810181811084821117156103a7576103a761033e565b6040529384528581018301938381019250878511156103c557600080fd5b83870191505b848210156103e4578135835291830191908301906103cb565b979650505050505050565b60008060006060848603121561040457600080fd5b833567ffffffffffffffff8082111561041c57600080fd5b61042887838801610354565b9450602086013591508082111561043e57600080fd5b5061044b86828701610354565b925050604084013590509250925092565b6000604082018483526020604081850152818551808452606086019150828701935060005b8181101561049d57845183529383019391830191600101610481565b5090979650505050505050565b634e487b7160e01b600052601160045260246000fd5b6000828210156104d2576104d26104aa565b500390565b600082198211156104ea576104ea6104aa565b500190565b634e487b7160e01b600052603260045260246000fd5b6000600019821415610519576105196104aa565b5060010190565b60008261053d57634e487b7160e01b600052601260045260246000fd5b50049056fea264697066735822122001a6c38e88f766811a8ef7130a59febae8c4b87c799f9703f0fb21975f50b59664736f6c63430008090033