1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.5.0) (utils/Checkpoints.sol)
pragma solidity ^0.8.0;
import "./math/Math.sol";
import "./math/SafeCast.sol";
/**
* @dev This library defines the `History` struct, for checkpointing values as they change at different points in
* time, and later looking up past values by block number. See {Votes} as an example.
*
* To create a history of checkpoints define a variable type `Checkpoints.History` in your contract, and store a new
* checkpoint for the current transaction block using the {push} function.
*
* _Available since v4.5._
*/
library Checkpoints {
struct Checkpoint {
uint32 _blockNumber;
uint224 _value;
}
struct History {
Checkpoint[] _checkpoints;
}
/**
* @dev Returns the value in the latest checkpoint, or zero if there are no checkpoints.
*/
function latest(History storage self) internal view returns (uint256) {
uint256 pos = self._checkpoints.length;
return pos == 0 ? 0 : self._checkpoints[pos - 1]._value;
}
/**
* @dev Returns the value at a given block number. If a checkpoint is not available at that block, the closest one
* before it is returned, or zero otherwise.
*/
function getAtBlock(History storage self, uint256 blockNumber) internal view returns (uint256) {
require(blockNumber < block.number, "Checkpoints: block not yet mined");
uint256 high = self._checkpoints.length;
uint256 low = 0;
while (low < high) {
uint256 mid = Math.average(low, high);
if (self._checkpoints[mid]._blockNumber > blockNumber) {
high = mid;
} else {
low = mid + 1;
}
}
return high == 0 ? 0 : self._checkpoints[high - 1]._value;
}
/**
* @dev Pushes a value onto a History so that it is stored as the checkpoint for the current block.
*
* Returns previous value and new value.
*/
function push(History storage self, uint256 value) internal returns (uint256, uint256) {
uint256 pos = self._checkpoints.length;
uint256 old = latest(self);
if (pos > 0 && self._checkpoints[pos - 1]._blockNumber == block.number) {
self._checkpoints[pos - 1]._value = SafeCast.toUint224(value);
} else {
self._checkpoints.push(
Checkpoint({_blockNumber: SafeCast.toUint32(block.number), _value: SafeCast.toUint224(value)})
);
}
return (old, value);
}
/**
* @dev Pushes a value onto a History, by updating the latest value using binary operation `op`. The new value will
* be set to `op(latest, delta)`.
*
* Returns previous value and new value.
*/
function push(
History storage self,
function(uint256, uint256) view returns (uint256) op,
uint256 delta
) internal returns (uint256, uint256) {
return push(self, op(latest(self), delta));
}
}