Details

Reviewers

sdulfari

Group Reviewers

Restricted Project

Commits

rABC1cc430a7a3f7: Let the radix tree work with 256 bits keys

Summary

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

Repository

rABC Bitcoin ABC

Branch

avalanche_radix_256

Lint

Lint Passed

Unit

No Test Coverage

Build Status

Buildable 18983
Build 37728: Build Diff	lint-circular-dependencies · build-debug · build-diff · build-without-wallet · build-clang-tidy · build-clang
Build 37727: arc lint + arc unit

Event Timeline

Fabien created this revision.May 3 2022, 16:38

Herald added a reviewer: Restricted Project. · View Herald TranscriptMay 3 2022, 16:38

Harbormaster completed remote builds in B18929: Diff 33377.May 3 2022, 16:54

Use a wrapper class for uint256.

Fabien edited the summary of this revision. (Show Details)May 9 2022, 16:41

Harbormaster completed remote builds in B18983: Diff 33452.May 9 2022, 16:57

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.

src/radix.h
399	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.
src/test/radix_tests.cpp
48	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

sdulfari added inline comments.May 9 2022, 22:17

src/test/radix_tests.cpp
48	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.
68	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

@bot build-osx

teamcity awarded a token.May 10 2022, 09:59

Harbormaster completed remote builds in B18985: Diff 33454.May 10 2022, 10:17

deadalnix added a subscriber: deadalnix.May 10 2022, 12:48

deadalnix added inline comments.

src/radix.h
370 ↗	(On Diff #33454)	Why is the cast needed here?

Fabien added inline comments.May 10 2022, 12:53

src/radix.h
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