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

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
rGa7eac018437e: stty(1): provide details about interaction with job control
Branches
Unknown
Tags
Unknown