Page MenuHomePhabricator
Differential D2336

Implement delete function for the RadixTree
ClosedPublic
Actions

Authored by deadalnix on Jan 18 2019, 00:52.

Details

Reviewers
jasonbcox
Fabien
Group Reviewers
Restricted Project
Commits
rSTAGINGbc165fe64bb0: Implement delete function for the RadixTree
rABCbc165fe64bb0: Implement delete function for the RadixTree
Summary

It is failry similar to an insert operation, except it never generates a subtree.

Return false if the key is not found in the tree, true if it is.

Test Plan

Added test cases.

Diff Detail

Repository
rABC Bitcoin ABC
Lint
Lint Not Applicable
Unit
Tests Not Applicable

Event Timeline

deadalnix created this revision.Jan 18 2019, 00:52
Herald added a reviewer: Restricted Project. · View Herald TranscriptJan 18 2019, 00:52
Herald added a subscriber: schancel. · View Herald Transcript
teamcity added a subscriber: teamcity.Jan 18 2019, 00:54

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing started.

deadalnix added parent revisions: D2311: Initial implementation of RadixTree, D2317: [RCU] Add facility to register cleanup actions to be run when other thread catch up.Jan 18 2019, 00:57
teamcity added a comment.Jan 18 2019, 00:59

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing failed.

Harbormaster failed remote builds in B4566: Diff 6719!Jan 18 2019, 00:59
jasonbcox requested changes to this revision.Jan 18 2019, 01:09
jasonbcox added a subscriber: jasonbcox.
jasonbcox added inline comments.
src/test/radix_tests.cpp
233 ↗(On Diff #6719)

Needs a for loop that provides a set of cases where some random values, including min/max values, are inserted and deleted in random order.

Additionally, the inserts and deletes should be logged logged so that in the event of a failure, debugging will be possible.

This revision now requires changes to proceed.Jan 18 2019, 01:09
deadalnix updated this revision to Diff 6745.Jan 19 2019, 15:04

Add remove operation to the stress test

teamcity added a comment.Jan 19 2019, 15:06

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing started.

teamcity added a comment.Jan 19 2019, 15:09

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing failed.

Harbormaster failed remote builds in B4581: Diff 6745!Jan 19 2019, 15:09
teamcity added a comment.Jan 20 2019, 20:58

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing started.

teamcity added a comment.Jan 20 2019, 21:01

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing failed.

deadalnix added a child revision: D2371: [Radix] Use RCUPtr to keep track of items in the tree.Jan 21 2019, 16:56
deadalnix updated this revision to Diff 6802.Jan 22 2019, 01:10

Add a synchronize after removing the element from the tree. As it turns out, we may delete the element we just inserted and have to ensure all other threads are past it for correctness. Not a hue deal because this code is going away anyways, but worth fixing for correctness.

teamcity added a comment.Jan 22 2019, 01:12

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing started.

teamcity added a comment.Jan 22 2019, 01:15

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing failed.

Harbormaster failed remote builds in B4627: Diff 6802!Jan 22 2019, 01:15
deadalnix updated this revision to Diff 6851.Jan 23 2019, 00:12

Use the NULLPTR trick to make boost happy

teamcity added a comment.Jan 23 2019, 00:12

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing started.

Harbormaster completed remote builds in B4654: Diff 6851.Jan 23 2019, 00:25
teamcity added a comment.Jan 23 2019, 00:25

Build Bitcoin-ABC / Diffs / Bitcoin-ABC Diff Testing passed.

Fabien accepted this revision.Jan 23 2019, 09:16
jasonbcox accepted this revision.Jan 24 2019, 00:39
This revision is now accepted and ready to land.Jan 24 2019, 00:39
jasonbcox mentioned this in D2385: [Radix] Have the radix tree cleanup after itself.Jan 24 2019, 00:41
Closed by commit rABCbc165fe64bb0: Implement delete function for the RadixTree (authored by deadalnix). · Explain WhyJan 24 2019, 02:51
This revision was automatically updated to reflect the committed changes.
deadalnix added a commit: rSTAGINGbc165fe64bb0: Implement delete function for the RadixTree.Sep 18 2019, 22:04

Revision Contents
Changeset List

PathSize
src/
40 lines
test/
110 lines

Diff 6891

View Options

src/radix.h

Loading...
View Options

src/test/radix_tests.cpp

Loading...