// SPDX-License-Identifier: MIT pragma solidity ^0.8.35; import { Math } from '../utils/Math.sol'; /** * @title Map implementation with enumeration functions * @dev derived from https://github.com/OpenZeppelin/openzeppelin-contracts (MIT license) */ library EnumerableMap { error EnumerableMap__IndexOutOfBounds(); error EnumerableMap__NonExistentKey(); struct MapEntry { bytes32 _key; bytes32 _value; } struct Map { MapEntry[] _entries; // 1-indexed to allow 0 to signify nonexistence mapping(bytes32 key => uint256 index) _indexes; } struct AddressToAddressMap { Map _inner; } struct UintToAddressMap { Map _inner; } function valueAt( AddressToAddressMap storage map, uint256 index ) internal view returns (address key, address value) { (bytes32 keyBytes, bytes32 valueBytes) = _valueAt(map._inner, index); key = address(uint160(uint256(keyBytes))); value = address(uint160(uint256(valueBytes))); } function valueAt( UintToAddressMap storage map, uint256 index ) internal view returns (uint256 key, address value) { (bytes32 keyBytes, bytes32 valueBytes) = _valueAt(map._inner, index); key = uint256(keyBytes); value = address(uint160(uint256(valueBytes))); } function contains( AddressToAddressMap storage map, address key ) internal view returns (bool) { return _contains(map._inner, bytes32(uint256(uint160(key)))); } function contains( UintToAddressMap storage map, uint256 key ) internal view returns (bool) { return _contains(map._inner, bytes32(key)); } function length( AddressToAddressMap storage map ) internal view returns (uint256) { return _length(map._inner); } function length( UintToAddressMap storage map ) internal view returns (uint256) { return _length(map._inner); } function get( AddressToAddressMap storage map, address key ) internal view returns (address) { return address( uint160( uint256(_get(map._inner, bytes32(uint256(uint160(key))))) ) ); } function get( UintToAddressMap storage map, uint256 key ) internal view returns (address) { return address(uint160(uint256(_get(map._inner, bytes32(key))))); } function set( AddressToAddressMap storage map, address key, address value ) internal returns (bool) { return _set( map._inner, bytes32(uint256(uint160(key))), bytes32(uint256(uint160(value))) ); } function set( UintToAddressMap storage map, uint256 key, address value ) internal returns (bool) { return _set(map._inner, bytes32(key), bytes32(uint256(uint160(value)))); } function remove( AddressToAddressMap storage map, address key ) internal returns (bool) { return _remove(map._inner, bytes32(uint256(uint160(key)))); } function remove( UintToAddressMap storage map, uint256 key ) internal returns (bool) { return _remove(map._inner, bytes32(key)); } function toArray( AddressToAddressMap storage map ) internal view returns (address[] memory keysOut, address[] memory valuesOut) { uint256 len = map._inner._entries.length; keysOut = new address[](len); valuesOut = new address[](len); unchecked { for (uint256 i; i < len; ++i) { keysOut[i] = address( uint160(uint256(map._inner._entries[i]._key)) ); valuesOut[i] = address( uint160(uint256(map._inner._entries[i]._value)) ); } } } function toArray( AddressToAddressMap storage map, uint256 startIndex, uint256 count ) internal view returns (address[] memory keysOut, address[] memory valuesOut) { uint256 size = length(map); if (startIndex >= size) revert EnumerableMap__IndexOutOfBounds(); uint256 outputSize = Math.min(count, size - startIndex); keysOut = new address[](outputSize); valuesOut = new address[](outputSize); for (uint256 i; i < count; i++) { keysOut[i] = address( uint160(uint256(map._inner._entries[startIndex + i]._key)) ); valuesOut[i] = address( uint160(uint256(map._inner._entries[startIndex + i]._value)) ); } } function toArray( UintToAddressMap storage map ) internal view returns (uint256[] memory keysOut, address[] memory valuesOut) { uint256 len = map._inner._entries.length; keysOut = new uint256[](len); valuesOut = new address[](len); unchecked { for (uint256 i; i < len; ++i) { keysOut[i] = uint256(map._inner._entries[i]._key); valuesOut[i] = address( uint160(uint256(map._inner._entries[i]._value)) ); } } } function toArray( UintToAddressMap storage map, uint256 startIndex, uint256 count ) internal view returns (uint256[] memory keysOut, address[] memory valuesOut) { uint256 size = length(map); if (startIndex >= size) revert EnumerableMap__IndexOutOfBounds(); uint256 outputSize = Math.min(count, size - startIndex); keysOut = new uint256[](outputSize); valuesOut = new address[](outputSize); for (uint256 i; i < count; i++) { keysOut[i] = uint256(map._inner._entries[startIndex + i]._key); valuesOut[i] = address( uint160(uint256(map._inner._entries[startIndex + i]._value)) ); } } function keys( AddressToAddressMap storage map ) internal view returns (address[] memory keysOut) { uint256 len = map._inner._entries.length; keysOut = new address[](len); unchecked { for (uint256 i; i < len; ++i) { keysOut[i] = address( uint160(uint256(map._inner._entries[i]._key)) ); } } } function keys( UintToAddressMap storage map ) internal view returns (uint256[] memory keysOut) { uint256 len = map._inner._entries.length; keysOut = new uint256[](len); unchecked { for (uint256 i; i < len; ++i) { keysOut[i] = uint256(map._inner._entries[i]._key); } } } function values( AddressToAddressMap storage map ) internal view returns (address[] memory valuesOut) { uint256 len = map._inner._entries.length; valuesOut = new address[](len); unchecked { for (uint256 i; i < len; ++i) { valuesOut[i] = address( uint160(uint256(map._inner._entries[i]._value)) ); } } } function values( UintToAddressMap storage map ) internal view returns (address[] memory valuesOut) { uint256 len = map._inner._entries.length; valuesOut = new address[](len); unchecked { for (uint256 i; i < len; ++i) { valuesOut[i] = address( uint160(uint256(map._inner._entries[i]._value)) ); } } } function _valueAt( Map storage map, uint256 index ) private view returns (bytes32 key, bytes32 value) { if (index >= map._entries.length) revert EnumerableMap__IndexOutOfBounds(); MapEntry storage entry = map._entries[index]; key = entry._key; value = entry._value; } function _contains( Map storage map, bytes32 key ) private view returns (bool) { return map._indexes[key] != 0; } function _length(Map storage map) private view returns (uint256) { return map._entries.length; } function _get(Map storage map, bytes32 key) private view returns (bytes32) { uint256 keyIndex = map._indexes[key]; if (keyIndex == 0) revert EnumerableMap__NonExistentKey(); unchecked { return map._entries[keyIndex - 1]._value; } } function _set( Map storage map, bytes32 key, bytes32 value ) private returns (bool) { uint256 keyIndex = map._indexes[key]; if (keyIndex == 0) { map._entries.push(MapEntry({ _key: key, _value: value })); map._indexes[key] = map._entries.length; return true; } else { unchecked { map._entries[keyIndex - 1]._value = value; } return false; } } function _remove(Map storage map, bytes32 key) private returns (bool) { uint256 keyIndex = map._indexes[key]; if (keyIndex != 0) { unchecked { MapEntry storage last = map._entries[map._entries.length - 1]; // move last entry to now-vacant index map._entries[keyIndex - 1] = last; map._indexes[last._key] = keyIndex; } // clear last index map._entries.pop(); delete map._indexes[key]; return true; } else { return false; } } }