Page MenuHomeFreeBSD

rb_tree: let insert search start from adjacent node
ClosedPublic

Authored by dougm on Jun 18 2022, 6:13 PM.
Tags
None
Referenced Files
Unknown Object (File)
May 18 2024, 4:31 AM
Unknown Object (File)
May 18 2024, 4:31 AM
Unknown Object (File)
May 18 2024, 4:31 AM
Unknown Object (File)
May 18 2024, 4:30 AM
Unknown Object (File)
May 18 2024, 4:30 AM
Unknown Object (File)
May 18 2024, 4:30 AM
Unknown Object (File)
May 18 2024, 4:30 AM
Unknown Object (File)
May 17 2024, 3:04 AM
Subscribers

Details

Summary

When the node to insert in the rb_tree is known to precede or follow a particular node, new methods RB_INSERT_PREV and RB_INSERT_NEXT, defined here, allow the search for where to insert the new node begin with that particular node, rather than at the root, to save a bit of time.

Using those methods, instead of RB_INSERT, in managing a tree in iommu_gas.c, saves a wee bit of time.

Diff Detail

Repository
rG FreeBSD src repository
Lint
Lint Not Applicable
Unit
Tests Not Applicable

Event Timeline

dougm requested review of this revision.Jun 18 2022, 6:13 PM
dougm created this revision.

Move the left/right path walking code into the insert function.

Reverse the order of insertion of the boundary entries of the tree. The 'end' entry, with its empty range, won't be considered 'changed' by augmentation, so won't lead to an augmentation update in 'begin', so insert it first.

If empty ranges can be routinely inserted, then the conditions for defining change by augmentation would need to change.

I just updated the wrong review request with an unrelated patch. Ignore for now.

dougm retitled this revision from Use INSERT_AT to avoid pointless tree searches in uppermatch, lowermatch to rb_tree: let insert search start from adjacent node.
dougm edited the summary of this revision. (Show Details)
dougm added a reviewer: kib.

Resolve conflict with recent commit.

Should there be some checks, at least in DIAGNOSTICS case, that the position of inserted element is the right one?

With DIAGNOSTIC defined, verify that the user of RB_INSERT_{PREV,NEXT} is using it properly.

kib added inline comments.
sys/sys/tree.h
922
#if defined(_KERNEL) && defined(DIAGNOSTIC)
This revision is now accepted and ready to land.Oct 2 2022, 11:30 PM