Checkpoints库定义了History、Trace224和Trace160结构体。这些结构体中包含了在各个不同的区块高度或自定义key上记录的数值并可以查询出对应区块高度或key上的记录值。Checkpoints库提供了标准的添加记录、查询记录的库方法。
[openzeppelin]:v4.8.3,[forge-std]:v1.5.6
Github: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/v4.8.3/contracts/utils/Checkpoints.sol
Checkpoints库定义了History、Trace224和Trace160结构体。这些结构体中包含了在各个不同的区块高度或自定义key上记录的数值并可以查询出对应区块高度或key上的记录值。Checkpoints库提供了标准的添加记录、查询记录的库方法。
封装Checkpoints library成为一个可调用合约:
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.0;
import "openzeppelin-contracts/contracts/utils/Checkpoints.sol";
contract MockCheckpointsHistory {
using Checkpoints for Checkpoints.History;
Checkpoints.History _history;
function getAtBlock(uint blockNumber) external view returns (uint) {
return _history.getAtBlock(blockNumber);
}
function getAtProbablyRecentBlock(uint blockNumber) external view returns (uint){
return _history.getAtProbablyRecentBlock(blockNumber);
}
function push(uint value) external returns (uint, uint) {
return _history.push(value);
}
// a customized function for update latest value of _history
function op(uint latestValue, uint delta) internal pure returns (uint){
return latestValue + delta;
}
function pushWithOp(uint delta) external returns (uint, uint) {
return _history.push(op, delta);
}
function latest() external view returns (uint224){
return _history.latest();
}
function latestCheckpoint() external view returns (
bool exists,
uint32 _blockNumber,
uint224 _value
){
return _history.latestCheckpoint();
}
function length() external view returns (uint){
return _history.length();
}
}
contract MockCheckpointsTrace224 {
using Checkpoints for Checkpoints.Trace224;
Checkpoints.Trace224 _trace224;
function push(
uint32 key,
uint224 value
) external returns (uint224, uint224){
return _trace224.push(key, value);
}
function lowerLookup(uint32 key) external view returns (uint224){
return _trace224.lowerLookup(key);
}
function upperLookup(uint32 key) external view returns (uint224){
return _trace224.upperLookup(key);
}
function latest() external view returns (uint224) {
return _trace224.latest();
}
function latestCheckpoint() external view returns (
bool exists,
uint32 _key,
uint224 _value
){
return _trace224.latestCheckpoint();
}
function length() external view returns (uint) {
return _trace224.length();
}
}
contract MockCheckpointsTrace160 {
using Checkpoints for Checkpoints.Trace160;
Checkpoints.Trace160 _trace160;
function push(
uint96 key,
uint160 value
) external returns (uint160, uint160){
return _trace160.push(key, value);
}
function lowerLookup(uint96 key) external view returns (uint160){
return _trace160.lowerLookup(key);
}
function upperLookup(uint96 key) external view returns (uint160) {
return _trace160.upperLookup(key);
}
function latest() external view returns (uint160) {
return _trace160.latest();
}
function latestCheckpoint() external view returns (
bool exists,
uint96 _key,
uint160 _value
){
return _trace160.latestCheckpoint();
}
function length() external view returns (uint) {
return _trace160.length();
}
}
全部foundry测试合约:
Checkpoints库中提供了History、Trace224和Trace160三种存储记录的结构体。各个结构体自成体系并提供每种体系下的读修改写的库方法。
// 定义History结构体,里面包含了不同时间点(区块高度)上的记录值
struct History {
Checkpoint[] _checkpoints;
}
struct Checkpoint {
// uint32+uint224=uint256,合起来占1个slot
// 区块号
uint32 _blockNumber;
// 记录值
uint224 _value;
}
push(History storage self, uint256 value)
:向History中添加记录值value,时间戳为当前的区块高度。返回值为前一条记录值和本次添加的记录值;push(History storage self, function(uint256, uint256) view returns (uint256) op, uint256 delta)
:向历史记录中添加新的记录值。新的记录值为op(latest(self), delta)的返回值,其中op的函数类型为function(uint256, uint256) view returns (uint256)。 function push(History storage self, uint256 value) internal returns (uint256, uint256) {
// 调用_insert()函数,添加的key和value都是被安全类型转换得到的(如果存在溢出会revert)
return _insert(self._checkpoints, SafeCast.toUint32(block.number), SafeCast.toUint224(value));
}
function push(
History storage self,
function(uint256, uint256) view returns (uint256) op,
uint256 delta
) internal returns (uint256, uint256) {
// latest(self)为总记录中最近的记录值。
return push(self, op(latest(self), delta));
}
// 将新的键值对(区块高度,记录值)添加进有序的记录数组中
// 注:如果传入的key跟最近的记录Checkpoint中的时间高度一样,则更新最近的记录Checkpoint中的值。如果传入的key跟最近的记录Checkpoint中的时间高度不一样,则在全部记录中新增一个Checkpoint。
function _insert(
Checkpoint[] storage self,
uint32 key,
uint224 value
) private returns (uint224, uint224) {
// pos为当前记录数组的长度
uint256 pos = self.length;
if (pos > 0) {
// 如果当前记录数组中存在过去的记录值,直接在内存中复制记录数组中最后一个Checkpoint(即时间点离现在最近的)
Checkpoint memory last = _unsafeAccess(self, pos - 1);
// 要求本次添加的键值对的区块高度>=历史数组中最近一条记录的区块高度
// 这样才能保证本记录数组的数据是按照时间升序排列
require(last._blockNumber <= key, "Checkpoint: invalid key");
if (last._blockNumber == key) {
// 如果输入的区块高度与最后一个Checkpoint的区块高度一致,则更新最后一个Checkpoint里的记录值
_unsafeAccess(self, pos - 1)._value = value;
} else {
// 如果输入的区块高度与最后一个Checkpoint的区块高度不一致,则在记录数组中新增一个Checkpoint
self.push(Checkpoint({_blockNumber: key, _value: value}));
}
// 返回last中的记录值和本次新增(或更新)的记录值
return (last._value, value);
} else {
// 如果数组中无任何历史记录,直接将键值对push到数组中
self.push(Checkpoint({_blockNumber: key, _value: value}));
// 返回0和本次添加的记录值
return (0, value);
}
}
latest(History storage self)
:返回最近的Checkpoint中的记录值。如果没有记录则返回0;latestCheckpoint(History storage self)
:返回全部历史记录中最近的一个Checkpoint的信息;length(History storage self)
:返回History中全部记录的Checkpoint数。 function latest(History storage self) internal view returns (uint224) {
// 记录总长度
uint256 pos = self._checkpoints.length;
// 如果pos等于0,表示没有记录,直接返回0。如果pos存在非0值,直接取pos-1索引的记录值返回
return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1)._value;
}
function latestCheckpoint(History storage self)
internal
view
returns (
// 如果没有记录返回false,否则返回true
bool exists,
// 最近记录的区块高度
uint32 _blockNumber,
// 最近记录的记录值
uint224 _value
)
{
// 记录总长度
uint256 pos = self._checkpoints.length;
if (pos == 0) {
// 如果无记录,则返回false,0,0
return (false, 0, 0);
} else {
// 如果有记录,则将记录中最后一个Checkpoint复制到内存中
Checkpoint memory ckpt = _unsafeAccess(self._checkpoints, pos - 1);
// 返回true以及最后一个Checkpoint的区块高度及记录值
return (true, ckpt._blockNumber, ckpt._value);
}
}
function length(History storage self) internal view returns (uint256) {
// 返回History中Checkpoint[]的数组长度
return self._checkpoints.length;
}
// 从一个数组中无边界检查地获取索引为pos的元素值。由于没有边界检查,pos的值要在传入时保证不会造成数组越界
function _unsafeAccess(Checkpoint[] storage self, uint256 pos) private pure returns (Checkpoint storage result) {
assembly {
// 将当前Checkpoint[] storage的本位slot号写入偏移量为0的内存中
// 为什么是偏移量为0的空间?因为solidity的内存模型中,前两个字(即前两个32字节)是专门用于哈希函数的临时空间
mstore(0, self.slot)
// keccak256(0, 0x20)计算出storage中的动态数组self的第一个元素的slot号,具体storage动态数组和定长数组的layout细节可参见我之前的博文:https://learnblockchain.cn/article/6111
// add(keccak256(0, 0x20), pos)得到的是动态数组self中索引为pos的元素的slot号,即返回值result就是对应slot号中存储的值
// 注:这里不会做数组越界的检查
result.slot := add(keccak256(0, 0x20), pos)
}
}
getAtBlock(History storage self, uint256 blockNumber)
:通过区块号查询对应时间点的记录值。如果输入的区块号上没有记录值,那么将返回该区块号之前最近时间点的记录值。如果输入区块号之前都没有记录值,将返回0;getAtProbablyRecentBlock(History storage self, uint256 blockNumber)
:通过区块号查询对应时间点的记录值。如果输入的区块号上没有记录值,那么将返回该区块号之前最近时间点的记录值。如果输入区块号之前都没有记录值,将返回0。 具体里面的查找函数照比前面的二分查找_upperBinaryLookup()做了一些算法上的优化:即如果记录长度>5,则不是在[0,len)的范围内做二分法查找,而是在[0,len-sqrt(len))或[len-sqrt(len)+1,len)范围中做二分查找。 function getAtBlock(History storage self, uint256 blockNumber) internal view returns (uint256) {
// 要求输入的区块号小于当前区块链上的区块高度
require(blockNumber < block.number, "Checkpoints: block not yet mined");
// 待查询区块号从uint256转换成uint32,存在溢出检查
uint32 key = SafeCast.toUint32(blockNumber);
// 获取History中所有的记录值数
uint256 len = self._checkpoints.length;
// 在所有记录的全量范围里找到区块号大于传入区块号blockNumber的第一条记录的索引pos
uint256 pos = _upperBinaryLookup(self._checkpoints, key, 0, len);
// 如果pos等于0,表示所有记录中的区块号都大于输入的blockNumber,直接返回0。如果pos存在非0值,表示所有记录中存在区块号小于等于输入的blockNumber的记录,直接取pos-1索引的记录值返回
return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1)._value;
}
function getAtProbablyRecentBlock(History storage self, uint256 blockNumber) internal view returns (uint256) {
// 要求输入的区块号小于当前区块链上的区块高度
require(blockNumber < block.number, "Checkpoints: block not yet mined");
// 待查询区块号从uint256转换成uint32,存在溢出检查
uint32 key = SafeCast.toUint32(blockNumber);
// 获取History中所有的记录值数
uint256 len = self._checkpoints.length;
// 设置查找边界,low为0,high为所有的记录值数
uint256 low = 0;
uint256 high = len;
if (len > 5) {
// 如果History中所有的记录值数大于5,mid为len-len的平方根(向下取整)
uint256 mid = len - Math.sqrt(len);
if (key < _unsafeAccess(self._checkpoints, mid)._blockNumber) {
// 如果索引为mid的Checkpoint的区块号>key,则更新high为mid
high = mid;
} else {
// 如果索引为mid的Checkpoint的区块号<=key,则更新low为mid+1
low = mid + 1;
}
}
// 从当下被调整过的[low,high)范围内进行二分查找
uint256 pos = _upperBinaryLookup(self._checkpoints, key, low, high);
// 如果pos等于0,表示所有[low,high)的记录中的区块号都大于输入的blockNumber,直接返回0。如果pos存在非0值,表示所有[low,high)的记录中存在区块号小于等于输入的blockNumber的记录,直接取pos-1索引的记录值返回
return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1)._value;
}
// Checkpoint[] storage self中,通过二分法查找出blockNumber在[low,high)的范围中记录的区块号大于目标区块号key的第一条记录的索引值。如果不存在这样的记录值,则返回值为high。
// 注: 传入的high不可以大于数组self的长度
function _upperBinaryLookup(
Checkpoint[] storage self,
uint32 key,
uint256 low,
uint256 high
) private view returns (uint256) {
// 跳出循环条件:low>=high
while (low < high) {
// mid为low和high的均值
uint256 mid = Math.average(low, high);
if (_unsafeAccess(self, mid)._blockNumber > key) {
// 如果索引为mid的Checkpoint的区块号>key,则更新high为mid
high = mid;
} else {
// 如果索引为mid的Checkpoint的区块号<=key,则更新low为mid+1
low = mid + 1;
}
}
// 跳出循环,返回high
return high;
}
// Checkpoint[] storage self中,通过二分法查找出blockNumber在[low,high)的范围中记录的区块号大于等于目标区块号key的第一条记录的索引值。如果不存在这样的记录值,则返回值为high。
// 注: 传入的high不可以大于数组self的长度
function _lowerBinaryLookup(
Checkpoint[] storage self,
uint32 key,
uint256 low,
uint256 high
) private view returns (uint256) {
// 跳出循环条件:low>=high
while (low < high) {
// mid为low和high的均值
uint256 mid = Math.average(low, high);
if (_unsafeAccess(self, mid)._blockNumber < key) {
// 如果索引为mid的Checkpoint的区块号<key,则更新low为mid+1
low = mid + 1;
} else {
// 如果索引为mid的Checkpoint的区块号>=key,则更新high为mid
high = mid;
}
}
// 跳出循环,返回high
return high;
}
contract CheckpointsTest is Test {
MockCheckpointsHistory mch = new MockCheckpointsHistory();
function test_CheckpointsHistory() external {
assertEq(mch.length(), 0);
(bool exists,uint32 blockNumber,uint224 value) = mch.latestCheckpoint();
assertFalse(exists);
assertEq(blockNumber, 0);
assertEq(value, 0);
assertEq(mch.latest(), 0);
// push on block number 1
vm.roll(1);
(uint latestValue,uint newValue) = mch.push(11);
assertEq(latestValue, 0);
assertEq(newValue, 11);
assertEq(mch.length(), 1);
(exists, blockNumber, value) = mch.latestCheckpoint();
assertTrue(exists);
assertEq(blockNumber, 1);
assertEq(value, 11);
assertEq(mch.latest(), newValue);
// push on block number 2
vm.roll(2);
(latestValue, newValue) = mch.push(22);
assertEq(latestValue, 11);
assertEq(newValue, 22);
assertEq(mch.length(), 2);
(exists, blockNumber, value) = mch.latestCheckpoint();
assertTrue(exists);
assertEq(blockNumber, 2);
assertEq(value, 22);
assertEq(mch.latest(), newValue);
// update value when push on block number 2 again
(latestValue, newValue) = mch.push(33);
// value before update
assertEq(latestValue, 22);
// value after update
assertEq(newValue, 33);
// total length no change
assertEq(mch.length(), 2);
(exists, blockNumber, value) = mch.latestCheckpoint();
assertTrue(exists);
assertEq(blockNumber, 2);
assertEq(value, 33);
assertEq(mch.latest(), newValue);
// push on block number 3
vm.roll(3);
(latestValue, newValue) = mch.push(44);
assertEq(latestValue, 33);
assertEq(newValue, 44);
assertEq(mch.length(), 3);
(exists, blockNumber, value) = mch.latestCheckpoint();
assertTrue(exists);
assertEq(blockNumber, 3);
assertEq(value, 44);
assertEq(mch.latest(), newValue);
// push with customized op function on a new block number
vm.roll(4);
(latestValue, newValue) = mch.pushWithOp(55);
assertEq(latestValue, 44);
// 44(latest)+55(delta)
assertEq(newValue, 99);
assertEq(mch.length(), 4);
(exists, blockNumber, value) = mch.latestCheckpoint();
assertTrue(exists);
assertEq(blockNumber, 4);
assertEq(value, 99);
assertEq(mch.latest(), newValue);
// push with customized op function on an existed block number
(latestValue, newValue) = mch.pushWithOp(11);
assertEq(latestValue, 99);
// 99(latest)+11(delta)
assertEq(newValue, 110);
assertEq(mch.length(), 4);
(exists, blockNumber, value) = mch.latestCheckpoint();
assertTrue(exists);
assertEq(blockNumber, 4);
assertEq(value, 110);
assertEq(mch.latest(), newValue);
// push more
vm.roll(10);
mch.push(100);
vm.roll(20);
mch.push(101);
vm.roll(25);
mch.push(102);
assertEq(mch.length(), 7);
// history now:
// 11(1)、33(2)、44(3)、110(4)、100(10)、101(20)、102(25)
uint[7] memory values = [uint(11), 33, 44, 110, 100, 101, 102];
uint[7] memory blockNumbers = [uint(1), 2, 3, 4, 10, 20, 25];
// test getAtBlock
// revert if the target block number not < the current block number of chain
vm.expectRevert("Checkpoints: block not yet mined");
mch.getAtBlock(25);
vm.roll(25 + 1);
for (uint i = 0; i < 7; ++i) {
assertEq(mch.getAtBlock(blockNumbers[i]), values[i]);
}
// test getAtProbablyRecentBlock
// revert if the target block number not < the current block number of chain
vm.expectRevert("Checkpoints: block not yet mined");
mch.getAtProbablyRecentBlock(26);
for (uint i = 0; i < 7; ++i) {
assertEq(mch.getAtProbablyRecentBlock(blockNumbers[i]), values[i]);
}
}
}
// 总记录,里面包含记录的动态数组_checkpoints
struct Trace224 {
Checkpoint224[] _checkpoints;
}
// 记录的结构体,具有uint32的key和uint224的value
struct Checkpoint224 {
// uint32+uint224=uint256,合起来占1个slot
uint32 _key;
uint224 _value;
}
向Trace224中添加新的记录键值对(key,value)。返回值为前一条记录值和本次添加的记录值。
function push(
Trace224 storage self,
uint32 key,
uint224 value
) internal returns (uint224, uint224) {
// 调用_insert()函数,添加的key和value都是被安全类型转换得到的(如果存在溢出会revert)
return _insert(self._checkpoints, key, value);
}
// 将新的键值对(key,记录值)添加进有序的记录数组中
// 注:如果传入的key跟最近的记录Checkpoint224._key一样,则更新最近的记录Checkpoint224中的值。如果传入的key跟最近的记录Checkpoint224._key不一样,则在全部记录中新增一个Checkpoint224。
function _insert(
Checkpoint224[] storage self,
uint32 key,
uint224 value
) private returns (uint224, uint224) {
// pos为当前记录数组的长度
uint256 pos = self.length;
if (pos > 0) {
// 如果当前记录数组中存在过去的记录值,直接在内存中复制记录数组中最后一个Checkpoint224
Checkpoint224 memory last = _unsafeAccess(self, pos - 1);
// 要求本次添加的键值对的key>=历史数组中最近一条记录的key
// 这样才能保证本记录数组的数据是按照key的升序排列
require(last._key <= key, "Checkpoint: invalid key");
if (last._key == key) {
// 如果输入的key与最后一个Checkpoint224._key一致,则更新最后一个Checkpoint224里的记录值
_unsafeAccess(self, pos - 1)._value = value;
} else {
// 如果输入的key与最后一个Checkpoint224._key不一致,则在记录数组中新增一个Checkpoint224
self.push(Checkpoint224({_key: key, _value: value}));
}
// 返回last中的记录值和本次新增(或更新)的记录值
return (last._value, value);
} else {
// 如果数组中无任何历史记录,直接将键值对push到数组中
self.push(Checkpoint224({_key: key, _value: value}));
// 返回0和本次添加的记录值
return (0, value);
}
}
latest(Trace224 storage self)
:返回最近的Checkpoint224中的记录值。如果没有记录则返回0;latestCheckpoint(Trace224 storage self)
:返回Trace224全部历史记录中最近的一个Checkpoint的信息;length(Trace224 storage self)
:返回Trace224中全部记录的Checkpoint224的数量。 function latest(Trace224 storage self) internal view returns (uint224) {
// 记录总长度
uint256 pos = self._checkpoints.length;
// 如果pos等于0,表示没有记录,直接返回0。如果pos存在非0值,直接取pos-1索引的记录值返回
return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1)._value;
}
function latestCheckpoint(Trace224 storage self)
internal
view
returns (
// 如果没有记录返回false,否则返回true
bool exists,
// 最近记录的key
uint32 _key,
// 最近记录的记录值
uint224 _value
)
{
// 记录总长度
uint256 pos = self._checkpoints.length;
if (pos == 0) {
// 如果无记录,则返回false,0,0
return (false, 0, 0);
} else {
// 如果有记录,则将记录中最后一个Checkpoint224复制到内存中
Checkpoint224 memory ckpt = _unsafeAccess(self._checkpoints, pos - 1);
// 返回true以及最后一个Checkpoint224的key及记录值
return (true, ckpt._key, ckpt._value);
}
}
function length(Trace224 storage self) internal view returns (uint256) {
// 返回Trace224中Checkpoint224[]的数组长度
return self._checkpoints.length;
}
// 从Checkpoint224[]数组中无边界检查地获取索引为pos的元素值。由于没有边界检查,pos的值要在传入时保证不会造成数组越界
function _unsafeAccess(Checkpoint224[] storage self, uint256 pos)
private
pure
returns (Checkpoint224 storage result)
{
assembly {
// 将当前Checkpoint224[] storage的本位slot号写入偏移量为0的内存中
// 为什么是偏移量为0的空间?因为solidity的内存模型中,前两个字(即前两个32字节)是专门用于哈希函数的临时空间
mstore(0, self.slot)
// keccak256(0, 0x20)计算出storage中的动态数组self的第一个元素的slot号,具体storage动态数组和定长数组的layout细节可参见我之前的博文:https://learnblockchain.cn/article/6111
// add(keccak256(0, 0x20), pos)得到的是动态数组self中索引为pos的元素的slot号,即返回值result就是对应slot号中存储的值
// 注:这里不会做数组越界的检查
result.slot := add(keccak256(0, 0x20), pos)
}
}
lowerLookup(Trace224 storage self, uint32 key)
:返回Trace224所有记录中key>=目标key的最近的记录值。如果不存在这样的记录,返回0。注:传入的high不可以大于总记录的长度;upperLookup(Trace224 storage self, uint32 key)
:返回Trace224所有记录中key<=目标key的最近的记录值。如果不存在这样的记录,返回0。注:传入的high不可以大于总记录的长度。 function lowerLookup(Trace224 storage self, uint32 key) internal view returns (uint224) {
// 记录总长度
uint256 len = self._checkpoints.length;
// 通过_lowerBinaryLookup方法在[0,len)的key的范围中找到key大于等于目标key的第一条记录的索引值
uint256 pos = _lowerBinaryLookup(self._checkpoints, key, 0, len);
// 如果pos为0表示不存在这样的记录,返回0。否则返回索引为pos的记录中的记录值
return pos == len ? 0 : _unsafeAccess(self._checkpoints, pos)._value;
}
function upperLookup(Trace224 storage self, uint32 key) internal view returns (uint224) {
// 记录总长度
uint256 len = self._checkpoints.length;
// 通过_upperBinaryLookup方法在[0,len)的key的范围中找到key大于目标key的第一条记录的索引值
uint256 pos = _upperBinaryLookup(self._checkpoints, key, 0, len);
// 如果pos为0表示不存在这样的记录,返回0。否则返回索引为pos-1的记录中的记录值
return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1)._value;
}
// Checkpoint224[] storage self中,通过二分法查找出key在[low,high)的范围中,记录的key大于目标key的第一条记录的索引值。如果不存在这样的记录值,则返回值为high。
// 注:传入的high不可以大于数组self的长度
function _upperBinaryLookup(
Checkpoint224[] storage self,
uint32 key,
uint256 low,
uint256 high
) private view returns (uint256) {
// 跳出循环条件:low>=high
while (low < high) {
// mid为low和high的均值
uint256 mid = Math.average(low, high);
if (_unsafeAccess(self, mid)._key > key) {
// 如果索引为mid的Checkpoint224._key>key,则更新high为mid
high = mid;
} else {
// 如果索引为mid的Checkpoint224._key<=key,则更新low为mid+1
low = mid + 1;
}
}
// 跳出循环,返回high
return high;
}
// Checkpoint224[] storage self中,通过二分法查找出key在[low,high)的范围中,记录的key大于或等于目标key的第一条记录的索引值。如果不存在这样的记录值,则返回值为high。
// 注: 传入的high不可以大于数组self的长度
function _lowerBinaryLookup(
Checkpoint224[] storage self,
uint32 key,
uint256 low,
uint256 high
) private view returns (uint256) {
// 跳出循环条件:low>=high
while (low < high) {
// mid为low和high的均值
uint256 mid = Math.average(low, high);
if (_unsafeAccess(self, mid)._key < key) {
// 如果索引为mid的Checkpoint224._key<key,则更新low为mid+1
low = mid + 1;
} else {
// 如果索引为mid的Checkpoint224._key>=key,则更新high为mid
high = mid;
}
}
// 跳出循环,返回high
return high;
}
contract CheckpointsTest is Test {
MockCheckpointsTrace224 mct224 = new MockCheckpointsTrace224();
function test_CheckpointsTrace224() external {
assertEq(mct224.length(), 0);
(bool exists,uint32 key,uint224 value) = mct224.latestCheckpoint();
assertFalse(exists);
assertEq(key, 0);
assertEq(value, 0);
assertEq(mct224.latest(), 0);
// push on key 1
(uint224 latestValue,uint224 newValue) = mct224.push(1, 10);
assertEq(latestValue, 0);
assertEq(newValue, 10);
assertEq(mct224.length(), 1);
(exists, key, value) = mct224.latestCheckpoint();
assertTrue(exists);
assertEq(key, 1);
assertEq(value, 10);
assertEq(mct224.latest(), newValue);
// push on key 2
(latestValue, newValue) = mct224.push(2, 20);
assertEq(latestValue, 10);
assertEq(newValue, 20);
assertEq(mct224.length(), 2);
(exists, key, value) = mct224.latestCheckpoint();
assertTrue(exists);
assertEq(key, 2);
assertEq(value, 20);
assertEq(mct224.latest(), newValue);
// update value on key 2
(latestValue, newValue) = mct224.push(2, 30);
// value before update
assertEq(latestValue, 20);
// value after update
assertEq(newValue, 30);
// total length no change
assertEq(mct224.length(), 2);
(exists, key, value) = mct224.latestCheckpoint();
assertTrue(exists);
assertEq(key, 2);
assertEq(value, 30);
assertEq(mct224.latest(), newValue);
// revert if the key to push is < latest key
vm.expectRevert("Checkpoint: invalid key");
mct224.push(2 - 1, 1);
// push more
mct224.push(3, 40);
mct224.push(4, 50);
mct224.push(5, 60);
mct224.push(6, 70);
assertEq(mct224.length(), 6);
// Trace224 now:
// 10(1)、30(2)、40(3)、50(4)、60(5)、70(6)
// lowerLookup():
// return the value in the oldest checkpoint with key greater or equal than the search key
assertEq(mct224.lowerLookup(0), 10);
assertEq(mct224.lowerLookup(1), 10);
assertEq(mct224.lowerLookup(2), 30);
assertEq(mct224.lowerLookup(3), 40);
assertEq(mct224.lowerLookup(4), 50);
assertEq(mct224.lowerLookup(5), 60);
assertEq(mct224.lowerLookup(6), 70);
assertEq(mct224.lowerLookup(7), 0);
// upperLookup():
// return the value in the most recent checkpoint with key lower or equal than the search key
assertEq(mct224.upperLookup(0), 0);
assertEq(mct224.upperLookup(1), 10);
assertEq(mct224.upperLookup(2), 30);
assertEq(mct224.upperLookup(3), 40);
assertEq(mct224.upperLookup(4), 50);
assertEq(mct224.upperLookup(5), 60);
assertEq(mct224.upperLookup(6), 70);
assertEq(mct224.upperLookup(7), 70);
}
}
// 总记录,里面包含记录的动态数组_checkpoints
struct Trace160 {
Checkpoint160[] _checkpoints;
}
// 记录的结构体,具有uint96的key和uint160的value
struct Checkpoint160 {
// uint96+uint160=uint256,合起来占1个slot
uint96 _key;
uint160 _value;
}
向Trace160中添加新的记录键值对(key,value)。返回值为前一条记录值和本次添加的记录值。
function push(
Trace160 storage self,
uint96 key,
uint160 value
) internal returns (uint160, uint160) {
// 调用_insert()函数,添加的key和value都是被安全类型转换得到的(如果存在溢出会revert)
return _insert(self._checkpoints, key, value);
}
// 将新的键值对(key,记录值)添加进有序的记录数组中
// 注:如果传入的key跟最近的记录Checkpoint160._key一样,则更新最近的记录Checkpoint160中的值。如果传入的key跟最近的记录Checkpoint160._key不一样,则在全部记录中新增一个Checkpoint160。
function _insert(
Checkpoint160[] storage self,
uint96 key,
uint160 value
) private returns (uint160, uint160) {
// pos为当前记录数组的长度
uint256 pos = self.length;
if (pos > 0) {
// 如果当前记录数组中存在过去的记录值,直接在内存中复制记录数组中最后一个Checkpoint160
Checkpoint160 memory last = _unsafeAccess(self, pos - 1);
// 要求本次添加的键值对的key>=历史数组中最近一条记录的key
// 这样才能保证本记录数组的数据是按照key的升序排列
require(last._key <= key, "Checkpoint: invalid key");
if (last._key == key) {
// 如果输入的key与最后一个Checkpoint160._key一致,则更新最后一个Checkpoint160里的记录值
_unsafeAccess(self, pos - 1)._value = value;
} else {
// 如果输入的key与最后一个Checkpoint160._key不一致,则在记录数组中新增一个Checkpoint160
self.push(Checkpoint160({_key: key, _value: value}));
}
// 返回last中的记录值和本次新增(或更新)的记录值
return (last._value, value);
} else {
// 如果数组中无任何历史记录,直接将键值对push到数组中
self.push(Checkpoint160({_key: key, _value: value}));
// 返回0和本次添加的记录值
return (0, value);
}
}
latest(Trace160 storage self)
:返回最近的Checkpoint160中的记录值。如果没有记录则返回0;latestCheckpoint(Trace160 storage self)
:返回Trace160全部历史记录中最近的一个Checkpoint的信息;length(Trace160 storage self)
:返回Trace160中全部记录的Checkpoint160的数量。 function latest(Trace160 storage self) internal view returns (uint160) {
// 记录总长度
uint256 pos = self._checkpoints.length;
// 如果pos等于0,表示没有记录,直接返回0。如果pos存在非0值,直接取pos-1索引的记录值返回
return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1)._value;
}
function latestCheckpoint(Trace160 storage self)
internal
view
returns (
// 如果没有记录返回false,否则返回true
bool exists,
// 最近记录的key
uint96 _key,
// 最近记录的记录值
uint160 _value
)
{
// 记录总长度
uint256 pos = self._checkpoints.length;
if (pos == 0) {
// 如果无记录,则返回false,0,0
return (false, 0, 0);
} else {
// 如果有记录,则将记录中最后一个Checkpoint160复制到内存中
Checkpoint160 memory ckpt = _unsafeAccess(self._checkpoints, pos - 1);
// 返回true以及最后一个Checkpoint160的key及记录值
return (true, ckpt._key, ckpt._value);
}
}
function length(Trace160 storage self) internal view returns (uint256) {
// 返回Trace160中Checkpoint160[]的数组长度
return self._checkpoints.length;
}
// 从Checkpoint160[]数组中无边界检查地获取索引为pos的元素值。由于没有边界检查,pos的值要在传入时保证不会造成数组越界
function _unsafeAccess(Checkpoint160[] storage self, uint256 pos)
private
pure
returns (Checkpoint160 storage result)
{
assembly {
// 将Checkpoint160[] storage的本位slot号写入偏移量为0的内存中
// 为什么是偏移量为0的空间?因为solidity的内存模型中,前两个字(即前两个32字节)是专门用于哈希函数的临时空间
mstore(0, self.slot)
// keccak256(0, 0x20)计算出storage中的动态数组self的第一个元素的slot号,具体storage动态数组和定长数组的layout细节可参见我之前的博文:https://learnblockchain.cn/article/6111
// add(keccak256(0, 0x20), pos)得到的是动态数组self中索引为pos的元素的slot号,即返回值result就是对应slot号中存储的值
// 注:这里不会做数组越界的检查
result.slot := add(keccak256(0, 0x20), pos)
}
}
lowerLookup(Trace160 storage self, uint96 key)
:返回Trace160所有记录中key>=目标key的最近的记录值。如果不存在这样的记录,返回0。注:传入的high不可以大于总记录的长度;upperLookup(Trace160 storage self, uint96 key)
:返回Trace160所有记录中key<=目标key的最近的记录值。如果不存在这样的记录,返回0。注:传入的high不可以大于总记录的长度。 function lowerLookup(Trace160 storage self, uint96 key) internal view returns (uint160) {
// 记录总长度
uint256 len = self._checkpoints.length;
// 通过_lowerBinaryLookup方法在[0,len)的key的范围中找到key大于等于目标key的第一条记录的索引值
uint256 pos = _lowerBinaryLookup(self._checkpoints, key, 0, len);
// 如果pos为0表示不存在这样的记录,返回0。否则返回索引为pos的记录中的记录值
return pos == len ? 0 : _unsafeAccess(self._checkpoints, pos)._value;
}
function upperLookup(Trace160 storage self, uint96 key) internal view returns (uint160) {
// 记录总长度
uint256 len = self._checkpoints.length;
// 通过_upperBinaryLookup方法在[0,len)的key的范围中找到key大于目标key的第一条记录的索引值
uint256 pos = _upperBinaryLookup(self._checkpoints, key, 0, len);
// 如果pos为0表示不存在这样的记录,返回0。否则返回索引为pos-1的记录中的记录值
return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1)._value;
}
// Checkpoint160[] storage self中,通过二分法查找出key在[low,high)的范围中,记录的key大于目标key的第一条记录的索引值。如果不存在这样的记录值,则返回值为high。
// 注:传入的high不可以大于数组self的长度
function _upperBinaryLookup(
Checkpoint160[] storage self,
uint96 key,
uint256 low,
uint256 high
) private view returns (uint256) {
// 跳出循环条件:low>=high
while (low < high) {
// mid为low和high的均值
uint256 mid = Math.average(low, high);
if (_unsafeAccess(self, mid)._key > key) {
// 如果索引为mid的Checkpoint160._key>key,则更新high为mid
high = mid;
} else {
// 如果索引为mid的Checkpoint160._key<=key,则更新low为mid+1
low = mid + 1;
}
}
// 跳出循环,返回high
return high;
}
// Checkpoint160[] storage self中,通过二分法查找出key在[low,high)的范围中,记录的key大于或等于目标key的第一条记录的索引值。如果不存在这样的记录值,则返回值为high。
// 注: 传入的high不可以大于数组self的长度
function _lowerBinaryLookup(
Checkpoint160[] storage self,
uint96 key,
uint256 low,
uint256 high
) private view returns (uint256) {
// 跳出循环条件:low>=high
while (low < high) {
// mid为low和high的均值
uint256 mid = Math.average(low, high);
if (_unsafeAccess(self, mid)._key < key) {
// 如果索引为mid的Checkpoint160._key<key,则更新low为mid+1
low = mid + 1;
} else {
// 如果索引为mid的Checkpoint160._key>=key,则更新high为mid
high = mid;
}
}
return high;
}
contract CheckpointsTest is Test {
MockCheckpointsTrace160 mct160 = new MockCheckpointsTrace160();
function test_CheckpointsTrace160() external {
assertEq(mct160.length(), 0);
(bool exists,uint96 key,uint160 value) = mct160.latestCheckpoint();
assertFalse(exists);
assertEq(key, 0);
assertEq(value, 0);
assertEq(mct160.latest(), 0);
// push on key 1
(uint160 latestValue,uint160 newValue) = mct160.push(1, 10);
assertEq(latestValue, 0);
assertEq(newValue, 10);
assertEq(mct160.length(), 1);
(exists, key, value) = mct160.latestCheckpoint();
assertTrue(exists);
assertEq(key, 1);
assertEq(value, 10);
assertEq(mct160.latest(), newValue);
// push on key 2
(latestValue, newValue) = mct160.push(2, 20);
assertEq(latestValue, 10);
assertEq(newValue, 20);
assertEq(mct160.length(), 2);
(exists, key, value) = mct160.latestCheckpoint();
assertTrue(exists);
assertEq(key, 2);
assertEq(value, 20);
assertEq(mct160.latest(), newValue);
// update value on key 2
(latestValue, newValue) = mct160.push(2, 30);
// value before update
assertEq(latestValue, 20);
// value after update
assertEq(newValue, 30);
// total length no change
assertEq(mct160.length(), 2);
(exists, key, value) = mct160.latestCheckpoint();
assertTrue(exists);
assertEq(key, 2);
assertEq(value, 30);
assertEq(mct160.latest(), newValue);
// revert if the key to push is < latest key
vm.expectRevert("Checkpoint: invalid key");
mct160.push(2 - 1, 1);
// push more
mct160.push(3, 40);
mct160.push(4, 50);
mct160.push(5, 60);
mct160.push(6, 70);
assertEq(mct160.length(), 6);
// Trace160 now:
// 10(1)、30(2)、40(3)、50(4)、60(5)、70(6)
// lowerLookup():
// return the value in the oldest checkpoint with key greater or equal than the search key
assertEq(mct160.lowerLookup(0), 10);
assertEq(mct160.lowerLookup(1), 10);
assertEq(mct160.lowerLookup(2), 30);
assertEq(mct160.lowerLookup(3), 40);
assertEq(mct160.lowerLookup(4), 50);
assertEq(mct160.lowerLookup(5), 60);
assertEq(mct160.lowerLookup(6), 70);
assertEq(mct160.lowerLookup(7), 0);
// upperLookup():
// return the value in the most recent checkpoint with key lower or equal than the search key
assertEq(mct160.upperLookup(0), 0);
assertEq(mct160.upperLookup(1), 10);
assertEq(mct160.upperLookup(2), 30);
assertEq(mct160.upperLookup(3), 40);
assertEq(mct160.upperLookup(4), 50);
assertEq(mct160.upperLookup(5), 60);
assertEq(mct160.upperLookup(6), 70);
assertEq(mct160.upperLookup(7), 70);
}
}
ps:\ 本人热爱图灵,热爱中本聪,热爱V神。 以下是我个人的公众号,如果有技术问题可以关注我的公众号来跟我交流。 同时我也会在这个公众号上每周更新我的原创文章,喜欢的小伙伴或者老伙计可以支持一下! 如果需要转发,麻烦注明作者。十分感谢!
公众号名称:后现代泼痞浪漫主义奠基人
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!