lowerLookup function from CheckPoints structs

Support Contracts
1 
/**
     * @dev Returns the value in the first (oldest) checkpoint with key greater or equal than the search key, or zero if
     * there is none.
     */
    function lowerLookup(Trace208 storage self, uint48 key) internal view returns (uint208) {
        uint256 len = self._checkpoints.length;
        uint256 pos = _lowerBinaryLookup(self._checkpoints, key, 0, len);
        return pos == len ? 0 : _unsafeAccess(self._checkpoints, pos)._value;
    }

In my application, 0 can be stored as a value for the key. Then how do I distinguish between zero value and not found value?

2

Please provide ALL the relevant information required for readers to be able to address your question.

For example:

  • What is self._checkpoints?
  • What is _lowerBinaryLookup ?
  • What is _unsafeAccess ?

And probably a whole lot more.

This question is missing pretty much the entire context in which it resides!

3
4

With function lowerLookup - you cannot.

In this test on OpenZeppelin's GitHub repository, I tried to print:

  • The value of key 21, which is mapped to 0
  • The value of key 22, which has not yet been reached

The result in both cases was 0.

Perhaps OZ have not intended for this library to be used for value 0, but I could not find any mention of this intention - neither on the official documentation, nor within the contract's internal documentation.

5

Also, is there any function to search for the value by key? Sth like exactLookUp?

6

What does that mean?

7

Hey @jusikX

In my application, 0 can be stored as a value for the key. Then how do I distinguish between zero value and not found value?

You can't, but I think this is the regular behavior for any value, they all start in 0.

Perhaps you can use a sentinel value? Instead of pushing 0, you push a 1 in the most significant bit. For example, if you're using Trace208, the value is uint48, so you can use only 47 bits for the value and reserve the first bit for the sentinel to use as a boolean.

  sentinel actual value
          ↓↓
uint48: 0b1aaa...aaaaaaaa
uint48: 0b0bbb...bbbbbbbb

It depends on what exactly you want to store, but 47 bits allow for more than 4,000,000 years if the value stored represents seconds (2**47), just be careful with the math.

Also, is there any function to search for the value by key? Sth like exactLookUp?

Unfortunately not, but this is only because the keys aren't indexed. An alternative is that you can keep a mapping from checkpoint keys and checkpoint indexes and then use the at function for accessing directly.

Honestly, I wouldn't recommend that approach because you'll be wasting gas on storing the index just to gain a few gas units in runtime. The upperBinaryLookup and lowerBinaryLookup perform a binary search on the checkpoints list (remember they're ordered!) that grows as O(logn) in complexity.

I'm pretty sure the binary lookup is the best option for the majority of the cases, but a test comparing the gas consumption between a contract that maintains a storage index vs one that uses the binary lookup would clarify it.

8

You mean uint208 for value, not uint48 (key), right?

9

Yeah sorry, my bad. It should've been:

   sentinel actual value
           ↓↓
uint208: 0b1aaa...aaaaaaaa
uint208: 0b0bbb...bbbbbbbb