// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (utils/Arrays.sol)
pragma solidity ^0.8.0;
import "./StorageSlot.sol";
import "./math/Math.sol";
/**
* @dev Collection of functions related to array types.
*/
library Arrays {
using StorageSlot for bytes32;
/**
* @dev Searches a sorted `array` and returns the first index that contains
* a value greater or equal to `element`. If no such index exists (i.e. all
* values in the array are strictly less than `element`), the array length is
* returned. Time complexity O(log n).
*
* `array` is expected to be sorted in ascending order, and to contain no
* repeated elements.
*/
function findUpperBound(uint256[] storage array, uint256 element) internal view returns (uint256) {
if (array.length == 0) {
return 0;
}
uint256 low = 0;
uint256 high = array.length;
while (low < high) {
uint256 mid = Math.average(low, high);
// Note that mid will always be strictly less than high (i.e. it will be a valid array index)
// because Math.average rounds down (it does integer division with truncation).
if (unsafeAccess(array, mid).value > element) {
high = mid;
} else {
low = mid + 1;
}
}
// At this point `low` is the exclusive upper bound. We will return the inclusive upper bound.
if (low > 0 && unsafeAccess(array, low - 1).value == element) {
return low - 1;
} else {
return low;
}
}
/**
* @dev Access an array in an "unsafe" way. Skips solidity "index-out-of-range" check.
*
* WARNING: Only use if you are certain `pos` is lower than the array length.
*/
function unsafeAccess(address[] storage arr, uint256 pos) internal pure returns (StorageSlot.AddressSlot storage) {
bytes32 slot;
// We use assembly to calculate the storage slot of the element at index `pos` of the dynamic array `arr`
// following https://docs.soliditylang.org/en/v0.8.17/internals/layout_in_storage.html#mappings-and-dynamic-arrays.
/// @solidity memory-safe-assembly
assembly {
mstore(0, arr.slot)
slot := add(keccak256(0, 0x20), pos)
}
return slot.getAddressSlot();
}
/**
* @dev Access an array in an "unsafe" way. Skips solidity "index-out-of-range" check.
*
* WARNING: Only use if you are certain `pos` is lower than the array length.
*/
function unsafeAccess(bytes32[] storage arr, uint256 pos) internal pure returns (StorageSlot.Bytes32Slot storage) {
bytes32 slot;
// We use assembly to calculate the storage slot of the element at index `pos` of the dynamic array `arr`
// following https://docs.soliditylang.org/en/v0.8.17/internals/layout_in_storage.html#mappings-and-dynamic-arrays.
/// @solidity memory-safe-assembly
assembly {
mstore(0, arr.slot)
slot := add(keccak256(0, 0x20), pos)
}
return slot.getBytes32Slot();
}
/**
* @dev Access an array in an "unsafe" way. Skips solidity "index-out-of-range" check.
*
* WARNING: Only use if you are certain `pos` is lower than the array length.
*/
function unsafeAccess(uint256[] storage arr, uint256 pos) internal pure returns (StorageSlot.Uint256Slot storage) {
bytes32 slot;
// We use assembly to calculate the storage slot of the element at index `pos` of the dynamic array `arr`
// following https://docs.soliditylang.org/en/v0.8.17/internals/layout_in_storage.html#mappings-and-dynamic-arrays.
/// @solidity memory-safe-assembly
assembly {
mstore(0, arr.slot)
slot := add(keccak256(0, 0x20), pos)
}
return slot.getUint256Slot();
}
}