0. 版本
[openzeppelin]:v4.8.3,[forge-std]:v1.5.6
0.1 EnumerableMap.sol
Github: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/v4.8.3/contracts/utils/structs/EnumerableMap.sol
EnumerableMap库提供了Bytes32ToBytes32Map、UintToUintMap、UintToAddressMap、AddressToUintMap和Bytes32ToUintMap五种可迭代元素的map,分别适用于(bytes32, bytes32)、(uint256, uint256)、(uint256, address)、(address, uint256)和(bytes32, uint256)类型的键值对。每种map都提供了增添/更新/删除键值对及由键查值等操作。所有操作的时间复杂度均为O(1)。
1. 目标合约
封装EnumerableMap library成为一个可调用合约:
Github: https://github.com/RevelationOfTuring/foundry-openzeppelin-contracts/blob/master/src/utils/structs/MockEnumerableMap.sol
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.0;import "openzeppelin-contracts/contracts/utils/structs/EnumerableMap.sol";contract MockBytes32ToBytes32Map {using EnumerableMap for EnumerableMap.Bytes32ToBytes32Map;EnumerableMap.Bytes32ToBytes32Map _bytes32ToBytes32Map;function set(bytes32 key, bytes32 value) external returns (bool) {return _bytes32ToBytes32Map.set(key, value);}function remove(bytes32 key) external returns (bool) {return _bytes32ToBytes32Map.remove(key);}function contains(bytes32 key) external view returns (bool) {return _bytes32ToBytes32Map.contains(key);}function length() external view returns (uint) {return _bytes32ToBytes32Map.length();}function at(uint index) external view returns (bytes32, bytes32) {return _bytes32ToBytes32Map.at(index);}function tryGet(bytes32 key) external view returns (bool, bytes32){return _bytes32ToBytes32Map.tryGet(key);}function get(bytes32 key) external view returns (bytes32) {return _bytes32ToBytes32Map.get(key);}function get(bytes32 key, string memory errorMessage) external view returns (bytes32) {return _bytes32ToBytes32Map.get(key, errorMessage);}
}contract MockUintToUintMap {using EnumerableMap for EnumerableMap.UintToUintMap;EnumerableMap.UintToUintMap _uintToUintMap;function set(uint key, uint value) external returns (bool) {return _uintToUintMap.set(key, value);}function remove(uint key) external returns (bool) {return _uintToUintMap.remove(key);}function contains(uint key) external view returns (bool) {return _uintToUintMap.contains(key);}function length() external view returns (uint) {return _uintToUintMap.length();}function at(uint index) external view returns (uint, uint) {return _uintToUintMap.at(index);}function tryGet(uint key) external view returns (bool, uint){return _uintToUintMap.tryGet(key);}function get(uint key) external view returns (uint) {return _uintToUintMap.get(key);}function get(uint key, string memory errorMessage) external view returns (uint) {return _uintToUintMap.get(key, errorMessage);}
}contract MockUintToAddressMap {using EnumerableMap for EnumerableMap.UintToAddressMap;EnumerableMap.UintToAddressMap _uintToAddressMap;function set(uint key, address value) external returns (bool) {return _uintToAddressMap.set(key, value);}function remove(uint key) external returns (bool) {return _uintToAddressMap.remove(key);}function contains(uint key) external view returns (bool) {return _uintToAddressMap.contains(key);}function length() external view returns (uint) {return _uintToAddressMap.length();}function at(uint index) external view returns (uint, address) {return _uintToAddressMap.at(index);}function tryGet(uint key) external view returns (bool, address){return _uintToAddressMap.tryGet(key);}function get(uint key) external view returns (address) {return _uintToAddressMap.get(key);}function get(uint key, string memory errorMessage) external view returns (address) {return _uintToAddressMap.get(key, errorMessage);}
}contract MockAddressToUintMap {using EnumerableMap for EnumerableMap.AddressToUintMap;EnumerableMap.AddressToUintMap _addressToUintMap;function set(address key, uint value) external returns (bool) {return _addressToUintMap.set(key, value);}function remove(address key) external returns (bool) {return _addressToUintMap.remove(key);}function contains(address key) external view returns (bool) {return _addressToUintMap.contains(key);}function length() external view returns (uint) {return _addressToUintMap.length();}function at(uint index) external view returns (address, uint) {return _addressToUintMap.at(index);}function tryGet(address key) external view returns (bool, uint){return _addressToUintMap.tryGet(key);}function get(address key) external view returns (uint) {return _addressToUintMap.get(key);}function get(address key, string memory errorMessage) external view returns (uint) {return _addressToUintMap.get(key, errorMessage);}
}contract MockBytes32ToUintMap {using EnumerableMap for EnumerableMap.Bytes32ToUintMap;EnumerableMap.Bytes32ToUintMap _bytes32ToUintMap;function set(bytes32 key, uint value) external returns (bool) {return _bytes32ToUintMap.set(key, value);}function remove(bytes32 key) external returns (bool) {return _bytes32ToUintMap.remove(key);}function contains(bytes32 key) external view returns (bool) {return _bytes32ToUintMap.contains(key);}function length() external view returns (uint) {return _bytes32ToUintMap.length();}function at(uint index) external view returns (bytes32, uint) {return _bytes32ToUintMap.at(index);}function tryGet(bytes32 key) external view returns (bool, uint){return _bytes32ToUintMap.tryGet(key);}function get(bytes32 key) external view returns (uint) {return _bytes32ToUintMap.get(key);}function get(bytes32 key, string memory errorMessage) external view returns (uint) {return _bytes32ToUintMap.get(key, errorMessage);}
}
全部foundry测试合约:
Github: https://github.com/RevelationOfTuring/foundry-openzeppelin-contracts/blob/master/test/utils/structs/EnumerableMap.t.sol
2. 代码精读
2.1 Bytes32ToBytes32Map体系
结构体Bytes32ToBytes32Map是由一个存储key值的EnumerableSet.Bytes32Set和一个存储value值的mapping(bytes32 => bytes32)构成:
// key: bytes32类型 value:bytes32类型struct Bytes32ToBytes32Map {// 利用EnumerableSet.Bytes32Set来存储全部keys// ps:EnumerableSet库详解见:https://learnblockchain.cn/article/6272EnumerableSet.Bytes32Set _keys;// 通过key来映射value的mappingmapping(bytes32 => bytes32) _values;}
2.1.1 set(Bytes32ToBytes32Map storage map, bytes32 key, bytes32 value) && remove(Bytes32ToBytes32Map storage map, bytes32 key)
-
set(Bytes32ToBytes32Map storage map, bytes32 key, bytes32 value)
:增添或更新键值对。如果输入key为已存在key(为更新键值对),返回false;如果输入key不存在(为新增键值对),返回true。时间复杂度为O(1); -
remove(Bytes32ToBytes32Map storage map, bytes32 key)
:删除键值对。如果输入key为已存在key(删除键值对),返回true;如果输入key不存在,返回false。时间复杂度为O(1)。
function set(Bytes32ToBytes32Map storage map,bytes32 key,bytes32 value) internal returns (bool) {// Bytes32ToBytes32Map._values中更新key-valuemap._values[key] = value;//调用EnumerableSet库中对应的add()方法,在EnumerableSet.Bytes32Set中增添key。如果该key已存在于set中,返回false。否则返回truereturn map._keys.add(key);}function remove(Bytes32ToBytes32Map storage map, bytes32 key) internal returns (bool) {// Bytes32ToBytes32Map._values中删除key-valuedelete map._values[key];// 调用EnumerableSet库中对应的remove()方法,从EnumerableSet.Bytes32Set中删除key。如果该key已存在于set中,返回true。否则返回falsereturn map._keys.remove(key);}
2.1.2 contains(Bytes32ToBytes32Map storage map, bytes32 key) && length(Bytes32ToBytes32Map storage map) && at(Bytes32ToBytes32Map storage map, uint256 index)
contains(Bytes32ToBytes32Map storage map, bytes32 key)
:查询输入key是否存在于Bytes32ToBytes32Map中。如果输入key为已存在key,返回true;如果输入key不存在,返回false。时间复杂度为O(1);length(Bytes32ToBytes32Map storage map)
:返回Bytes32ToBytes32Map中已存在的键值对数量。时间复杂度为O(1);at(Bytes32ToBytes32Map storage map, uint256 index)
:返回Bytes32ToBytes32Map中索引为index的key和对应的value。函数内部没有对index是否越界进行检查,所以在调用时请确保传入的index小于整个Bytes32ToBytes32Map的长度。时间复杂度为O(1)。注:index其实是指Bytes32ToBytes32Map.Bytes32Set的key的index。当每次进行key的remove操作时,set中的key顺序都会发生变化。所以不要盲目地认为该index就是键值对的添加顺序的index。
function contains(Bytes32ToBytes32Map storage map, bytes32 key) internal view returns (bool) {// 调用EnumerableSet库中对应的contains()方法,从EnumerableSet.Bytes32Set中查询输入key是否存在。如果该key已存在于set中,返回true。否则返回falsereturn map._keys.contains(key);}function length(Bytes32ToBytes32Map storage map) internal view returns (uint256) {// 调用EnumerableSet库中对应的length()方法,返回已存在于map中的key的数量。key的数量其实就是map中键值对的数量return map._keys.length();}function at(Bytes32ToBytes32Map storage map, uint256 index) internal view returns (bytes32, bytes32) {// 调用EnumerableSet库中对应的at()方法,返回已存在于set中对应index位置的keybytes32 key = map._keys.at(index);// 返回key,并通过key找到对应的value一起返回return (key, map._values[key]);}
2.1.3 tryGet(Bytes32ToBytes32Map storage map, bytes32 key) && get(Bytes32ToBytes32Map storage map, bytes32 key) && get(Bytes32ToBytes32Map storage map, bytes32 key, string memory errorMessage)
tryGet(Bytes32ToBytes32Map storage map, bytes32 key)
:返回输入key是否存在于Bytes32ToBytes32Map中及输入key对应的value。时间复杂度为O(1)。注:如果key不存在于Bytes32ToBytes32Map中,不会revert,而是第一个参数返回false且对应值为bytes32(0);get(Bytes32ToBytes32Map storage map, bytes32 key)
:返回输入key对应的value。时间复杂度为O(1)。注:如果key不存在于Bytes32ToBytes32Map中,会revert;get(Bytes32ToBytes32Map storage map, bytes32 key, string memory errorMessage)
:返回输入key对应的value(已弃用)。时间复杂度为O(1)。注:该方法与上面的get方法功能完全一致,只是本方法提供自定义revert msg的功能。但是不建议使用该方法,因为字符串参数会增加额外的memory的消耗。如果当key不存在时一定要使用自定义revert msg,建议使用tryGet()进行组合。
function tryGet(Bytes32ToBytes32Map storage map, bytes32 key) internal view returns (bool, bytes32) {// 通过key找到valuebytes32 value = map._values[key];// 如果value为0,可能存在两种情况:1. 已存在key对应的value就是0、2. key不存在if (value == bytes32(0)) {// 返回该key是否存在于map中和0值return (contains(map, key), bytes32(0));} else {// 如果value不为0说明该key存在于map中,返回true和对应value值return (true, value);}}function get(Bytes32ToBytes32Map storage map, bytes32 key) internal view returns (bytes32) {// 通过key找到valuebytes32 value = map._values[key];// 如果value为0且map中不包含该key,直接revertrequire(value != 0 || contains(map, key), "EnumerableMap: nonexistent key");// 返回value值return value;}function get(Bytes32ToBytes32Map storage map,bytes32 key,string memory errorMessage) internal view returns (bytes32) {// 通过key找到valuebytes32 value = map._values[key];// 如果value为0且map中不包含该key,直接以传入的errorMessage revertrequire(value != 0 || contains(map, key), errorMessage);// 返回value值return value;}
2.1.4 foundry代码验证
contract EnumerableMapTest is Test {MockBytes32ToBytes32Map mbtbm = new MockBytes32ToBytes32Map();function test_Bytes32ToBytes32Map_Operations() external {// emptyassertEq(mbtbm.length(), 0);assertFalse(mbtbm.contains(0));// setassertTrue(mbtbm.set(0, 'v_0'));assertEq(mbtbm.length(), 1);assertTrue(mbtbm.set('a', 'v_a'));assertEq(mbtbm.length(), 2);// set key 'a' againassertFalse(mbtbm.set('a', 'v_a_new'));assertEq(mbtbm.length(), 2);(bytes32 key, bytes32 value) = mbtbm.at(0);assertEq(0, key);assertEq('v_0', value);(key, value) = mbtbm.at(1);assertEq('a', key);assertEq('v_a_new', value);assertTrue(mbtbm.set('b', 'v_b'));assertTrue(mbtbm.set('c', 'v_c'));assertEq(mbtbm.length(), 4);// remove// key array: [0,'a','b','c']assertTrue(mbtbm.contains('a'));assertTrue(mbtbm.remove('a'));assertFalse(mbtbm.contains('a'));assertEq(mbtbm.length(), 3);// remove key 'a' againassertFalse(mbtbm.remove('a'));assertEq(mbtbm.length(), 3);// key array after remove: [0,'c','b'](key, value) = mbtbm.at(0);assertEq(0, key);assertEq('v_0', value);(key, value) = mbtbm.at(1);assertEq('c', key);assertEq('v_c', value);(key, value) = mbtbm.at(2);assertEq('b', key);assertEq('v_b', value);// check tryGet()/get()/get() with error msgbytes32[3] memory keys = [bytes32(0), 'b', 'c'];bytes32[3] memory values = [bytes32('v_0'), 'v_b', 'v_c'];// case 1: key existsbool exist;for (uint i; i < 3; ++i) {// tryGet()(exist, value) = mbtbm.tryGet(keys[i]);assertTrue(exist);assertEq(value, values[i]);// get()assertEq(mbtbm.get(keys[i]), values[i]);// get() with error msgassertEq(mbtbm.get(keys[i], "revert msg: key not exist"), values[i]);}// case 2: key doesn't existbytes32 keyNotExist = 'key not exist';(exist, value) = mbtbm.tryGet(keyNotExist);assertFalse(exist);assertEq(value, 0);// get()vm.expectRevert("EnumerableMap: nonexistent key");mbtbm.get(keyNotExist);// get() with error msgvm.expectRevert("revert msg: key not exist");mbtbm.get(keyNotExist, "revert msg: key not exist");// revert if out of boundsvm.expectRevert();mbtbm.at(1024);}
}
2.2 UintToUintMap体系
结构体UintToUintMap的内部直接封装了一个Bytes32ToBytes32Map:
// key: uint256类型 value:uint256类型struct UintToUintMap {// 内部直接封装了一个Bytes32ToBytes32MapBytes32ToBytes32Map _inner;}
2.2.1 set(UintToUintMap storage map, uint256 key, uint256 value) && remove(UintToUintMap storage map, uint256 key)
-
set(UintToUintMap storage map, uint256 key, uint256 value)
:增添或更新键值对。如果输入key为已存在key(为更新键值对),返回false;如果输入key不存在(为新增键值对),返回true。时间复杂度为O(1); -
remove(UintToUintMap storage map, uint256 key)
:删除键值对。如果输入key为已存在key(删除键值对),返回true;如果输入key不存在,返回false。时间复杂度为O(1)。
function set(UintToUintMap storage map,uint256 key,uint256 value) internal returns (bool) {// 将传入的key和value都转成bytes32类型并调用底层的Bytes32ToBytes32Map的set()方法return set(map._inner, bytes32(key), bytes32(value));}function remove(UintToUintMap storage map, uint256 key) internal returns (bool) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的remove()方法return remove(map._inner, bytes32(key));}
2.2.2 contains(UintToUintMap storage map, uint256 key) && length(UintToUintMap storage map) && at(UintToUintMap storage map, uint256 index)
contains(UintToUintMap storage map, uint256 key)
:查询输入key是否存在于UintToUintMap中。如果输入key为已存在key,返回true;如果输入key不存在,返回false。时间复杂度为O(1);length(UintToUintMap storage map)
: 返回UintToUintMap中已存在的键值对数量。时间复杂度为O(1);at(UintToUintMap storage map, uint256 index)
:返回UintToUintMap中索引为index的key和对应的value。函数内部没有对index是否越界进行检查,所以在调用时请确保传入的index小于整个UintToUintMap的长度。时间复杂度为O(1)。注:index其实是指Bytes32ToBytes32Map.Bytes32Set的key的index。当每次进行key的remove操作时,set中的key顺序都会发生变化。所以不要盲目地认为该index就是键值对的添加顺序的index。
function contains(UintToUintMap storage map, uint256 key) internal view returns (bool) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的contains()方法return contains(map._inner, bytes32(key));}function length(UintToUintMap storage map) internal view returns (uint256) {// 调用底层的Bytes32ToBytes32Map的length()方法return length(map._inner);}function at(UintToUintMap storage map, uint256 index) internal view returns (uint256, uint256) {// 调用底层的Bytes32ToBytes32Map的at()方法,得到底层返回的bytes32类型的key和value值(bytes32 key, bytes32 value) = at(map._inner, index);// 将bytes32类型的key和value转换成uint256类型并返回return (uint256(key), uint256(value));}
2.2.3 tryGet(UintToUintMap storage map, uint256 key) && get(UintToUintMap storage map, uint256 key) && get(UintToUintMap storage map, uint256 key, string memory errorMessage)
tryGet(UintToUintMap storage map, uint256 key)
:返回输入key是否存在于UintToUintMap中及输入key对应的value。时间复杂度为O(1)。注:如果key不存在于UintToUintMap中,不会revert,而是第一个参数返回false且对应值为uint256(0);get(UintToUintMap storage map, uint256 key)
:返回输入key对应的value。时间复杂度为O(1)。注:如果key不存在于UintToUintMap中,会revert;get(UintToUintMap storage map, uint256 key, string memory errorMessage)
:返回输入key对应的value(已弃用)。时间复杂度为O(1)。注:该方法与上面的get方法功能完全一致,只是本方法提供自定义revert msg的功能。但是不建议使用该方法,因为字符串参数会增加额外的memory的消耗。如果当key不存在时一定要使用自定义revert msg,建议使用tryGet()进行组合。
function tryGet(UintToUintMap storage map, uint256 key) internal view returns (bool, uint256) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的tryGet()方法(bool success, bytes32 value) = tryGet(map._inner, bytes32(key));// 将底层返回的传入key是否存在及bytes32类型的value转换成uint256类型返回return (success, uint256(value));}function get(UintToUintMap storage map, uint256 key) internal view returns (uint256) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的get()方法,得到的bytes32类型结果转换成uint256类型返回return uint256(get(map._inner, bytes32(key)));}function get(UintToUintMap storage map,uint256 key,string memory errorMessage) internal view returns (uint256) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的get()方法,得到的bytes32类型结果转换成uint256类型返回return uint256(get(map._inner, bytes32(key), errorMessage));}
2.2.4 foundry代码验证
contract EnumerableMapTest is Test {MockUintToUintMap mutum = new MockUintToUintMap();function test_UintToUintMap_Operations() external {// emptyassertEq(mutum.length(), 0);assertFalse(mutum.contains(0));// setassertTrue(mutum.set(0, 1));assertEq(mutum.length(), 1);assertTrue(mutum.set(1, 2));assertEq(mutum.length(), 2);// set key 1 againassertFalse(mutum.set(1, 2 + 1));assertEq(mutum.length(), 2);(uint key, uint value) = mutum.at(0);assertEq(0, key);assertEq(1, value);(key, value) = mutum.at(1);assertEq(1, key);assertEq(3, value);assertTrue(mutum.set(2, 4));assertTrue(mutum.set(3, 8));assertEq(mutum.length(), 4);// remove// key array: [0,1,2,3]assertTrue(mutum.contains(1));assertTrue(mutum.remove(1));assertFalse(mutum.contains(1));assertEq(mutum.length(), 3);// remove key 1 againassertFalse(mutum.remove(1));assertEq(mutum.length(), 3);// key array after remove: [0,3,2](key, value) = mutum.at(0);assertEq(0, key);assertEq(1, value);(key, value) = mutum.at(1);assertEq(3, key);assertEq(8, value);(key, value) = mutum.at(2);assertEq(2, key);assertEq(4, value);// check tryGet()/get()/get() with error msguint[3] memory keys = [uint(0), 2, 3];uint[3] memory values = [uint(1), 4, 8];// case 1: key existsbool exist;for (uint i; i < 3; ++i) {// tryGet()(exist, value) = mutum.tryGet(keys[i]);assertTrue(exist);assertEq(value, values[i]);// get()assertEq(mutum.get(keys[i]), values[i]);// get() with error msgassertEq(mutum.get(keys[i], "revert msg: key not exist"), values[i]);}// case 2: key doesn't existuint keyNotExist = 1024;(exist, value) = mutum.tryGet(keyNotExist);assertFalse(exist);assertEq(value, 0);// get()vm.expectRevert("EnumerableMap: nonexistent key");mutum.get(keyNotExist);// get() with error msgvm.expectRevert("revert msg: key not exist");mutum.get(keyNotExist, "revert msg: key not exist");// revert if out of boundsvm.expectRevert();mutum.at(1024);}
}
2.3 UintToAddressMap体系
结构体UintToAddressMap的内部直接封装了一个Bytes32ToBytes32Map:
// key: uint256类型 value:address类型struct UintToAddressMap {// 内部直接封装了一个Bytes32ToBytes32MapBytes32ToBytes32Map _inner;}
2.3.1 set(UintToAddressMap storage map, uint256 key, address value) && remove(UintToAddressMap storage map, uint256 key)
-
set(UintToAddressMap storage map, uint256 key, address value)
:增添或更新键值对。如果输入key为已存在key(为更新键值对),返回false;如果输入key不存在(为新增键值对),返回true。时间复杂度为O(1); -
remove(UintToAddressMap storage map, uint256 key)
:删除键值对。如果输入key为已存在key(删除键值对),返回true;如果输入key不存在,返回false。时间复杂度为O(1)。
function set(UintToAddressMap storage map,uint256 key,address value) internal returns (bool) {// 将传入的key和value都转成bytes32类型并调用底层的Bytes32ToBytes32Map的set()方法return set(map._inner, bytes32(key), bytes32(uint256(uint160(value))));}function remove(UintToAddressMap storage map, uint256 key) internal returns (bool) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的remove()方法return remove(map._inner, bytes32(key));}
2.3.2 contains(UintToAddressMap storage map, uint256 key) && length(UintToAddressMap storage map) && at(UintToAddressMap storage map, uint256 index)
contains(UintToAddressMap storage map, uint256 key)
:查询输入key是否存在于UintToAddressMap中。如果输入key为已存在key,返回true;如果输入key不存在,返回false。时间复杂度为O(1);length(UintToAddressMap storage map)
:返回UintToAddressMap中已存在的键值对数量。时间复杂度为O(1);at(UintToAddressMap storage map, uint256 index)
:返回UintToAddressMap中索引为index的key和对应的value。函数内部没有对index是否越界进行检查,所以在调用时请确保传入的index小于整个UintToAddressMap的长度。时间复杂度为O(1)。注:index其实是指Bytes32ToBytes32Map.Bytes32Set的key的index。当每次进行key的remove操作时,set中的key顺序都会发生变化。所以不要盲目地认为该index就是键值对的添加顺序的index。
function contains(UintToAddressMap storage map, uint256 key) internal view returns (bool) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的contains()方法return contains(map._inner, bytes32(key));}function length(UintToAddressMap storage map) internal view returns (uint256) {// 调用底层的Bytes32ToBytes32Map的length()方法return length(map._inner);}function at(UintToAddressMap storage map, uint256 index) internal view returns (uint256, address) {// 调用底层的Bytes32ToBytes32Map的at()方法,得到底层返回的bytes32类型的key和value值(bytes32 key, bytes32 value) = at(map._inner, index);// 将bytes32类型的key和value分别转换成uint256和address类型并返回return (uint256(key), address(uint160(uint256(value))));}
2.3.3 tryGet(UintToAddressMap storage map, uint256 key) && get(UintToAddressMap storage map, uint256 key) && get(UintToAddressMap storage map, uint256 key, string memory errorMessage)
tryGet(UintToAddressMap storage map, uint256 key)
:返回输入key是否存在于UintToAddressMap中及输入key对应的value。时间复杂度为O(1)。注:如果key不存在于UintToAddressMap中,不会revert,而是第一个参数返回false且对应值为address(0);get(UintToAddressMap storage map, uint256 key)
:返回输入key对应的value。时间复杂度为O(1)。注:如果key不存在于UintToAddressMap中,会revert;get(UintToAddressMap storage map, uint256 key, string memory errorMessage)
:返回输入key对应的value(已弃用)。时间复杂度为O(1)。注:该方法与上面的get方法功能完全一致,只是本方法提供自定义revert msg的功能。但是不建议使用该方法,因为字符串参数会增加额外的memory的消耗。如果当key不存在时一定要使用自定义revert msg,建议使用tryGet()进行组合。
function tryGet(UintToAddressMap storage map, uint256 key) internal view returns (bool, address) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的tryGet()方法(bool success, bytes32 value) = tryGet(map._inner, bytes32(key));// 将底层返回的传入key是否存在及bytes32类型的value转换成address类型返回return (success, address(uint160(uint256(value))));}function get(UintToAddressMap storage map, uint256 key) internal view returns (address) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的get()方法,得到的bytes32类型结果转换成address类型返回return address(uint160(uint256(get(map._inner, bytes32(key)))));}function get(UintToAddressMap storage map,uint256 key,string memory errorMessage) internal view returns (address) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的get()方法,得到的bytes32类型结果转换成address类型返回return address(uint160(uint256(get(map._inner, bytes32(key), errorMessage))));}
2.3.4 foundry代码验证
contract EnumerableMapTest is Test {MockUintToAddressMap mutam = new MockUintToAddressMap();function test_UintToAddressMap_Operations() external {// emptyassertEq(mutam.length(), 0);assertFalse(mutam.contains(0));// setassertTrue(mutam.set(0, address(0)));assertEq(mutam.length(), 1);assertTrue(mutam.set(1, address(1)));assertEq(mutam.length(), 2);// set key 1 againassertFalse(mutam.set(1, address(1 + 1)));assertEq(mutam.length(), 2);(uint key, address value) = mutam.at(0);assertEq(0, key);assertEq(address(0), value);(key, value) = mutam.at(1);assertEq(1, key);assertEq(address(2), value);assertTrue(mutam.set(2, address(2)));assertTrue(mutam.set(3, address(3)));assertEq(mutam.length(), 4);// remove// key array: [0,1,2,3]assertTrue(mutam.contains(1));assertTrue(mutam.remove(1));assertFalse(mutam.contains(1));assertEq(mutam.length(), 3);// remove key 1 againassertFalse(mutam.remove(1));assertEq(mutam.length(), 3);// key array after remove: [0,3,2](key, value) = mutam.at(0);assertEq(0, key);assertEq(address(0), value);(key, value) = mutam.at(1);assertEq(3, key);assertEq(address(3), value);(key, value) = mutam.at(2);assertEq(2, key);assertEq(address(2), value);// check tryGet()/get()/get() with error msguint[3] memory keys = [uint(0), 2, 3];address[3] memory values = [address(0), address(2), address(3)];// case 1: key existsbool exist;for (uint i; i < 3; ++i) {// tryGet()(exist, value) = mutam.tryGet(keys[i]);assertTrue(exist);assertEq(value, values[i]);// get()assertEq(mutam.get(keys[i]), values[i]);// get() with error msgassertEq(mutam.get(keys[i], "revert msg: key not exist"), values[i]);}// case 2: key doesn't existuint keyNotExist = 1024;(exist, value) = mutam.tryGet(keyNotExist);assertFalse(exist);assertEq(value, address(0));// get()vm.expectRevert("EnumerableMap: nonexistent key");mutam.get(keyNotExist);// get() with error msgvm.expectRevert("revert msg: key not exist");mutam.get(keyNotExist, "revert msg: key not exist");// revert if out of boundsvm.expectRevert();mutam.at(1024);}
}
2.4 AddressToUintMap体系
结构体AddressToUintMap的内部直接封装了一个Bytes32ToBytes32Map:
// key: address类型 value:uint256类型struct AddressToUintMap {// 内部直接封装了一个Bytes32ToBytes32MapBytes32ToBytes32Map _inner;}
2.4.1 set(AddressToUintMap storage map, address key, uint256 value) && remove(AddressToUintMap storage map, address key)
-
set(AddressToUintMap storage map, address key, uint256 value)
:增添或更新键值对。如果输入key为已存在key(为更新键值对),返回false;如果输入key不存在(为新增键值对),返回true。时间复杂度为O(1); -
remove(AddressToUintMap storage map, address key)
:删除键值对。如果输入key为已存在key(删除键值对),返回true;如果输入key不存在,返回false。时间复杂度为O(1)。
function set(AddressToUintMap storage map,address key,uint256 value) internal returns (bool) {// 将传入的key和value都转成bytes32类型并调用底层的Bytes32ToBytes32Map的set()方法return set(map._inner, bytes32(uint256(uint160(key))), bytes32(value));}function remove(AddressToUintMap storage map, address key) internal returns (bool) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的remove()方法return remove(map._inner, bytes32(uint256(uint160(key))));}
2.4.2 contains(AddressToUintMap storage map, address key) && length(AddressToUintMap storage map) && at(AddressToUintMap storage map, uint256 index)
contains(AddressToUintMap storage map, address key)
:查询输入key是否存在于AddressToUintMap中。如果输入key为已存在key,返回true;如果输入key不存在,返回false。时间复杂度为O(1);length(AddressToUintMap storage map)
:返回AddressToUintMap中已存在的键值对数量。时间复杂度为O(1);at(AddressToUintMap storage map, uint256 index)
:返回AddressToUintMap中索引为index的key和对应的value。函数内部没有对index是否越界进行检查,所以在调用时请确保传入的index小于整个UintToAddressMap的长度。时间复杂度为O(1)。注:index其实是指Bytes32ToBytes32Map.Bytes32Set的key的index。当每次进行key的remove操作时,set中的key顺序都会发生变化。所以不要盲目地认为该index就是键值对的添加顺序的index。
function contains(AddressToUintMap storage map, address key) internal view returns (bool) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的contains()方法return contains(map._inner, bytes32(uint256(uint160(key))));}function length(AddressToUintMap storage map) internal view returns (uint256) {// 调用底层的Bytes32ToBytes32Map的length()方法return length(map._inner);}function at(AddressToUintMap storage map, uint256 index) internal view returns (address, uint256) {// 调用底层的Bytes32ToBytes32Map的at()方法,得到底层返回的bytes32类型的key和value值(bytes32 key, bytes32 value) = at(map._inner, index);// 将bytes32类型的key和value分别转换成address和uint256类型并返回return (address(uint160(uint256(key))), uint256(value));}
2.4.3 tryGet(AddressToUintMap storage map, address key) && get(AddressToUintMap storage map, address key) && get(AddressToUintMap storage map, address key, string memory errorMessage)
tryGet(AddressToUintMap storage map, address key)
:返回输入key是否存在于AddressToUintMap中及输入key对应的value。时间复杂度为O(1)。注:如果key不存在于AddressToUintMap中,不会revert,而是第一个参数返回false且对应值为uint256(0);get(AddressToUintMap storage map, address key)
:返回输入key对应的value。时间复杂度为O(1)。注:如果key不存在于AddressToUintMap中,会revert;get(AddressToUintMap storage map, address key, string memory errorMessage)
:返回输入key对应的value(已弃用)。时间复杂度为O(1)。注:该方法与上面的get方法功能完全一致,只是本方法提供自定义revert msg的功能。但是不建议使用该方法,因为字符串参数会增加额外的memory的消耗。如果当key不存在时一定要使用自定义revert msg,建议使用tryGet()进行组合。
function tryGet(AddressToUintMap storage map, address key) internal view returns (bool, uint256) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的tryGet()方法(bool success, bytes32 value) = tryGet(map._inner, bytes32(uint256(uint160(key))));// 将底层返回的传入key是否存在及bytes32类型的value转换成uint256类型返回return (success, uint256(value));}function get(AddressToUintMap storage map, address key) internal view returns (uint256) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的get()方法,得到的bytes32类型结果转换成uint256类型返回return uint256(get(map._inner, bytes32(uint256(uint160(key)))));}function get(AddressToUintMap storage map,address key,string memory errorMessage) internal view returns (uint256) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的get()方法,得到的bytes32类型结果转换成uint256类型返回return uint256(get(map._inner, bytes32(uint256(uint160(key))), errorMessage));}
2.4.4 foundry代码验证
contract EnumerableMapTest is Test {MockAddressToUintMap matum = new MockAddressToUintMap();function test_AddressToUintMap_Operations() external {// emptyassertEq(matum.length(), 0);assertFalse(matum.contains(address(0)));// setassertTrue(matum.set(address(0), 0));assertEq(matum.length(), 1);assertTrue(matum.set(address(1), 1));assertEq(matum.length(), 2);// set key address(1) againassertFalse(matum.set(address(1), 1 + 1));assertEq(matum.length(), 2);(address key, uint value) = matum.at(0);assertEq(address(0), key);assertEq(0, value);(key, value) = matum.at(1);assertEq(address(1), key);assertEq(2, value);assertTrue(matum.set(address(2), 2));assertTrue(matum.set(address(3), 3));assertEq(matum.length(), 4);// remove// key array: [address(0),address(1),address(2),address(3)]assertTrue(matum.contains(address(1)));assertTrue(matum.remove(address(1)));assertFalse(matum.contains(address(1)));assertEq(matum.length(), 3);// remove key address(1) againassertFalse(matum.remove(address(1)));assertEq(matum.length(), 3);// key array after remove: [address(0),address(3),address(2)](key, value) = matum.at(0);assertEq(address(0), key);assertEq(0, value);(key, value) = matum.at(1);assertEq(address(3), key);assertEq(3, value);(key, value) = matum.at(2);assertEq(address(2), key);assertEq(2, value);// check tryGet()/get()/get() with error msgaddress[3] memory keys = [address(0), address(2), address(3)];uint[3] memory values = [uint(0), 2, 3];// case 1: key existsbool exist;for (uint i; i < 3; ++i) {// tryGet()(exist, value) = matum.tryGet(keys[i]);assertTrue(exist);assertEq(value, values[i]);// get()assertEq(matum.get(keys[i]), values[i]);// get() with error msgassertEq(matum.get(keys[i], "revert msg: key not exist"), values[i]);}// case 2: key doesn't existaddress keyNotExist = address(1024);(exist, value) = matum.tryGet(keyNotExist);assertFalse(exist);assertEq(value, 0);// get()vm.expectRevert("EnumerableMap: nonexistent key");matum.get(keyNotExist);// get() with error msgvm.expectRevert("revert msg: key not exist");matum.get(keyNotExist, "revert msg: key not exist");// revert if out of boundsvm.expectRevert();matum.at(1024);}
}
2.5 Bytes32ToUintMap体系
结构体Bytes32ToUintMap的内部直接封装了一个Bytes32ToBytes32Map:
// key: bytes32类型 value:uint256类型struct Bytes32ToUintMap {// 内部直接封装了一个Bytes32ToBytes32MapBytes32ToBytes32Map _inner;}
2.5.1 set(Bytes32ToUintMap storage map, bytes32 key, uint256 value) && remove(Bytes32ToUintMap storage map, bytes32 key)
-
set(Bytes32ToUintMap storage map, bytes32 key, uint256 value)
:增添或更新键值对。如果输入key为已存在key(为更新键值对),返回false;如果输入key不存在(为新增键值对),返回true。时间复杂度为O(1); -
remove(Bytes32ToUintMap storage map, bytes32 key)
:删除键值对。如果输入key为已存在key(删除键值对),返回true;如果输入key不存在,返回false。时间复杂度为O(1)。
function set(Bytes32ToUintMap storage map,bytes32 key,uint256 value) internal returns (bool) {// 将传入的key和value都转成bytes32类型并调用底层的Bytes32ToBytes32Map的set()方法return set(map._inner, key, bytes32(value));}function remove(Bytes32ToUintMap storage map, bytes32 key) internal returns (bool) {// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的remove()方法return remove(map._inner, key);}
2.5.2 contains(Bytes32ToUintMap storage map, bytes32 key) && length(Bytes32ToUintMap storage map) && at(Bytes32ToUintMap storage map, uint256 index)
contains(Bytes32ToUintMap storage map, bytes32 key)
:查询输入key是否存在于Bytes32ToUintMap中。如果输入key为已存在key,返回true;如果输入key不存在,返回false。时间复杂度为O(1);length(Bytes32ToUintMap storage map)
:返回Bytes32ToUintMap中已存在的键值对数量。时间复杂度为O(1);at(Bytes32ToUintMap storage map, uint256 index)
:返回Bytes32ToUintMap中索引为index的key和对应的value。函数内部没有对index是否越界进行检查,所以在调用时请确保传入的index小于整个Bytes32ToUintMap的长度。时间复杂度为O(1)。注:index其实是指Bytes32ToBytes32Map.Bytes32Set的key的index。当每次进行key的remove操作时,set中的key顺序都会发生变化。所以不要盲目地认为该index就是键值对的添加顺序的index。
function contains(Bytes32ToUintMap storage map, bytes32 key) internal view returns (bool) {// 直接调用底层的Bytes32ToBytes32Map的contains()方法return contains(map._inner, key);}function length(Bytes32ToUintMap storage map) internal view returns (uint256) {// 调用底层的Bytes32ToBytes32Map的length()方法return length(map._inner);}function at(Bytes32ToUintMap storage map, uint256 index) internal view returns (bytes32, uint256) {// 调用底层的Bytes32ToBytes32Map的at()方法,得到底层返回的bytes32类型的key和value值(bytes32 key, bytes32 value) = at(map._inner, index);// 直接返回key,并将value转换成uint256类型返回return (key, uint256(value));}
2.5.3 tryGet(Bytes32ToUintMap storage map, bytes32 key) && get(Bytes32ToUintMap storage map, bytes32 key) && get(Bytes32ToUintMap storage map, bytes32 key, string memory errorMessage)
tryGet(Bytes32ToUintMap storage map, bytes32 key)
:返回输入key是否存在于Bytes32ToUintMap中及输入key对应的value。时间复杂度为O(1)。注:如果key不存在于Bytes32ToUintMap中,不会revert,而是第一个参数返回false且对应值为uint256(0);get(Bytes32ToUintMap storage map, bytes32 key)
:返回输入key对应的value。时间复杂度为O(1)。注:如果key不存在于Bytes32ToUintMap中,会revert;get(Bytes32ToUintMap storage map, bytes32 key, string memory errorMessage)
:返回输入key对应的value(已弃用)。时间复杂度为O(1)。注:该方法与上面的get方法功能完全一致,只是本方法提供自定义revert msg的功能。但是不建议使用该方法,因为字符串参数会增加额外的memory的消耗。如果当key不存在时一定要使用自定义revert msg,建议使用tryGet()进行组合。
function tryGet(Bytes32ToUintMap storage map, bytes32 key) internal view returns (bool, uint256) {// 直接调用底层的Bytes32ToBytes32Map的tryGet()方法(bool success, bytes32 value) = tryGet(map._inner, key);// 直接返回key是否存在,并将value转换成uint256类型返回return (success, uint256(value));}function get(Bytes32ToUintMap storage map, bytes32 key) internal view returns (uint256) {// 直接调用底层的Bytes32ToBytes32Map的get()方法,得到的bytes32类型结果转换成uint256类型返回return uint256(get(map._inner, key));}function get(Bytes32ToUintMap storage map,bytes32 key,string memory errorMessage) internal view returns (uint256) {// 直接调用底层的Bytes32ToBytes32Map的get()方法,得到的bytes32类型结果转换成uint256类型返回return uint256(get(map._inner, key, errorMessage));}
2.5.4 foundry代码验证
contract EnumerableMapTest is Test {MockBytes32ToUintMap mbtum = new MockBytes32ToUintMap();function test_Bytes32ToUintMap_Operations() external {// emptyassertEq(mbtum.length(), 0);assertFalse(mbtum.contains(0));// setassertTrue(mbtum.set(0, 0));assertEq(mbtum.length(), 1);assertTrue(mbtum.set('a', 1));assertEq(mbtum.length(), 2);// set key 'a' againassertFalse(mbtum.set('a', 97));assertEq(mbtum.length(), 2);(bytes32 key, uint value) = mbtum.at(0);assertEq(0, key);assertEq(0, value);(key, value) = mbtum.at(1);assertEq('a', key);assertEq(97, value);assertTrue(mbtum.set('b', 98));assertTrue(mbtum.set('c', 99));assertEq(mbtum.length(), 4);// remove// key array: [0,'a','b','c']assertTrue(mbtum.contains('a'));assertTrue(mbtum.remove('a'));assertFalse(mbtum.contains('a'));assertEq(mbtum.length(), 3);// remove key 'a' againassertFalse(mbtum.remove('a'));assertEq(mbtum.length(), 3);// key array after remove: [0,'c','b'](key, value) = mbtum.at(0);assertEq(0, key);assertEq(0, value);(key, value) = mbtum.at(1);assertEq('c', key);assertEq(99, value);(key, value) = mbtum.at(2);assertEq('b', key);assertEq(98, value);// check tryGet()/get()/get() with error msgbytes32[3] memory keys = [bytes32(0), 'b', 'c'];uint[3] memory values = [uint(0), 98, 99];// case 1: key existsbool exist;for (uint i; i < 3; ++i) {// tryGet()(exist, value) = mbtum.tryGet(keys[i]);assertTrue(exist);assertEq(value, values[i]);// get()assertEq(mbtum.get(keys[i]), values[i]);// get() with error msgassertEq(mbtum.get(keys[i], "revert msg: key not exist"), values[i]);}// case 2: key doesn't existbytes32 keyNotExist = 'key not exist';(exist, value) = mbtum.tryGet(keyNotExist);assertFalse(exist);assertEq(value, 0);// get()vm.expectRevert("EnumerableMap: nonexistent key");mbtum.get(keyNotExist);// get() with error msgvm.expectRevert("revert msg: key not exist");mbtum.get(keyNotExist, "revert msg: key not exist");// revert if out of boundsvm.expectRevert();mbtum.at(1024);}
}
ps:
本人热爱图灵,热爱中本聪,热爱V神。
以下是我个人的公众号,如果有技术问题可以关注我的公众号来跟我交流。
同时我也会在这个公众号上每周更新我的原创文章,喜欢的小伙伴或者老伙计可以支持一下!
如果需要转发,麻烦注明作者。十分感谢!
公众号名称:后现代泼痞浪漫主义奠基人