Page MenuHomePhabricator

Initial implementation of RadixTree
ClosedPublic

Authored by deadalnix on Jan 14 2019, 22:34.

Details

Summary

This implements a radix tree that can be read from and inserted into concurently. Deletion is not implemented at this stage.

Test Plan

Added unit tests for implemented features.

Diff Detail

Repository
rABC Bitcoin ABC
Branch
radixtree
Lint
Lint Passed
Unit
No Test Coverage
Build Status
Buildable 4555
Build 7173: Bitcoin ABC Buildbot (legacy)
Build 7172: arc lint + arc unit

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
jasonbcox requested changes to this revision.Jan 15 2019, 00:09
jasonbcox added a subscriber: jasonbcox.
jasonbcox added inline comments.
src/radix.h
67 ↗(On Diff #6656)

const

143 ↗(On Diff #6656)

getDiscriminent -> hasData or something similar
A discriminant is used to discriminate, so getting it should actually just return 0x01 but that has no use to the caller.

155 ↗(On Diff #6656)

const

170 ↗(On Diff #6656)

const

186 ↗(On Diff #6656)

Why does this exist? 🤔

203 ↗(On Diff #6656)

s/alignement/alignment/g on all three lines

This revision now requires changes to proceed.Jan 15 2019, 00:09
src/test/radix_tests.cpp
77 ↗(On Diff #6656)

How about uint256 as well?

80 ↗(On Diff #6656)

Could rename this to testInsertAndGet since testGet 100% reproduces testInsert. I understand why you didn't do this conceptually, but it's hard to imagine how testGet will evolve in a way that deviates substantially without testing inserts as a consequence.

152 ↗(On Diff #6656)

uint256 here too

174 ↗(On Diff #6656)

remove duplicate comment

src/radix.h
143 ↗(On Diff #6656)

Using a discriminant to discriminate a discriminated union seems appropriate.

155 ↗(On Diff #6656)

Please pay attention.

170 ↗(On Diff #6656)

dito

186 ↗(On Diff #6656)

initialization

src/test/radix_tests.cpp
80 ↗(On Diff #6656)

You'll get failure and you don't know if insert of get failed.

Mengerian added inline comments.
src/radix.h
22 ↗(On Diff #6661)

in chunk -> into chunks
as index -> as an index

25 ↗(On Diff #6661)

lazyly -> lazily
leaf -> leafs

28 ↗(On Diff #6661)

element -> elements

29 ↗(On Diff #6661)

require to wait -> requires waiting

33 ↗(On Diff #6661)

beofre -> before

59 ↗(On Diff #6661)

is -> if

84 ↗(On Diff #6661)

match -> matches

98 ↗(On Diff #6661)

untill -> until

117 ↗(On Diff #6661)

already was -> was already

124 ↗(On Diff #6661)

inertion in -> insertion into

200 ↗(On Diff #6661)

work -> works (I think)

src/test/radix_tests.cpp
32 ↗(On Diff #6661)

in -> into

56 ↗(On Diff #6661)

"They can a be inserted"
Unsure what you are trying to say, the "a" seems superfluous.

92 ↗(On Diff #6661)

in -> into

96 ↗(On Diff #6661)

element -> elements

131 ↗(On Diff #6661)

in -> into

185 ↗(On Diff #6661)

others -> other

199 ↗(On Diff #6661)

element -> elements
in -> into

src/radix.h
25 ↗(On Diff #6661)

I think it is leaves :)

src/radix.h
25 ↗(On Diff #6661)

Yeah, maybe "leaves" is better, but I think you could write either and still be considered correct.

For example, in electrical engineering "antennas" is the standard plural, not "antennae".

see also the "Toronto Maple Leafs"

We're getting into the arcana of linguistics, but in English is is considered normal to "standardize" grammar rules for a word when it occupies a new cognitive category. That seems to be what people's brains naturally do.

src/radix.h
25 ↗(On Diff #6661)

Actually, feel free to ignore my digression.

A quick Google shows that "leaves" is better.

src/radix.h
143 ↗(On Diff #6656)

ya, I'm just saying the function name makes no sense

jasonbcox added inline comments.
src/radix.h
143 ↗(On Diff #6656)

at the very least, fix the typo:
getDiscriminent -> getDiscriminant

This revision is now accepted and ready to land.Jan 15 2019, 23:54
jasonbcox requested changes to this revision.Jan 15 2019, 23:54

Fix build failure

This revision now requires changes to proceed.Jan 15 2019, 23:54

rationalize get's constness

Use strong CAS instead of weak.

strong is significantly more expensive on some architectures, therefore should be avoided. In this case however, in one case failign will just cause the loop to repeat and in the other, an allocation to be made and then freed for no reason. As a result, it is preferable to use a stong CAS in these cases.

Fabien requested changes to this revision.Jan 17 2019, 13:31
Fabien added a subscriber: Fabien.

The automatic build failed

src/radix.h
62

Will be more robust to check value against nullptr

162

This should not happen in any normal scenario, but asserting against nullptr would make the code more robust.

This revision now requires changes to proceed.Jan 17 2019, 13:31
src/radix.h
62

We get it for free when calling getId :)

162

It is definitively possible for the caller to cal this when the discriminated union is not a node. It is not the responsibility of the union to decide if we ant null nodes or not.

It looks like the test failure comes from an bug in either GCC or boost used on the CI. I do not know what versions are used, so I'm not sure how to move forward here.

This revision is now accepted and ready to land.Jan 23 2019, 08:13
This revision was automatically updated to reflect the committed changes.