Checkpoints

Title: Checkpoints

Author: Modified from OpenZeppelin (https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/structs/Checkpoints.sol)

Utility library for checkpointed values: uint208 values keyed by uint48 timepoints (Trace208), and uint160 values keyed by uint96 ids (Trace160, the ERC721Consecutive ownership ranges).

Mirrors OpenZeppelin v5 Checkpoints (the Trace208 and Trace160 variants). Trace160 carries only the push and lowerLookup its one caller needs.

Functions

push

Pushes a new checkpoint. If key equals the latest key, replaces the value. Reverts if key is less than the latest key.

function push(Trace208 storage self, uint48 key, uint208 value) internal returns (uint208, uint208);

Parameters

Name	Type	Description
self	`Trace208`	Storage pointer to the trace.
key	`uint48`	The timepoint key (e.g. block.timestamp cast to uint48).
value	`uint208`	The uint208 value to store.

Returns

Name	Type	Description
<none>	`uint208`	The previous value at the latest checkpoint (before the update).
<none>	`uint208`	The new value (same as `value`).

push

Pushes a uint160 checkpoint. If key equals the latest key, replaces the value. Reverts if key is less than the latest key. Unlike OpenZeppelin's, it returns nothing: its one caller needs neither the previous nor the new value.

function push(Trace160 storage self, uint96 key, uint160 value) internal;

Parameters

Name	Type	Description
self	`Trace160`
key	`uint96`
value	`uint160`

lowerLookup

Returns the value of the first checkpoint whose key is greater than or equal to key.

Binary search. Returns 0 if all checkpoints have keys < key.

function lowerLookup(Trace160 storage self, uint96 key) internal view returns (uint160);

Parameters

Name	Type	Description
self	`Trace160`
key	`uint96`

Returns

Name	Type	Description
<none>	`uint160`

lowerLookup

Returns the lowest value whose key is greater than or equal to key. (Lower-bound lookup — useful for "find first checkpoint at or after key".)

Binary search. Returns 0 if all checkpoints have keys < key.

function lowerLookup(Trace208 storage self, uint48 key) internal view returns (uint208);

Parameters

Name	Type	Description
self	`Trace208`
key	`uint48`

Returns

Name	Type	Description
<none>	`uint208`

upperLookup

Returns the highest value whose key is less than or equal to key. (Upper-bound lookup — standard "what was the value at timepoint key".)

Binary search. Returns 0 if all checkpoints have keys > key.

function upperLookup(Trace208 storage self, uint48 key) internal view returns (uint208);

Parameters

Name	Type	Description
self	`Trace208`
key	`uint48`

Returns

Name	Type	Description
<none>	`uint208`

upperLookupRecent

Same as upperLookup but optimised for recent (near-latest) timepoints.

Uses OZ v5's sqrt-pivot: a single sqrt(len)-from-tail probe splits the array, then binary search handles the remainder. O(sqrt(N)) amortised for recent lookups.

function upperLookupRecent(Trace208 storage self, uint48 key) internal view returns (uint208);

Parameters

Name	Type	Description
self	`Trace208`
key	`uint48`

Returns

Name	Type	Description
<none>	`uint208`

_sqrt

Integer square root (floor). Used by upperLookupRecent pivot. Matches the algorithm used in OZ Math.sqrt (Newton's method, rounded down).

function _sqrt(uint256 x) private pure returns (uint256 result);

Parameters

Name	Type	Description
x	`uint256`

Returns

Name	Type	Description
result	`uint256`

_log2

Floor log2 of x, used by _sqrt to seed the initial estimate.

function _log2(uint256 x) private pure returns (uint256 r);

Parameters

Name	Type	Description
x	`uint256`

Returns

Name	Type	Description
r	`uint256`

latest

Returns the value of the most recently pushed checkpoint, or 0 if empty.

function latest(Trace208 storage self) internal view returns (uint208);

Parameters

Name	Type	Description
self	`Trace208`

Returns

Name	Type	Description
<none>	`uint208`

latestCheckpoint

Returns whether there is at least one checkpoint, and if so, its key and value.

function latestCheckpoint(Trace208 storage self) internal view returns (bool exists, uint48 _key, uint208 _value);

Parameters

Name	Type	Description
self	`Trace208`

Returns

Name	Type	Description
exists	`bool`
_key	`uint48`
_value	`uint208`

length

Returns the total number of checkpoints stored.

function length(Trace208 storage self) internal view returns (uint256);

Parameters

Name	Type	Description
self	`Trace208`

Returns

Name	Type	Description
<none>	`uint256`

at

Returns the checkpoint at the given position (0-indexed).

function at(Trace208 storage self, uint32 pos) internal view returns (Checkpoint208 memory);

Parameters

Name	Type	Description
self	`Trace208`
pos	`uint32`

Returns

Name	Type	Description
<none>	`Checkpoint208`

Errors

CheckpointUnorderedInsertion

Thrown when attempting to push a checkpoint with a key smaller than the latest key.

error CheckpointUnorderedInsertion();

Structs

Checkpoint208

A single checkpoint storing a uint208 value at a uint48 key (timepoint).

struct Checkpoint208 {
        uint48 _key;
        uint208 _value;
    }

Properties

Name	Type	Description
_key	`uint48`
_value	`uint208`

Trace208

An ordered list of checkpoints.

struct Trace208 {
        Checkpoint208[] _checkpoints;
    }

Properties

Name	Type	Description
_checkpoints	`Checkpoint208[]`

Checkpoint160

A single checkpoint storing a uint160 value at a uint96 key.

struct Checkpoint160 {
        uint96 _key;
        uint160 _value;
    }

Properties

Name	Type	Description
_key	`uint96`
_value	`uint160`

Trace160

An ordered list of uint160 checkpoints keyed by uint96.

struct Trace160 {
        Checkpoint160[] _checkpoints;
    }

Properties

Name	Type	Description
_checkpoints	`Checkpoint160[]`