EthCC2024-DatastructuresForVerkle

0_EthCC2024_DatastructuresforVerkle.txt

Mapping 0x304BC89A59E41902B58934E0642772830CcA744d
721     0x9ed6c5564541b130cbc7436bb6654f9144bbe9c0cf2b44c8464388b879395586 42180
155     0xf262d37ae1c0ea0878f60cc3950cb170e55e21ee96b2e219d243c1bed44b9f87 56089
4337    0x8c3d7a8727a5cad487721f898aa42e8b0e82522b134a6d825819b6db91a94c58 46801
191     0x201376e974ba73b059efb473bea9ecda54a2be4a4f83c45f094bf28f8173e6ab 60510
20      0xb9f16779eb69d6675606fe7304b74d24f90d9e754412863d7566766b5b119da6 68810
7702    0xb07efe99850a1e62f24b2faf01ce65f70ee4444edd9fad86f15b07285545de7d 46801
1559    0xceec4797d1fd0abd248120dd31c7a20943e7e667739defcf8a24595f196d73ae 60522
712     0x025e447415c3cc3053201332e288abc28cf5d351eb347cf0cf38c52c738d2913 60522
1363    0x292d6b88cb79fe9355b66db13247df32e727275f4a52a66c350a3ccdf055f3e0 46801
1155    0x36234686a2191b2a0ce37fb8deea2555fc26884206cdc15b08716826909f3de3 46801
pop     0xe3ec04ae9a868b67362cdc64c3ca35f84f7e23bd83dd9288009c6ab1f2f794bd 83815

Array   0xee62665b7560bE5c1099eC3A583f03Ef0Fc2B00e
721     0xa45bae0183283d4e49f17c53dbc03e273150b6c62446d5e02e7c177c4c9fa170 35925
155     0x76eae70c5974f2e29048e51e9355caa25e0f31b7433d34d57891ca6ac8f17581 39658
4337    0x43546f6d3715314d0a96d90a1b8367073a5c50439ed9363ceb1863f08ddb2d08 37175
191     0x254a97faee26a40f025cbfe6074e83bd1b68be60cda736a5d5acb830a571ef67 40708
20      0x7e66e1a8c9dc1e2d6e7c9bd85ff25f3ec1f6ff99bffd6314dd609ed09aae11e2 42503
7702    0xba29d9224f12bb1f8b4c3afc1a166815074f1933ebf3aec9cf3b48fed9ba0201 37175
1559    0x7bc118634c266e02df2328df6650f1cf1396cb628bc59d519492b8aaf17511f0 40320
712     0xfcbdab37f29bc0b21870dd87f34e7cdb12a31c41ae9124046f74c91a9b433b71 40820
1363    0x6f0c52209c3cf724f780f0a3899ad7f8fb90a3811fc3e4d7f50b70d1386fcdce 37175
1155    0x811454f61e0a112fd6dd01e9b491d1d7eba05f252b640af8bd91cccb1a8a6ed8 37175
pop     0x1a1a20dc5a41786134dd56fa5dd9c9453404e2f5f92b2ee031771736a36e6d61 50739

Array2  0xC321bcE6da566FC575F1C112a33d9c47b2A5c008
721     0xa6d1e07760fe75d81b63a2f02831193f70a6c70df545402ac7c14c49d327ad26 33098
155     0x0e9fc98cc5bee2f234acf8e4bee8d5a7977bc05e0a143caff71937020c2131fb 37060
4337    0xef8eef6ba84c2718269fb5b14b331fef52ae54f364b5fc01385408d6fef06f49 34171
191     0xf5a87418a473dbf25b42cdcf55b6bef680807d5daed59575990be715e82079ac 38133
20      0x130cd2b596a22fa04ae40fc576888190b398725873dfe5003c3dd81e44412283 39934
7702    0xca3848f9eb26f77e4513010ae9bdd21c02d9aa794e76f2612b79ead292c1cf83 34171
1559    0x34b41c76d928de4a747c01dfbb63f3fe0408acda1abb407547bbf9063374b221 37745
712     0x7867310536f1a45a1b1863323d3b42de83ba62a494a0eac90edb7f68ba3a0ca8 38245
1363    0x651cfe1bb45611fb7317236144bfdecd78616aa3871868429fa9d262486cdf1c 34171
1155    0x0ceac2b2bc77de96c749e25b74810e7bdd0c99c955ed9f0b5ec866f9e7fb6969 34171
pop     0x4e50851512c6b80476bc02a2884e146fb777dc5ffb6281c097f167bd2a435245 46859


ERC721             0x697bCd5513F62773030135cA227848C4F499F7e4
Mint               0xfe52af8243fcf2d18708b45cc4a13030fb746a1a0bbccc36b90e153f8473678f 40772
Transfer           0x8392b88383b22ea3a7ae822dfa7594651b6d39464fa8903496340df5754c5631 55180

ERC721Consolidated 0x63FA0723a30405f10B0Aa8c21442D3C3a71595Dd
Mint               0xc84ab8f9615c2104b12d70cc78c5ab0c0c187719f62a5e8e8e6ec1c35981b025 40772
Transfer           0x6462301b788718119ce47c91ec3ae8198afca9448785e8ac7006b4bb7a1c51fe 49886

ERC721Consolidated.sol

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (token/ERC721/ERC721.sol)

pragma solidity ^0.8.20;

import {ERC721} from "@openzeppelin/contracts/token/ERC721/ERC721.sol";
import {IERC721} from "@openzeppelin/contracts/token/ERC721/IERC721.sol";
import {IERC721Receiver} from "@openzeppelin/contracts/token/ERC721/IERC721Receiver.sol";
import {IERC721Metadata} from "@openzeppelin/contracts/token/ERC721/extensions/IERC721Metadata.sol";
import {Context} from "@openzeppelin/contracts/utils/Context.sol";
import {Strings} from "@openzeppelin/contracts/utils/Strings.sol";
import {IERC165, ERC165} from "@openzeppelin/contracts/utils/introspection/ERC165.sol";
import {IERC721Errors} from "@openzeppelin/contracts/interfaces/draft-IERC6093.sol";

contract ERC721Mock is ERC721 {
    constructor() ERC721("ERC721Mock", "ERC721Mock") {}

    function mint(address account, uint256 tokenId) external {
        _mint(account, tokenId);
    }

    function burn(uint256 tokenId) external {
        _burn(tokenId);
    }
}

contract ERC721ConsolidatedMock is ERC721Consolidated {
    constructor() ERC721Consolidated("ERC721Mock", "ERC721Mock") {}

    function mint(address account, uint256 tokenId) external {
        _mint(account, tokenId);
    }

    function burn(uint256 tokenId) external {
        _burn(tokenId);
    }
}

/**
 * @dev Implementation of https://eips.ethereum.org/EIPS/eip-721[ERC721] Non-Fungible Token Standard, including
 * the Metadata extension, but not including the Enumerable extension, which is available separately as
 * {ERC721Enumerable}.
 */
abstract contract ERC721Consolidated is Context, ERC165, IERC721, IERC721Metadata, IERC721Errors {
    using Strings for uint256;

    // Token name
    string private _name;

    // Token symbol
    string private _symbol;

    struct TokenDetails {
        address owner;
        address approval;
    }

    struct AccountDetails {
        uint256 balance;
        mapping(address => bool) operators;
    }

    mapping(uint256 tokenId => TokenDetails) private _tokens;
    mapping(address owner => AccountDetails) private _accounts;

    /**
     * @dev Initializes the contract by setting a `name` and a `symbol` to the token collection.
     */
    constructor(string memory name_, string memory symbol_) {
        _name = name_;
        _symbol = symbol_;
    }

    /**
     * @dev See {IERC165-supportsInterface}.
     */
    function supportsInterface(bytes4 interfaceId) public view virtual override(ERC165, IERC165) returns (bool) {
        return
            interfaceId == type(IERC721).interfaceId ||
            interfaceId == type(IERC721Metadata).interfaceId ||
            super.supportsInterface(interfaceId);
    }

    /**
     * @dev See {IERC721-balanceOf}.
     */
    function balanceOf(address owner) public view virtual returns (uint256) {
        if (owner == address(0)) {
            revert ERC721InvalidOwner(address(0));
        }
        return _accounts[owner].balance;
    }

    /**
     * @dev See {IERC721-ownerOf}.
     */
    function ownerOf(uint256 tokenId) public view virtual returns (address) {
        return _requireOwned(tokenId);
    }

    /**
     * @dev See {IERC721Metadata-name}.
     */
    function name() public view virtual returns (string memory) {
        return _name;
    }

    /**
     * @dev See {IERC721Metadata-symbol}.
     */
    function symbol() public view virtual returns (string memory) {
        return _symbol;
    }

    /**
     * @dev See {IERC721Metadata-tokenURI}.
     */
    function tokenURI(uint256 tokenId) public view virtual returns (string memory) {
        _requireOwned(tokenId);

        string memory baseURI = _baseURI();
        return bytes(baseURI).length > 0 ? string.concat(baseURI, tokenId.toString()) : "";
    }

    /**
     * @dev Base URI for computing {tokenURI}. If set, the resulting URI for each
     * token will be the concatenation of the `baseURI` and the `tokenId`. Empty
     * by default, can be overridden in child contracts.
     */
    function _baseURI() internal view virtual returns (string memory) {
        return "";
    }

    /**
     * @dev See {IERC721-approve}.
     */
    function approve(address to, uint256 tokenId) public virtual {
        _approve(to, tokenId, _msgSender());
    }

    /**
     * @dev See {IERC721-getApproved}.
     */
    function getApproved(uint256 tokenId) public view virtual returns (address) {
        _requireOwned(tokenId);

        return _getApproved(tokenId);
    }

    /**
     * @dev See {IERC721-setApprovalForAll}.
     */
    function setApprovalForAll(address operator, bool approved) public virtual {
        _setApprovalForAll(_msgSender(), operator, approved);
    }

    /**
     * @dev See {IERC721-isApprovedForAll}.
     */
    function isApprovedForAll(address owner, address operator) public view virtual returns (bool) {
        return _accounts[owner].operators[operator];
    }

    /**
     * @dev See {IERC721-transferFrom}.
     */
    function transferFrom(address from, address to, uint256 tokenId) public virtual {
        if (to == address(0)) {
            revert ERC721InvalidReceiver(address(0));
        }
        // Setting an "auth" arguments enables the `_isAuthorized` check which verifies that the token exists
        // (from != 0). Therefore, it is not needed to verify that the return value is not 0 here.
        address previousOwner = _update(to, tokenId, _msgSender());
        if (previousOwner != from) {
            revert ERC721IncorrectOwner(from, tokenId, previousOwner);
        }
    }

    /**
     * @dev See {IERC721-safeTransferFrom}.
     */
    function safeTransferFrom(address from, address to, uint256 tokenId) public {
        safeTransferFrom(from, to, tokenId, "");
    }

    /**
     * @dev See {IERC721-safeTransferFrom}.
     */
    function safeTransferFrom(address from, address to, uint256 tokenId, bytes memory data) public virtual {
        transferFrom(from, to, tokenId);
        _checkOnERC721Received(from, to, tokenId, data);
    }

    /**
     * @dev Returns the owner of the `tokenId`. Does NOT revert if token doesn't exist
     *
     * IMPORTANT: Any overrides to this function that add ownership of tokens not tracked by the
     * core ERC721 logic MUST be matched with the use of {_increaseBalance} to keep balances
     * consistent with ownership. The invariant to preserve is that for any address `a` the value returned by
     * `balanceOf(a)` must be equal to the number of tokens such that `_ownerOf(tokenId)` is `a`.
     */
    function _ownerOf(uint256 tokenId) internal view virtual returns (address) {
        return _tokens[tokenId].owner;
    }

    /**
     * @dev Returns the approved address for `tokenId`. Returns 0 if `tokenId` is not minted.
     */
    function _getApproved(uint256 tokenId) internal view virtual returns (address) {
        return _tokens[tokenId].approval;
    }

    /**
     * @dev Returns whether `spender` is allowed to manage `owner`'s tokens, or `tokenId` in
     * particular (ignoring whether it is owned by `owner`).
     *
     * WARNING: This function assumes that `owner` is the actual owner of `tokenId` and does not verify this
     * assumption.
     */
    function _isAuthorized(address owner, address spender, uint256 tokenId) internal view virtual returns (bool) {
        return
            spender != address(0) &&
            (owner == spender || isApprovedForAll(owner, spender) || _getApproved(tokenId) == spender);
    }

    /**
     * @dev Checks if `spender` can operate on `tokenId`, assuming the provided `owner` is the actual owner.
     * Reverts if `spender` does not have approval from the provided `owner` for the given token or for all its assets
     * the `spender` for the specific `tokenId`.
     *
     * WARNING: This function assumes that `owner` is the actual owner of `tokenId` and does not verify this
     * assumption.
     */
    function _checkAuthorized(address owner, address spender, uint256 tokenId) internal view virtual {
        if (!_isAuthorized(owner, spender, tokenId)) {
            if (owner == address(0)) {
                revert ERC721NonexistentToken(tokenId);
            } else {
                revert ERC721InsufficientApproval(spender, tokenId);
            }
        }
    }

    /**
     * @dev Unsafe write access to the balances, used by extensions that "mint" tokens using an {ownerOf} override.
     *
     * NOTE: the value is limited to type(uint128).max. This protect against _balance overflow. It is unrealistic that
     * a uint256 would ever overflow from increments when these increments are bounded to uint128 values.
     *
     * WARNING: Increasing an account's balance using this function tends to be paired with an override of the
     * {_ownerOf} function to resolve the ownership of the corresponding tokens so that balances and ownership
     * remain consistent with one another.
     */
    function _increaseBalance(address account, uint128 value) internal virtual {
        unchecked {
            _accounts[account].balance += value;
        }
    }

    /**
     * @dev Transfers `tokenId` from its current owner to `to`, or alternatively mints (or burns) if the current owner
     * (or `to`) is the zero address. Returns the owner of the `tokenId` before the update.
     *
     * The `auth` argument is optional. If the value passed is non 0, then this function will check that
     * `auth` is either the owner of the token, or approved to operate on the token (by the owner).
     *
     * Emits a {Transfer} event.
     *
     * NOTE: If overriding this function in a way that tracks balances, see also {_increaseBalance}.
     */
    function _update(address to, uint256 tokenId, address auth) internal virtual returns (address) {
        address from = _ownerOf(tokenId);

        // Perform (optional) operator check
        if (auth != address(0)) {
            _checkAuthorized(from, auth, tokenId);
        }

        // Execute the update
        if (from != address(0)) {
            // Clear approval. No need to re-authorize or emit the Approval event
            _approve(address(0), tokenId, address(0), false);

            unchecked {
                _accounts[from].balance -= 1;
            }
        }

        if (to != address(0)) {
            unchecked {
                _accounts[to].balance += 1;
            }
        }

        _tokens[tokenId].owner = to;

        emit Transfer(from, to, tokenId);

        return from;
    }

    /**
     * @dev Mints `tokenId` and transfers it to `to`.
     *
     * WARNING: Usage of this method is discouraged, use {_safeMint} whenever possible
     *
     * Requirements:
     *
     * - `tokenId` must not exist.
     * - `to` cannot be the zero address.
     *
     * Emits a {Transfer} event.
     */
    function _mint(address to, uint256 tokenId) internal {
        if (to == address(0)) {
            revert ERC721InvalidReceiver(address(0));
        }
        address previousOwner = _update(to, tokenId, address(0));
        if (previousOwner != address(0)) {
            revert ERC721InvalidSender(address(0));
        }
    }

    /**
     * @dev Mints `tokenId`, transfers it to `to` and checks for `to` acceptance.
     *
     * Requirements:
     *
     * - `tokenId` must not exist.
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called upon a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function _safeMint(address to, uint256 tokenId) internal {
        _safeMint(to, tokenId, "");
    }

    /**
     * @dev Same as {xref-ERC721-_safeMint-address-uint256-}[`_safeMint`], with an additional `data` parameter which is
     * forwarded in {IERC721Receiver-onERC721Received} to contract recipients.
     */
    function _safeMint(address to, uint256 tokenId, bytes memory data) internal virtual {
        _mint(to, tokenId);
        _checkOnERC721Received(address(0), to, tokenId, data);
    }

    /**
     * @dev Destroys `tokenId`.
     * The approval is cleared when the token is burned.
     * This is an internal function that does not check if the sender is authorized to operate on the token.
     *
     * Requirements:
     *
     * - `tokenId` must exist.
     *
     * Emits a {Transfer} event.
     */
    function _burn(uint256 tokenId) internal {
        address previousOwner = _update(address(0), tokenId, address(0));
        if (previousOwner == address(0)) {
            revert ERC721NonexistentToken(tokenId);
        }
    }

    /**
     * @dev Transfers `tokenId` from `from` to `to`.
     *  As opposed to {transferFrom}, this imposes no restrictions on msg.sender.
     *
     * Requirements:
     *
     * - `to` cannot be the zero address.
     * - `tokenId` token must be owned by `from`.
     *
     * Emits a {Transfer} event.
     */
    function _transfer(address from, address to, uint256 tokenId) internal {
        if (to == address(0)) {
            revert ERC721InvalidReceiver(address(0));
        }
        address previousOwner = _update(to, tokenId, address(0));
        if (previousOwner == address(0)) {
            revert ERC721NonexistentToken(tokenId);
        } else if (previousOwner != from) {
            revert ERC721IncorrectOwner(from, tokenId, previousOwner);
        }
    }

    /**
     * @dev Safely transfers `tokenId` token from `from` to `to`, checking that contract recipients
     * are aware of the ERC721 standard to prevent tokens from being forever locked.
     *
     * `data` is additional data, it has no specified format and it is sent in call to `to`.
     *
     * This internal function is like {safeTransferFrom} in the sense that it invokes
     * {IERC721Receiver-onERC721Received} on the receiver, and can be used to e.g.
     * implement alternative mechanisms to perform token transfer, such as signature-based.
     *
     * Requirements:
     *
     * - `tokenId` token must exist and be owned by `from`.
     * - `to` cannot be the zero address.
     * - `from` cannot be the zero address.
     * - If `to` refers to a smart contract, it must implement {IERC721Receiver-onERC721Received}, which is called upon a safe transfer.
     *
     * Emits a {Transfer} event.
     */
    function _safeTransfer(address from, address to, uint256 tokenId) internal {
        _safeTransfer(from, to, tokenId, "");
    }

    /**
     * @dev Same as {xref-ERC721-_safeTransfer-address-address-uint256-}[`_safeTransfer`], with an additional `data` parameter which is
     * forwarded in {IERC721Receiver-onERC721Received} to contract recipients.
     */
    function _safeTransfer(address from, address to, uint256 tokenId, bytes memory data) internal virtual {
        _transfer(from, to, tokenId);
        _checkOnERC721Received(from, to, tokenId, data);
    }

    /**
     * @dev Approve `to` to operate on `tokenId`
     *
     * The `auth` argument is optional. If the value passed is non 0, then this function will check that `auth` is
     * either the owner of the token, or approved to operate on all tokens held by this owner.
     *
     * Emits an {Approval} event.
     *
     * Overrides to this logic should be done to the variant with an additional `bool emitEvent` argument.
     */
    function _approve(address to, uint256 tokenId, address auth) internal {
        _approve(to, tokenId, auth, true);
    }

    /**
     * @dev Variant of `_approve` with an optional flag to enable or disable the {Approval} event. The event is not
     * emitted in the context of transfers.
     */
    function _approve(address to, uint256 tokenId, address auth, bool emitEvent) internal virtual {
        // Avoid reading the owner unless necessary
        if (emitEvent || auth != address(0)) {
            address owner = _requireOwned(tokenId);

            // We do not use _isAuthorized because single-token approvals should not be able to call approve
            if (auth != address(0) && owner != auth && !isApprovedForAll(owner, auth)) {
                revert ERC721InvalidApprover(auth);
            }

            if (emitEvent) {
                emit Approval(owner, to, tokenId);
            }
        }

        _tokens[tokenId].approval = to;
    }

    /**
     * @dev Approve `operator` to operate on all of `owner` tokens
     *
     * Requirements:
     * - operator can't be the address zero.
     *
     * Emits an {ApprovalForAll} event.
     */
    function _setApprovalForAll(address owner, address operator, bool approved) internal virtual {
        if (operator == address(0)) {
            revert ERC721InvalidOperator(operator);
        }
        _accounts[owner].operators[operator] = approved;
        emit ApprovalForAll(owner, operator, approved);
    }

    /**
     * @dev Reverts if the `tokenId` doesn't have a current owner (it hasn't been minted, or it has been burned).
     * Returns the owner.
     *
     * Overrides to ownership logic should be done to {_ownerOf}.
     */
    function _requireOwned(uint256 tokenId) internal view returns (address) {
        address owner = _ownerOf(tokenId);
        if (owner == address(0)) {
            revert ERC721NonexistentToken(tokenId);
        }
        return owner;
    }

    /**
     * @dev Private function to invoke {IERC721Receiver-onERC721Received} on a target address. This will revert if the
     * recipient doesn't accept the token transfer. The call is not executed if the target address is not a contract.
     *
     * @param from address representing the previous owner of the given token ID
     * @param to target address that will receive the tokens
     * @param tokenId uint256 ID of the token to be transferred
     * @param data bytes optional data to send along with the call
     */
    function _checkOnERC721Received(address from, address to, uint256 tokenId, bytes memory data) private {
        if (to.code.length > 0) {
            try IERC721Receiver(to).onERC721Received(_msgSender(), from, tokenId, data) returns (bytes4 retval) {
                if (retval != IERC721Receiver.onERC721Received.selector) {
                    revert ERC721InvalidReceiver(to);
                }
            } catch (bytes memory reason) {
                if (reason.length == 0) {
                    revert ERC721InvalidReceiver(to);
                } else {
                    /// @solidity memory-safe-assembly
                    assembly {
                        revert(add(32, reason), mload(reason))
                    }
                }
            }
        }
    }
}

HeapArray.sol

// SPDX-License-Identifier: MIT
// This file was procedurally generated from scripts/generate/templates/Heap.js.

pragma solidity ^0.8.20;

import {SafeCast} from "@openzeppelin/contracts/utils/math/SafeCast.sol";
import {Panic} from "./Panic.sol";


contract HeapArrayMock {
    using HeapArray for HeapArray.Uint256Heap;

    HeapArray.Uint256Heap data;

    function peek() public view returns (uint256) { return data.peek(); }
    function pop() public returns (uint256) { return data.pop(); }
    function insert(uint256 value) public { data.insert(value); }
    function length() public view returns (uint32) { return data.length(); }
    function clear() public { data.clear(); }
} 

library HeapArray {
    using SafeCast for *;

    struct Uint256Heap {
        Uint256HeapNode[] data;
    }

    struct Uint256HeapNode {
        uint256 value;
        uint32 index; // position -> value
        uint32 lookup; // value -> position
    }

    function peek(Uint256Heap storage self) internal view returns (uint256) {
        return _unsafeNodeAccess(self, self.data[0].index).value;
    }

    function pop(Uint256Heap storage self) internal returns (uint256) {
        unchecked {
            uint32 size = length(self);
            if (size == 0) Panic.panic(Panic.EMPTY_ARRAY_POP);

            uint32 last = size - 1;

            // get root location (in the data array) and value
            Uint256HeapNode storage rootNode = _unsafeNodeAccess(self, 0);
            uint32 rootIdx = rootNode.index;
            Uint256HeapNode storage rootData = _unsafeNodeAccess(self, rootIdx);
            Uint256HeapNode storage lastNode = _unsafeNodeAccess(self, last);
            uint256 rootDataValue = rootData.value;

            // if root is not the last element of the data array (that will get pop-ed), reorder the data array.
            if (rootIdx != last) {
                // get details about the value stored in the last element of the array (that will get pop-ed)
                uint32 lastDataIdx = lastNode.lookup;
                uint256 lastDataValue = lastNode.value;
                // copy these values to the location of the root (that is safe, and that we no longer use)
                rootData.value = lastDataValue;
                rootData.lookup = lastDataIdx;
                // update the tree node that used to point to that last element (value now located where the root was)
                _unsafeNodeAccess(self, lastDataIdx).index = rootIdx;
            }

            // get last leaf location (in the data array) and value
            uint32 lastIdx = lastNode.index;
            uint256 lastValue = _unsafeNodeAccess(self, lastIdx).value;

            // move the last leaf to the root, pop last leaf ...
            rootNode.index = lastIdx;
            _unsafeNodeAccess(self, lastIdx).lookup = 0;
            self.data.pop();

            // ... and heapify
            _siftDown(self, last, 0, lastValue);

            // return root value
            return rootDataValue;
        }
    }

    function insert(Uint256Heap storage self, uint256 value) internal {
        uint32 size = length(self);
        if (size == type(uint32).max) Panic.panic(Panic.RESOURCE_ERROR);

        self.data.push(Uint256HeapNode({index: size, lookup: size, value: value}));
        _siftUp(self, size, value);
    }

    function length(Uint256Heap storage self) internal view returns (uint32) {
        return self.data.length.toUint32();
    }

    function clear(Uint256Heap storage self) internal {
        Uint256HeapNode[] storage data = self.data;
        /// @solidity memory-safe-assembly
        assembly {
            sstore(data.slot, 0)
        }
    }

    function _swap(Uint256Heap storage self, uint32 i, uint32 j) private {
        Uint256HeapNode storage ni = _unsafeNodeAccess(self, i);
        Uint256HeapNode storage nj = _unsafeNodeAccess(self, j);
        uint32 ii = ni.index;
        uint32 jj = nj.index;
        // update pointers to the data (swap the value)
        ni.index = jj;
        nj.index = ii;
        // update lookup pointers for consistency
        _unsafeNodeAccess(self, ii).lookup = j;
        _unsafeNodeAccess(self, jj).lookup = i;
    }

    function _siftDown(
        Uint256Heap storage self,
        uint32 size,
        uint32 pos,
        uint256 value
    ) private {
        uint256 left = 2 * pos + 1; // this could overflow uint32
        uint256 right = 2 * pos + 2; // this could overflow uint32

        if (right < size) {
            // the check guarantees that `left` and `right` are both valid uint32
            uint32 lIndex = uint32(left);
            uint32 rIndex = uint32(right);
            uint256 lValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, lIndex).index).value;
            uint256 rValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, rIndex).index).value;
            if (lValue < value || rValue < value) {
                if (lValue < rValue) {
                    _swap(self, pos, lIndex);
                    _siftDown(self, size, lIndex, value);
                } else {
                    _swap(self, pos, rIndex);
                    _siftDown(self, size, rIndex, value);
                }
            }
        } else if (left < size) {
            // the check guarantees that `left` is a valid uint32
            uint32 lIndex = uint32(left);
            uint256 lValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, lIndex).index).value;
            if (lValue < value) {
                _swap(self, pos, lIndex);
                _siftDown(self, size, lIndex, value);
            }
        }
    }

    function _siftUp(
        Uint256Heap storage self,
        uint32 pos,
        uint256 value
    ) private {
        unchecked {
            while (pos > 0) {
                uint32 parent = (pos - 1) / 2;
                uint256 parentValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, parent).index).value;
                if (parentValue < value) break;
                _swap(self, pos, parent);
                pos = parent;
            }
        }
    }

    function _unsafeNodeAccess(
        Uint256Heap storage self,
        uint32 pos
    ) private pure returns (Uint256HeapNode storage result) {
        assembly ("memory-safe") {
            mstore(0x00, self.slot)
            result.slot := add(keccak256(0x00, 0x20), mul(pos, 2))
        }
    }
}

HeapArray2.sol

// SPDX-License-Identifier: MIT
// This file was procedurally generated from scripts/generate/templates/Heap.js.

pragma solidity ^0.8.20;

import {SafeCast} from "@openzeppelin/contracts/utils/math/SafeCast.sol";
import {Panic} from "./Panic.sol";


contract HeapArray2Mock {
    using HeapArray2 for HeapArray2.Uint256Heap;

    HeapArray2.Uint256Heap data;

    function peek() public view returns (uint256) { return data.peek(); }
    function pop() public returns (uint256) { return data.pop(); }
    function insert(uint256 value) public { data.insert(value); }
    function length() public view returns (uint32) { return data.length(); }
    function clear() public { data.clear(); }
} 

library HeapArray2 {
    using SafeCast for *;

    struct Uint256Heap {
        bytes32 _placeholder_do_not_use;
    }

    struct Uint256HeapNode {
        uint256 value;
        uint32 index; // position -> value
        uint32 lookup; // value -> position
    }

    struct Uint256HeapLength {
        uint256 value;
    }

    function peek(Uint256Heap storage self) internal view returns (uint256) {
        uint32 size = length(self);
        if (size == 0) Panic.panic(Panic.ARRAY_OUT_OF_BOUNDS);

        return _unsafeNodeAccess(self, _unsafeNodeAccess(self, 0).index).value;
    }

    function pop(Uint256Heap storage self) internal returns (uint256) {
        unchecked {
            uint32 size = length(self);
            if (size == 0) Panic.panic(Panic.EMPTY_ARRAY_POP);

            uint32 last = size - 1;

            // get root location (in the data array) and value
            Uint256HeapNode storage rootNode = _unsafeNodeAccess(self, 0);
            uint32 rootIdx = rootNode.index;
            Uint256HeapNode storage rootData = _unsafeNodeAccess(self, rootIdx);
            Uint256HeapNode storage lastNode = _unsafeNodeAccess(self, last);
            uint256 rootDataValue = rootData.value;

            // if root is not the last element of the data array (that will get pop-ed), reorder the data array.
            if (rootIdx != last) {
                // get details about the value stored in the last element of the array (that will get pop-ed)
                uint32 lastDataIdx = lastNode.lookup;
                uint256 lastDataValue = lastNode.value;
                // copy these values to the location of the root (that is safe, and that we no longer use)
                rootData.value = lastDataValue;
                rootData.lookup = lastDataIdx;
                // update the tree node that used to point to that last element (value now located where the root was)
                _unsafeNodeAccess(self, lastDataIdx).index = rootIdx;
            }

            // get last leaf location (in the data array) and value
            uint32 lastIdx = lastNode.index;
            uint256 lastValue = _unsafeNodeAccess(self, lastIdx).value;

            // move the last leaf to the root, pop last leaf ...
            rootNode.index = lastIdx;
            _unsafeNodeAccess(self, lastIdx).lookup = 0;

            // self.data.pop();
            --_unsafeLengthAccess(self).value;

            // ... and heapify
            _siftDown(self, last, 0, lastValue);

            // return root value
            return rootDataValue;
        }
    }

    function insert(Uint256Heap storage self, uint256 value) internal {
        uint32 size = length(self);
        if (size == type(uint32).max) Panic.panic(Panic.RESOURCE_ERROR);

        // self.data.push(Uint256HeapNode({index: size, lookup: size, value: value}));
        Uint256HeapNode storage node = _unsafeNodeAccess(self, size);
        node.index = size;
        node.lookup = size;
        node.value = value;
        ++_unsafeLengthAccess(self).value;

        _siftUp(self, size, value);
    }

    function length(Uint256Heap storage self) internal view returns (uint32) {
        return _unsafeLengthAccess(self).value.toUint32();
    }

    function clear(Uint256Heap storage self) internal {
        _unsafeLengthAccess(self).value = 0;
        // Uint256HeapNode[] storage data = self.data;
        // /// @solidity memory-safe-assembly
        // assembly {
        //     sstore(data.slot, 0)
        // }
    }

    function _swap(Uint256Heap storage self, uint32 i, uint32 j) private {
        Uint256HeapNode storage ni = _unsafeNodeAccess(self, i);
        Uint256HeapNode storage nj = _unsafeNodeAccess(self, j);
        uint32 ii = ni.index;
        uint32 jj = nj.index;
        // update pointers to the data (swap the value)
        ni.index = jj;
        nj.index = ii;
        // update lookup pointers for consistency
        _unsafeNodeAccess(self, ii).lookup = j;
        _unsafeNodeAccess(self, jj).lookup = i;
    }

    function _siftDown(
        Uint256Heap storage self,
        uint32 size,
        uint32 pos,
        uint256 value
    ) private {
        uint256 left = 2 * pos + 1; // this could overflow uint32
        uint256 right = 2 * pos + 2; // this could overflow uint32

        if (right < size) {
            // the check guarantees that `left` and `right` are both valid uint32
            uint32 lIndex = uint32(left);
            uint32 rIndex = uint32(right);
            uint256 lValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, lIndex).index).value;
            uint256 rValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, rIndex).index).value;
            if (lValue < value || rValue < value) {
                if (lValue < rValue) {
                    _swap(self, pos, lIndex);
                    _siftDown(self, size, lIndex, value);
                } else {
                    _swap(self, pos, rIndex);
                    _siftDown(self, size, rIndex, value);
                }
            }
        } else if (left < size) {
            // the check guarantees that `left` is a valid uint32
            uint32 lIndex = uint32(left);
            uint256 lValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, lIndex).index).value;
            if (lValue < value) {
                _swap(self, pos, lIndex);
                _siftDown(self, size, lIndex, value);
            }
        }
    }

    function _siftUp(
        Uint256Heap storage self,
        uint32 pos,
        uint256 value
    ) private {
        unchecked {
            while (pos > 0) {
                uint32 parent = (pos - 1) / 2;
                uint256 parentValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, parent).index).value;
                if (parentValue < value) break;
                _swap(self, pos, parent);
                pos = parent;
            }
        }
    }

    function _unsafeNodeAccess(
        Uint256Heap storage self,
        uint32 pos
    ) private pure returns (Uint256HeapNode storage result) {
        assembly ("memory-safe") {
            mstore(0x00, self.slot)
            result.slot := add(keccak256(0x00, 0x20), add(mul(pos, 2), 1))
        }
    }

    function _unsafeLengthAccess(
        Uint256Heap storage self
    ) private pure returns (Uint256HeapLength storage result) {
        assembly ("memory-safe") {
            mstore(0x00, self.slot)
            result.slot := keccak256(0x00, 0x20)
        }
    }
}

HeapMapping.sol

// SPDX-License-Identifier: MIT
// This file was procedurally generated from scripts/generate/templates/Heap.js.

pragma solidity ^0.8.20;

import {SafeCast} from "@openzeppelin/contracts/utils/math/SafeCast.sol";
import {Panic} from "./Panic.sol";


contract HeapMappingMock {
    using HeapMapping for HeapMapping.Uint256Heap;

    HeapMapping.Uint256Heap data;

    function peek() public view returns (uint256) { return data.peek(); }
    function pop() public returns (uint256) { return data.pop(); }
    function insert(uint256 value) public { data.insert(value); }
    function length() public view returns (uint32) { return uint32(data.size); }
} 

library HeapMapping {
    using SafeCast for *;

    struct Uint256Heap {
        mapping(uint32 => uint32) tree;
        mapping(uint32 => Node) items;
        uint32 size;
        uint32 nextItemIdx;
    }

    struct Node {
        uint256 value;
        uint32 heapIndex; // value -> position
    }

    function peek(Uint256Heap storage self) internal view returns (uint256) {
        return self.items[self.tree[0]].value;
    }

    function pop(Uint256Heap storage self) internal returns (uint256) {
        unchecked {
            uint32 last = --self.size;

            uint32 rootIdx = self.tree[0];
            uint256 rootValue = self.items[rootIdx].value;
            delete self.items[rootIdx];

            self.tree[0] = self.tree[last];
            self.items[self.tree[0]].heapIndex = 0;
            delete self.tree[last];

            _siftDown(self, last, 0);

            return rootValue;
        }
    }

    function insert(Uint256Heap storage self, uint256 value) internal {
        uint32 pos = self.size++;
        uint32 idx = self.nextItemIdx++;

        self.tree[pos] = idx;
        self.items[idx] = Node({ value: value, heapIndex: pos });

        _siftUp(self, pos, value);
    }

    function length(Uint256Heap storage self) internal view returns (uint32) {
        return self.size;
    }

    function _swap(Uint256Heap storage self, uint32 i, uint32 j) private {
        uint32 ii = self.tree[i];
        uint32 jj = self.tree[j];
        self.tree[i] = jj;
        self.tree[j] = ii;
        self.items[ii].heapIndex = j;
        self.items[jj].heapIndex = i;
    }

    function _siftDown(Uint256Heap storage self, uint32 size, uint32 pos) private {
        uint256 left = 2 * pos + 1; // this could overflow uint32
        uint256 right = 2 * pos + 2; // this could overflow uint32

        if (right < size) {
            // the check guarantees that `left` and `right` are both valid uint32
            uint32 lIndex = uint32(left);
            uint32 rIndex = uint32(right);
            uint256 lValue = self.items[self.tree[lIndex]].value;
            uint256 rValue = self.items[self.tree[rIndex]].value;
            uint256 value = self.items[pos].value;
            if (lValue < value || rValue < value) {
                if (lValue < rValue) {
                    _swap(self, pos, lIndex);
                    _siftDown(self, size, lIndex);
                } else {
                    _swap(self, pos, rIndex);
                    _siftDown(self, size, rIndex);
                }
            }
        } else if (left < size) {
            // the check guarantees that `left` is a valid uint32
            uint32 lIndex = uint32(left);
            uint256 lValue = self.items[self.tree[lIndex]].value;
            uint256 value = self.items[pos].value;
            if (lValue < value) {
                _swap(self, pos, lIndex);
                _siftDown(self, size, lIndex);
            }
        }
    }

    function _siftUp(
        Uint256Heap storage self,
        uint32 pos,
        uint256 value
    ) private {
        unchecked {
            while (pos > 0) {
                uint32 parent = (pos - 1) / 2;
                uint256 parentValue = self.items[self.tree[parent]].value;
                if (parentValue < value) break;
                _swap(self, pos, parent);
                pos = parent;
            }
        }
    }
}

Panic.sol

// SPDX-License-Identifier: MIT

pragma solidity ^0.8.20;

/**
 * @dev Helper library for emitting standardized panic codes.
 *
 * ```solidity
 * contract Example {
 *      using Panic for uint256;
 *
 *      // Use any of the declared internal constants
 *      function foo() { Panic.GENERIC.panic(); }
 *
 *      // Alternatively
 *      function foo() { Panic.panic(Panic.GENERIC); }
 * }
 * ```
 *
 * Follows the list from https://github.com/ethereum/solidity/blob/v0.8.24/libsolutil/ErrorCodes.h[libsolutil].
 */
// slither-disable-next-line unused-state
library Panic {
    /// @dev generic / unspecified error
    uint256 internal constant GENERIC = 0x00;
    /// @dev used by the assert() builtin
    uint256 internal constant ASSERT = 0x01;
    /// @dev arithmetic underflow or overflow
    uint256 internal constant UNDER_OVERFLOW = 0x11;
    /// @dev division or modulo by zero
    uint256 internal constant DIVISION_BY_ZERO = 0x12;
    /// @dev enum conversion error
    uint256 internal constant ENUM_CONVERSION_ERROR = 0x21;
    /// @dev invalid encoding in storage
    uint256 internal constant STORAGE_ENCODING_ERROR = 0x22;
    /// @dev empty array pop
    uint256 internal constant EMPTY_ARRAY_POP = 0x31;
    /// @dev array out of bounds access
    uint256 internal constant ARRAY_OUT_OF_BOUNDS = 0x32;
    /// @dev resource error (too large allocation or too large array)
    uint256 internal constant RESOURCE_ERROR = 0x41;
    /// @dev calling invalid internal function
    uint256 internal constant INVALID_INTERNAL_FUNCTION = 0x51;

    /// @dev Reverts with a panic code. Recommended to use with
    /// the internal constants with predefined codes.
    function panic(uint256 code) internal pure {
        /// @solidity memory-safe-assembly
        assembly {
            mstore(0x00, 0x4e487b71)
            mstore(0x20, code)
            revert(0x1c, 0x24)
        }
    }
}