HomeFreeBSD

rb_tree: let insert search start from next node

Description

rb_tree: let insert search start from next node

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 little time.

Reviewed by: kib
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D35516

(cherry picked from commit 368ee2f86a0f4f60338472be4bfd3c09ab401f87)

Details

Provenance
dougmAuthored on Oct 3 2022, 3:27 AM
Reviewer
kib
Differential Revision
D35516: rb_tree: let insert search start from adjacent node
Parents
rGb948644cfa07: inet: Simplify if_multiaddrs iteration.
Branches
Unknown
Tags
Unknown