Reorder manipulations in RB_REMOVE
ClosedPublic
Actions

Authored by dougm on May 15 2020, 5:27 AM.

Details

Reviewers

alc
markj

Commits

rS361324: For the case when RB_REMOVE requires a nontrivial search to find the

Summary

For the case when RB_REMOVE requires a nontrivial search to find the node to replace the one being removed, restructure to remove the replacement node, and correct the parent pointers around it first, and let the all-cases code at the end deal with the parent of deleted node, making it point to the replacement node. This removes one or two conditional branches.

Diff Detail

Lint

Lint Skipped

Unit

Tests Skipped

Event Timeline

dougm requested review of this revision.May 15 2020, 5:27 AM

dougm created this revision.

dougm added a reviewer: markj.May 16 2020, 7:37 PM

dougm added a subscriber: pho.

markj accepted this revision.May 18 2020, 2:49 PM

markj added inline comments.

sys/sys/tree.h
597–602	Perhaps use a local variable for RB_PARENT(old, field)?

This revision is now accepted and ready to land.May 18 2020, 2:49 PM

Use a local variable for RB_PARENT(old, field).

This revision now requires review to proceed.May 18 2020, 7:15 PM

I ran all but the last 7 stress2 tests on D24845.71808.diff without seeing any problems.
I'm now switching to D24845.71955.diff

markj accepted this revision.May 19 2020, 1:43 PM

This revision is now accepted and ready to land.May 19 2020, 1:43 PM

I completed a full stress2 test of D24845.71955.diff. No problems seen except for this known iflib problem: https://people.freebsd.org/~pho/stress/log/dougm070.txt

Closed by commit rS361324: For the case when RB_REMOVE requires a nontrivial search to find the (authored by dougm). · Explain WhyMay 21 2020, 5:34 AM

This revision was automatically updated to reflect the committed changes.

dougm added a commit: rS361324: For the case when RB_REMOVE requires a nontrivial search to find the.

Herald added a subscriber: imp. · View Herald TranscriptMay 21 2020, 5:34 AM