Page MenuHomePhabricator

Let the radix tree work with 256 bits keys

Authored by Fabien on May 3 2022, 16:38.


Group Reviewers
Restricted Project
rABC1cc430a7a3f7: Let the radix tree work with 256 bits keys

The radix tree is relying on several features that prevent it from using an arbitrary key type:

  • The key of type K is expected to return the correct size via a call to sizeof(K)
  • It should implement several operators for the RadixNode::get() to work, including a cast to size_t so it can be used as an array index.

The radix tree is expected to be used wtih uint256 type keys, for both ProofId and TxId. The uint256 type behaves correctly with sizeof() but still need to be able to perform the arithmetic and cast operations. This diff implements a key wrapper class that implements the required methods that make it possible to work with uint256 as a key type.

Test Plan
ninja check

Diff Detail

Event Timeline

Use a wrapper class for uint256.

Fabien published this revision for review.May 9 2022, 20:32
sdulfari requested changes to this revision.May 9 2022, 21:34
sdulfari added a subscriber: sdulfari.
sdulfari added inline comments.

Although these are used throughout the RadixTree tests, these operators could use tests in case arith_uint256 changes under the hood.

This review item is non-blocking, but encouraged.


Running all of the tests on this wrapper means we are not testing RadixTree<Uint256KeyWrapper> which is what we expect to use in production.

It should be possible to add a getter that returns the underlying Uint256KeyWrapper and use it's type to init the RadixTree and RCUPtrs in each test. Calls to extreme-value functions would remain unchanged, as they should since this part of the wrapper design makes sense.

This revision now requires changes to proceed.May 9 2022, 21:34

Retracting this comment because Uint256KeyWrapper isn't the RadixTree type being used, but instead the type returned by T::getId.

We are not testing the RadixTree typed for use in production (ie Avalanche). I assume this will be taken care of in a future patch. Please catch me if that assumption is incorrect.


nit: We spoke offline about implementing MinusOne, MinusTwo, and potentially SignedMax to be computed at compile-time. This improves readability and doesn't force the reviewer to know the implementation details of uint256.

Use arithmetic to compute MinusOne and co, add unit tests for the wrapper operators

deadalnix added inline comments.
370 ↗(On Diff #33454)

Why is the cast needed here?

370 ↗(On Diff #33454)

It's here to make sure we have a consistent interface independently of the architecture we are building on, and not sometime int and sometimes long for example

sdulfari added inline comments.
564 ↗(On Diff #33454)

There should also be a case to check the boundary bit immediately beyond the range for size_t. Example would be key >> 185u

This revision is now accepted and ready to land.May 10 2022, 15:29

Add bit-boundary cases for the size_t cast

This revision was automatically updated to reflect the committed changes.
Unknown Object (User) added a subscriber: Unknown Object (User).Feb 19 2024, 08:25
This comment was removed by Fabien.